基于差分進化的離散粒子群算法求解TSP問題

付 聰，沙 偉，張海霞，楊 亞

（河海大學物聯(lián)網(wǎng)工程學院，常州213022）

基于差分進化的離散粒子群算法求解TSP問題

付 聰，沙 偉，張海霞，楊 亞

（河海大學物聯(lián)網(wǎng)工程學院，常州213022）

針對TSP問題，結(jié)合離散粒子群算法和差分進化算法各自的特點，提出了基于差分進化的離散粒子群算法。該算法先利用差分進化算法的變異、選擇算子產(chǎn)生新的群體，再通過離散粒子群算法和交叉及選擇算子進行局部搜索。通過對標準的30個城市進行實驗，實驗結(jié)果表明，該優(yōu)化算法在求解TSP問題上有很好的性能。

優(yōu)化算法；離散粒子群；差分進化；旅行商問題

1 引 言

TSP問題是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復雜問題的集中概括和簡化，是圖論、運籌學和組合優(yōu)化中的NP難問題，常被用于對智能啟發(fā)式算法有效性的驗證。雖然它的數(shù)學描述很簡單，但卻很難精確求出最優(yōu)解，另一方面很多研究領(lǐng)域出現(xiàn)的復雜優(yōu)化問題可以被抽象概括為TSP問題加以求解，因此找到能夠有效解決TSP問題的方法，在理論上和實際應用中都很有價值［1］。

目前求解TSP問題的算法大致可以分兩類：一類是局部啟發(fā)式算法，比如2-opt、3-opt、LK算法等，這類算法的優(yōu)點是尋找最優(yōu)解效率非常高，但是由于過分依賴于問題，容易陷入局部最優(yōu)；另外一類是智能優(yōu)化算法，例如遺傳算法、差分進化算法、蟻群算法、粒子群算法等，這類方法獨立于問題，目前已經(jīng)取得了些階段性的成果，而差分進化算法和粒子群算法都是近年的研究熱點［2］?；谝陨戏治?，提出基于差分進化的離散粒子群算法，并應用到TSP問題中，取得了滿意的效果。

2 離散粒子群算法和差分進化算法

2.1 離散粒子群優(yōu)化算法

Eberhart和Kennedy于1995年提出粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）［3］，該算法簡單易實現(xiàn)且可調(diào)參數(shù)少。PSO算法最初被應用于連續(xù)空間的優(yōu)化，研究也主要集中在連續(xù)函數(shù)方面，即其速度、加速度等狀態(tài)都是連續(xù)的，它們的運算法則也是連續(xù)量的運算。然而，許多實際工程應用問題是離散的，變量是有限的，需要將基本PSO算法在二進制空間進行擴展。早在1997年，Kennedy和Eberhart就提出了PSO算法的離散二進制版［4］。在求解TSP問題方面，高尚，韓斌等［5］結(jié)合遺傳算法、蟻群算法和模擬退火算法的思想，提出了一種混合粒子算法用于求解TSP問題，其中還討論了多種交叉策略和變異策略。Clerc給出一種求解TSP問題的DPSO算法（TSP-DPSO）［6］，等等。

在TSP-DPSO算法中，粒子的位置用所有城市的一個排列來表示，則所有排列就構(gòu)成了粒子的搜索空間。該算法引入了交換子和交換序列的概念，一個交換子S＝Swap（i，j）是指交換粒子第i個和第j元素的位置，一個交換子集則是指一組以特定順序排列的交換子。粒子的速度則是指粒子為達到最優(yōu)解而需要對當前位置執(zhí)行的基本交換序?；诖烁拍?，TSP-DPSO算法對粒子群中的加減法等操作算子進行了重新定義，其更新公式如下：

其中：粒子的位置和速度分別為Xt和Vt，均由0和1組成，c1、c2和c3是隨機生成的學習因子；Pi，t和Pg，t則是粒子局部最優(yōu)和全局最優(yōu)值。這里，速度與隨機數(shù)的數(shù)乘表示依隨機數(shù)概率保留原速度中的交換子，算子⊕為粒子速度間的異或操作。

該算法通過對粒子位置和速度矢量的操作，實現(xiàn)了連續(xù)粒子群向離散空間的映射。但實驗結(jié)果表明，在解決TSP問題時該算法并非最優(yōu)算法。

2.2 差分進化算法

差分進化算法（Differential Evolution，DE）是一種新興的進化計算技術(shù)，它是由Storn等人于1995年提出的［7］，最初的設(shè)想是用于解決切比雪夫多項式問題，后來發(fā)現(xiàn)DE也是解決復雜優(yōu)化問題的有效技術(shù)。

DE算法是一種隨機的并行直接搜索算法，有3種運算貫穿著整個算法的執(zhí)行過程：變異、交叉和選擇。算法首先利用在搜索空間內(nèi)隨機選取兩個向量的差值與第3個隨機選取向量的加權(quán)求和來實現(xiàn)群體變異，然后通過比較由交叉算子生成的個體和相應父代個體的適應值優(yōu)劣來保存優(yōu)秀個體，如此反復迭代，不斷進化，向最優(yōu)解逼近［8］。整個運行過程中群體的規(guī)模保持不變。3種操作描述如下：

（1）變異

對于個體xi（t），根據(jù)下面公式生成變異個體：

其中：xr1，xr2，xr3為從進化群體中隨機選取的互不相同的3個個體，并且i和r1、r2、r3之間必須是不同的。因此，一個群體中個體的數(shù)量必須多于4個。F為縮放比例因子，用于控制差向量的影響大小。

（2）交叉

為了增加群體的多樣性，交叉操作被引入差分進化算法。將個體xi（t）和變異個體進行二項分布雜交生成雜交個體。

操作公式如下：

其中：D為解空間維數(shù)，CR∈［0，1］，為交叉概率，Pc是［0，l］之間的隨機數(shù)。

（3）選擇

在基本差分進化算法中，選擇操作采取貪婪策略，即只有當產(chǎn)生的子代個體優(yōu)于父代個體時（對應目標函數(shù)值f（xi（t＋1））≤f（ti（t）））才被保留，否則父代個體被保留至下一代。

3 基于差分進化的離散粒子群優(yōu)化算法

為了改善DPSO的全局搜索性能，改進算法應考慮以下兩個方面：迭代初始階段在保證一定收斂速度的同時應盡量避免粒子“早熟”，引導粒子探索新的區(qū)域并盡可能讓粒子足跡遍歷整個解空間；搜索后期當算法達到一定收斂精度時，若粒子陷入局部最優(yōu)則通過更換粒子或重新調(diào)整算法參數(shù)引導粒子逃離局部最優(yōu)區(qū)，以進一步提高DPSO的收斂精度［9］。

相比于其他進化算法，DE算法的變異算子有利于增加全局搜索能力，保證種群的多樣性；交叉算子可以提高局部搜索能力，加快收斂速度；選擇算子具有一定的記憶能力，能夠保留優(yōu)秀個體［10］。

基于前文對DPSO和DE算法特點分析，提出基于差分進化的離散粒子群優(yōu)化算法（簡稱DEDPSO），在離散粒子群優(yōu)化算法中引入差分進化算法，作為種群信息更新方式，將DE全局信息收集機制與DPSO尋優(yōu)搜索機制相結(jié)合。

DEDPSO算法的具體步驟總結(jié)如下：

（1）在搜索空間內(nèi)，初始化群體的位置和速度，以及粒子群種群規(guī)模和最大迭代次數(shù)等參數(shù)；

（2）變異和選擇，根據(jù)公式（3）更新群體的位置，并更新群體最優(yōu)點；

（3）根據(jù)公式（1）（2）更新群體的位置和速度；

（4）根據(jù)公式（4）對位置進行交叉和選擇；

（5）滿足結(jié)束條件或達到最大迭代次數(shù)，則輸出結(jié)果，否則轉(zhuǎn)至步驟（2）。

4 基于差分進化的離散粒子群算法求解TSP問題

文中提出了基于差分進化的離散粒子群算法求解TSP問題。以標準的30個城市進行試驗，初始粒子種群大小為200。表1為基于差分進化的離散粒子群算法求解TSP問題的運算結(jié)果，600、1000和1500是程序運行的代數(shù)，Average為10組數(shù)據(jù)的平均值，N為10次搜索，搜索到最優(yōu)值的次數(shù)，初始種群大小同樣設(shè)置為200，縮放比例大小設(shè)為0.1，交叉概率大小設(shè)置為0.6，還是采用標準的30個城市，它的最優(yōu)值為423.74。

表1 基于差分進化的離散粒子群算法效果表

兩種算法分別連續(xù)運行10組，運行600次后，DEDPSO的10組數(shù)據(jù)平均值比DPSO的10組數(shù)據(jù)平均值明顯要小。此時雖然DEDPSO搜索到全局最優(yōu)值的次數(shù)還較少，但是搜索結(jié)果已經(jīng)很接近全局最優(yōu)值。運行1000次后，可以看出此時10組1000次DEDPSO搜索結(jié)果平均值更加接近全局最優(yōu)值，并且10次搜索結(jié)果中有6次搜索到了全局最優(yōu)值。當運算代數(shù)達到1500時，10次搜索有8次搜索到最優(yōu)值，也就是基本每次都能搜索到最優(yōu)值。

基于上述分析，可以知道基于差分進化的離散粒子群算法在相同的運行次數(shù)內(nèi)提高了優(yōu)化質(zhì)量，在城市數(shù)目較少的情況下，更加容易搜索到TSP問題的最優(yōu)值。

表2 DPSO多粒子群運算效果表

表3 DEDPSO多粒子群運算效果表

鑒于單純的DPSO算法求解TSP問題容易陷入局部極值，而加入差分進化算法后，DPSO算法求解TSP問題的求解速度加快和求解質(zhì)量提高，但是也不代表就得到了全局極值，本文還設(shè)置了多個粒子群進行并行搜索，提高了搜索到最優(yōu)值的可能性。

設(shè)置了四個子種群進行并行搜索，四個子種群運行次數(shù)相同，分別為總運行次數(shù)的四分之一，且初始種群為200，縮放比例為0.1，交叉概率為0.6，同樣還是采用標準的30個城市。依次運行2400次，3200次，4000次，對應的每個子種群也就是運行600次，800次，1000次，同時也分別運行基本的DPSO算法求解TSP問題2400次，3200次，4000次。得到的數(shù)據(jù)分別記錄下來，表2為多粒子群DPSO算法運算效果表，表3為多粒子群DEDPSO算法運算效果表。表2和表3中P為每十次運行得到最優(yōu)值的概率，Average為十次運行的平均值，E為平均值與最優(yōu)值相比所存在的誤差。

對比分析表2和表3：搜索次數(shù)均在2400次以上。運行2400次時，P等于20%，即每次有20%的可能性搜索到最優(yōu)結(jié)果。運行3200次P等于40%。運行4000次P等于20%?？梢钥闯鲭S著程序運行次數(shù)的增加，基本的DPSO算法求解TSP問題尋優(yōu)能力沒什么突破，并且很不穩(wěn)定，陷入局部極值的可能性很大。表3中的搜索次數(shù)也是2400次以上，即單個子種群運行次數(shù)在600次以上。運行2400次時，P等于80%，運行2600次時，P等于90%，運行4000次時，P等于90%，即運行次數(shù)在3200次以上，基本每次都能搜索到最優(yōu)值。

這種基于差分進化的離散粒子群算法求解TSP問題充分利用了變異算子和交叉算子可以加快收斂速度的優(yōu)勢，提高了算法的整體尋優(yōu)能力。

5 結(jié)束語

基于差分進化的離散粒子群算法的應用前景：文中提出的這種算法已經(jīng)成功應用到了求解TSP問題上，并取得了較好結(jié)果；這種算法也可以應用到更大規(guī)模的TSP問題上以及類似的各種求解TSP問題的方法中，具體應用方式和對相應算法的改進有待進一步研究。

［1］王東，吳湘濱，毛先成，等.一種改進的求解TSP混合粒子群優(yōu)化算法［J］.計算機工程，2008，34（6）：185-187.

［2］鄧偉林，胡桂武.一種求旅行商問題的離散粒子群算法［J］.計算機與現(xiàn)代化，2012（3）：1-4.

［3］Eberhart R C，Kennedy J.A new optimizer using particles swarm theory［C］.Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Nagoya：IEEE Inc，1995：39-43.

［4］Kennedy J，Eberhart R.A discrete binary version of the particle swarm algorithm.Proceedings of the World Multi-conference on Systemics［J］.Cybernetics and Informatics.Piscataway，NJ：IEEE Service Center，1997，4104-4109.

［5］高尚，韓斌，吳小俊，等.求解旅行商問題的混合粒子群優(yōu)化算法［J］.控制與決策，2004，19（11）：1286-1289.

［6］Clerc M.Discrete particle swarm optimization-illustrated by the traveling salesman problem［EB／OL］.2000-02-29.http：／／clerc.maurice.free.fr／pso／pso_tsp／Discrete_ PSO_TSP.htm.

［7］Storn R，Price K.Differential evolution-A simple and efficient adaptive scheme for global optimization over continuous space［R］.International Computer Science Institute，Berkley，1995.

［8］楊妍，陳如清，俞金壽.差分進化粒子群混合優(yōu)化算法的研究與應用［J］.計算機工程與應用，2010，46（25）：238-241.

［9］池元成，方杰，蔡國飆.基于差分進化和粒子群優(yōu)化算法的混合優(yōu)化算法［J］.計算機工程與設(shè)計，2009，30（12）：2963-2965.

［10］楊啟文，蔡亮，薛云燦.差分進化算法綜述［J］.模式識別與人工智能，2008，21（4）：506-513.

Discrete Particle Swarm Optim ization Algorithm Based on Differential Evolution for TSP

FU Cong，SHAWei，ZHANG Hai-xia，YANG Ya
（College of Internet of Things Engineering，Hohai University，Changzhou 213022，China）

Combining with the advantage of discrete particle swarm optimization（DPSO）and differential evolution（DE），a discrete particle swarm optimization algorithm based on differential evolution（DEDPSO）is proposed for solving traveling salesman problem（TSP）.There are two steps，one is employing the differentialmutation and selection operators to produce a new population for effective variation，and the other is carrying out DPSO for local exploration by crossover and selection operations.In this paper，some cases from TSPLIB are tested，and the experiment results show that DEDPSO has good performance for solving TSP.

Optimization algorithm；Discrete particle swarm；Differential evolution；Traveling salesman problem

10.3969／j.issn.1002-2279.2014.03.009

TP301.6

：A

：1002-2279（2014）03-0030-03

付聰（1990-），男，江蘇省鹽城市人，碩士研究生，主研方向：智能優(yōu)化與控制。

2014-03-03