遺傳算法應(yīng)用的分析與研究課件

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

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

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

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

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

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