文化基因算法求解TSP问题的研究
|
摘要
TSP是组合优化问题中著名的NP-hard问题。针对粒子群算法求解离散的TSP问题收敛速度慢,求解精度低,易于陷入局部最优和模拟退火算法的性能与参数初始值有关及参数敏感等不足,提出了将改进的粒子群算法作为全局搜索策略,改进的模拟退火算法作为局部搜索策略的文化基因算法。介绍了两种算法的协同方法,定义了局部搜索邻域的确定以及在新种群产生中引入自组织随机移民策略。仿真结果表明,改进算法在求解TSP问题中具有很快的收敛速度,且能搜索到最优解。
The TSP problem is famous NP- hard problem in combinatorial optimization. The this paper,we put forward an improved particle swarm optimization( pso) as a global searching and a simulated annealing algorithm as a local searching,which we called Memetic algorithm. We introduced two algorithms' synergism,defined the determination of neighborhood and introduced self- organizing random immigrants strategy to generate new population.The simulation results show that the proposed algorithm has fast convergence speed in solving TSP problem,and can search the optimal solution.
The TSP problem is famous NP- hard problem in combinatorial optimization. The this paper,we put forward an improved particle swarm optimization( pso) as a global searching and a simulated annealing algorithm as a local searching,which we called Memetic algorithm. We introduced two algorithms' synergism,defined the determination of neighborhood and introduced self- organizing random immigrants strategy to generate new population.The simulation results show that the proposed algorithm has fast convergence speed in solving TSP problem,and can search the optimal solution.
引文
[1]胡银厚.求解TSP算法的研究与改进[D].郑州大学,2012.
[2]段海滨,张祥银,徐春芳.仿生智能计算[M].北京:科学出版社,2011-1.
[3]曾建潮,崔志华.微粒群优化算法[M].北京:科学出版社,2011-4.
[4]宋莉莉,张宏立.应用改进粒子群算法辨识Hammerstein模型[J].计算机仿真,2013-3:269-272.
[5]J Kennedy,R C Eberhart.Particle Swarm Optimization//Interna-tional Conferenc on Neural Networks[C].Perth,Australia,IEEE,1995:1942-1948.
[6]高志宇,孙新娟.基于模拟退火优化的磁共振图像重建优化仿真[J].计算机仿真,2013-11:388-391.
[7]曲晓丽,潘昊,柳向斌.旅行商问题的一种模拟退火算法求解[J].现代电子技术,2007,18:78-79,82.
[8]王洪峰,汪定伟,黄敏.动态环境中的Memetic算法[J].控制理论与应用,2010-8:1060-1068.
[9]Tinos R Yangs.A self-organizing random immigrants genetic algorithm for dynamic optimization problems[J].Genet Program Evolvable Mach,2007,8(3):225-286.
[10]周永权,黄正新.求解TSP的人工萤火虫群优化算法[J].控制与决策,2012-12:1816-1821.
[11]蔡之华,彭锦国,高伟,魏巍,康立山.一种改进的求解TSP问题的演化算法[J].计算机学报,2005-5:823-828.
[12]冀俊忠,黄振,刘椿年,代启国.基于多粒度的旅行商问题描述及其蚁群优化算法[J].计算机研究与发展,2010-3:434-444.
[2]段海滨,张祥银,徐春芳.仿生智能计算[M].北京:科学出版社,2011-1.
[3]曾建潮,崔志华.微粒群优化算法[M].北京:科学出版社,2011-4.
[4]宋莉莉,张宏立.应用改进粒子群算法辨识Hammerstein模型[J].计算机仿真,2013-3:269-272.
[5]J Kennedy,R C Eberhart.Particle Swarm Optimization//Interna-tional Conferenc on Neural Networks[C].Perth,Australia,IEEE,1995:1942-1948.
[6]高志宇,孙新娟.基于模拟退火优化的磁共振图像重建优化仿真[J].计算机仿真,2013-11:388-391.
[7]曲晓丽,潘昊,柳向斌.旅行商问题的一种模拟退火算法求解[J].现代电子技术,2007,18:78-79,82.
[8]王洪峰,汪定伟,黄敏.动态环境中的Memetic算法[J].控制理论与应用,2010-8:1060-1068.
[9]Tinos R Yangs.A self-organizing random immigrants genetic algorithm for dynamic optimization problems[J].Genet Program Evolvable Mach,2007,8(3):225-286.
[10]周永权,黄正新.求解TSP的人工萤火虫群优化算法[J].控制与决策,2012-12:1816-1821.
[11]蔡之华,彭锦国,高伟,魏巍,康立山.一种改进的求解TSP问题的演化算法[J].计算机学报,2005-5:823-828.
[12]冀俊忠,黄振,刘椿年,代启国.基于多粒度的旅行商问题描述及其蚁群优化算法[J].计算机研究与发展,2010-3:434-444.