謝 旻

（南京工業(yè)大學(xué) 電子與信息工程學(xué)院，南京210009）

TSP（traveling salesman problem）也稱旅行商問題，是一個(gè)經(jīng)典的 NP（non－deterministic polynomial）問題，可以簡(jiǎn)單地描述成：已知n個(gè)城市的坐標(biāo)，尋找一條走遍所有城市且路徑最短的路線。其數(shù)學(xué)模型如下：設(shè)有城市集合C＝｛C1，C2，C3，…，Cn｝，其每對(duì)城市的距離為d（Ci，Cj），求一條經(jīng)過C中每個(gè)城市恰好一次的路徑（C1，C2，C3，…，Cn），使的值最小。

針對(duì)TSP提出的隨機(jī)優(yōu)化方法包括神經(jīng)網(wǎng)絡(luò)算法、模擬退火算法、遺傳算法以及近年來提出的群體智能算法等。其中，粒子群算法（PSO算法）由于模型簡(jiǎn)單、參數(shù)少而得到了廣泛應(yīng)用。為了進(jìn)一步提高算法的性能，大量研究基于PSO算法，融合了進(jìn)化算法或采用混合群體優(yōu)化方法。如文獻(xiàn)［1］對(duì)離散粒子群算法分別加入逆轉(zhuǎn)變異優(yōu)化策略、受蟻群?jiǎn)⑹镜淖儺悆?yōu)化策略以及近鄰搜索變異優(yōu)化策略；文獻(xiàn)［2］通過改進(jìn)離散粒子群運(yùn)動(dòng)方程，加入啟發(fā)因子，提高算法的收斂性和穩(wěn)定性；文獻(xiàn)［3］利用遺傳算法全局搜索能力強(qiáng)的特點(diǎn)對(duì)用粒子群優(yōu)化算法所求解進(jìn)行優(yōu)化；文獻(xiàn)［4］提出一種融合蟻群算法、遺傳算法、粒子群優(yōu)化算法思想的混合算法；文獻(xiàn)［5］提出一種自適應(yīng)離散PSO算法，并利用調(diào)節(jié)算子和交換序?qū)SO算法進(jìn)行改進(jìn)，等等。但已有文獻(xiàn)大多針對(duì)整個(gè)種群進(jìn)行進(jìn)化操作，并未在現(xiàn)有種群上分類篩選優(yōu)質(zhì)個(gè)體，淘汰劣質(zhì)個(gè)體，筆者通過對(duì)已有文獻(xiàn)的研究，提出一種混合粒子群優(yōu)化方法，加入種群分類機(jī)制，對(duì)劃分后的子種群實(shí)施不同的策略達(dá)到保留優(yōu)秀個(gè)體的目的，從而提高算法的性能。

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

粒子群（particle swarm optimization，PSO）算法是計(jì)算智能領(lǐng)域，除了蟻群算法、魚群算法之外的一種群體智能優(yōu)化算法。PSO算法模擬鳥類捕食行為，通過搜索當(dāng)前距離食物最近的鳥的周圍區(qū)域來找到食物。PSO算法中每個(gè)粒子代表問題的一個(gè)潛在解，每個(gè)粒子對(duì)應(yīng)一個(gè)由適應(yīng)度函數(shù)決定的適應(yīng)度值。粒子的速度決定了粒子移動(dòng)的方向和距離，速度隨自身及其他粒子的移動(dòng)經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)正，從而實(shí)現(xiàn)個(gè)體在可解空間中的尋優(yōu)。

假設(shè)在一個(gè)D維的搜索空間中，由n個(gè)粒子組成的種群X＝（X1，X2，…，Xn），其中第i個(gè)粒子表示為一個(gè)d 維的向量Xi＝（Xi1，Xi2，…，XiD），代表一個(gè)問題的潛在解。根據(jù)目標(biāo)函數(shù)可計(jì)算每個(gè)粒子位置Xi對(duì)應(yīng)的適應(yīng)度值。第i個(gè)粒子的速度為Vi＝（Vi1，Vi2，…，ViD），種群的群體極值為 Pg＝（Pg1，Pg2，…，PgD）。每次迭代過程中，粒子通過個(gè)體極值Pbest和群體極值Gbest更新自身的速度和位置，即

式中：w 為慣性權(quán)重；d＝1，2，…，D；i＝1，2，3，…，n；k為迭代次數(shù)；Vid為粒子的速度；c1，c2為加速因子；r1，r2為［0，1］區(qū)間的隨機(jī)數(shù)。為防止粒子的盲目搜索，一般將其位置和速度限定在區(qū)間［－Xmax，Xmax］。

標(biāo)準(zhǔn)PSO算法的步驟如下：

1）初始化粒子和粒子速度；

2）粒子適應(yīng)度值計(jì)算，計(jì)算每個(gè)粒子在每一維空間的適應(yīng)度值；

3）比較粒子的適應(yīng)度值和個(gè)體極值Pbest，如果當(dāng)前值比Pbest更優(yōu)，則置Pbest為當(dāng)前值，并設(shè)Pbest位置為D維空間中的當(dāng)前位置；

4）比較粒子的適應(yīng)度值與種群極值Gbest，如果當(dāng)前值比Gbest更優(yōu)，則重置Gbest的索引號(hào)；

5）更新粒子速度、位置，產(chǎn)生新種群；

6）檢查結(jié)束條件，若滿足條件，則結(jié)束尋優(yōu)；否則，轉(zhuǎn)至2）。

2 混合粒子群算法（PSO－GA）

標(biāo)準(zhǔn)粒子群算法通過追逐個(gè)體極值和群體極值完成極值尋優(yōu)，雖然操作簡(jiǎn)單且能快速收斂，但隨著迭代次數(shù)的增加，在種群收斂集中的同時(shí)，粒子的相似度越來越高，可能在局部最優(yōu)解周邊無法跳出?；旌狭Ｗ尤核惴ǎ≒SO－GA）摒棄了標(biāo)準(zhǔn)粒子群算法中通過跟蹤極值來更新粒子位置的方法，引入遺傳算法中的交叉算子和變異算子，通過粒子與個(gè)體最優(yōu)粒子和群體最優(yōu)粒子的交叉以及粒子自身變異的方式來搜索最優(yōu)解，算法步驟如下：

1）種群初始化；

2）計(jì)算粒子的適應(yīng)度值；

3）根據(jù)粒子適應(yīng)度值更新個(gè)體最優(yōu)粒子和群體最優(yōu)粒子；

4）個(gè)體最優(yōu)交叉，將個(gè)體和個(gè)體最優(yōu)粒子進(jìn)行交叉得到新粒子；

5）群體最優(yōu)交叉，將個(gè)體和群體最優(yōu)粒子進(jìn)行交叉得到新粒子；

6）粒子自身變異；

7）檢查結(jié)束條件，若滿足條件，則結(jié)束尋優(yōu)；否則，轉(zhuǎn)至2）。

3 混合粒子群優(yōu)化算法（IHPSO）

由于GA算法本身存在“早熟”收斂，故筆者基于PSO－GA算法，提出一種IHPSO算法，將整個(gè)群體分為若干子群體，將每個(gè)子群體作為一個(gè)整體施行進(jìn)化操作；同時(shí)，在PSO－GA的基礎(chǔ)上引入克隆選擇算子對(duì)算法進(jìn)行免疫優(yōu)化，通過計(jì)算個(gè)體間的親和度來進(jìn)行增殖復(fù)制和變異，從而保留最佳個(gè)體和改進(jìn)較差個(gè)體。

IHPSO的算法流程如下：

1）種群初始化，種群規(guī)模為N，記為P1；

2）計(jì)算P1中每個(gè)抗體的親和力，按照親和力降序順序?qū)贵w進(jìn)行排序，取親和力高的一半抗體作為當(dāng)前群體，記為P2；

3）對(duì)當(dāng)前群體進(jìn)行個(gè)體最優(yōu)交叉和群體最優(yōu)交叉；

4）按照親和力值對(duì)當(dāng)前群體施行克隆操作，克隆數(shù)量與抗體的親和力成正比；

5）用抗體重組算子對(duì)克隆后群體中所有的抗體進(jìn)行隨機(jī)重組；

6）用自適應(yīng)變異算子對(duì)克隆后的群體進(jìn)行變異操作；

7）計(jì)算變異后抗體的親和力，并按照親和力排序，取親和力高的前N個(gè)抗體記為P3；

8）更新當(dāng)前群體，合并P2和P3，作為新的群體P1；

9）檢查結(jié)束條件，若滿足條件，則結(jié)束尋優(yōu)；否則，轉(zhuǎn)至2）。

算法中設(shè)計(jì)了克隆算子、交叉算子、自適應(yīng)變異算子和抗體重組算子等4個(gè)算子。

3．1 克隆算子

將粒子對(duì)應(yīng)于生物染色體，抗體對(duì)應(yīng)于含有n條染色體的群體，抗原對(duì)應(yīng)于含有最優(yōu)粒子的子群體，抗體與抗原的親和力為：

式中：Fj為抗體中粒子的適應(yīng)度值；lbesti為抗體中粒子的最大適應(yīng)度值?？寺∷阕訉?duì)親和力高的抗體進(jìn)行克隆操作，克隆數(shù)量Nc為：

式中：β為克隆系數(shù)，用來控制克隆規(guī)模，β＝0．4－0．3 g／gmax，gmax為規(guī)定的最大群體代數(shù)；n為常數(shù)；i為粒子按親和力降序排序后的序號(hào)，g為當(dāng)前群體代數(shù)。從式（5）中可見，克隆規(guī)模隨親和力的增加而增加，親和力越高，抗體克隆的數(shù)量越多，從而使群體中親和力高的優(yōu)秀個(gè)體得以保存和發(fā)展。

3．2 交叉算子

交叉操作是遺傳算法獲得子代優(yōu)秀個(gè)體的重要手段。針對(duì)TSP，筆者設(shè)計(jì)一種基于系統(tǒng)信息的交叉策略來指導(dǎo)交叉操作，可以大大提高算法的搜索能力和收斂速度。

首先建立每個(gè)城市的最小鄰居庫，記錄與城市Ci距離最短的城市Cj，記為｛Ci，Cj｝，如8個(gè)城市的最小鄰居庫為｛1，2｝，｛2，4｝，｛3，1｝，｛4，1｝，｛5，4｝，｛6，5｝，｛7，1｝，｛8，3｝，選取父代個(gè)體 X，Y，設(shè)X＝｛X1，X2，…，Xn｝，Y＝｛Y1，Y2，…，Yn｝，交叉方法如下：

1）對(duì)父代X隨機(jī)選取位置Xi，在最小鄰居庫中找到與Xi距離最小的城市Xj，將Xj放至序列最后，得到X′；

2）在父代Y中以Xj（方便起見，在父代Y中以Yj標(biāo)記）為起始點(diǎn)將父代Y的序列重置，得到Y(jié)′＝｛Yj，Yj＋1，…，Yn，Y1，Y2，…，Yn－1｝；

3）在Y′中刪除X′中從起始到Xi出現(xiàn)的城市，得到交叉序列Xc；

4）以Xc替換X′中從Xj＋1位置開始的序列，生成子代Child1。

同理，對(duì)父代Y進(jìn)行交叉操作可得到子代Child2。

3．3 自適應(yīng)變異算子

變異操作是增加種群多樣性的重要手段，適度的變異，既可保持種群個(gè)體的多樣化，又能提高局部搜索能力?；诹Ｗ尤憾鄻有缘淖兓紤]，在克隆操作后引入自適應(yīng)變異算子。當(dāng)多樣性小時(shí)，變異因素增強(qiáng)，使得算法有更寬的搜索能力；當(dāng)多樣性較大時(shí)，變異因素減弱，使算法能夠在小范圍內(nèi)精確搜索［6］。

用Aij表示粒子Xi與Xj的相似程度：

當(dāng)Xik＝Xjk時(shí)，表示粒子Xi與Xj的第k個(gè)位置的值相同。Aij∈［0，1］，若Aij＝1，則表示Xi與Xj完全相同。

第i個(gè)粒子的多樣性D（i）定義為：

式中：Pi、Pj分別為個(gè)體極值和全局極值。

粒子多樣性定義為個(gè)體多樣性的平均值：

當(dāng)D＜0．4時(shí)，執(zhí)行變異算子。變異方法采用順序交換法［7］，在粒子

Xi＝ ｛Xi1，Xi2，…，Xij，…，Xik，…，XiD｝隨機(jī)產(chǎn)生Xij，Xik兩個(gè)變異位，將兩個(gè)變異位交換得到

3．4 抗體重組算子

抗體重組算子重新將子種群隨機(jī)劃分，使原來在不同子種群的粒子被劃分到同一群體中，使子種群之間發(fā)生信息交換，這樣利于擴(kuò)展搜索空間，使算法找到全局最優(yōu)解。若粒子的鄰域范圍保持不變，容易陷入局部最優(yōu)解。

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

筆者針對(duì)TSP 30城市問題（Oliver30）、14城市問題（Burma14）和51城市問題（eil51）分別用標(biāo)準(zhǔn)PSO、PSO－GA、IHPSO、文獻(xiàn)［4］算法和文獻(xiàn)［5］算法進(jìn)行測(cè)試比較。其中IHPSO的參數(shù)如下：Burma14種群粒子數(shù)為10、最大迭代次數(shù)為50；Oliver30種群粒子數(shù)為30、最大迭代次數(shù)為200；eil51種群粒子數(shù)為60、最大迭代次數(shù)為1 000。

Oliver30問題的PSO、PSO－GA和IHPSO收斂過程分別如圖1、圖2和圖3所示，圖4為IHPSO（Oliver30）最優(yōu)路徑，表1為三種算法在Oliver30

圖1 PSO收斂過程（30城市）

圖2 PSO－GA收斂過程（30城市）

問題上運(yùn)行30次的結(jié)果比較，表2為幾種算法在不同TSP上的最優(yōu)結(jié)果比較。

圖3 IHPSO收斂過程（30城市）

圖4 IHPSO最優(yōu)路徑（30城市）

表1 Oliver30問題算法比較

表2 幾種算法最優(yōu)解比較

可以看出，本研究提出的算法在Oliver30、Burma14問題上收斂較快，并能取得較優(yōu)結(jié)果，在eil51問題上也能取得較接近最優(yōu)解的值。

5 結(jié)束語

筆者針對(duì)TSP提出了一種混合粒子群優(yōu)化算法IHPSO，在PSO－GA的基礎(chǔ)上增加種群分類機(jī)制和克隆免疫機(jī)制，對(duì)不同子群體有區(qū)別地進(jìn)行進(jìn)化操作，設(shè)計(jì)了四個(gè)算子：克隆算子作用于適應(yīng)度值高的粒子，增加了位置好的粒子進(jìn)入下一次迭代的機(jī)會(huì)；交叉算子有效地利用了系統(tǒng)信息；自適應(yīng)變異算子保證了種群的多樣性；抗體重組算子使子種群之間發(fā)生信息交換。IHPSO就經(jīng)典 TSP（Oliver30、Burma14、eil51）與多種算法進(jìn)行了比較。實(shí)驗(yàn)數(shù)據(jù)證明IHPSO的收斂速度和全局尋優(yōu)能力，特別在大規(guī)模問題上都較優(yōu)。

［1］ 余伶俐，蔡自興．改進(jìn)混合離散粒子群的多種優(yōu)化策略算法［J］．中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，40（4）：1047－1053．

［2］ 范會(huì)聯(lián)，李獻(xiàn)禮．基于近鄰關(guān)系求解 TSP的離散PSO算法［J］．計(jì)算機(jī)應(yīng)用研究，2011，28（2）：511－513．

［3］ 俞靚亮，王萬良，介婧．基于混合粒子群優(yōu)化算法的旅行商問題求解［J］．計(jì)算機(jī)工程，2010，36（11）：183－184．

［4］ 胡志軍，王鴻斌，應(yīng)璐．基于求解 TSP問題的 ACA－GA－PSO算法［J］．科技通報(bào)，2012，28（4）：82－84．

［5］ 何靜，劉躍華，周偉林．用自適應(yīng)離散微粒群算法求解旅行商問題［J］．計(jì)算機(jī)技術(shù)與自動(dòng)化，2012，31（1）：82－85．

［6］ 王蒙，介婧，曾建潮，等．解決 TSP問題的局部調(diào)整離散微粒群算法［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（21）：4936－4938．

［7］ 王永貴，曲海成，趙婉彤．一種改進(jìn)的遺傳算法在TSP問題中的應(yīng)用［J］．遼寧工程技術(shù)大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，30（2）：263－267．

［8］ Shi X H，Liang Y C，Lee H P，et al．An Improved GA and a Novel PSO－GA－based Hybrid Algorithm［J］．Information Processing Letters，2005，93（5）：255－261．

［9］ 劉朝華，張英杰，吳建輝．一種求解TSP問題的改進(jìn)克隆選擇算法［J］．系統(tǒng)仿真學(xué)報(bào)，2010，22（7）：1627－1631．

［10］ 張瑜，李濤，吳麗華，等．求解 TSP問題的抗體克隆優(yōu)化算法［J］．四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2010，42（3）：127－131．