喬 屾,呂志民,張 楠

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

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

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

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

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

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

0 引言

旅行商問題(Traveling Salesman Problem,TSP)是一個(gè)經(jīng)典的組合優(yōu)化問題。隨著城市節(jié)點(diǎn)數(shù)的增加,該問題不可能使用窮舉方式找到最優(yōu)解,是著名的NP-Hard問題。計(jì)算智能的發(fā)展對(duì)該問題的求解提供了很多優(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)化問題上取得了極其良好的效果。同遺傳算法對(duì)比,粒子群優(yōu)化算法收斂更快,結(jié)果更優(yōu),因此受到眾多研究者關(guān)注。盡管如此,在求解離散問題,如旅行商問題(TSP)上,粒子群優(yōu)化算法中的速度概念,不能直接地應(yīng)用在問題模型中,需要對(duì)算法進(jìn)行一定改進(jìn)才能適合求解。

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

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

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

(1)

2 基于漢明距離的改進(jìn)粒子群算法

2.1 標(biāo)準(zhǔn)粒子群算法

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

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

(2)

(3)

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

圖1 標(biāo)準(zhǔn)PSO流程

2.2 漢明距離

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

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

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

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

(4)

(5)

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

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

在求解TSP的局部路徑優(yōu)化方面,2-opt[12-14]與3-opt[15-17]是常用的兩種優(yōu)化算子,通過對(duì)TSP路徑中邊的調(diào)整以獲得問題一個(gè)解的鄰域解。在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調(diào)整后尋得解更優(yōu)。2-opt的合理運(yùn)用,可以大幅縮減一個(gè)解的路徑總長(zhǎng),達(dá)到更好的尋優(yōu)。這種局部尋優(yōu)在算法前期效果極佳,當(dāng)結(jié)果收斂到一定程度時(shí),合適的2-opt調(diào)整邊已經(jīng)不容易找到,因此該算子不適用于算法后期，而適合用在初試解的優(yōu)化和每一次迭代之后,所有粒子進(jìn)行鄰域的搜尋。相比之下,在算法后期,3-opt的調(diào)整則更為有效。在路徑中連接某點(diǎn)Xi相鄰的兩條邊,將其刪除,并將Xi-1和Xi+1相連,在路徑中另外兩個(gè)相鄰點(diǎn)Xj和Xj+1之間插入Xi,此時(shí)需重新生成兩條邊d(Xj-1,Xi)和d(Xi,Xj+1),實(shí)現(xiàn)三條邊的調(diào)整,如圖3所示。

圖3 3-opt算子

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

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

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

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

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

2.4 改進(jìn)粒子搜索能力

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

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

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

2.5 本文IMRGHPSO算法流程

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

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

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

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

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

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

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

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

Step8 判斷是否達(dá)到結(jié)束條件,若達(dá)到則算法結(jié)束,若未達(dá)到則返回Step4。

圖4 IMRGHPSO算法流程

3 實(shí)驗(yàn)與結(jié)果分析

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

表2 HPSO、RGSPSO、IMRGHPSO算法求解TSP結(jié)果對(duì)比

各標(biāo)準(zhǔn)算例的測(cè)試基本參數(shù)如表1所示。

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

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

表1 算法參數(shù)

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

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

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

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

圖5 Ch130收斂曲線

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

4 結(jié)語

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

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ìn)粒子群算法[J]. 計(jì)算機(jī)工程與設(shè)計(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中的應(yīng)用[J]. 太原理工大學(xué)學(xué)報(bào), 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]. 模式識(shí)別與人工智能, 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]. 華南理工大學(xué)學(xué)報(bào) (自然科學(xué)版), 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īng)優(yōu)秀系數(shù)粒子群優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用, 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è)機(jī)械學(xué)報(bào), 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] 鄧曉衡, 曹德娟, 潘琰, 等. 一種基于時(shí)延約束的社會(huì)網(wǎng)絡(luò)信用分布優(yōu)化模型[J]. 計(jì)算機(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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(51274043)。

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

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.