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