袁成林

（1.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004；2.廣西醫(yī)科大學(xué)基礎(chǔ)醫(yī)學(xué)院，廣西 南寧530021）

遺傳算法是一種基于進(jìn)化策略的優(yōu)化算法[1]，被廣泛使用在組合優(yōu)化問題中。但是遺傳算法在解決問題的時(shí)候也有諸多不足，首先是在早期的搜索中常常丟失種群的多樣性[2]。在單目標(biāo)優(yōu)化中，對(duì)于種群的適應(yīng)性方面的研究很多，多樣性保持方面常常用的手段是小生境方法。其次由于遺傳算法的局部能力差，也有學(xué)者采用其他局部搜索算法來構(gòu)造混合遺傳算法[3]，這些方法對(duì)在種群適應(yīng)性方面是有效的，但是在種群多樣性方面卻不足，對(duì)于有的優(yōu)化問題來說，多樣性保持對(duì)搜索最優(yōu)解有著重要的作用。最后在旅行商問題中普通的交叉算子會(huì)破壞要交換的基因片段，針對(duì)這個(gè)問題本文提出了對(duì)應(yīng)連通子圖交叉(Corresponding Connected Subgraph Crossover,CCSC)，結(jié)合LK局部搜索和小生境等操作構(gòu)造一種基于CCSC的混合遺傳算法(CHGA)。通過幾個(gè)實(shí)例的計(jì)算和對(duì)比表明，算法的設(shè)計(jì)是有效的，求解質(zhì)量也有較大提高。

1 對(duì)應(yīng)連通子圖交叉

交叉算子是遺傳算法中最重要的部分，既可以使個(gè)體發(fā)生變化，又能保留父體的優(yōu)秀基因片段，使種群向著理想的方向進(jìn)化。對(duì)于旅行商問題通常采取自然編碼，即每個(gè)基因位對(duì)應(yīng)一個(gè)城市的號(hào)碼。例如1-2-3-4-5-6表示依次經(jīng)過城市1到6最后回到1。這種編碼容易理解，效率高。但是在這種編碼方式下普通的交叉算法就不再適用了，因?yàn)榭赡墚a(chǎn)生沒有意義的個(gè)體。圖1中兩條可用路徑經(jīng)過交叉操作以后，產(chǎn)生的1-1-5-6-3-6路徑是沒有意義的。為了解決這個(gè)問題，很多學(xué)者提出了適用于TSP的交叉算子，像順序插入法，啟發(fā)式交叉等，但是這些算法會(huì)打亂交叉片段中的基因位置因而不能保存父體的優(yōu)秀基因片段。

圖1 普通交叉操作產(chǎn)生的不可用路徑

基于以上分析，本文提出一種新的交叉算子：對(duì)應(yīng)連通子圖交叉(CCSC)。這種交叉方法可以做到嚴(yán)格的交叉，即子代的基因都是從父代繼承所得，所有基因片段都可以在兩個(gè)父體中找到。CCSC通過合并兩條父體路徑，構(gòu)造連通圖G。對(duì)G中的對(duì)應(yīng)連通子圖進(jìn)行搜索，然后進(jìn)行交叉，交叉策略可以是：隨機(jī)選擇某個(gè)或若干個(gè)對(duì)應(yīng)連通子圖進(jìn)行交換，還可以采用貪婪選擇對(duì)每個(gè)對(duì)應(yīng)連通子圖進(jìn)行多次搜索，找到最短個(gè)體，這幾種方法時(shí)間復(fù)雜度都在O(n)之內(nèi)，本文權(quán)衡算法效率和求解效果，決定采用隨機(jī)選擇若干個(gè)對(duì)應(yīng)連通子圖進(jìn)行交換的交叉策略。明顯可以看出若對(duì)應(yīng)連通子圖的個(gè)數(shù)大于等于1，CCSC就可以創(chuàng)造兩個(gè)以上的后代個(gè)體。若有k個(gè)對(duì)應(yīng)連通子圖，則可以產(chǎn)生2k+1-2個(gè)個(gè)體，減2是因?yàn)橛袃蓚€(gè)個(gè)體和父體是相同的。

對(duì)應(yīng)連通子圖：合并兩條父體路徑，構(gòu)造連通圖G，在G中，刪除兩條父體路徑的重合邊后，得到圖G1，G1的某個(gè)連通子圖中的節(jié)點(diǎn)在兩條父體中均為連續(xù)的基因片段，此連通子圖稱為對(duì)應(yīng)連通子圖。

圖2-2中的a-b-c-d,a-c-b-d和g-h-j-i-k,g-i-h-j-k就是兩對(duì)對(duì)應(yīng)連通子圖：

圖2 對(duì)應(yīng)連通子圖示意

尋找對(duì)應(yīng)連通子圖的流程如下：

（1）刪除圖G中兩條路徑重合的邊。

（2）建立隊(duì)列Q，把度為1的n個(gè)節(jié)點(diǎn)放在隊(duì)頭，設(shè)定計(jì)數(shù)器K=n。

（3）從隊(duì)列的n+1個(gè)節(jié)點(diǎn)開始進(jìn)行廣度遍歷，找出所有連通子圖，把遍歷過的點(diǎn)前移，記錄連通子圖結(jié)點(diǎn)個(gè)數(shù)ti，直至所有節(jié)點(diǎn)操作完成。

（4）對(duì)結(jié)點(diǎn)個(gè)數(shù)ti大于等于3的連通子圖i，對(duì)其父體進(jìn)行檢查如果連通子圖的節(jié)點(diǎn)在兩父體中均為連續(xù)的基因片段，則該連通子圖為一個(gè)對(duì)應(yīng)連通子圖g，記錄g。

（5）如果符合要求的連通子圖都已經(jīng)搜索就退出程序，否則返回步驟4。

2 混合遺傳算法CHGA的實(shí)現(xiàn)

2.1 選擇算子

選擇算子是算法中關(guān)鍵的一環(huán)，可以選擇優(yōu)秀個(gè)體進(jìn)入下一代進(jìn)行交叉和變異操作，本文采用的是輪盤賭法，根據(jù)個(gè)體的適應(yīng)度進(jìn)行選擇，適應(yīng)度越大個(gè)體被選擇的概率就越大，并且可以保留少量適應(yīng)度較差的個(gè)體，增加種群多樣性。

2.2 變異和交叉算子

變異：本文采用兩點(diǎn)隨機(jī)交換的變異操作對(duì)種群進(jìn)行擾動(dòng)，跳出某些局部最優(yōu)解。

交叉：本文采用第一節(jié)提出的對(duì)應(yīng)聯(lián)通子圖交叉作為交叉算子。

2.3 小生境操作

經(jīng)過輪盤賭選擇等操作后，適應(yīng)度大的個(gè)體更容易進(jìn)入新種群，種群里就會(huì)出現(xiàn)很多一樣或者很相似的個(gè)體，這樣就會(huì)導(dǎo)致算法早熟，結(jié)果陷入局部最優(yōu)解，所以本文引入小生境操作來保持物種多樣性。

具體方法是：假設(shè)種群共有n個(gè)個(gè)體，首先計(jì)算個(gè)體i(i=1,2…n)和其他個(gè)體之間的小生境距離L(i,j)。在對(duì)個(gè)體i與其他所有個(gè)體的小生境距離L(i,j)求和，計(jì)算出個(gè)體i的小生境排序值循環(huán)這個(gè)步驟直到計(jì)算出所有si。升序排列si后，用隨機(jī)產(chǎn)生的個(gè)體代替si最高的n個(gè)個(gè)體，算法的時(shí)間復(fù)雜度是O(n2)。

其中L(i,j)的求法是，假設(shè)TSP共有N個(gè)城市，取個(gè)體i的第k（k=1,2,3…N）個(gè)基因位城市i(k)，在個(gè)體j中找到城市i(k)的位置t，對(duì)i(k)和j(t)左右兩邊城市號(hào)做同或操作∶L(i,j)=i(k+1)⊙j(t+1)+ i(k+1)⊙j(t-1)+ i(k-1)⊙j(t+1)+ i(k-1)⊙j(t-1)。因?yàn)?0≤L(i,j)≤2，所以 0≤si≤2n。小生境排序值si越大說明個(gè)體i周圍的個(gè)體越多。對(duì)種群的非精英個(gè)體進(jìn)行小生境操作，起到了保留精英又增加種群多樣性的作用。

2.4 局部搜索

在CHGA中局部搜索算法起著十分重要的作用。它可以使種群迅速向著希望的方向進(jìn)化。它的另一個(gè)作用是使 CHGA算法的第一代開始就能夠找到更多的對(duì)應(yīng)連通子圖，提高算法的效率，本文采用LK算法[4]作為局部搜索。

在本文中局部搜索的另一個(gè)作用是使算法的第一代開始就能夠找到等多的對(duì)應(yīng)連通子圖(CCS)，通過實(shí)驗(yàn)測(cè)試 CCSC結(jié)合局部搜索算法可以產(chǎn)生的對(duì)應(yīng)連通子圖的大致個(gè)數(shù)，實(shí)驗(yàn)采用TSPLIB中的att532,nrw1379 和 u1817三個(gè)算例，用3-OPT，3-OPT和MO-LK算法對(duì)50個(gè)隨即路徑進(jìn)行測(cè)試，平均實(shí)驗(yàn)結(jié)果如表1。通過實(shí)驗(yàn)發(fā)現(xiàn)2-OPT與CCSC結(jié)合在90%的情況下可以產(chǎn)生可用個(gè)體，也就是至少有一對(duì)對(duì)應(yīng)連通子圖而，結(jié)合3-OPT和LK算法的CCSC產(chǎn)生可用解的概率達(dá)到了將近100%。

表1 不同局部搜索找到的對(duì)應(yīng)連通子圖個(gè)數(shù)

3 算例實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

為驗(yàn)證所設(shè)計(jì)算法的有效性，基于如下實(shí)驗(yàn)環(huán)境進(jìn)行相關(guān)實(shí)驗(yàn)：聯(lián)想臺(tái)式機(jī)，其配置為：

（1）CPU：AMD 64 2X 4400+；

（2）內(nèi)存：2 G DDR2；

（3）操作系統(tǒng)：Windows XP

程序以 VC++2008編寫及編譯，實(shí)驗(yàn)使用數(shù)據(jù)取自TSPLIB。算法各參數(shù)如表1所示。實(shí)驗(yàn)結(jié)果均為運(yùn)行算法10次后計(jì)算得到的平均值、最優(yōu)值以及最差值。

3.2 實(shí)驗(yàn)參數(shù)

表2 混合遺傳算法算法的參數(shù)設(shè)置

3.3 實(shí)驗(yàn)結(jié)果

本文的算例采用 TSPLIB數(shù)據(jù)庫(kù)中的 Att48、Eil51、Eil76、Kroa100、 Ch130 、Tsp225、Ch 150等6個(gè)測(cè)試對(duì)象，每個(gè)算例進(jìn)行20次計(jì)算，結(jié)果取平均值，并與文獻(xiàn)[5,6]進(jìn)行了對(duì)比。具體數(shù)據(jù)如下：

表3 混合遺傳算法算法的計(jì)算結(jié)果

圖3 算例Eil51收斂情況

實(shí)驗(yàn)結(jié)果表明，本文所做改進(jìn)效果明顯。100以內(nèi)規(guī)模的問題每次都可以計(jì)算出TSPLAB最優(yōu)解，而且速度上相比文獻(xiàn)所述也有優(yōu)勢(shì)。100以上問題在 20次實(shí)驗(yàn)中可以計(jì)算出TSPLAB最優(yōu)解，而且平均值的誤差也在1%以內(nèi)。在下一步工作中，可以著力改善算法的計(jì)算速度，并且向更大規(guī)模的問題發(fā)起挑戰(zhàn)。

[1] Holland John H. Adaptation in natural andartificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[J]. USA: University of Michigan, 1975.

[2] 馬良.旅行推銷員問題的算法綜述[J].數(shù)學(xué)實(shí)踐與認(rèn)識(shí),2000,32(2):156-165.

[3] 葛繼科,丘玉輝,等.遺傳算法研究綜述[J],計(jì)算機(jī)應(yīng)用研究,2008,25(10): 2911-2917.

[4] Helsgaun K. General k-opt submoves for the Lin–Kernighan TSP heuristic[J]. Mathematical Programming Computation, 2009,1(2-3): 119-163.

[5] 孫凱,吳紅星,王浩,丁家棟.蟻群與粒子混合算法求解TSP問題[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(34):60-63.

[6] 李哲,夏立,莊浩俊,董紅生.MMAS_EC 算法求解旅行商問題[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(9):41-47.