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

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

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

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

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

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

1　基本算法原理簡介

1.1遺傳算法概述

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

1.2粒子群算法概述

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

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

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

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

3.1TSP問題建模

3.2算法流程

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

3.3MATLAB程序?qū)崿F(xiàn)

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

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

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

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

4　總結(jié)

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

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

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

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