求解TSP问题的自逃逸混合离散粒子群算法研究

通过对旅行商问题（TSP）局部最优解与个体最优解、群体最优解之间的关系分析,针对DPSO算法易早熟和收敛慢的缺点,重新定义了离散粒子群DPSO的速度、位置公式,结合生物界中物种在生存密度过大时个体会自动分散迁徙的特性和局部搜索算法（SEC）后,提出了一种新的自逃逸混合离散粒子群算法（SEHDPSO）.自逃逸思想是一种确定性变异操作,能使算法中陷入局部极小区域的粒子通过自逃逸行为进行全局寻优,从而克服算法易早熟的缺陷.仿真结果表明,SEHDPSO算法比混合蚁群算法（ACS＋2-OPT）具有更好的收敛性和搜索效率.

Study of a Self-Escape Hybrid Discrete Particle Swarm Optimization for TSP

To deal with the problem of premature convergence and slow search speed,a new algorithm which named the discrete particle swarm optimization algorithm(DPSO)has been proposed based on redefining speed and position of the DPSO,for solving the symmetrical traveling salesman problem(TSP)in this paper.We change the algorithm to self-escape hybrid discrete particle swarm optimization(SEHDPSO)after combining a strategy called self-escape method and local search method.The SEHDPSO uses to explore the global minima thoroughly,which derives from the phenomena that some organisms can escape dynamically from the original cradle when they find the survival density is too high to live.The subsequent experiment result shows that the SEHDPSO can not only speed up the convergence significantly but also solve the premature problem effectively.