1、一個問題：道路鋪設電網架設網絡構設537( ,154,)線形時間Prim 算法Kruskal算法指數時間搜索算法 牛牛文庫文檔分享方案基本費用難度系數生態破壞e1,e2504030e2,e3503050e3,e1405040綜合評價260310300(20,30,10)(30,10,20)(20,20,30)e1e2e3CITY1CITY2CITY3架設鐵路的基本費用架設鐵路的難度系數鐵路造成的生態破壞修建一條鐵路需要考慮的因素124一個簡單的例子 牛牛文庫文檔分享一個問題：道路鋪設電網架設網絡構設537( ,154,)線形時間Prim 算法Kruskal算法指數時間搜索算法 牛牛文庫文檔分享

2、一個問題：數據規模1789101112131415估計用時1s內2s40s20m6h8d270d30y1200y天文數字537( ,154,)搜索算法的時間復雜度我們真的要等1200年？如果有一種方法能在短短的時間內得到一組與最優解十分逼近的近似解呢？ 牛牛文庫文檔分享遺傳算法歷史背景遺傳算法（Genetic Algorithm）是一種模擬自然選擇和遺傳的隨機搜索算法。它由John Holland提出，最初用于研究自然系統的適應過程和設計具有自適應性能的軟件。近年來，遺傳算法作為問題求解和最優化的有效工具，已被非常成功地應用與解決許多最優化問題并越來越流行。42578714769940初始化群

3、體估價工作流程問題的一個可行解編碼理論編碼理論 牛牛文庫文檔分享57409987761442遺傳算法工作流程估價保持遺傳交配遺傳變異遺傳概率控制 牛牛文庫文檔分享遺傳算法多目標最小生成樹編碼理論Prfer編碼機制 每一棵樹與一個長度為n-2的數字串對應 對于任意一個長度為n-2的數字串也與唯一的一棵生成樹相對應編碼過程 編碼串初始為空串 令j為樹中編號最小的葉節點； 如果j與i相鄰，則把i加入當前編碼串的最右端 把j以及連接i和j的邊從樹中刪除，這時候樹只有n-1個頂點 重復以上步驟直到樹中只剩下一條邊這時候得到的編碼串即為相應樹的Prfer編碼解碼過程設P為編碼串，S為圖的頂點編號不出現在P

4、中的頂點的集合；設i為S中編號最小的頂點，j為P中最左端的頂點，則將連接i和j的邊加入到樹中，然后分別把i和j從P和S中刪除，如果P中不在出現頂點j則把j加入到S中重復以上步驟，直到P為空；當P為空串時，S中剛好剩下兩個頂點，將連接這兩個頂點的邊加入到樹中，最后構成的樹即為與最初P對應的生成樹。 優勢可以很容易地隨機生成一棵生成樹很適合執行各類遺傳操作 牛牛文庫文檔分享遺傳算法多目標最小生成樹編碼理論估價函數估價函數設置 fi(x)表示待估價的染色體在目標i的費用情況，mini表示截止到上一代為止，產生的所有染色體在目標i的費用的最小值。優勢更好的突出了每個染色體在各個目標上的優勢避免了由于每

5、個目標的取值范圍不同或者費用的整體趨勢不同而造成的某些個體在某些目標的優勢無法被體現 牛牛文庫文檔分享遺傳算法多目標最小生成樹編碼理論估價函數遺傳算子PARENT 12565交配遺傳錯位交叉算子從當前群體中抽出兩條染色體，在兩條染色體上隨機抽取一個等位的長度不超過的片段進行交換，并擇擇優選取。PARENT 28577 22 8優勢由于編碼理論的性質，這種操作很大程度地保留了親本優良特性，并且能一定程度上引入另一個樣本一些特性。變異遺傳從當前群體中抽出一條染色體(Parent)，在染色體上隨機抽取一個位置，用一個隨機的值替換。單點變異算子優勢由于編碼理論的性質，這種操作也可以在較大程度上保留親本

6、的優良性質。概率控制保持遺傳（54）交配遺傳（45）變異遺傳（ 1） 牛牛文庫文檔分享遺傳算法多目標最小生成樹編碼理論估價函數遺傳算子 牛牛文庫文檔分享遺傳算法多目標最小生成樹算例分析 牛牛文庫文檔分享遺傳算法多目標最小生成樹算例分析 牛牛文庫文檔分享遺傳算法多目標最小生成樹算例分析 牛牛文庫文檔分享小結編碼理論估價函數遺傳算子通過測試結果我們可以看到遺傳算法在解決組合優化類問題有著和其他算法無法比擬的強大優勢，它的特點就是可以在較短的時間內，得到令人滿意的解，而且算法相對簡潔。對于現實生活中的大量常規算法無法解決的問題，遺傳算法都有著良好的應用前景。謝謝！ 遺傳算法不僅一種算法，更是一種思想。在各種常用算法中