許 沖,鐘 瑋,劉欣欣

（閩南師范大學(xué)計(jì)算機(jī)學(xué)院,福建漳州363000）

1948 年由美國(guó)蘭德公司推動(dòng)的TSP（Traveling Salesman Problem）是一個(gè)較古老的巡回旅行商問(wèn)題[1]，成為近代組合優(yōu)化領(lǐng)域的一個(gè)典型難題，已被證明為NP 難題.TSP 描述為在一個(gè)加權(quán)無(wú)向圖中，尋找一個(gè)邊的權(quán)值之和最小的Hamilton圈.

隨著TSP的研究和利用的不斷擴(kuò)展，圖的復(fù)雜程度不斷加大，導(dǎo)致TSP求解的搜索空間不斷加大.諸多學(xué)者也提出了多種不同的求解TSP 問(wèn)題的算法.其中，湖水能量算法[2]就是一種高效的求解算法，但其缺點(diǎn)在于找到最優(yōu)解的概率較低.郭濤算法[3]（GT）是一種改進(jìn)遺傳演化算法，被證明是一種效率很高的算法.但是，隨著圖的規(guī)模和復(fù)雜度增大，GT算法找到最優(yōu)解的概率不斷下降.蔡之華[4]，謝大同[5]等給出了一種對(duì)郭濤算法或其Inver-over算子[3]進(jìn)行改進(jìn)的求解TSP問(wèn)題的演化算法，經(jīng)過(guò)實(shí)驗(yàn)證明其找到最優(yōu)解的能力雖有改善，但仍不夠理想，其在實(shí)例CHN144上找到最優(yōu)解的概率僅為0.7.本文采用粒子群[6]的基因片段插入[7-8]與Inver-over算子結(jié)合，隨機(jī)的在粒子中插入其他粒子的片段，以達(dá)到擴(kuò)大粒子搜索范圍的作用，從而防止算法解的早熟.

1 新的演化算法

為方便算法描述，先對(duì)算法中使用的參數(shù)、符號(hào)和數(shù)據(jù)作以下說(shuō)明.

給定n 個(gè)城市{1,2,…,n}以及對(duì)應(yīng)的坐標(biāo)值，記兩個(gè)城市i 和j 之間的距離d(i,j).用c1c2…cn來(lái)表示TSP的一個(gè)解的路徑（其中1 ≤ci≤n,且c1c2…cn互不相同），并稱(chēng)c1c2…cn為一個(gè)個(gè)體p，一組個(gè)體的集合稱(chēng)為P ，第i 個(gè)個(gè)體稱(chēng)為Pi. c1c2…cn個(gè)體的長(zhǎng)度定義為d(c1,c2)+ d(c2,c3)+ …+ d(cn-1,cn)+ d(cn,c1). 設(shè)1 ≤t ≤n - 1,長(zhǎng)度為l 的路徑cici+1…ci+t稱(chēng)為個(gè)體c1c2…cn的一個(gè)起始位置為i，長(zhǎng)度為t 的基因片段(若下標(biāo)大于n,則將此下標(biāo)除n取余數(shù)).

1.1 郭濤算法

郭濤算法提出的Inver-over算子具有雜交和變異的演化特征，算法在設(shè)置群體規(guī)模參數(shù)后，按照隨機(jī)倒置概率ρ 對(duì)個(gè)體進(jìn)行盲目或自適應(yīng)的兩種方式倒置，直到滿(mǎn)足結(jié)束條件，算法結(jié)束.其中，倒置操作作用于個(gè)體的局部，隨機(jī)倒置概率ρ 一般設(shè)置很小，大部分倒置操作來(lái)自群體中的其他個(gè)體，達(dá)到加快收斂的目的；極少部分隨機(jī)產(chǎn)生，其作用打破收斂趨勢(shì)，增加搜索全局最優(yōu)解的可能性.郭濤算法對(duì)個(gè)體Pi操作如圖1所示.

圖1 郭濤算法的Inver-over算子Fig.1 Inver-over operator of Guo Tao algorithm

TSP 結(jié)果得到的路徑是個(gè)閉合的環(huán)路，每次操作都對(duì)基因片段進(jìn)行反轉(zhuǎn)，算法運(yùn)行的速度快.因此，郭濤算法相比于其他演化算法在求解質(zhì)量和速度上都有較好效果，這主要在于算法中群體趨優(yōu)信息得到了充分的利用.但是在試驗(yàn)中也發(fā)現(xiàn)，郭濤算法對(duì)于小規(guī)模TSP問(wèn)題的求解效果優(yōu)異，但是對(duì)于解決規(guī)模較大的TSP 問(wèn)題，其尋找全局最優(yōu)解的效果就大為下降.這主要是由于該算法的操作迭代在前期的收斂速度很快，而到了后期，群體中的粒子所表示的解的路徑都是沒(méi)有交叉的較優(yōu)環(huán)形路徑，所以算法在后期的收斂速度明顯變慢，且容易陷入局部最優(yōu)解.

1.2 基因片段插入運(yùn)算

基因片段插入對(duì)個(gè)體Pi的運(yùn)算如圖2所示.

圖2 基因片段插入運(yùn)算Fig.2 Gene fragment insertion

取Q( j),R( j)中的最小值，若最小值為Q(m)，則將基因片段S 正序插入到P'i的cm與cm+1之間，若最小值為R(m),則將基因片段S逆序插入到P'i的cm與cm+1之間，得到新的個(gè)體.

基因片段插入運(yùn)算的主要思想是在于通過(guò)從群體的其它個(gè)體中截取部分基因片段插入到原個(gè)體，以達(dá)到保持個(gè)體的多樣性和改善個(gè)體局部的目的.

1.3 混合算法

根據(jù)算法分析和試驗(yàn)結(jié)果，本文將郭濤算法的Inver-over算子與基因片段插入算法相融合，提出了一個(gè)新的算法.混合算法描述如下.

Input：城市數(shù)n及各城市對(duì)應(yīng)位置坐標(biāo).

Output：輸出全局最優(yōu)解global_best及其路徑長(zhǎng)度gb_length.

Step1：設(shè)置種群中個(gè)體個(gè)數(shù)N_ALL(一般設(shè)置為N_ALL = 4n)及算法迭代次數(shù)T.

初始化所有個(gè)體，其中n個(gè)個(gè)體利用貪心算法從城市i開(kāi)始產(chǎn)生{P1,P2,…,Pn-1,Pn}，其余N_ALL_n個(gè)個(gè)體采用隨機(jī)方式產(chǎn)生，得到N_ALL 個(gè)個(gè)體的種群{P1,P2,…,Pn,Pn+1,…,PN_ALL}，記迭代計(jì)數(shù)變量T_number = 0.

Step 2：將個(gè)體Pi的值保存到R，即(R = Pi).

1）使用郭濤算法對(duì)個(gè)體R進(jìn)行操作.

2）生成3個(gè)隨機(jī)數(shù)j(1 ≤j ≤N_ALL,j ≠i)、s(1 ≤wz ≤n)、k(2 ≤k ≤n/6),其中k = 2 +(int)((rand()%(n/6 -1))*(1 - T_number%(2*n)*0.98/(2*n))).然后，從個(gè)體Pj的起始位置為s，長(zhǎng)為k 的基因片段gene，并把gene采用基因片段插入算法插入到個(gè)體R中.若R的路徑長(zhǎng)度小于Pi路徑長(zhǎng)度，則Pi= R.

Step 3：T_number = T_number + 1.

Step 4：如果T_number ＜T,則執(zhí)行Step 2；否則轉(zhuǎn)至Step 5.

Step 5：從種群中找出最優(yōu)個(gè)體,并將個(gè)體及其路徑長(zhǎng)度分別保存至global_best和gb_length.

此算法不僅保持種群中個(gè)體的多樣性，擴(kuò)大種群對(duì)解的搜索能力，同時(shí)對(duì)個(gè)體的局部進(jìn)行有針對(duì)性的改良.算法中，空間復(fù)雜度主要體現(xiàn)在種群的存儲(chǔ)空間，為O(n2).郭濤算法的時(shí)間復(fù)雜度為O(n2)，基因片段插入的時(shí)間復(fù)雜度為O(n3)，迭代次數(shù)為T(mén)，因此算法的時(shí)間復(fù)雜度為O(n3T).

2 仿真試驗(yàn)

仿真試驗(yàn)采用TSPLIB 中的Eil51、st70、ch150、pr226 以及中國(guó)144 個(gè)城市的Ch144 等5 個(gè)實(shí)例作為試驗(yàn)用例.在試驗(yàn)過(guò)程中，將5 組用例分別采用郭濤算法、基因片段插入算法和混合算法各重復(fù)運(yùn)行50 次，以最多迭代n2次為限制，得到對(duì)比數(shù)據(jù)如表1所示.

表1 測(cè)試結(jié)果對(duì)比Tab.1 Comparison of test results

從表1中的試驗(yàn)對(duì)比數(shù)據(jù)可見(jiàn)，使用郭濤算法單獨(dú)求解時(shí)，當(dāng)圖的規(guī)模變大后，其迭代次數(shù)極具增加，且找到最優(yōu)解的概率也不斷下降.而單獨(dú)使用基因片段插入算法進(jìn)行求解時(shí)，效率較不穩(wěn)定，且找到最優(yōu)解的概率也不夠理想.但采用兩個(gè)算法結(jié)合的混合算法，對(duì)上述5 個(gè)試驗(yàn)用例進(jìn)行50 次試驗(yàn)均找到最優(yōu)解.雖然該混合算法的時(shí)間復(fù)雜度較高，但其優(yōu)異的搜索能力和收斂速度，其找到最優(yōu)解的迭代次數(shù)遠(yuǎn)低于n2，也低于其它兩個(gè)算法的迭代次數(shù)，即使在圖的規(guī)模增大的情況下，其迭代次數(shù)也未明顯增加.

3 結(jié)論

本文將兩種算法融合產(chǎn)生一種新的求解旅行商問(wèn)題的演化算法.試驗(yàn)結(jié)果表明，該算法不僅能夠有效地提高找到最優(yōu)解的概率，而且運(yùn)行效率很高，是一種有效可行的算法.