变异概率对PSO算法求解TSP问题的影响研究

刘衍民,赵庆祯,罗东升

(1.遵义师范学院数学系,贵州遵义563002;2.山东师范大学管理与经济学院,山东济南250014)

变异概率对PSO算法求解TSP问题的影响研究

刘衍民1,2,赵庆祯2,罗东升1

(1.遵义师范学院数学系,贵州遵义563002;2.山东师范大学管理与经济学院,山东济南250014)

提出了一种求解旅行商问题的改进粒子群算法,该算法引入了求解离散问题的学习机制和变异策略以提升粒子群算法求解旅行商问题的效率.通过对两个经典的测试问题(Oliver30和burma14)的仿真研究,表明不同变异概率对算法的影响,当变异概率为0.5时,算法的运行效率最高.

旅行商问题;粒子群算法;变异概率

粒子群算法(Particle Swarm Optimizer,PSO)是一种基于种群的进化算法.PSO与遗传算法类似,都是基于迭代的优化工具,即初始化一组随机解,通过迭代搜寻最优值.但粒子群算法没有遗传算法采用的交叉和变异策略,而是在解空间追随最优粒子进行搜索.与遗传算法相比,PSO操作简单,易于实现,没有许多参数需要调整.因此PSO算法已广泛应用于单目标,多目标,约束优化问题中.

TSP(Traveling Salesman Problem)是一个著名的NP完全问题,目前求解TSP问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、蚁群算法等.由于PSO快速收敛的特点,许多研究者已经提出将PSO算法用于求解TSP问题[1-3].本文是在前人研究的基础上,结合遗传算法的思想,提出的一种带有变异策略的PSO算法来求解旅行商问题.

1 相关背景

1.1 基本粒子群算法

Clerc和Kennedy[4]根据粒子邻居拓扑结构的不同,把粒子群算法分为局部版本粒子群算法 (LPSO)和全局版本粒子群算法 (GPSO).它们的区别主要在于学习样本的选择不同.针对不同的学习样本,种群中粒子的位置和速度更新过程,可以按照等式(1)(2)进行.

3 仿真实验

为了测试算法的有效性和变异概率的影响，选取Oliver30和burma14作为仿真数据,数据来源于http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.参数设置如下：种群规模30，变异概率分别取p=0.1,0.3,0.5,0.7,0.9；迭代次数为100；每个实验独立运行 30次;运行环境为ThinkPad-SL400电脑上应用Matlab R2008b软件.图2给出了不同变异概率下的收敛特征图,图3给出了最优路径图,表1给出了不同变异概率下的测试结果.可以看出变异概率对算法有一定的影响,当变异概率p=0.5时算法取得了最好的结果.

表1 不同变异概率下的测试结果

4 结束语

本文研究了一种带有变异策略的PSO算法求解TSP问题,并且探讨了不同变异概率对算法的影响.通过Oliver30和burma14仿真实验说明,当变异概率p=0.5时,算法获得了最好的解.将来的工作主要集中于将该算法延伸到求大规模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]邹鹏,周智,江贺.求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析[J].计算机学报,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.

（责任编辑：朱 彬）

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

贵州省教育厅社科项目(2007018)；遵义师范学院基础教育研究项目(基07015,基07017)；遵义师范学院科研资金资助项目(2007018)

刘衍民,男,黑龙江牡丹江人,遵义师范学院数学系讲师,在读博士,从事运筹学理论、进化计算的研究。