變異概率對PSO算法求解TSP問題的影響研究

劉衍民,趙慶禎,羅東升

(1.遵義師范學(xué)院數(shù)學(xué)系,貴州遵義563002;2.山東師范大學(xué)管理與經(jīng)濟(jì)學(xué)院,山東濟(jì)南250014)

變異概率對PSO算法求解TSP問題的影響研究

劉衍民1,2,趙慶禎2,羅東升1

(1.遵義師范學(xué)院數(shù)學(xué)系,貴州遵義563002;2.山東師范大學(xué)管理與經(jīng)濟(jì)學(xué)院,山東濟(jì)南250014)

提出了一種求解旅行商問題的改進(jìn)粒子群算法,該算法引入了求解離散問題的學(xué)習(xí)機(jī)制和變異策略以提升粒子群算法求解旅行商問題的效率.通過對兩個(gè)經(jīng)典的測試問題(Oliver30和burma14)的仿真研究,表明不同變異概率對算法的影響,當(dāng)變異概率為0.5時(shí),算法的運(yùn)行效率最高.

旅行商問題;粒子群算法;變異概率

粒子群算法(Particle Swarm Optimizer,PSO)是一種基于種群的進(jìn)化算法.PSO與遺傳算法類似,都是基于迭代的優(yōu)化工具,即初始化一組隨機(jī)解,通過迭代搜尋最優(yōu)值.但粒子群算法沒有遺傳算法采用的交叉和變異策略,而是在解空間追隨最優(yōu)粒子進(jìn)行搜索.與遺傳算法相比,PSO操作簡單,易于實(shí)現(xiàn),沒有許多參數(shù)需要調(diào)整.因此PSO算法已廣泛應(yīng)用于單目標(biāo),多目標(biāo),約束優(yōu)化問題中.

TSP(Traveling Salesman Problem)是一個(gè)著名的NP完全問題,目前求解TSP問題的主要方法有模擬退火算法、遺傳算法、啟發(fā)式搜索法、蟻群算法等.由于PSO快速收斂的特點(diǎn),許多研究者已經(jīng)提出將PSO算法用于求解TSP問題[1-3].本文是在前人研究的基礎(chǔ)上,結(jié)合遺傳算法的思想,提出的一種帶有變異策略的PSO算法來求解旅行商問題.

1 相關(guān)背景

1.1 基本粒子群算法

Clerc和Kennedy[4]根據(jù)粒子鄰居拓?fù)浣Y(jié)構(gòu)的不同,把粒子群算法分為局部版本粒子群算法 (LPSO)和全局版本粒子群算法 (GPSO).它們的區(qū)別主要在于學(xué)習(xí)樣本的選擇不同.針對不同的學(xué)習(xí)樣本,種群中粒子的位置和速度更新過程,可以按照等式(1)(2)進(jìn)行.

3 仿真實(shí)驗(yàn)

為了測試算法的有效性和變異概率的影響，選取Oliver30和burma14作為仿真數(shù)據(jù),數(shù)據(jù)來源于http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.參數(shù)設(shè)置如下：種群規(guī)模30，變異概率分別取p=0.1,0.3,0.5,0.7,0.9；迭代次數(shù)為100；每個(gè)實(shí)驗(yàn)獨(dú)立運(yùn)行 30次;運(yùn)行環(huán)境為ThinkPad-SL400電腦上應(yīng)用Matlab R2008b軟件.圖2給出了不同變異概率下的收斂特征圖,圖3給出了最優(yōu)路徑圖,表1給出了不同變異概率下的測試結(jié)果.可以看出變異概率對算法有一定的影響,當(dāng)變異概率p=0.5時(shí)算法取得了最好的結(jié)果.

表1 不同變異概率下的測試結(jié)果

4 結(jié)束語

本文研究了一種帶有變異策略的PSO算法求解TSP問題,并且探討了不同變異概率對算法的影響.通過Oliver30和burma14仿真實(shí)驗(yàn)說明,當(dāng)變異概率p=0.5時(shí),算法獲得了最好的解.將來的工作主要集中于將該算法延伸到求大規(guī)模TSP問題.

[1]Lin S,Kernighan，B W.An Effective Heuristic Algorithm for the Traveling-salesman Problem [J].Operations Research,1973,21(2):498-516.

[2]鄒鵬,周智,江賀.求解旅行商問題的循環(huán)局部搜索算法的運(yùn)行時(shí)間和性能分布分析[J].計(jì)算機(jī)學(xué)報(bào),2006,29(1):92-99.

[3]Shi X H，Liang Y C.Particle swarm optimization-based algorithms for TSP and generalized TSP[J].Information Processing Letters,2007,103(5):169-176.

[4]Clerc M，Kennedy J.The particle swarm-explosion,stability,and convergence in a multidimensional complex space[J].IEEE Transactions on Evolutionary Computation,2002,2(6):58–73.

（責(zé)任編輯：朱 彬）

Effect Research on Mutation Probability of Particle Swarm optimizer for Solving Traveling Salesman Problem

LIU Yan-min1,2,ZHAO Qing-zhen2,LUO Dong-Sheng1
(1.Department of math,Zunyi Normal College,Zunyi 563002,China;2.School of Management and Economics,Shandong Normal University,Jinan,250014,China.)

An improved particle swarm optimizer for solving Traveling Salesman Problem (TSP)is proposed,in which the learning strategy of discrete problem and mutation operation are introduced to improve the algorithm efficiency.Finally,the different mutation probability is analyzed by two typical test problems(Oliver30 and burma14)and the conclusion of experiment shows that the probability p=0.5 has the best result.

Particle Swarm Optimizer(PSO);Traveling Salesman Problem(TSP);Mutation probability

TP301

A

1009-3583（2010）-06-0099－03

2010-09-12

貴州省教育廳社科項(xiàng)目(2007018)；遵義師范學(xué)院基礎(chǔ)教育研究項(xiàng)目(基07015,基07017)；遵義師范學(xué)院科研資金資助項(xiàng)目(2007018)

劉衍民,男,黑龍江牡丹江人,遵義師范學(xué)院數(shù)學(xué)系講師,在讀博士,從事運(yùn)籌學(xué)理論、進(jìn)化計(jì)算的研究。