解决TSP问题的局部调整离散微粒群算法  

Local adjusting discrete particle swarm optimization algorithm for traveling salesman problem

作　　者：王蒙[1] 介婧[1] 曾建潮[1] 董殿敏[1] 

机构地区：[1]太原科技大学系统仿真与计算机应用研究所,山西太原030024

出　　处：《计算机工程与设计》2009年第21期4936-4938,共3页Computer Engineering and Design

基　　金：国家自然科学基金项目(60674104);山西省自然科学基金项目(2007011046)

摘　　要：微粒群算法提出以来一直不能较好的解决离散及组合优化问题,针对这个问题,通过对微粒群算法的优化机理的分析,对原有的微粒群进化方程中的速度和位置的更新等进行重新的定义,同时提出一种具有自适应能力的惯性因子,使其适合解决TSP这样的组合优化问题。针对过去的离散算法整体调整容易形成对路径的破坏这一缺点,在重新定义的算法上加入局部调整的策略,形成一种局部调整的离散微粒群算法(local adjustive discrete PSO,LADPSO),通过在ch31和eil51上的试验,证明了该算法在解决这一问题上是可行的。Particle swarm optimization （PSO） is generic heuristic algorithm based on swarm intelligence. It is applied to many practical continuous optimization problems. But it is not extended to solve discrete and combinatorial optimization problem effectively. For solving the problem, particle＇ s position, velocity and their operation rules are redefined, at the same time, this inertial operator is put forward which has the self-adaptive ability. For the past discrete algorithm＇ s shortcomings in damaging the path caused by adjusting the overall formation, this new algorithm adds a local adjustment strategy, then forming a local adjustment discrete PSO algorithm. Through the test on Ch31 and eil51, it proves new algorithm in solving TSP is feasible.

关 键 词：离散微粒群算法 旅行商问题 局部调整 组合优化 自适应 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]