求解旅行商问题的改进离散竞争进化算法  

Improved Discrete Competition Evolutionary Algorithm for Solving Traveling Salesman Problems

作　　者：王洁[1,2] 彭召升[2] 刘乐[3] 

机构地区：[1]中国海洋大学信息科学与工程学院,青岛266071 [2]中国船舶重工集团公司第719研究所,武汉430064 [3]山东师范大学管理与经济学院,济南250014

出　　处：《计算机与数字工程》2009年第12期34-37,共4页Computer & Digital Engineering

摘　　要：在分析竞争进化算法原理和特点的基础上,针对旅行商问题的求解,提出一种改进的离散竞争进化算法(IDCE),其中采取三项关键策略:根据个体适值排名计算变异次数、实施逆转子变异算子和并行贪心机制执行多次子变异,目的在于提高算法的全局搜索能力和单位时间内的进化效率。IDCE算法跟另两种离散竞争进化算法对于4个对称旅行商问题算例进行了性能对比,实验结果显示,在解的整体水平、最好解质量以及求解效率上,IDCE算法都优于另两种算法。On the basis of analyzing competition evolutionary （CE） algorithm＇s principle and characters, aiming at solving traveling salesman problems（TSP）, an improved discrete competition evolutionary algorithm（IDCE） was presented, which applied three critical strategies： computing mutation times by individual＇s fitness rank; doing inverse mutation operator; implementing sub-mutations with parallel greed mechanism. Performance comparison of IDCE for four TSP Benchmarks was provided against two other existing DCEs. Experimental results showed that IDCE algortithm outper- formed two other DCEs in terms of overall quality of solutions, best solution obtained and optimization efficiency.

关 键 词：竞争进化算法 竞争推动力 旅行商问题 子变异 嵌套策略 

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