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

姚宇威* 鄧燕妮

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

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

1 旅行商問題

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

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

2 混合算法及鄰序矩陣

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

遺傳算法（GA）最早是由美國密歇根大學(xué)的Holland 教授在設(shè)計(jì)人工自適應(yīng)系統(tǒng)時(shí)提出一種方法，是一種擴(kuò)展性強(qiáng)、通用性很好的一種全局搜索算法。

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

2.1 算法流程

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

第一步，初始雜草進(jìn)行入侵，生成初始種群；

第二步，初始雜草進(jìn)行生長，達(dá)到最大環(huán)境容量，每株雜草單體繁殖生長，多方向搜索。每株產(chǎn)生的種子數(shù)量與其適應(yīng)度成正比；

第三步，達(dá)到環(huán)境容量，進(jìn)行全局交流。若達(dá)到迭代數(shù)或存在合格個(gè)體，則停止算法；

第四步，群體進(jìn)行競爭性生存，適應(yīng)度低的個(gè)體消失，優(yōu)勝劣汰形成新的初代雜草。

2.2 鄰序矩陣

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

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

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

Wj為個(gè)體Sj的后代種子個(gè)數(shù)，F(xiàn)j為個(gè)體Sj的適應(yīng)度，Smax為最優(yōu)適應(yīng)度個(gè)體允許生成的后代個(gè)數(shù)，Smin為最差適應(yīng)度個(gè)體允許生成的后代個(gè)數(shù)。

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

例如，個(gè)體基因?yàn)椋?/p>

1 3 5 2 4 6 7

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

1 3 6 4 2 5 7

這一過程保證了種群的多樣性，同時(shí)也是適應(yīng)度高的個(gè)體保持在群體中較多的占比。

3.3 全局交流

交叉采用單點(diǎn)順序交叉，對兩個(gè)父代個(gè)體隨機(jī)確定交叉點(diǎn)。例如，對兩父代編碼隨機(jī)交叉點(diǎn)為3：

1 4 5 / 6 7 3 2

6 1 2 / 3 5 4 7

進(jìn)一步，將交叉點(diǎn)前半部分的編碼分配給另一方，形成如下兩種編碼：

6 1 2 1 4 5 6 7 3 2

1 4 5 6 1 2 3 5 4 7

去除原生段編碼的重復(fù)項(xiàng)，得到新的后代：

6 1 2 4 5 7 3

1 4 5 6 2 3 7

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

4 實(shí)例仿真

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

圖1 兩種城市規(guī)模下的最優(yōu)路徑

5 結(jié)論

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