基于LabVIEW仿真的全局最短路徑的遺傳算法設(shè)計
加入技術(shù)交流群
為了改善這種情況，本文摒棄了雙父代雜交而采用一種“群體精英父代雜交”的方法。因?yàn)殡s交運(yùn)算就是為了使優(yōu)秀基因快速繁殖，擴(kuò)大影響，所以不妨直接判定哪些基因是有較大概率優(yōu)秀的。舉例說明判斷方法，選擇所有f>favg的父代個體，這些個體明顯都是優(yōu)秀的，從這些優(yōu)秀父代中提取出共有的或出現(xiàn)次數(shù)較多的基因，因?yàn)閮?yōu)秀父代中含有優(yōu)秀基因的可能大，所以這些共有的基因就更可能是優(yōu)秀基因。保留這些基因，在剩余的基因位上隨機(jī)產(chǎn)生新的基因。最后從產(chǎn)生的這些新個體和ffavg的低適應(yīng)度父代中選出適應(yīng)度高的一部分作為子代，它們與開始的那些優(yōu)秀父代一起合成新的子代。因?yàn)閷?shí)際上并沒有使用單點(diǎn)雜交的方法，所以不使用式(3)。
5．2 變異
按式(4)計算，如果一個父代個體要變異時，從其中隨機(jī)取一條線段除去換上一條新的線段。為了提高變異操作提供新基因的效率，防止無方向性的變異產(chǎn)生大量冗余，新的線段要有一個端點(diǎn)不變。如圖5所示，當(dāng)除去線段12時，新產(chǎn)生的線段必須以節(jié)點(diǎn)3或6為端點(diǎn)，不算線段12，節(jié)點(diǎn)3、節(jié)點(diǎn)6分別還可以與其他M-2個節(jié)點(diǎn)產(chǎn)生共2M-4個子代個體，當(dāng)然其中有很多新個體是不合法的，從合法的子代個體中選擇適應(yīng)度最高的遺傳到下一代。這樣，經(jīng)過幾代變異后，個體就會逐漸趨于所求目標(biāo)。本文引用地址：http://butianyuan.cn/article/202494.htm
為了防止局部收斂，即使產(chǎn)生的予代個體適應(yīng)度不如父代個體，也要淘汰父代個體。
5．3 精英保留
根據(jù)上述方法，在進(jìn)化中很可能導(dǎo)致高適應(yīng)度個體被意外的破壞，減緩進(jìn)化速度甚至導(dǎo)致局部收斂。所以每次進(jìn)化前取出當(dāng)代個體中適應(yīng)度最高的一個個體直接進(jìn)入下一代，保證最優(yōu)基因的安全。
6 仿真實(shí)驗(yàn)
選取一組數(shù)據(jù)(見表1)進(jìn)行仿真實(shí)驗(yàn)，種群數(shù)量取50個，計算100代。
得到仿真結(jié)果如圖6所示。
圖6為分別截取了運(yùn)行到不同代數(shù)時的結(jié)果。圖6(a)表示所有點(diǎn)的位置及所有可能的連線，圖6(b)～圖6(d)中數(shù)字含義，括號內(nèi)的數(shù)字表示運(yùn)行代數(shù)，括號外是此時線段的總長度。圖6(d)顯示最終總長度為1087．77。
7 結(jié)論
綜上所述，此方法可以有效地解決全局最短路徑問題。相對于“旅行商問題”單一起點(diǎn)終點(diǎn)的“一筆畫”情況和繁復(fù)的編碼解碼運(yùn)算，本文的方法更具有廣泛性。因?yàn)楣?jié)省了一般的編碼解碼過程，所以運(yùn)算更加快捷，結(jié)果更易識別。隨著約束條件的改變，只需相應(yīng)的修改目標(biāo)函數(shù)即可，不會影響程序的其他功能。該方法可以適用多類工程設(shè)計，如Zigbee無線模塊組網(wǎng)、城鄉(xiāng)間道路和配電網(wǎng)設(shè)置、農(nóng)田灌溉點(diǎn)之間的管道連接、多目標(biāo)的運(yùn)輸問題等等。
評論