基于漢明距離的改進粒子群算法求解旅行商問題

喬 屾,呂志民,張 楠

(1.北京科技大學 工程技術研究院,北京 100083; 2.北京科技大學 鋼鐵共性技術協(xié)同創(chuàng)新中心,北京,100083) (*通信作者電子郵箱xiaoqiao_0412@126.com)

基于漢明距離的改進粒子群算法求解旅行商問題

喬 屾1*,呂志民2,張 楠1

(1.北京科技大學 工程技術研究院,北京 100083; 2.北京科技大學 鋼鐵共性技術協(xié)同創(chuàng)新中心,北京,100083) (*通信作者電子郵箱xiaoqiao_0412@126.com)

針對傳統(tǒng)粒子群算法不適合求解離散型問題，提出一種基于漢明距離的改進粒子群算法。該算法保留了粒子群算法的基本思想和流程，并基于漢明距離為粒子定義了一種新型的速度表示。同時，為了使算法尋優(yōu)能力更高、避免迭代過程陷入局部最優(yōu)無法跳出，設計了2-opt和3-opt算子，結合隨機貪婪規(guī)則，使求解質量更高、收斂更快。在算法后期，為了提高粒子在整體解空間中的全局搜索能力，采用一部分粒子重新生成的方式去重新探索解空間。為了驗證算法的有效性，采用了眾多旅行商問題(TSP)標準算例進行測試。實驗結果表明，對于小規(guī)模TSP，該算法可以找到歷史最優(yōu)解；對于大規(guī)模TSP，如城市數(shù)在100以上的問題，也可以找到滿意解，與已知最優(yōu)解之間偏差度較小，通常在5%以內(nèi)。

粒子群優(yōu)化算法;漢明距離;隨機貪婪規(guī)則;2-opt算子;3-opt算子;旅行商問題

0 引言

旅行商問題(Traveling Salesman Problem,TSP)是一個經(jīng)典的組合優(yōu)化問題。隨著城市節(jié)點數(shù)的增加,該問題不可能使用窮舉方式找到最優(yōu)解,是著名的NP-Hard問題。計算智能的發(fā)展對該問題的求解提供了很多優(yōu)化算法,如遺傳算法(Genetic Algorithm,GA)[1]、蟻群優(yōu)化(Ant Colony Optimization, ACO)算法[2]、文化基因算法(Memetic Algorithm, MA)[3]、模擬退火(Simulated Annealing, SA)算法[4]等。

粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法自提出以來,在函數(shù)優(yōu)化問題上取得了極其良好的效果。同遺傳算法對比,粒子群優(yōu)化算法收斂更快,結果更優(yōu),因此受到眾多研究者關注。盡管如此,在求解離散問題,如旅行商問題(TSP)上,粒子群優(yōu)化算法中的速度概念,不能直接地應用在問題模型中,需要對算法進行一定改進才能適合求解。

目前國內(nèi)外諸多學者研究了如何將該算法與其他算法結合以求解TSP。Mahi等[5]將蟻群算法和粒子群算法結合,利用信息素信息對粒子間位置進行更新；Chen等[6]提出了模擬退火蟻群系統(tǒng)粒子群算法,該算法除了用信息素來處理粒子間信息傳遞,還用了遺傳算法進行種群迭代,并利用模擬退火算法增強尋優(yōu)質量；易云飛等[7]利用蟻群算法的信息素為兩城市間的距離賦予權重,并基于伊藤隨機過程定義了漂移算子和波動算子,用以改進粒子群算法中的學習因子。除了和其他算法相結合使用,一些研究者將標準粒子群算法中概念加以改進,以適應離散問題求解；Clerc[8]提出了離散PSO(Discrete PSO, DPSO)算法,將城市序列定義為粒子的位置,將城市的交換序定義為粒子的速度,并為粒子間的飛行運動定義了運算規(guī)則,成功解決了TSP中粒子的更新方式；謝旻[9]將粒子群算法和遺傳算法結合,同時引入克隆免疫機制,從而設計了克隆算子、交叉算子、自適應變異算子和抗體重組算子來解決粒子間的更新。從已有研究來看,利用交換子與交換序概念的粒子速度與位置定義方式,或與其他算法相結合的新式定義算子,在一定程度上提高了算法的求解質量,但同時也引入了更多的概念或參數(shù),使算法本身復雜化。本文提出了一種基于漢明距離的改進的隨機貪婪PSO(Improved Random Greedy PSO Based on Hamming Distance, IMRGHPSO)算法,該算法通過引入漢明距離的概念定義了TSP中粒子間位置與速度的更新。同時設計了2-opt和3-opt算子,引入粒子重生機制,進一步提高了算法的尋優(yōu)能力。

1 TSP的其數(shù)學模型

TSP的數(shù)學描述:給定n個城市的坐標點或城市間的距離矩陣,從某點出發(fā),遍歷所有城市點,每個城市只經(jīng)過一次,最終回到出發(fā)城市點,求如何選擇路徑使所走過的總路程最短。若對于城市集合V={V1,V2,…,Vn},則一條路徑可表示為有序序列C=C1C2…Ci…Cn,其中Ci∈V(i=1,2,…,n)。令兩城市間距離為d(Ci,Ci+1),TSP的目標即為:

(1)

2 基于漢明距離的改進粒子群算法

2.1 標準粒子群算法

在粒子群算法中,首先產(chǎn)生一定規(guī)模的粒子作為問題搜索空間的有效解,然后通過一定次數(shù)迭代,得到優(yōu)化結果。和鳥群中的小鳥一樣,每一個粒子都具有速度和位置,迭代過程中,由每個粒子本身的歷史最優(yōu)解和群體全局歷史最優(yōu)解來改變粒子的飛行速度和下一個位置,讓粒子在解空間中探索和開發(fā),最終得到問題的最優(yōu)結果。

用N維向量來表示粒子的位置,設群體中有m個粒子,則第i個粒子的位置可表示為Xi=(Xi1,Xi2,…,XiN),粒子速度為Vi=(Vi1,Vi2,…,ViN),其中i=1,2,…,m。每個粒子的歷史最優(yōu)位置記為pi=(pi1,pi2,…,piN)。整個群體的歷史最優(yōu)位置記為pg=(pg1,pg2,…,pgN)。每一次迭代過程,粒子需要更新狀態(tài)。其中,粒子速度和位置更新公式為:

(2)

(3)

粒子群算法基本流程如圖1所示。

圖1 標準PSO流程

2.2 漢明距離

在信息學中,兩個等長的字符串之間,對應位置上不同的字符的個數(shù)即稱為漢明距離,也稱為海明距離。換言之,將一個字符串變換成另一個字符串所需的字符個數(shù)即為兩個字符串的漢明距離。如兩個二進制串:a=[0 1 0 0 0 1],b=[1 0 0 0 1 1],a與b第一、二、五位不同,即漢明距離為3。

漢明距離已經(jīng)運用在各類問題上,如：Rai等[10]將支持向量機和漢明距離相結合運用于虹膜識別系統(tǒng),取得了相當高的識別率；Osaba等[11]在利用蝙蝠算法求解TSP時,引入漢明距離的概念,改進了該算法中對蝙蝠速度的定義,在與其他算法的比較后證明改進后的算法求解效果令人滿意。

在TSP中,每一個解是長度為N的一維數(shù)組,不同解之間特征為長度相同,相對應位置的節(jié)點部分不同。以8個城市的TSP為例,設t時刻有兩個可行解:

則兩個解之間的漢明距離為4。由于TSP的解是一條閉合回路,因此不相同的兩個解有可能代表的是同一個路徑,如路徑[1 3 4 6 2 5 8 7]和[4 6 2 5 8 7 1 3],這兩個解所有對應位城市節(jié)點編碼均不相同,但是所代表的路徑完全相同。因此,在運用漢明距離概念比較TSP的解時,需要對解進行一定處理,將相比較的兩個解的起始節(jié)點調整為相同節(jié)點后,再進行漢明距離計算。

(4)

(5)

速度上限為兩粒子間漢明距離,在此本文算法并未設置其上限為一個更小的數(shù)值,目的是為了使粒子在飛行過程中產(chǎn)生差異化,從而確保群體的搜索能力。

2.3 基于隨機貪婪規(guī)則的2-opt和3-opt算子

在求解TSP的局部路徑優(yōu)化方面,2-opt[12-14]與3-opt[15-17]是常用的兩種優(yōu)化算子,通過對TSP路徑中邊的調整以獲得問題一個解的鄰域解。在2-opt中,刪除不相鄰的兩條邊,并重新生成兩條邊,如圖2所示。

圖2 2-opt算子

圖2中,刪除d(B,G)和d(F,C),重新生成d(B,C)和d(F,G),若d(B,G)+d(F,C)gt;d(B,C)+d(F,G),則該2-opt調整后尋得解更優(yōu)。2-opt的合理運用,可以大幅縮減一個解的路徑總長,達到更好的尋優(yōu)。這種局部尋優(yōu)在算法前期效果極佳,當結果收斂到一定程度時,合適的2-opt調整邊已經(jīng)不容易找到,因此該算子不適用于算法后期，而適合用在初試解的優(yōu)化和每一次迭代之后,所有粒子進行鄰域的搜尋。相比之下,在算法后期,3-opt的調整則更為有效。在路徑中連接某點Xi相鄰的兩條邊,將其刪除,并將Xi-1和Xi+1相連,在路徑中另外兩個相鄰點Xj和Xj+1之間插入Xi,此時需重新生成兩條邊d(Xj-1,Xi)和d(Xi,Xj+1),實現(xiàn)三條邊的調整,如圖3所示。

圖3 3-opt算子

圖3中,刪除d(A,B),d(B,C)和d(E,F),重新生成d(A,C),d(E,B)以及d(B,F),若能夠找到合適的點B,使得d(A,B)+d(B,C)+d(E,F)gt;d(A,C)+d(E,B)+d(B,F),則該3-opt實現(xiàn)了鄰域搜索到更優(yōu)解。在算法前期,該算子可用來使粒子在自己的鄰域內(nèi)探索需求新的路徑;在算法后期,可使粒子試圖跳出局部最優(yōu)。

2-opt和3-opt算子的提出,改善了算法中粒子搜索能力。無論是哪一種算子,對于隨機取點這種方式,采用后的結果都并不能保證一定會向著更優(yōu)的方向前進。因此,需要采用一種規(guī)則,來判斷哪些點或者哪些邊需要進行操作,確保粒子的局部搜索向著算法所希望的結果飛行。

對于城市節(jié)點Xi,可以根據(jù)TSP的城市數(shù)據(jù)獲得n個城市的距離矩陣dn*n。矩陣中第i行數(shù)據(jù)代表從城市Xi到其他各城市的距離。通常來講,從某點出發(fā)到距離該點最近的點,或較近的點,通常是一個優(yōu)質解的路徑片段。因此,可以通過距離矩陣,使一個解中的城市節(jié)點,盡量去選擇較近的其他節(jié)點。

貪婪算法,又稱貪心算法(Greedy Algorithm),常常用在各類優(yōu)化問題當中[18-19]。它是指在求解一個問題時,每一步總是作出當前最好的選擇。以TSP為例,由于各城市間距離已知,則從一個城市出發(fā),每一次總是選擇最近城市。該算法可獲得一個可行解,該解通常不是最優(yōu)解,但極有可能是一個較優(yōu)解,比隨機生成的解優(yōu)秀很多。在求解大規(guī)模TSP局部優(yōu)化時,借鑒“貪婪”的思想,可以使一個粒子中某節(jié)點去連接最近幾個點中的一個,稱之為隨機貪婪規(guī)則。運用該規(guī)則可以使一個解有很大概率尋求更優(yōu)的結果,是跳出局部最優(yōu)的有效方式[20]。

該規(guī)則最有效的使用是在3-opt算子當中。在求解一個TSP中,設置一個隨機貪婪因子g,如g=3,即在運用3-opt算則時,若某城市節(jié)點V的下一個鄰接節(jié)點,不是距離自身最近的三個城市節(jié)點,則隨機選擇三個城市中的一個,插入到V的緊后節(jié)點位置。通過大量的實現(xiàn)驗證,在城市數(shù)Nlt;50的情況下,屬于小規(guī)模問題,隨機貪婪因子g取2或3;當城市數(shù)Ngt;50時,取[2,5]內(nèi)的整數(shù)。

2.4 改進粒子搜索能力

根據(jù)粒子群算法基本原理,所有粒子會受到最優(yōu)粒子的吸引,因此,該算法在一定時間時會陷入局部最優(yōu)。若最優(yōu)粒子無法在短時間內(nèi)尋得更優(yōu)的位置,跳出早熟狀態(tài),其他粒子會逐漸聚攏在局部最優(yōu)位置。

在2.3節(jié)已經(jīng)為最優(yōu)粒子設計了局部尋優(yōu)的方式。當其他粒子接近最優(yōu)粒子時,可以停止受最優(yōu)粒子吸引,轉而和最優(yōu)粒子一樣以2-opt或3-opt方式做局部尋優(yōu)。但該方式的解搜索空間已經(jīng)被壓縮,非最優(yōu)粒子的局部搜索空間依然和最優(yōu)粒子搜索空間極其接近,或者已經(jīng)屬于一個局部空間內(nèi),而最優(yōu)解所在局部很可能與該局部距離較遠,使得陷入局部最優(yōu)的粒子即使多次進行鄰域搜索也無法搜索到最優(yōu)解所在局部空間。本文算法為最優(yōu)粒子設計的3-opt搜索已經(jīng)足夠讓最優(yōu)粒子具備較強的局部尋優(yōu)能力,因此相比之下,那些已經(jīng)接近最優(yōu)粒子的普通粒子,其局部搜索已經(jīng)意義不大。

于是,將算法進一步改進,當其他粒子距離最優(yōu)粒子極為接近時,將消滅該粒子,轉而重新生成新粒子。新生粒子雖然距離最優(yōu)解較遠,但是由于群里空間再次被擴大,且新生粒子與當前最優(yōu)粒子的漢明距離非常遠,將會獲得較不穩(wěn)定的飛行速度。這種不穩(wěn)定的速度賦予了粒子群在整體解空間中更強大的搜索能力,很有可能搜索到之前未到達的局部解鄰域,為群體搜索到新的解奠定了基礎。

2.5 本文IMRGHPSO算法流程

本文提出的IMRGHPSO算法流程如下:

Step1 初試化城市距離矩陣dn*n(n為城市數(shù)),設置基本參數(shù):種群數(shù)M;最大迭代次數(shù)T。

Step2 初始化種群,對種群中的個體以隨機貪婪規(guī)則進行2-opt優(yōu)化,優(yōu)化次數(shù)選取n/10。

Step3 評估粒子,獲得群體最優(yōu)值。

Step4 計算粒子和最優(yōu)粒子之間的漢明距離,并通過式(4)計算粒子速度。

Step5 根據(jù)速度判斷粒子是否接近最優(yōu)粒子,若接近則消滅粒子并根據(jù)Step2中方式重生；否則粒子通過速度更新各自的位置,最優(yōu)粒子通過隨機貪婪規(guī)則進行3-opt優(yōu)化。

Step6 所有粒子通過隨機貪婪規(guī)則進行3-opt優(yōu)化。

Step7 評估粒子,獲得群體最優(yōu)值。

Step8 判斷是否達到結束條件,若達到則算法結束,若未達到則返回Step4。

圖4 IMRGHPSO算法流程

3 實驗與結果分析

為了驗證算法的效果,選取了標準數(shù)據(jù)庫TSPLIB中一系列數(shù)據(jù)對本文算法進行驗證,并在處理器為Intel Core i5- 5200U 2.20 GHz內(nèi)存8 GB的計算機上,使用Matlab進行仿真實驗。

表2 HPSO、RGSPSO、IMRGHPSO算法求解TSP結果對比

各標準算例的測試基本參數(shù)如表1所示。

在算例Burma14中,由于規(guī)模較小,問題較為簡單,并未使用隨機貪婪規(guī)則,同樣在算例Oliver30中,也屬于較小規(guī)模問題,隨機貪婪因子為2,即在使用隨機貪婪規(guī)則時,只考慮最近的兩個城市節(jié)點。

為了說明算法的效果,本文對比了基于漢明距離的粒子群算法HPSO,在HPSO基礎上加入貪婪隨機規(guī)則的RGHPSO,以及本文提出的IMRGHPSO。表2為三種算法的結果對比。

表1 算法參數(shù)

從表2可以看出,在小規(guī)模算例中,HPSO已經(jīng)可以找到最優(yōu)解,充分證明基于漢明距離的粒子群算法HPSO是可行的。在中小規(guī)模的算例(30lt;Nlt;100)中,IMRGHPSO算法已經(jīng)能夠獲得非常優(yōu)質的解和最優(yōu)解的偏離度lt;1%;在大規(guī)模城市數(shù)TSP算例(N≥100)中,IMRGHPSO算法在尋找解的質量上有待提高,偏離度一般能小于5%。在城市數(shù)gt;30的算例結果中可以看出,隨機貪婪規(guī)則的引入對于算法性能是有提高的,隨著城市數(shù)增加而愈發(fā)明顯。增加粒子重生的改進算法,還可以進一步提高算法尋優(yōu)的能力。

通常來講,一種對于算法的改進,會令算法找到的最優(yōu)值以及群體平均值都向著更優(yōu)的方向逼近。而對于優(yōu)化問題,以粒子群算法求解TSP為例,最優(yōu)的個體才代表該算法的結果,平均值只是對于群體而言。本文所提出的IMRGHPSO算法在迭代中由于不斷有新粒子重生加入,并未使群體平均值下降,但正是這一特點,使得算法可以在解空間尋得更好的結果。

圖5為RGHPSO與IMRGHPSO在求解算例Ch130時的收斂曲線。從圖5可以看出,RGHPSO算法的平均值呈現(xiàn)波動狀,這是由于粒子會進行鄰域搜索而導致。IMRGHPSO由于粒子會不斷有重生者加入,其平均值則呈大幅震蕩情況,證明群體在平均值曲線的波峰時差異性很大。從之前給出的結果可以看出,這種較大的差異性對于該算法的尋優(yōu)能力具有較大幫助。

圖6是本文中測試的大規(guī)模算例得出的最優(yōu)路徑圖。從圖6(a)可以看出,盡管和已知最優(yōu)解之間存在偏差,局部路徑可以進一步優(yōu)化,但本文算法已經(jīng)可以求解部分大規(guī)模TSP,其精度有待進一步提高。

圖5 Ch130收斂曲線

圖6 最優(yōu)路徑圖

4 結語

本文提出了基于漢明距離的改進粒子群算法,通過定義離散型速度與位置表達式,使得改進后的粒子群算法更適用于求解TSP。針對算法在后期易陷入早熟的特點,本文設計了2-opt和3-opt算子用于局部搜索,并讓陷入局部最優(yōu)的粒子重生以使群體再次獲得較大空間搜索新的鄰域。通過標準TSP算例的求解,實驗結果表明本文提出的IMRGHPSO算法是有效的。在未來的研究工作中,該算法在以下方面需進一步提高改進：一是對于TSP問題，本文所提出的漢明距離計算方式存在缺陷，兩個解之間相應位置的不同只代表編碼的差異，而非兩條TSP問題路徑的差異,未來將考慮為TSP漢明距離的計算提出更合理的計算方式；二是算法在求解大規(guī)模TSP上精度有待提高,局部搜索算子需要設計更有效的搜索機制。

References)

[1] WANG Y. The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem [J]. Computers amp; Industrial Engineering, 2014, 70(2): 124-133.

[2] ARIYASINGHA I D I D, FERNANDO T G I. Performance analysis of the multi-objective ant colony optimization algorithms for the traveling salesman problem [J]. Swarm and Evolutionary Computation, 2015, 23: 11-26.

[3] WANG Y, CHEN Y, LIN Y. Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem [J]. Computers amp; Industrial Engineering, 2016, 106: 105-122.

[4] LIN Y, BIAN Z, LIU X. Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing tabu search algorithm to solve the symmetrical traveling salesman problem [J]. Applied Soft Computing, 2016, 49 (C): 937-952.

[5] MAHI M, BAYKAN ? K, KODAZ H. A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem [J]. Applied Soft Computing, 2015, 30 (C): 484-490.

[6] CHEN S M, CHIEN C Y. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques [J]. Expert Systems with Applications, 2011, 38(12): 14439-14450.

[7] 易云飛, 林曉東, 蔡永樂. 求解旅行商問題的改進粒子群算法[J]. 計算機工程與設計, 2016, 37(8): 2195-2199, 2223. (YI Y F, LIN X D, CAI Y L. Improved particle swarm optimization algorithm for solving traveling salesman problem [J]. Computer Engineering and Design, 2016, 37(8): 2195-2199, 2223.)

[8] CLERC M. Discrete particle swarm optimization, illustrated by the traveling salesman problem [M]// ONWUBOLU P G C, BABU P B V. New Optimization Techniques in Engineering. Berlin: Springer, 2004: 219-239.

[9] 謝旻. 一種混合粒子群優(yōu)化算法在TSP中的應用[J]. 太原理工大學學報, 2013, 44(4): 506-509, 513. (XIE M. An improved hybrid particle swarm optimization algorithm for TSP [J]. Journal of Taiyuan University of Technology, 2013, 44(4): 506-509, 513.)

[10] RAI H, YADAV A. Iris recognition using combined support vector machine and Hamming distance approach [J]. Expert Systems with Applications, 2014, 41(2): 588-593.

[11] OSABA E, YANG X S, DIAZ F, et al. An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems [J]. Engineering Applications of Artificial Intelligence, 2016, 48 (C): 59-71.

[12] LOZANO L, SMITH J C, KURZ M E. Solving the traveling salesman problem with interdiction and fortification [J]. Operations Research Letters, 2017, 45(3): 210-216.

[13] WANG Y, CHEN Y, LIN Y. Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem [J]. Computers amp; Industrial Engineering, 2016, 106: 105-122.

[14] 韓偉, 張子成. 求解旅行商問題的離散型貝殼漫步優(yōu)化算法[J]. 模式識別與人工智能, 2016, 29(7): 650-657. (HAN W, ZHANG Z C. Discrete mussels wandering optimization algorithm for solving traveling salesman problem [J]. Pattern Recognition and Artificial Intelligence, 2016, 29(7): 650-657.)

[15] ZHOU Y, LUO Q, CHEN H, et al. A discrete invasive weed optimization algorithm for solving traveling salesman problem [J]. Neurocomputing, 2015, 151(3): 1227-1236.

[16] 王勇臻, 陳燕, 張金松. 用于求解旅行商問題的多策略離散型和聲搜索算法[J]. 華南理工大學學報 (自然科學版), 2016, 44(1): 131-138. (WANG Y Z, CHEN Y, ZHANG J S. Multi-strategy discrete harmony search algorithm for solving traveling salesman problem [J]. Journal of South China University of Technology (Natural Science Edition), 2016, 44(1): 131-138.)

[17] 程畢蕓, 魯海燕, 黃洋, 等. 求解TSP的自適應優(yōu)秀系數(shù)粒子群優(yōu)化算法[J]. 計算機應用, 2017, 37(3): 750-754, 781. (CHENG B Y, LU H Y, HUANG Y, et al. Particle swarm optimization algorithm based on self-adaptive excellence coefficients for solving traveling salesman problem [J]. Journal of Computer Applications, 2017, 37(3): 750-754, 781.)

[18] 童俊華, 蔣煥煜, 武傳宇. 基于貪心算法的溫室缽苗稀植移栽路徑優(yōu)化[J]. 農(nóng)業(yè)機械學報, 2016, 47(3): 8-13. (TONG J H, JIANG H Y, WU C Y. Optimization of seedlings lower density transplanting path based on greedy algorithm [J]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(3): 8-13.)

[19] 鄧曉衡, 曹德娟, 潘琰, 等. 一種基于時延約束的社會網(wǎng)絡信用分布優(yōu)化模型[J]. 計算機研究與發(fā)展, 2017, 54(2): 382-393. (DENG X H, CAO D J, PAN Y, et al. An optimized credit distribution model in social networks with time-delay constraint [J]. Journal of Computer Research and Development, 2017, 54(2): 382-393.)

[20] MARINAKIS Y, MARINAKI M. A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem [J]. Computers amp; Operations Research, 2010, 37(3): 432-442.

ImprovedparticleswarmoptimizationalgorithmbasedonHammingdistancefortravelingsalesmanproblem

QIAO Shen1*,LYU Zhimin2,ZHANG Nan1

(1.InstituteofEngineeringTechnology,UniversityofScienceandTechnologyBeijing,Beijing100083,China;2.CollaborativeInnovationCenterofSteelTechnology,UniversityofScienceandTechnologyBeijing,Beijing100083,China)

An improved Particle Swarm Optimization (PSO) algorithm based on Hamming distance was proposed to solve the discrete problems. The basic idea and process of traditional PSO was retained, and a new speed representation based on Hamming distance was defined. Meanwhile, in order to make the algorithm be more efficient and avoid the iterative process falling into the local optimum, new operators named 2-opt and 3-opt were designed, and the random greedy rule was also used to improve the quality of the solution and speed up the convergence. At the later period of the algorithm, in order to increase the global search ability of the particles in the whole solution space, a part of particles was regenerated to re-explore the solution space. Finally, a number of TSP standard examples were used to verify the effectiveness of the proposed algorithm. The experimental results show that the proposed algorithm can find the historical optimal solution for small scale TSP; for large-scale TSP, for example, the city number is more than 100, satisfactory solutions can also be found, and the deviations between the known and the optimal solutions are small, usually within 5%.

Particle Swarm Optimization (PSO) algorithm; Hamming distance; random greedy rule; 2-opt operator; 3-opt operator; Traveling Salesman Problem (TSP)

2017- 05- 11;

2017- 08- 01。

國家自然科學基金資助項目(51274043)。

喬屾(1985—),男,河北保定人,碩士研究生,主要研究方向:智能算法、生產(chǎn)計劃與調度; 呂志民(1971—),男,河北邯鄲人,研究員,博士生導師,博士,主要研究方向:工業(yè)大數(shù)據(jù)、智能制造、生產(chǎn)計劃與調度; 張楠(1990—),女(滿族),吉林四平人,博士研究生,主要研究方向:智能算法、生產(chǎn)計劃與調度。

1001- 9081(2017)10- 2767- 06

10.11772/j.issn.1001- 9081.2017.10.2767

TP301.6

A

This work is partially supported by the National Natural Science Foundation of China (51274043).

QIAOShen, born in 1985, M. S. candidate. His research interests include intelligent algorithm, production planning and scheduling.

LYUZhimin, born in 1971, Ph. D., research fellow. His research interests include industrial big data, intelligent manufacturing, production planning and scheduling.

ZHANGNan, born in 1990, Ph. D. candidate. His research interests include intelligent algorithm, production planning and scheduling.