一种求解旅行商问题的新型帝国竞争算法  

A new imperialist competitive algorithm for solving TSP problem

作　　者：张鑫龙[1] 陈秀万[1] 肖汉[1] 李伟[1] 

机构地区：[1]北京大学地球与空间科学学院,北京100871

出　　处：《控制与决策》2016年第4期586-592,共7页Control and Decision

基　　金：国家科技支撑计划项目(2011BAH05B08)

摘　　要：帝国竞争算法是一种已在连续优化问题上取得较好效果的新型社会政治算法.为了使该算法更好地应用于离散型组合优化问题,提出一种求解旅行商问题的新型帝国竞争算法.在传统算法的基础上,改变初始帝国的生成方式;同化过程采取替换重建方式,以提升求解质量;革命过程中引入自适应变异算子,以增强搜索能力;殖民竞争过程中调整了殖民地分配方式;算法加入帝国增强过程,以加快寻化速度.实验结果表明,新型帝国竞争算法求解质量高、收敛速度快.Imperialist competitive algorithm is a new socio-political motivated strategy, which has better performance in continuous optimization problems. In order to apply this method to complex discrete combinatorial optimization problems appropriately, an improved imperialist competitive algorithm for solving traveling salesman problem is proposed. Based on the traditional algorithm, the proposed algorithm changes the way of forming initial empires. In the assimilation process, solutions are improved by a replacement-reconstruction policy. Then a method of adaptive adjustment of mutation probabilities is introduced in the revolution process, which enhances the search capability of the proposed algorithm. The method of colony allocation is adjusted in the imperialist competition process. An imperialist improvement mechanism is presented in order to enhance the optimization speed. The results of a set of TSP instances demonstrate the superiority of the proposed algorithm in both solution quality and convergence speed.

关 键 词：旅行商问题 帝国竞争算法 遗传算法 

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