一種混合粒子群優化算法在TSP中的應用

謝 旻

（南京工業大學 電子與信息工程學院，南京210009）

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

針對TSP提出的隨機優化方法包括神經網絡算法、模擬退火算法、遺傳算法以及近年來提出的群體智能算法等。其中，粒子群算法（PSO算法）由于模型簡單、參數少而得到了廣泛應用。為了進一步提高算法的性能，大量研究基于PSO算法，融合了進化算法或采用混合群體優化方法。如文獻［1］對離散粒子群算法分別加入逆轉變異優化策略、受蟻群啟示的變異優化策略以及近鄰搜索變異優化策略；文獻［2］通過改進離散粒子群運動方程，加入啟發因子，提高算法的收斂性和穩定性；文獻［3］利用遺傳算法全局搜索能力強的特點對用粒子群優化算法所求解進行優化；文獻［4］提出一種融合蟻群算法、遺傳算法、粒子群優化算法思想的混合算法；文獻［5］提出一種自適應離散PSO算法，并利用調節算子和交換序對PSO算法進行改進，等等。但已有文獻大多針對整個種群進行進化操作，并未在現有種群上分類篩選優質個體，淘汰劣質個體，筆者通過對已有文獻的研究，提出一種混合粒子群優化方法，加入種群分類機制，對劃分后的子種群實施不同的策略達到保留優秀個體的目的，從而提高算法的性能。

1 標準粒子群算法

粒子群（particle swarm optimization，PSO）算法是計算智能領域，除了蟻群算法、魚群算法之外的一種群體智能優化算法。PSO算法模擬鳥類捕食行為，通過搜索當前距離食物最近的鳥的周圍區域來找到食物。PSO算法中每個粒子代表問題的一個潛在解，每個粒子對應一個由適應度函數決定的適應度值。粒子的速度決定了粒子移動的方向和距離，速度隨自身及其他粒子的移動經驗進行動態調正，從而實現個體在可解空間中的尋優。

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

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

標準PSO算法的步驟如下：

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

2）粒子適應度值計算，計算每個粒子在每一維空間的適應度值；

3）比較粒子的適應度值和個體極值Pbest，如果當前值比Pbest更優，則置Pbest為當前值，并設Pbest位置為D維空間中的當前位置；

4）比較粒子的適應度值與種群極值Gbest，如果當前值比Gbest更優，則重置Gbest的索引號；

5）更新粒子速度、位置，產生新種群；

6）檢查結束條件，若滿足條件，則結束尋優；否則，轉至2）。

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

標準粒子群算法通過追逐個體極值和群體極值完成極值尋優，雖然操作簡單且能快速收斂，但隨著迭代次數的增加，在種群收斂集中的同時，粒子的相似度越來越高，可能在局部最優解周邊無法跳出。混合粒子群算法（PSO－GA）摒棄了標準粒子群算法中通過跟蹤極值來更新粒子位置的方法，引入遺傳算法中的交叉算子和變異算子，通過粒子與個體最優粒子和群體最優粒子的交叉以及粒子自身變異的方式來搜索最優解，算法步驟如下：

1）種群初始化；

2）計算粒子的適應度值；

3）根據粒子適應度值更新個體最優粒子和群體最優粒子；

4）個體最優交叉，將個體和個體最優粒子進行交叉得到新粒子；

5）群體最優交叉，將個體和群體最優粒子進行交叉得到新粒子；

6）粒子自身變異；

7）檢查結束條件，若滿足條件，則結束尋優；否則，轉至2）。

3 混合粒子群優化算法（IHPSO）

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

IHPSO的算法流程如下：

1）種群初始化，種群規模為N，記為P1；

2）計算P1中每個抗體的親和力，按照親和力降序順序對抗體進行排序，取親和力高的一半抗體作為當前群體，記為P2；

3）對當前群體進行個體最優交叉和群體最優交叉；

4）按照親和力值對當前群體施行克隆操作，克隆數量與抗體的親和力成正比；

5）用抗體重組算子對克隆后群體中所有的抗體進行隨機重組；

6）用自適應變異算子對克隆后的群體進行變異操作；

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

8）更新當前群體，合并P2和P3，作為新的群體P1；

9）檢查結束條件，若滿足條件，則結束尋優；否則，轉至2）。

算法中設計了克隆算子、交叉算子、自適應變異算子和抗體重組算子等4個算子。

3．1 克隆算子

將粒子對應于生物染色體，抗體對應于含有n條染色體的群體，抗原對應于含有最優粒子的子群體，抗體與抗原的親和力為：

式中：Fj為抗體中粒子的適應度值；lbesti為抗體中粒子的最大適應度值。克隆算子對親和力高的抗體進行克隆操作，克隆數量Nc為：

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

3．2 交叉算子

交叉操作是遺傳算法獲得子代優秀個體的重要手段。針對TSP，筆者設計一種基于系統信息的交叉策略來指導交叉操作，可以大大提高算法的搜索能力和收斂速度。

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

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

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

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

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

同理，對父代Y進行交叉操作可得到子代Child2。

3．3 自適應變異算子

變異操作是增加種群多樣性的重要手段，適度的變異，既可保持種群個體的多樣化，又能提高局部搜索能力。基于粒子群多樣性的變化考慮，在克隆操作后引入自適應變異算子。當多樣性小時，變異因素增強，使得算法有更寬的搜索能力；當多樣性較大時，變異因素減弱，使算法能夠在小范圍內精確搜索［6］。

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

當Xik＝Xjk時，表示粒子Xi與Xj的第k個位置的值相同。Aij∈［0，1］，若Aij＝1，則表示Xi與Xj完全相同。

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

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

粒子多樣性定義為個體多樣性的平均值：

當D＜0．4時，執行變異算子。變異方法采用順序交換法［7］，在粒子

Xi＝ ｛Xi1，Xi2，…，Xij，…，Xik，…，XiD｝隨機產生Xij，Xik兩個變異位，將兩個變異位交換得到

3．4 抗體重組算子

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

4 實驗結果與分析

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

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

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

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

問題上運行30次的結果比較，表2為幾種算法在不同TSP上的最優結果比較。

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

圖4 IHPSO最優路徑（30城市）

表1 Oliver30問題算法比較

表2 幾種算法最優解比較

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

5 結束語

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

［1］ 余伶俐，蔡自興．改進混合離散粒子群的多種優化策略算法［J］．中南大學學報（自然科學版），2009，40（4）：1047－1053．

［2］ 范會聯，李獻禮．基于近鄰關系求解 TSP的離散PSO算法［J］．計算機應用研究，2011，28（2）：511－513．

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

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

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

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

［7］ 王永貴，曲海成，趙婉彤．一種改進的遺傳算法在TSP問題中的應用［J］．遼寧工程技術大學學報（自然科學版），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］．系統仿真學報，2010，22（7）：1627－1631．

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