遺傳算法應用的分析與研究

關于遺傳算法應用

的分析與研究

.一個問題：道路鋪設電網(wǎng)架設網(wǎng)絡構設…………537(

,154,……)線形時間Prim算法Kruskal算法指數(shù)時間搜索算法.方案基本費用難度系數(shù)生態(tài)破壞e1,e2504030e2,e3503050e3,e1405040綜合評價260310300(20,30,10)(30,10,20)(20,20,30)e1e2e3CITY1CITY2CITY3架設鐵路的基本費用架設鐵路的難度系數(shù)鐵路造成的生態(tài)破壞修建一條鐵路需要考慮的因素×1×2×4一個簡單的例子.一個問題：道路鋪設電網(wǎng)架設網(wǎng)絡構設…………537(

,154,……)線形時間Prim算法Kruskal算法指數(shù)時間搜索算法.一個問題：數(shù)據(jù)規(guī)模1~789101112131415……估計用時1s內(nèi)2s40s20m6h8d270d30y1200y天文數(shù)字537(

,154,……)搜索算法的時間復雜度我們真的要等1200年？如果有一種方法能在短短的時間內(nèi)得到一組與最優(yōu)解十分逼近的近似解呢？.遺傳算法歷史背景遺傳算法（GeneticAlgorithm）是一種模擬自然選擇和遺傳的隨機搜索算法。它由JohnHolland提出，最初用于研究自然系統(tǒng)的適應過程和設計具有自適應性能的軟件。近年來，遺傳算法作為問題求解和最優(yōu)化的有效工具，已被非常成功地應用與解決許多最優(yōu)化問題并越來越流行。42578714769940初始化群體估價－工作流程問題的一個可行解編碼理論編碼理論.57409987761442遺傳算法－工作流程估價保持遺傳交配遺傳變異遺傳概率控制.遺傳算法－多目標最小生成樹編碼理論Prüfer編碼機制

每一棵樹與一個長度為n-2的數(shù)字串對應對于任意一個長度為n-2的數(shù)字串也與唯一的一棵生成樹相對應★編碼過程▲編碼串初始為空串▲令j為樹中編號最小的葉節(jié)點；▲如果j與i相鄰，則把i加入當前編碼串的最右端▲把j以及連接i和j的邊從樹中刪除，這時候樹只有n-1個頂點▲重復以上步驟直到樹中只剩下一條邊這時候得到的編碼串即為相應樹的Prüfer編碼★解碼過程▲設P為編碼串，S為圖的頂點編號不出現(xiàn)在P中的頂點的集合；▲設i為S中編號最小的頂點，j為P中最左端的頂點，則將連接i和j的邊加入到樹中，然后分別把i和j從P和S中刪除，如果P中不在出現(xiàn)頂點j則把j加入到S中▲重復以上步驟，直到P為空；▲當P為空串時，S中剛好剩下兩個頂點，將連接這兩個頂點的邊加入到樹中，最后構成的樹即為與最初P對應的生成樹。

優(yōu)勢可以很容易地隨機生成一棵生成樹很適合執(zhí)行各類遺傳操作.遺傳算法－多目標最小生成樹編碼理論估價函數(shù)估價函數(shù)設置

fi(x)表示待估價的染色體在目標i的費用情況，min[i]表示截止到上一代為止，產(chǎn)生的所有染色體在目標i的費用的最小值。優(yōu)勢更好的突出了每個染色體在各個目標上的優(yōu)勢避免了由于每個目標的取值范圍不同或者費用的整體趨勢不同而造成的某些個體在某些目標的優(yōu)勢無法被體現(xiàn).遺傳算法－多目標最小生成樹編碼理論估價函數(shù)遺傳算子PARENT12565交配遺傳錯位交叉算子從當前群體中抽出兩條染色體，在兩條染色體上隨機抽取一個等位的長度不超過２的片段進行交換，并擇擇優(yōu)選取。PARENT28３577

22

8優(yōu)勢由于編碼理論的性質(zhì)，這種操作很大程度地保留了親本優(yōu)良特性，并且能一定程度上引入另一個樣本一些特性。變異遺傳從當前群體中抽出一條染色體(Parent)，在染色體上隨機抽取一個位置，用一個隨機的值替換。單點變異算子優(yōu)勢由于編碼理論的性質(zhì)，這種操作也可以在較大程度上保留親本的優(yōu)良性質(zhì)。概率控制保持遺傳（54％）交配遺傳（45％）變異遺傳（1％）.遺傳算法－多目標最小生成樹編碼理論估價函數(shù)遺傳算子.遺傳算法－多目標最小生成樹算例分析.遺傳算法－多目標最小生成樹算例分析.遺傳算法－多目標最小生成樹算例分析.小結編碼理論估價函數(shù)遺傳算子通過測試結果我們可以看到遺傳算法在解決組合優(yōu)化類問題有著和其他算法無法比擬的強大優(yōu)勢，它的特點就是可以在較短的時間內(nèi)，得到令人滿意的解，而且算法相對簡潔。對于現(xiàn)實生活中的大量常規(guī)算法無法解決的問題，遺傳算法都有著良好的應用前景。謝謝！

遺傳算法