強 寧，康鳳舉

（西北工業(yè)大學航海學院，陜西西安710072）

加速度粒子群算法在多旅行商問題中的應用

強 寧，康鳳舉

（西北工業(yè)大學航海學院，陜西西安710072）

標準粒子群算法（PSO）在求解多旅行商問題（MTSP）時易發(fā)生早熟收斂，為此提出一種新的加速度粒子群算法。借鑒力學思想將粒子的運動描述為受力以后在解空間中的搜索運動，粒子受個體最優(yōu)、全局最優(yōu)的牽引力，并受局部最優(yōu)的排斥力，加速度由粒子所受的合力決定。通過審斂操作判斷早熟收斂，當發(fā)生早熟時局部最優(yōu)對所有粒子產(chǎn)生的排斥力使種群跳出局部最優(yōu)繼續(xù)搜索。為進一步提高算法效率，針對MTSP問題的特點設(shè)計了基于維度的粒子學習策略和編解碼方法。仿真結(jié)果表明，該算法能夠有效克服早熟收斂，從而提高解的收斂性和穩(wěn)定性，為MTSP問題提供了一種可行的方法。

多旅行商問題；粒子群算法；學習策略；編解碼方法

PACS：45.50.Dd

多旅行商問題（Multiple Traveling Salesman Problem，MTSP）是經(jīng)典的旅行商問題（Traveling Salesman Problem，TSP）的擴展［1］。實際應用中的很多優(yōu)化問題，例如網(wǎng)絡(luò)優(yōu)化、車輛路徑規(guī)劃、生產(chǎn)調(diào)度等都可以歸納為MTSP問題。針對MTSP問題，近年來很多學者都研究了采用智能啟發(fā)式算法來求解此類問題［2－4］。但是由于MTSP問題本身的復雜性，現(xiàn)有的智能啟發(fā)式算法在求解時一般都存在易早熟、解的質(zhì)量不高等問題。

粒子群算法由于其結(jié)構(gòu)簡單、易實現(xiàn)、收斂速度快、調(diào)節(jié)參數(shù)少等優(yōu)點，在優(yōu)化領(lǐng)域得到了廣泛的應用［57］。但是與其他智能啟發(fā)式算法類似，現(xiàn)有的粒子群算法應用于MTSP仍然存在容易陷入局部最優(yōu)的缺點，主要原因是隨著算法的迭代，種群多樣性快速降低，在求解MTSP這一類具有多個局部極值的問題時很難跳出局部最優(yōu)。文獻［8］提出了一種加速粒子群算法，該算法去除了速度公式只采用全局最優(yōu)引導粒子進化，簡潔高效。文獻［9］提出了加速度粒子群算法的概念，這兩種算法對于單極值問題都能起到加速收斂的作用，但并沒有考慮多局部極值問題，因此并不適合求解MTSP。

本文設(shè)計了一種新的加速度粒子群算法，將粒子在解空間中的搜索行為看作受合力以后的加速運動，粒子受個體最優(yōu)和全局最優(yōu)的牽引力，并受局部最優(yōu)的排斥力，通過審斂操作判斷早熟收斂。利用外部存儲保存所找到的局部最優(yōu)解，當?shù)Y(jié)束時輸出最好的局部最優(yōu)作為全局最優(yōu)解。為了進一步提高算法的性能，根據(jù)MTSP問題的特點設(shè)計了基于維度的粒子學習策略，在每次迭代時粒子的每一維向不同的粒子學習；針對閉合式MTSP問題設(shè)計了一種新的編解碼方法；采用均勻變異和高斯變異混合的變異策略保持種群的多樣性。數(shù)值仿真結(jié)果表明了本文算法求解MTSP問題時的有效性和優(yōu)越性。

1 多旅行商問題模型

典型的MTSP問題描述如下：考慮完全圖G（V，A），V是由n個城市構(gòu)成的點的集合表示為V＝｛1，2，3，..，n｝，其中1為所有旅行商的出發(fā)點，其他點為需要旅行商拜訪的城市。A是V中兩點之間路徑的集合，C＝（cij）為與A中路徑對應的距離矩陣，cij表示城市之間的距離。需要指派m個旅行商訪問所有n個城市，每個城市只被一個旅行商訪問一次（除了出發(fā)點）。對問題加以不同的約束就可以得到幾種MTSP問題的變型［10－11］。如果C是對稱矩陣，代表兩個城市之間的往返距離是相等的，即cij＝cji，此時問題為對稱MTSP，否則為非對稱MTSP。根據(jù)是否要求旅行商返回出發(fā)點分為開放路徑MTSP和閉合路徑MTSP。根據(jù)旅行商的出發(fā)城市是否相同分為單起點MTSP和多起點MTSP。如果對旅行商的能力和城市的能力需求加以約束，MTSP就轉(zhuǎn)化為車輛路徑問題（Vehicle Routing Problem，VRP）。本文在二維空間內(nèi)研究單起點的閉合式MTSP問題，城市之間的距離為歐氏距離，并滿足三角不等式cij+cjk≥cik。定義變量xij，當cij包含在路徑中時xij為1，否則為0。定義變量ui，代表城市i（i不等于1）被旅行商訪問的次序。綜上得到以下模型：

約束條件：

式（1）為目標函數(shù)，代表所有旅行商路程之和最小。式（2）限定恰好有m個旅行商離開和回到出發(fā)點。式（3）限定每個城市（除了出發(fā)點）只有一條路徑進入且只有一條路徑離開。式（4）、（5）和（6）用來限定每個旅行商允許訪問城市個數(shù)的上限（L）和下限（K），式（7）和式（8）為變量說明。

2 加速度粒子群算法

為了克服早熟收斂問題，本文提出了一種新的加速度粒子群算法（Acceleration Particle Swarm Optimization，APSO），由于粒子受局部最優(yōu)排斥力，因此能夠迅速跳出局部最優(yōu)。另外，為MTSP問題設(shè)計了基于維度的粒子學習策略，并采用了一種均勻變異和高斯變異混合的變異策略。

2.1 粒子群算法概述

粒子群算法（Particle Swarm Optimization，PSO）是一種新興的智能算法［12］，具有結(jié)構(gòu)簡單易實現(xiàn)、收斂速度快等優(yōu)點，但存在易陷入局部最優(yōu)的缺陷?；綪SO的表達式為

2.2 加速度粒子群算法描述

在基本的PSO算法中，當粒子陷入局部最優(yōu)時，式（9）右端的第二項和第三項等于0或接近于0，第一項隨著w的遞減變得很小，粒子的速度幾乎接近于0，很難跳出局部最優(yōu)，導致算法早熟。

為了解決這一問題，本文設(shè)計了一種新的加速度粒子群算法，首先假想一群鳥的覓食行為：群體中的每一只鳥根據(jù)個體的經(jīng)驗和附近其他鳥的經(jīng)驗調(diào)整飛行的速度和方向不斷向食物靠近。如果一只鳥發(fā)現(xiàn)了食物，附近的一些鳥將跟隨這只鳥飛向食物，這些鳥在吃完食物后會繼續(xù)搜索其他區(qū)域，并且會判定剛才找到食物的區(qū)域已不必再判定搜索。鳥群的行為可以看作粒子找到局部最優(yōu)解后會存儲并遠離此區(qū)域，之后繼續(xù)搜索其他區(qū)域，所以粒子不存在穩(wěn)定狀態(tài)。隨著找到的局部最優(yōu)解增加粒子搜索空間變得越來越小，種群更有機會找到全局最優(yōu)解，最終的全局最優(yōu)解就是鳥群記憶中最好的局部最優(yōu)解。

為了模擬這種行為，首先給出運動規(guī)律

參數(shù)a、v和x分別代表加速度、速度和位移。將粒子在解空間中的搜索行為看作受力以后的加速運動，粒子受個體最優(yōu)和群體最優(yōu)的牽引力，并產(chǎn)生加速度向最優(yōu)解方向搜索，當發(fā)生早熟收斂時，局部最優(yōu)粒子對種群中的所有粒子產(chǎn)生排斥力，這個排斥力隨著粒子遠離局部最優(yōu)將逐步減弱，以免對粒子將來的搜索造成影響，圖1為粒子受力的示意圖。綜上，提出了一種新的加速度粒子群算法（APSO）如下

圖1 粒子受力示意圖Fig.1 Force diagram for a particle

式（14）為加速度公式，右端第1和第2項分別代表粒子受個體最優(yōu)和全局最優(yōu)粒子的牽引力所產(chǎn)生的加速度，參數(shù)的含義和式（9）相同。式（14）右端第3項代表粒子受當前所有局部最優(yōu)粒子的排斥力所產(chǎn)生的加速度，加速度的方向由局部最優(yōu)解指向當前粒子位置，加速度的大小與距離（－pj）成反比，當（－pj）從0到無窮變化時，排斥力所產(chǎn)生的加速度在［c3·R／c，0］之間變化，r3為［0，1］上均勻分布的隨機數(shù)，k為當前所找到的局部最優(yōu)解的個數(shù)，pj代表局部最優(yōu)解的位置。參數(shù)c3、R和c決定排斥力的大小，參數(shù)b決定排斥力加速度隨距離的變化率。在找到局部最優(yōu)之前，式（14）右端第三項為0，當找到一個局部最優(yōu)時，將它保存在一個外部存儲中（為方便描述命名為集合G），集合G中的元素作為式（14）中的pj。

2.3 個體最優(yōu)和全局最優(yōu)的重新選擇策略

當粒子陷入局部最優(yōu)時，粒子的個體最優(yōu)和全局最優(yōu)一般也在局部最優(yōu)附近，因此粒子所受的引力和排斥力方向相反，導致粒子在局部最優(yōu)附近震蕩。為了保證粒子不再飛回局部最優(yōu)，當找到局部最優(yōu)以后需要重新選擇粒子的個體最優(yōu)和全局最優(yōu)。具體方法為：如果當前粒子迭代一次以后適應值和到局部最優(yōu)的距離都減小，那么視為一次“危險飛行”，如果局部最優(yōu)對粒子的排斥力大于個體最優(yōu)和全局最優(yōu)對粒子的引力，則從當前迭代向前剔除所有連續(xù)的“危險飛行”所對應的個體位置，并重新確定粒子的個體最優(yōu)和全局最優(yōu)。

該策略可以理解為鳥群可以記住通向局部最優(yōu)的“通道”，如果鳥群發(fā)現(xiàn)一條“通道”通向局部最優(yōu)，則在將來的搜索中，“通道”中的所有位置都不能再作為個體最優(yōu)和全局最優(yōu)。在編程時，保存每個粒子每一代的適應值和位置，當確認一組連續(xù)的“危險飛行”導致粒子飛回局部最優(yōu)時，將所有連續(xù)的“危險飛行”所對應的適應值附加一個很大的值（保證他們不再被選中），再重新選擇個體最優(yōu)和全局最優(yōu)。

2.4 基于維度的粒子學習策略

粒子的編碼為n－1維，每一維代表一個城市的指派（詳見本文第3部分）。標準的粒子群算法中粒子每一維的學習對象都是同一個粒子，這可能造成在一次迭代以后粒子的某些維度靠近全局最優(yōu)解，而另一些維度卻遠離全局最優(yōu)解。對于MTSP問題，若當前解向同一個最優(yōu)解學習，可能導致部分城市的指派達到最優(yōu)，而另一些城市的指派卻遠離最優(yōu)。

因此，提出了基于維度的粒子學習策略，使粒子的每一維向不同的粒子學習。當前粒子每一維的學習樣本應滿足兩個條件：（1）具有更好的適應值；（2）更接近當前粒子的維度。

定義約束量

則粒子個體認知學習策略為：在當前粒子的鄰域范圍內(nèi)找到使得式（17）取最大值的粒子作為當前粒子第d維個體認知的學習對象。在初始化時按照歐氏距離取最近的k個粒子作為粒子的鄰域，并且每隔T1代重建粒子的鄰域。Fit代表粒子的適應值，即粒子位置代表的城市指派所對應的旅行商路程之和。

定義約束量

其中pgj代表群體中歷史適應值最優(yōu)的k個粒子。則粒子社會認知學習策略為：在其中找到使得式（18）取最大值的粒子作為當前粒子第d維社會認知的學習對象。

基于維度的粒子學習策略充分利用了鄰域粒子和全局最優(yōu)粒子每一維上的最優(yōu)信息，針對實數(shù)編碼的MTSP問題能夠使得每個城市的指派都向當前該城市的最優(yōu)指派學習，使得種群更有機會找到全局最優(yōu)解。

2.5 審斂操作

本文提出的加速度粒子群算法能夠克服早熟收斂，跳出局部最優(yōu)，早熟收斂的判定依據(jù)是一個關(guān)鍵問題。根據(jù)前面的分析，當種群陷入局部最優(yōu)時粒子的速度很小，種群聚集在局部最優(yōu)位置附近，很難跳出局部最優(yōu)。引入變異操作可以提高種群的多樣性，但由于其隨機性和盲目性，變異操作并不能確保種群跳出局部最優(yōu)。種群陷入局部最優(yōu)時具有兩個基本特征：（1）全局最優(yōu)連續(xù)多代沒有更新；（2）粒子聚集導致種群多樣性降低。首先定義種群的多樣性測度為

其代表平均粒子間距，描述了種群中粒子間相互分布的離散程度，用來定義種群的多樣性，Div越小表明種群越集中，多樣性越小。N為種群規(guī)模，dn為粒子編碼的維數(shù)，L為解空間的最大長度，代表第t次迭代時第i個粒子第d維的編碼值代表所有粒子第d維編碼的平均值。

審斂操作可描述為：如果全局最優(yōu)連續(xù)T2代沒有更新，且種群多樣性Div小于ε（ε∈（0，1））則認為發(fā)生早熟收斂，將當前最優(yōu)解記為局部最優(yōu)，并存入外部檔案集G。

2.6 變異操作

當算法發(fā)生早熟收斂時種群的多樣性很低，局部最優(yōu)粒子對種群的排斥力可以幫助粒子迅速跳出局部最優(yōu)，一定程度上能夠提高種群的多樣性，但是當種群遠離局部最優(yōu)時仍可能發(fā)生聚集。為了進一步在整個迭代過程中提高種群的多樣性，采取均勻變異和高斯變異結(jié)合的變異策略，具體方法為：在迭代初期以更大概率采用均勻變異策略，使得粒子有機會在整個解空間中搜索，而在迭代后期以更大概率采用高斯變異策略，提高粒子的局部搜索能力。均勻變異公式為

高斯變異的公式為

采用均勻變異策略時粒子的位置和速度均發(fā)生變異，而采用高斯變異策略時只有粒子的位置發(fā)生變異，速度不變。xmin，d、vmin，d和xmax，d、vmax，d代表粒子在第d維的位置和速度的最小值和最大值，R代表（0，1）上的均勻分布隨機數(shù)，Gaussian（0，0.1）代表均值為0方差為0.1的高斯分布隨機數(shù)。種群中的粒子以概率1／N發(fā)生變異，發(fā)生變異的粒子以概率（tmax－t）／tmax選擇均勻變異策略，以概率1－（tmax－t）／tmax選擇高斯變異策略。N為種群規(guī)模，t和tmax分別為當前迭代次數(shù)和最大迭代次數(shù)。

2.7 算法流程

APSO算法求解MTSP問題的步驟：

步驟1：初始化種群，確定粒子鄰域。根據(jù)具體的MTSP問題，決定決策空間的維度和每一維的取值范圍。

步驟2：進行解碼操作，根據(jù)公式（1）計算粒子的適應值。

步驟3：根據(jù)公式（17）和（18）選擇粒子每一維的個體和全局學習對象，根據(jù)公式（14）、（15）和（16）更新粒子位置、速度和加速度；每隔T1代重新計算粒子的鄰域；如果G不為空集判斷粒子是否經(jīng)歷“危險飛行”，如果是則重新選擇粒子的個體和全局最優(yōu)。

步驟4：執(zhí)行變異操作，若發(fā)現(xiàn)更優(yōu)解，則更新當前最優(yōu)解。

步驟5：根據(jù)審斂操作判斷是否找到最優(yōu)解？若為是，則轉(zhuǎn)到步驟6；否則轉(zhuǎn)到步驟7。

步驟6：保存找到的最優(yōu)解到集合G。

步驟7：判斷迭代是否結(jié)束？若為否，則轉(zhuǎn)到步驟2；若為是，則輸出G中最好的解作為全局最優(yōu)解。

3 編碼和解碼方法

編碼是指將MTSP問題的解和粒子的位置之間建立一種合適的映射關(guān)系。編碼和解碼方法對算法的效率影響顯著，本文參考文獻［11］設(shè)計的實數(shù)編碼方法并加以改進。

3.1 編碼方法

假定城市個數(shù)為n，旅行商個數(shù)為m，則粒子編碼為n－1維，每一維的整數(shù)部分代表城市指派的旅行商，而小數(shù)部分代表城市被訪問的順序。假定有8個城市（1為起點）3個旅行商，一個粒子的編碼為

3.2 分組解碼

上例中具有相同整數(shù)部分的城市分在同一組，被一個旅行商訪問，分組結(jié)果為

第一個旅行商訪問的城市：2，5；

第二個旅行商訪問的城市：4，6，8；

第三個旅行商訪問的城市：3，7。

粒子編碼的整數(shù)部分只能在｛0，1，2｝中取值，代表3個旅行商，如果編碼計算以后超出范圍將自動調(diào)整在（0，3）上，例如計算結(jié)果為3.37則調(diào)整為0.37。

3.3 排序解碼

假定一個旅行商所訪問的城市順序為｛1，3，2，6，5，4，1｝，考慮當前研究的MTSP問題是對稱且閉合的，因此該訪問順序等同于｛1，4，5，6，2，3，1｝，而傳統(tǒng)的解碼方法認為這是兩個不同的解。為了消除重復編碼，提高算法效率，提出了解碼方法為將分組中各城市編碼的小數(shù)部分由小到大進行排序。為方便編寫代碼，定義了路徑的左側(cè)和右側(cè)，在分組中選擇編碼值最小的兩個城市加入路徑，且其中較小的一個城市加入左側(cè)，而另一個加入右側(cè)。重復上述過程直到所有城市都加入了路徑中。表1為一個分組中城市的編碼排序，圖2演示了排序解碼的過程。

表1 分組中7個城市的編碼排序Tab.1 The sequence of encoding values in a group with 7 cities

圖2 組內(nèi)排序解碼過程Fig.2 The sequence decoding process within a group

4 仿真實驗

算法通過Matlab編程在雙核3.10GHz、4G內(nèi)存的計算機上運行，選用標準TSPLIB庫中的三組數(shù)據(jù)eil51、eil76和eil101做數(shù)值仿真實驗。將APSO的運行結(jié)果與UPSO［13］、MPSO［14］和EDPACA［15］比較。UPSO為統(tǒng)一的PSO算法，是經(jīng)典的PSO算法之一；MPSO是一種改進的多種群PSO算法；EDPACA是一種均分點蟻群算法，在處理MTSP時獲得了良好的效果。APSO的參數(shù)設(shè)置為：種群規(guī)模N＝80，慣性因子w在［0.9，0.4］上隨迭代次數(shù)線性遞減，加速因子c1＝c2＝1.496，c3＝0.5，R＝1，b＝3，c＝0.5，ε＝0.05，T1＝T2＝20，鄰域范圍k＝10，最大迭代次數(shù)tmax＝1 000。UPSO和MPSO除種群規(guī)模和迭代次數(shù)統(tǒng)一設(shè)置為80和1 000，其他參數(shù)設(shè)置來自文獻［13］和［14］。EDPACA的參數(shù)設(shè)置和結(jié)果均來自文獻［15］，值得注意的是EDPACA結(jié)合了2－OPT算法進行局部路徑優(yōu)化，而UPSO、MPSO和APSO都沒有采用局部優(yōu)化。四種算法分別獨立運行50次。

圖3為m＝3時UPSO、MPSO和APSO求解eil51、eil76和eil101的進化圖。可以看出UPSO算法易早熟、求解質(zhì)量較差；MPSO算法采用了多種群結(jié)構(gòu)搜索范圍更廣、多樣性更好，因此具有一定的抑制早熟能力，求解質(zhì)量優(yōu)于UPSO；APSO算法引入了加速度策略，粒子始終受局部最優(yōu)的排斥力，因此能夠有效克服早熟收斂，求解質(zhì)量最好。圖4為m＝3時APSO求解eil51、eil76和eil101所得的最優(yōu)路徑。

表2為4種算法分別運行50次的統(tǒng)計結(jié)果?？梢钥闯鯝PSO算法效果最好，在9種測試情況下最優(yōu)值和平均值都領(lǐng)先于其他3種算法，說明AP－SO的求解質(zhì)量和穩(wěn)定性都最好，結(jié)合局部路徑優(yōu)化的EAPACA算法性能次之，而采用多種群結(jié)構(gòu)的MPSO算法性能超過了UPSO算法。

圖3 UPSO、MPSO和APSO求解m＝3時的eil51、eil76和eil101的進化圖Fig.3 Evolution of UPSO、MPSO and APSO on eil51、eil76 and eil101 while mis equal to 3

圖4 APSO求解m＝3時的eil51、eil76和eil101的最優(yōu)路徑Fig.4 The optimal paths on eil51、eil76 and eil101 while mis equal to 3 using APSO

表2 4種算法的結(jié)果比較Tab.2 Comparison of the results solved by four algorithms

表3比較了當m＝3時3種PSO算法找到最優(yōu)值時的平均迭代次數(shù)和運行時間，并且比較了采用新的編解碼方法和文獻［11］的編解碼方法時3種PSO算法找到最優(yōu)值時的平均迭代次數(shù)，t代表算法運行的平均時間。3種算法最大迭代次數(shù)設(shè)置為1 500，獨立運行30次。c1和c2分別代表采用新的編解碼方法和文獻［11］的編解碼方法時找到最優(yōu)值的平均迭代次數(shù)，t代表算法運行的平均時間。采用兩種不同編碼方法時，每種PSO算法的運行時間均差別不大?？梢钥闯鯱PSO找到最優(yōu)值的平均迭代次數(shù)最小但最優(yōu)值較大，說明UPSO易早熟收斂導致求解質(zhì)量不高，而MPSO和APSO均能夠較好的克服早熟收斂，求解質(zhì)量較高，但由于具有更高的計算復雜度所以運行時間大于UPSO。當算法采用新的編解碼方法時，UPSO找到最優(yōu)值的平均迭代次數(shù)變化不大，這是因為UPSO易早熟，新的編解碼方法沒有充分發(fā)揮作用，而MPSO和APSO算法在找到相同最優(yōu)值的情況下采用新的編解碼方法比采用文獻［11］的編解碼方法時的平均迭代次數(shù)顯著減少，這是因為新的編解碼方法能夠消除重復編碼，提高了算法的效率。

表3 3種PSO算法比較Tab.3 Comparison of three PSO algorithms

5 結(jié)語

本文提出了一種新的加速度粒子群算法，種群中的粒子受局部最優(yōu)的排斥力，能夠迅速跳出局部最優(yōu)，且在將來的搜索中不會重復搜素局部最優(yōu)區(qū)域，使得種群有更大機會找到全局最優(yōu)解。所提出的基于維度的粒子學習策略和新的編解碼方法進一步提高了算法的性能。該算法能夠有效克服早熟收斂，從而提高MTSP問題的求解質(zhì)量和穩(wěn)定性。算法在多模態(tài)函數(shù)優(yōu)化以及多目標優(yōu)化領(lǐng)域的應用還需進一步研究。

［1］Bellmore M.Transformation of multi－salesmen problem to the standard traveling salesman problem［J］.Journal of the Association Computer Machinery，1974，21（5）：500－504.

［2］Imdat Kara，Tolga Bektas.Integer linear programming formulations of multiple salesman problems and its variations［J］.European Journal of Operational Research，2006，174：1449－1458.

［3］Carter A E，Ragsdale C T.A new approach to solving the multiple traveling salesperson problem using genetic algorithms［J］.European Journal of Operational Research，2006，175：246－257.

［4］Chen A，Yang G.Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem［J］.Journal of Zhejiang University Science A， 2006，4247：158－165.

［5］吳曉軍，楊戰(zhàn)中，趙明.均勻搜索粒子群算法［J］.電子學報，2011，39（6）：1261－1266.

［6］張長勝，孫吉貴，歐陽丹彤，等.求解車間調(diào)度問題的自適應混合粒子群算法［J］.計算機學報，2009，32（11）：2137－2146.

［7］王靜云，常安定，徐春龍，等.應用粒子群算法設(shè)計錐形孔微穿孔板結(jié)構(gòu)［J］.陜西師范大學學報：自然科學版，2014，42（2）：37－41.

［8］Yang Xinshe，Suash Deb，Simon Fong.Accelerated particle swarm optimization and support vector machine for business optimization and applications［J］.Networked Digital Technologies，2011，136：53－66.

［9］陳彥宇.基于加速度粒子群算法的微控制器電磁抗擾度建模研究［D］.北京：華北電力大學電器工程學院，2013：13－20.

［10］馬建華，房勇，袁杰.多車場多車型最快完成車輛路徑問題的變異蟻群算法［J］.系統(tǒng)工程理論與實踐，2011，31（8）：1508－1516.

［11］Marinakis Y，Iordanidou G，Marinaki M.Particle swarm optimization for the vehicle routing problem with stochastic demands［J］.Applied Soft Computing，2013，13：1693－1704.

［12］Kennedy J，Eberhart R.Particle swarm optimization［C］∥Proceedings of IEEE International Conference on Neural Networks.1995：1942－1948.

［13］Parsopoulos K E，Vrahatis M N.UPSO：A unified particle swarm optimization scheme［C］∥Proceedings of Conference of Computational Methods in Science and Engineering.2004：868－873.

［14］Chang Weide.A modified particle swarm optimization with multiple subpopulations for multimodal function optimization problems［J］.Applied Soft Computing，2015，33：170－182.

［15］余伶俐，蔡自興.均分點蟻群算法在群集機器人任務(wù)規(guī)劃中的應用研究［J］.高技術(shù)通訊，2009，19（10）：1054－1060.

〔責任編輯 李 博〕

Application of a new acceleration particle swarm optimization for solving multiple traveling salesman problems

QIANG Ning，KANG Fengju
（School of Marine，Northwestern Polytechnical University，Xi'an 710072，Shaanxi，China）

To overcome the premature convergence of the standard particle swarm optimization（PSO）in solving multiple travelling salesman problems（MTSP），a new acceleration particle swarm optimization is constructed.Rely on the idea of mechanics，the movement of particle is described as search motion driving by force in solution space.The particle is attracted by personal best force，global best force and repelled by local best force.Thus the acceleration of particle depends on the resultant of forces.Using convergence criterions to estimate premature convergence，the local best will repel all the particles when premature convergence occurs，so the particle swarm can jump out the local best and continue to search.In order to improve the efficiency of the algorithm，a dimensional learning strategy of particle and a new coding method are designed for MTSP.The simulation results show that the proposed algorithm can effectively overcome the premature convergence，and improve the quality and stability of solutions.Thus it provides a feasible method for MTSP.

multiple traveling salesman problems；particle swarm optimization；learning strategy；coding method

TP393

：A

1672－4291（2015）06－0036－07

10.15983／j.cnki.jsnu.2015.06.263

2015－05－13

船舶預研支撐技術(shù)基金（11J4.1.1）；水下信息處理與控制國家重點實驗室基金（9140C2305041001）

強寧，男，講師，博士研究生，研究方向為多Agent系統(tǒng)理論及應用。E－mail：qn315＠snnu.edu.cn