基于近邻关系求解TSP的离散PSO算法  

Discrete particle swarm optimization for TSP based on neighborhood

作　　者：范会联[1] 李献礼[2] 

机构地区：[1]长江师范学院数学与计算机学院,重庆408100 [2]长江师范学院网络中心,重庆408100

出　　处：《计算机应用研究》2011年第2期511-513,544,共4页Application Research of Computers

基　　金：重庆市教委科学技术研究项目(KJ091309)

摘　　要：针对NP-hard组合优化问题,提出一种基于启发因子的自适应混合离散粒子群算法对其进行求解。通过改进离散粒子群运动方程,并加入启发因子,从而提高算法的收敛性和稳定性;依据粒子多样性的动态变化,引入自适应扰动算子,以保持种群进化能力。该算法对低、中、高维的TSP数据仿真结果表明,与其他混合离散粒子群算法相比,具有更好的全局收敛性和稳定性。Aiming at the NP-hard combinatorial optimization problem,this paper proposed a hybrid discrete particle swam optimization（DPSO）algorithm based on neighborhood.In order to improve the algorithm stability and accelerate the convergence speed,updated kinetic equations for discrete particle swarm optimization and introduced a mechanism of heuristic factor into this algorithm.Introduced adaptive perturbation factor according to the population heterogeneity to keep particle swarm evolutional capability.Experiments on low and high-dimensional data in TSPLIB show that,comparing with others hybrid discrete particle swarm,the proposed algorithm can improve the search performance significantly no matter in convergent speed or precision.

关 键 词：离散粒子群优化 旅行商问题 启发因子 邻域交换 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]