基于局部搜索機(jī)制快速求解TSP問(wèn)題的自適應(yīng)遺傳算法

夏 凱，戴文戰(zhàn)

（1.浙江理工大學(xué)機(jī)械與自動(dòng)控制學(xué)院，杭州310018；2.浙江工商大學(xué)信息與電子工程學(xué)院，杭州310018）

基于局部搜索機(jī)制快速求解TSP問(wèn)題的自適應(yīng)遺傳算法

夏 凱1，戴文戰(zhàn)2

（1.浙江理工大學(xué)機(jī)械與自動(dòng)控制學(xué)院，杭州310018；2.浙江工商大學(xué)信息與電子工程學(xué)院，杭州310018）

提出了一種基于局部搜索機(jī)制快速求解TSP的遺傳算法?；诰植克阉鳈C(jī)制，自適應(yīng)地將標(biāo)準(zhǔn)遺傳算法與局部啟發(fā)式算法結(jié)合，使得局部啟發(fā)式算法只在有效改善種群個(gè)體質(zhì)量的情況下才允許執(zhí)行，有效地避免了因局部搜索次數(shù)過(guò)多而引起的陷入局部最優(yōu)和計(jì)算負(fù)擔(dān)過(guò)重現(xiàn)象的發(fā)生。仿真結(jié)果表明，該算法具有較強(qiáng)的全局優(yōu)化能力及較快的收斂速度，在求解TSP問(wèn)題時(shí)有較高效率。

局部搜索機(jī)制；自適應(yīng)；遺傳算法；旅行商問(wèn)題

0 引 言

旅行商問(wèn)題（traveling salesman problem，TSP）一直具有重要理論研究?jī)r(jià)值和廣泛工程應(yīng)用價(jià)值。精確算法如分支定界法、動(dòng)態(tài)規(guī)劃法等，在問(wèn)題規(guī)模較小時(shí)能到得到最優(yōu)解，但算法的時(shí)間復(fù)雜度和空間復(fù)雜度都會(huì)隨著問(wèn)題規(guī)模的增加而成指數(shù)增長(zhǎng)。由于近似算法能夠在合理的時(shí)間和存儲(chǔ)空間范圍內(nèi)求出問(wèn)題的最優(yōu)解或近似最優(yōu)解，因而眾多學(xué)者對(duì)其進(jìn)行了大量的研究。遺傳算法（genetic algorithm，GA）因其具有較強(qiáng)的全局搜索能力、高效的群體搜索策略以及與目標(biāo)梯度信息無(wú)關(guān)等優(yōu)點(diǎn)，是求解TSP問(wèn)題的一種理想方法。

GA中一個(gè)較難解決的問(wèn)題是如何較快地找到最優(yōu)解并防止“早熟”收斂問(wèn)題。許多研究者提出了各種改進(jìn)方法來(lái)提高GA的搜索性能。彭丹平等［1］從相似性的思想出發(fā)，按適應(yīng)值相似性將群體分級(jí)，在不同的級(jí)內(nèi)采用不同的操作，產(chǎn)生數(shù)目不等的新解并利用加速算子使其更接近局部極小值，較好地解決了群體多樣性與收斂性的矛盾。姜昌華［2］等結(jié)合遺傳算法和2-opt領(lǐng)域搜索優(yōu)化技術(shù)，提出了K近鄰點(diǎn)集以縮減搜索空間從而加快求解速度。楊輝［3］等提出了構(gòu)建基因庫(kù)與遺傳算法相結(jié)合的算法，利用基因庫(kù)實(shí)現(xiàn)初始種群的優(yōu)生和指導(dǎo)種群的進(jìn)化方向，并用全局搜索算子和局部搜索算子增強(qiáng)GA的“探測(cè)”和“開(kāi)發(fā)”能力，加快了算法的收斂速度和尋優(yōu)能力。Ren等［4］構(gòu)建了混沌搜索算法，并結(jié)合單親遺傳算法和貪婪局部搜索算法求解旅行商問(wèn)題，能較好逃離局部最優(yōu)，獲得全局最優(yōu)或近似最優(yōu)解。Yang等［5］引入了遷移機(jī)制，當(dāng)進(jìn)化中的種群多樣性缺失時(shí)，通過(guò)遷移機(jī)制，將種群中的一部分個(gè)體用優(yōu)良的個(gè)體替代。Hua等［6］提出了一種自適應(yīng)調(diào)整控制參數(shù)的遺傳算法，自適應(yīng)的調(diào)整交叉和變異概率，并與2-opt算法相結(jié)合。許多研究結(jié)果表明將遺傳算法與局部啟發(fā)式算法結(jié)合起來(lái)可以有效地提高求解大型TSP問(wèn)題的質(zhì)量，利用遺傳算法自適應(yīng)的隨機(jī)搜索性能“勘探”潛在的最優(yōu)空間，而局部啟發(fā)式搜索則在這些子空間進(jìn)行深入“開(kāi)發(fā)”。這類(lèi)算法在提高收斂速度和尋求全局最優(yōu)之間找到一個(gè)平衡點(diǎn)［7］。文獻(xiàn)［1-6］雖然將局部搜索算法加入到遺傳算中，但往往導(dǎo)致過(guò)多的局部搜索而陷入局部最優(yōu)和造成計(jì)算時(shí)間上的不必要浪費(fèi)。

針對(duì)這個(gè)問(wèn)題，提出了一種基于局部搜索機(jī)制的自適應(yīng)遺傳算法（adaptive genetic algorithm，AGA）。在算法中，局部搜索是根據(jù)種群個(gè)體適應(yīng)度值標(biāo)準(zhǔn)偏差和種群個(gè)體的平均巡回路徑長(zhǎng)度的變化情況自適應(yīng)地與全局搜索相結(jié)合，局部搜索只在能有效改善種群個(gè)體質(zhì)量的情況下才允許執(zhí)行，因而能有效避免陷入局部最優(yōu)，減輕了計(jì)算負(fù)擔(dān)。

1 TSP問(wèn)題模型

TSP模型可簡(jiǎn)單描述如下：

假設(shè)一名旅行商需要訪問(wèn)n個(gè)城市且每個(gè)城市的坐標(biāo)為（xi，yi），（i∈［1，n］），城市i與城市j之間的歐拉距離是：

旅行商需要找到一條哈密頓回路，即從任意一城市出發(fā)，路途中經(jīng)過(guò)每個(gè)城市當(dāng)且僅當(dāng)一次然后回到原出發(fā)點(diǎn)，使其路徑長(zhǎng)度最短。即：

此外，TSP問(wèn)題模型也可以從圖論的角度來(lái)描述。給出有向圖G=（V，E），圖中每條邊e∈E，有一個(gè)非負(fù)的權(quán)值ω（e），目的是在有向圖G上發(fā)現(xiàn)一個(gè)具有最小權(quán)值和的哈密頓回路［8］。如下：

2 局部搜索策略

本研究采用了2-opt鄰域搜索優(yōu)化技術(shù)作為與GA結(jié)合的局部搜索算法。利用GA自適應(yīng)性的隨機(jī)搜索性能勘探潛在的最優(yōu)解空間，2-opt在這些子空間內(nèi)進(jìn)行深入搜索。按照特定的適應(yīng)性機(jī)制，將GA與2-opt局部搜索算法自適應(yīng)地結(jié)合，能較好地解決提高收斂速度和尋求全局最優(yōu)之間的矛盾，使它們達(dá)到平衡。其基本思想為：局部搜索算法只在需要的時(shí)候才允許執(zhí)行。提出了以下適應(yīng)性機(jī)制，確保只在局部搜索算法能有效地改善種群個(gè)體解的質(zhì)量的前提下才允許執(zhí)行。

2.1 局部搜索機(jī)制

局部搜索只在能提供給種群進(jìn)化有用的信息時(shí)才被執(zhí)行。一開(kāi)始種群個(gè)體適應(yīng)度值標(biāo)準(zhǔn)偏差σ和種群個(gè)體的平均巡回路徑距離ρ都比較大，但是隨著種群的不斷進(jìn)化，最后種群中的個(gè)體非常相似或趨于一致，此時(shí)σ很小或趨于0，ρ也變得很小。

偏差σ的計(jì)算公式如下：

其中n為種群中個(gè)體的總數(shù)，xi為種群中第i個(gè)個(gè)體的適應(yīng)度為種群中所有個(gè)體適應(yīng)度的平均值。為了跟蹤σ的變化，本文定義V來(lái)表示兩個(gè)連續(xù)代之間σ的變化率。V的計(jì)算公式如下：

其中σ（i）表示第i代種群個(gè)體適應(yīng)度值的標(biāo)準(zhǔn)偏差。如果V＞1，則說(shuō)明種群中第i代種群中個(gè)體適應(yīng)度值偏離種群平均適應(yīng)度值的程度比第i-1代大，即種群中的個(gè)體適應(yīng)度分布比較分散。

同時(shí)，為了跟蹤ρ的變化，本文定義W來(lái)表示連續(xù)兩代之間ρ的變化率。W的計(jì)算公式如下：

其中ρ（i）表示第i代種群個(gè)體所代表的巡回路徑距離平均值。如果W＞1，則說(shuō)明第i代種群中個(gè)體的平均距離比第i-1代大，即種群中個(gè)體的平均個(gè)體解質(zhì)量比前代差。

如果同時(shí)滿(mǎn)足V＞1且W＞1，則表明第i代種群個(gè)體解的質(zhì)量比第i-1代差，說(shuō)明算法正在探索新的解空間，這些解子空間可能是通過(guò)遺傳算法的交叉或變異算子產(chǎn)生，由于新產(chǎn)生的個(gè)體的適應(yīng)度值與種群中剩余個(gè)體相比相差較大，這樣會(huì)導(dǎo)致種群的標(biāo)準(zhǔn)偏差值增加和個(gè)體平均適應(yīng)度值減少，此時(shí)需要進(jìn)一步對(duì)新的解子空間進(jìn)行開(kāi)發(fā)，則啟用局部搜索。

當(dāng)種群中最優(yōu)個(gè)體適應(yīng)度值fbest與個(gè)體平均適應(yīng)度值fave的偏差率φ很小時(shí)，此時(shí)，局部搜索不但不能有效的改善解的質(zhì)量，而且會(huì)額外的增加計(jì)算時(shí)間，則結(jié)束局部搜索。偏差率的參考值為1%。

φ的計(jì)算公式如下：

3 算法流程

算法流程描述如下：

Step1 遺傳代數(shù)計(jì)數(shù)器初始化：t←0。

Step2 基于基因庫(kù)初始化群體P（t），對(duì)P（t）進(jìn)行預(yù)處理并計(jì)算個(gè)體適應(yīng)度。

Step3 采用賭輪轉(zhuǎn)方式選擇個(gè)體，同時(shí)采用精英保留策略，即保存當(dāng)前群體中的最優(yōu)個(gè)體。

Step4 對(duì)種群個(gè)體進(jìn)行雜交、變異操作，即進(jìn)行標(biāo)準(zhǔn)遺傳算法操作，并計(jì)算種群個(gè)體適應(yīng)值。

Step5 判斷是否應(yīng)該執(zhí)行局部搜索。如果滿(mǎn)足V＞1，W＞1且φ＞1%，轉(zhuǎn)到Step6執(zhí)行，否則轉(zhuǎn)到Step3。

Step6 局部搜索優(yōu)化。隨機(jī)從種群中選擇一定比例的個(gè)體，對(duì)這些個(gè)體進(jìn)行局部搜索優(yōu)化，將優(yōu)化后的個(gè)體替代原先的個(gè)體。

Step7 終止條件判斷。若t總設(shè)定的進(jìn)化迭代次數(shù)，則t=t+1，轉(zhuǎn)向Step3。否則，輸出最優(yōu)結(jié)果，算法結(jié)束。

4 仿真研究

本文針對(duì)城市規(guī)模分別為31［1］和50［4］的典型TSP問(wèn)題，用本算法在matlab7.0軟件上進(jìn)行仿真研究。初始化控制參數(shù)：種群個(gè)體數(shù)均設(shè)為30，最大迭代次數(shù)分別設(shè)為100和500，交叉概率均設(shè)為0.9，變異概率均設(shè)為0.01。每組實(shí)驗(yàn)均分別進(jìn)行10次，得出的城市規(guī)模為31的最優(yōu)路徑如圖1所示。最短路徑長(zhǎng)度為15 378，最短迭代次數(shù)為18，如圖2所示。

城市規(guī)模為50的最優(yōu)路徑如圖3所示。最短路徑長(zhǎng)度為549.96，最短迭代次數(shù)為16，如圖4所示。仿真結(jié)果表明，AGA算法具有較強(qiáng)的全局搜索能力和較快的收斂速度，能在較短的時(shí)間內(nèi)獲得滿(mǎn)意的解，確實(shí)能夠有效地提高TSP問(wèn)題的求解質(zhì)量和求解速度。

圖1 城市規(guī)模為N=31時(shí)的最優(yōu)路徑

圖2 城市規(guī)模為N=31時(shí)的優(yōu)化過(guò)程

圖3 城市規(guī)模為N=50時(shí)的最優(yōu)路徑

圖4 城市規(guī)模為N=50時(shí)的優(yōu)化過(guò)程

為了更好的檢驗(yàn)本算法的性能，將AGA算法所得的最優(yōu)解分別與文獻(xiàn)［1］和［4］給出的最優(yōu)解進(jìn)行比較，結(jié)果見(jiàn)表1。

表1 城市規(guī)模N=31，50的仿真結(jié)果

其中，城市規(guī)模指代的是具有不同城市個(gè)數(shù)的TSP問(wèn)題；本文結(jié)果指代的是采用本文算法求解對(duì)應(yīng)TSP問(wèn)題獲得的最短路徑長(zhǎng)度；已公布最優(yōu)解指代的是現(xiàn)有已公布的算法求解對(duì)應(yīng)TSP問(wèn)題所獲得的最短路徑長(zhǎng)度；偏差=本研究算法獲得的結(jié)果-已知公布結(jié)果；改進(jìn)率=（本研究算法獲得的最短路徑長(zhǎng)度-已知公布結(jié)果）/已知公布結(jié)果。從表1中可以看出，通過(guò)本文提出的算法求解規(guī)模分別為31和50的TSP問(wèn)題，所得的最優(yōu)解明顯優(yōu)于文獻(xiàn)［1］和［4］給出的最優(yōu)解，證明了本算法的有效性。

本研究運(yùn)行了來(lái)自TSPLIB的多個(gè)實(shí)例。將計(jì)算結(jié)果與標(biāo)準(zhǔn)遺傳算法（SGA）、混合遺傳算法（HGA）（將SGA與2opt結(jié)合的混合算法）進(jìn)行比較。其中HGA和AGA算法的最大迭代次數(shù)設(shè)為500，SGA的最大迭代次數(shù)設(shè)為2000。仿真結(jié)果具體見(jiàn)表2。表中的每個(gè)實(shí)例都是在連續(xù)運(yùn)行10次后得到的統(tǒng)計(jì)結(jié)果。實(shí)例表示的是帶有不同城市數(shù)的TSP具體問(wèn)題；最優(yōu)表示的是目前所獲得的求解所對(duì)應(yīng)具體TSP實(shí)例的最優(yōu)路徑長(zhǎng)度；算法表示的是求解所對(duì)應(yīng)具體實(shí)例問(wèn)題所使用的不同求解方法，最好表示的是不同算法求解對(duì)應(yīng)的TSP實(shí)例問(wèn)題時(shí)得到的最短的路徑長(zhǎng)度；平均表示的是指每種算法針對(duì)某一實(shí)例在10次試驗(yàn)中所得的在規(guī)定的迭代次數(shù)內(nèi)收斂到某一值后不在發(fā)生變化的最短路徑長(zhǎng)度的平均值。從實(shí)驗(yàn)結(jié)果可以看出，AGA算法求得的最好解與TSPLIB提供的最優(yōu)解非常接近，而且求解的平均代數(shù)與其它算法相比要少，均優(yōu)于文獻(xiàn)［1］和［4］所求得結(jié)果。AGA算法確實(shí)能夠有效的提高TSP的求解質(zhì)量和求解速度。

表2 SGA、HGA、AGA算法實(shí)驗(yàn)結(jié)果的比較

5 結(jié) 論

針對(duì)TSP問(wèn)題，提出了一種基于局部搜索機(jī)制的自適應(yīng)遺傳算法。設(shè)計(jì)了局部搜索機(jī)制，在該機(jī)制的指導(dǎo)下，把全局搜索與局部搜索方法自適應(yīng)地結(jié)合，有效減小了算法陷入局部最優(yōu)解的可能，增強(qiáng)了算法的尋優(yōu)能力和速度。實(shí)驗(yàn)結(jié)果表明，該算法是有效的。對(duì)生產(chǎn)調(diào)度、路徑規(guī)劃等排列組合優(yōu)化問(wèn)題具有現(xiàn)實(shí)指導(dǎo)意義。

由于提出的算法在求解小規(guī)模TSP問(wèn)題時(shí)比較有效，而在求解大規(guī)模TSP問(wèn)題時(shí)存在搜索質(zhì)量差和速度慢等缺點(diǎn)，仍需進(jìn)一步改進(jìn)算法的性能加以解決。

［1］彭丹平，林志毅，王江晴.求解TSP的一種改進(jìn)遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42（13）：91-93.

［2］姜昌華，胡幼華.一種求解旅行商問(wèn)題的高效混合遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40（22）：67-70.

［3］楊 輝，康立山，陳毓屏.一種基于構(gòu)建基因庫(kù)求解TSP問(wèn)題的遺傳算法［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26（12）：1753-1758.

［4］Ren S，Wang J，Zhang X J.Research on chaos partheno-genetic algorithm for TSP［C］//Computer Application and System Modeling（ICCASM），2010 International Conference on.IEEE，2010，1：290-293.

［5］Yang W，Hu Y，G K.Parallel search strategies for TSPs using a greedy genetic algorithm［C］//Natural Computation，2007.ICNC 2007.Third International Conference on.IEEE，2007，3：786-790.

［6］Hua F D，Xiao L L，Xue L.An improved genetic algorithm for combinatorial optimization［C］//Computer Science and Automation Engineering（CSAE），2011 IEEE International Conference on.IEEE，2011，1：58-61.

［7］高海昌，馮博琴，朱 利.智能優(yōu)化算法求解TSP問(wèn)題［J］.控制與決策，2006，21（3）：241-247.

［8］王宇平，李英華.求解TSP的量子遺傳算法［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（5）：748-755.

Adaptive Genetic Algorithm Based on Local Search Mechanism Quickly Solving TSP

XIA Kai1，DAI Wen-zhan2
（1.School of Mechanical Engineering and Automation，Zhejiang Sci-Tech University，Hangzhou，310018，China；2.School of Information and Electronic Engineering，Zhejiang Gongshang University，Hangzhou 310018，China）

This paper proposes a genetic algorithm based on local search mechanism quickly solving TSP.Based on local search mechanism，this paper adaptively combines standard genetic algorithm with local heuristic algorithm，so that local heuristic algorithm is allowed to execute only when individual quality is effectively improved，and thus avoid effectively phenomena of local optimum or computational overburden due to excessive number of local search.Simulation results show that this algorithm has a strong global optimization ability，fast convergence speed，and high efficiency in solving TSP.

local search mechanism；adaptive；genetic algorithm；traveling salesman problem

U461；TP308

A

（責(zé)任編輯：康 鋒）

1673-3851（2014）03-0287-05

2013-11-07

國(guó)家自然科學(xué)基金（61374022）；國(guó)家高新技術(shù)研究發(fā)展項(xiàng)目（2009AA04Z139）

夏 凱（1988-），男，浙江富陽(yáng)人，碩士研究生，主要從事智能優(yōu)化與模式識(shí)別等方面的研究。