基于混合粒子群算法求解TSP問題

侯 穎，何建軍，米 閣，謝日華，何汶?。ǔ啥祭砉ご髮W信息科學與技術學院，610059）

基于混合粒子群算法求解TSP問題

侯 穎，何建軍，米 閣，謝日華，何汶俊
（成都理工大學信息科學與技術學院，610059）

遺傳算法是研究TSP問題中最為廣泛的一種算法，它具有全局搜索的能力。而粒子群算法收斂速度較快，但容易造成局部最優(yōu)的情況。本文基于遺傳算法的交叉變異設計了混合粒子群算法，通過對TSP問題求解分析，證實該方法提高了標準粒子群的搜索能力，獲得了較高的收斂速度和近似最優(yōu)解。

旅行商問題；遺傳算法；粒子群算法；混合粒子群算法

1　基本算法原理簡介

1.1遺傳算法概述

遺傳算法的構成要素 ：染色體編碼方法：TSP問題中主要采用符號編碼；個體適應度評價：遺傳算法中使用適應度函數(shù)評估個體的適應性；遺傳算子：選擇算子—比例選擇算子、交叉運算—部分映射雜交、變異運算—變異算子或均勻變異算子；基本遺傳算法的運行參數(shù)：NIND：群體大小、MAXGEN：遺傳運算的終止進化迭代數(shù)、：交叉概率、：變異概率。

1.2粒子群算法概述

在實際生物中，群居種群共同進行覓食、御敵，這種行為就是我們所說的群體智能。學者們通過對自然界中鳥群活動的模擬，建立了粒子群優(yōu)化算法。

2　基于遺傳算法原理改進的混合粒子群算法

在標準的粒子群算法中，個體會根據(jù)個體歷史最優(yōu)和群體歷史最優(yōu)來更新自己的加速度方向，使得自身往這兩個方向偏離，使得群體中的個體越來越集中。但是有可能會使得粒子在局部最優(yōu)解的周圍徘徊而使得群體無法獲得更好的近似解?；旌狭Ｗ尤核惴ú捎昧诉z傳算法的部分思想，在進化過程中加入了交叉和變異，粒子將個體最優(yōu)解和群體最優(yōu)解進行交叉，再通過變異來搜索最優(yōu)解，這樣雖然不能完全避免粒子群算法造成局部最優(yōu)的情況，但提高了該算法的全局搜索功能。

3　基于混合粒子群算法求解TSP問題

3.1TSP問題建模

3.2算法流程

求解TSP問題的混合粒子群算法。算法的執(zhí)行步驟如下：首先初始化粒子群種群，構造適應函數(shù)計算個體適應值，根據(jù)適應值更新粒子，將個體中的最優(yōu)個體和群體最優(yōu)個體進行交叉，從而得到變異后更加適應環(huán)境的粒子，直到進化次數(shù)終止。

3.3MATLAB程序實現(xiàn)

①采用混合粒子群算法規(guī)劃TSP路徑

②優(yōu)化后的路線最優(yōu)解：3-＞10-＞4-＞7-＞1-＞8-＞6-＞9-＞5-＞2-＞3，總距離：27.488。通過測試，在城市數(shù)目較少時，此混合粒子群算法能得到真實最優(yōu)解。當都市數(shù)目增加到20個，最優(yōu)解如圖2所示，總距離：48.54。此時，該算法無法獲得相同的近似最優(yōu)解，但它們所得到的結果已經(jīng)非常接近了，說明該混合粒子群算法也是行之有效的。

圖 最優(yōu)解路線圖1（20個都市）

③經(jīng)測試，本例中混合粒子群算法的收斂速度大概為20代—30代之間，該算法的收斂速度與初始解存在一定關系，但是最終還是能完成對全局空間的搜索。

4　總結

比較混合粒子群算法不同進化次數(shù)下的最優(yōu)解以及收斂速度，發(fā)現(xiàn)該算法基本在200代以后才能完成收斂，并且隨著隨著進化次數(shù)增加，最優(yōu)解越發(fā)優(yōu)秀。對于收斂速度，在上述測試中，可以看出遺傳算法的收斂速度比混合粒子群算法的收斂速度快。對于CPU占用時間，在目標城市數(shù)為10測試中，遺傳算法占用29.634s，混合粒子群算法占用13.591s，可以看出混合粒子群算法的CPU占用時間更少。所以基于遺傳算法改進粒子群算法來求解TSP問題是行之有效的。

［1］魏秀業(yè)，潘宏俠.粒子群優(yōu)化及智能故障診斷［M］.北京：國防工業(yè)出版社，2010.7.

侯穎（1992.09）女，碩士研究生，成都理工大學信息科學與技術學院，研究方向：計算機技術。

Hybrid particle swarm optimization algorithm for solving TSP problem

Hou Ying，He Jianjun，Mi Ge，Xie Rihua，He Wenjun
（Chengdu University of Technology，College of information science and technology， 610059）

Genetic algorithm is the most widely used one in the research of TSP problem.It has the ability of global search.But the particle swarm algorithm converges quickly，but it is easy to cause the local optimum.The genetic algorithm crossover and mutation based on design hybrid particle swarm optimization algorithm，through the analysis to solve traveling salesman problem（TSP），confirmed that the method improves the search ability of standard particle swarm optimization，higher speed of convergence and approximate optimal solution is obtained.

traveling salesman problem；genetic algorithm；particle swarm optimization；hybrid particle swarm optimization