混合雜草遺傳算法求解旅行商問題

姚宇威* 鄧燕妮

（武漢理工大學控制工程系，湖北 武漢430000）

在這項研究中，研究了一種改進的混合雜草遺傳算法（GIWO），以解決旅行商問題，最大程度地縮小解空間，在有限的時間內找到最優解。為了驗證所提出算法的有效性和效率，通過Matlab 進行仿真測試。結果表明，GIWO 算法可以找到相同或更好的最優解。

1 旅行商問題

旅行商問題（TSP）是經典的NP-hard 問題，可以簡單描述為：一個商人在地圖的一系列城市中訪問，求解訪問每個城市一次并回到起點的最短路程。

TSP 問題有著廣泛的應用，如無人機路徑規劃、物流配送、網絡通訊等。國內外有許多的學者致力于研究TSP 問題。目前大致的解決方法可以分為兩種：精確算法和智能算法[1]。目前學者更傾向于智能算法的研究，由仿生機制得到啟發，提出不同角度的解決方案[2]。目前這些經典的智能算法或多或少存在著一些問題，如易陷入局部收斂、收斂速度較慢、面對大型節點適應性差、收斂精度不夠等[3]。

2 混合算法及鄰序矩陣

現階段對于解決TSP 問題的各種智能算法，大多是以犧牲某些性能來換取速度或者精度，有的則是針對一些依賴特定規則的問題提出相應的算法，缺少通用性[4]。

遺傳算法（GA）最早是由美國密歇根大學的Holland 教授在設計人工自適應系統時提出一種方法，是一種擴展性強、通用性很好的一種全局搜索算法。

入侵野草算法（IWO）是由伊朗德黑蘭大學的學者A.R.Mehrabian 等提出的，是基于野草生長繁殖特性的一種智能算法[5]。目前，關于IWO 的研究與應用主要活躍在解決連續性問題，對于離散問題應用研究較少[6]。

2.1 算法流程

混合雜草遺傳算法采用IWO 空間擴展思想，模擬雜草的初始入侵、生長、繁殖和競爭過程。具體流程如下：

第一步，初始雜草進行入侵，生成初始種群；

第二步，初始雜草進行生長，達到最大環境容量，每株雜草單體繁殖生長，多方向搜索。每株產生的種子數量與其適應度成正比；

第三步，達到環境容量，進行全局交流。若達到迭代數或存在合格個體，則停止算法；

第四步，群體進行競爭性生存，適應度低的個體消失，優勝劣汰形成新的初代雜草。

2.2 鄰序矩陣

鄰序矩陣是對TSP 問題模型的一種模型優化，該優化建立在TSP 問題特有機制上，即與城市相連的兩個城市中至少一個是與其距離較近的[7]。針對這一特點，建立了TSP 問題的鄰序矩陣和鄰序概率矩陣。

3 求解TSP 的混合雜草遺傳算法

3.1 初始化種群，包括初始種群大小、最大迭代次數、城市維數、最大種群數量、最大種子數、最小種子數、交叉率、變異率。城市初始化，生成鄰序矩陣Aij以及鄰序概率矩陣Pij。初始種群生成時，部分隨機生成，部分采用貪心算法根據鄰序矩陣生成。設定貪心系數g，尋找鄰序矩陣中距離當前城市最近可行的g 個節點，對于已選的節點順位后移，從g個節點中隨機選擇一個作為下一個城市。

Wj為個體Sj的后代種子個數，Fj為個體Sj的適應度，Smax為最優適應度個體允許生成的后代個數，Smin為最差適應度個體允許生成的后代個數。

在個體生成種子過程中，雜草進行單體繁衍，保證基因純度，即隨機生成的與貪婪算法生成的初始種群的純凈性。隨機選擇個體中的基因xj，由鄰序矩陣Aij以及鄰序概率矩陣Pij選擇xk來置換xj的下一位xj+1。并將xj+1和xk之間的城市進行倒序排列。

例如，個體基因為：

1 3 5 2 4 6 7

隨機xj為3，如若根據鄰序矩陣Aij以及鄰序概率Pij選擇城市3 的下一位xk為6，則后代為：

1 3 6 4 2 5 7

這一過程保證了種群的多樣性，同時也是適應度高的個體保持在群體中較多的占比。

3.3 全局交流

交叉采用單點順序交叉，對兩個父代個體隨機確定交叉點。例如，對兩父代編碼隨機交叉點為3：

1 4 5 / 6 7 3 2

6 1 2 / 3 5 4 7

進一步，將交叉點前半部分的編碼分配給另一方，形成如下兩種編碼：

6 1 2 1 4 5 6 7 3 2

1 4 5 6 1 2 3 5 4 7

去除原生段編碼的重復項，得到新的后代：

6 1 2 4 5 7 3

1 4 5 6 2 3 7

變異采取基于鄰序矩陣的單點變異。隨機選擇個體中的基因xj，根據鄰序矩陣Aij以及鄰序概率矩陣Pij選擇xk 來置換xj的下一位xj+1。

4 實例仿真

分別對30 和100 節點的TSP 問題進行了仿真。對前者設置初始種群大小8、最大迭代為數200、最大種子數10、最小種子數0、最大種群數量40，圖1（a）為收斂的結果。對后者設置初始種群大小20、最大迭代為數500、最大種子數10、最小種子數0、最大種群數量50，圖1（b）為找到的最優路徑。

圖1 兩種城市規模下的最優路徑

5 結論

本文根據TSP 問題的特性提出的城市節點鄰序矩陣和鄰序選擇概率矩陣大大加快了算法的收斂速度和穩定性。GIWO 算法引入入侵性雜草優化算法的空間擴展思想和遺傳算法的繁殖優化思想，對旅行上問題進行優化求解，很好的解決了在TPS問題中由于引入貪心算法而易陷入局部收斂的問題。從仿真結果得知GIWO 算法全局收斂性強、具有優秀的收斂速度和求解穩定性。