1. 首頁 > 生活 > >

遺傳算法經典實例matlab代碼 遺傳算法matlab程序案例詳解

小知識



文章插圖
遺傳算法經典實例matlab代碼 遺傳算法matlab程序案例詳解

文章插圖
旅行商問題（Traveling Salesman Problem，簡稱TSP問題），即為求解最優化的城市線路組合，要求每個城市都要走且只走一遍，終點城市同出發城市為同一個，最終所走路程需最短 。本文在傳統遺傳算法基礎上，對其進行改進優化，提出了精英保留的協同進化遺傳算法，并分別以30、50和75個城市為例，對二者進行對比 。該算法的運行流程如圖1所示 。
圖1 協同進化遺傳算法運行流程
產生初始種群后（設種群數量為POP），便按照適應度值（即總路程倒數）高低將其分為三個子種群，其中，子種群1的適應度值最大，子種群3的適應度值最小 。接著，在各個子種群內部進行交叉變異操作，依次產生新子種群1、新子種群2、新子種群3 。同時，三個子種群兩兩之間，也進行交叉變異操作，依次產生新子種群4、新子種群5、新子種群6 。最后便將這6個新子種群進行組合，然后從中隨機挑選出POP-1個個體，并根據精英保留策略，將其與父代最優個體相合并，從而得到新種群、開始下一代的操作 。
以30、50、75個城市為例，分別進行10次重復試驗，取各次試驗兩種算法最優解的平均值進行對比，結果如圖2所示 。
圖2 兩種算法的尋優結果對比
顯然，同傳統遺傳算法相比，協同進化遺傳算法具備更強大的最優解搜索能力，尤其當城市數量較多時（如此例中的75），其能更有效地避免陷入局部最優，從而找到全局最優的解、使得總路程更小 。以75個城市數量為例，兩種算法所確定的最優路徑分別如圖3(a)與3(b)所示 。
(a) 傳統遺傳算法
(b) 協同進化遺傳算法
圖3 兩種算法所確定的最優路徑對比
【遺傳算法經典實例matlab代碼 遺傳算法matlab程序案例詳解】圖3中，橫軸縱軸分別為每個城市的橫縱坐標，圖中的數字即為每個城市的編號 。顯然，協同進化遺傳算法所確定的最優路徑更為規整，這表明其同傳統遺傳算法相比，具有更強的全局尋優能力，且具備更好的魯棒性 。