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