求解多目标TSP的降幂编码遗传算法  

Genetic algorithm with descending order code designed for solving multi-objective TSP

作　　者：汪勇[1] 徐琼[1] 王艳红[1] 张百栈 

机构地区：[1]武汉科技大学管理学院,湖北武汉430081 [2]元智大学信息管理系,台湾32026

出　　处：《计算机工程与设计》2014年第6期1988-1993,2003,共7页Computer Engineering and Design

基　　金：国家自然科学基金项目(51275365)

摘　　要：为解决采用结点序号编码的遗传算法在求解旅行商问题时,需要花费大量时间处理交叉和变异操作带来的重码问题,提出一种新的降幂编码遗传算法。根据结点位置信息,设计降幂编码与解码算法,并设计降幂编码的交叉和变异算子。建立一个多目标旅行商问题模型,分析每一代个体适应度值的差异性,采用主成分分析法确定路程和费用权重。实验结果表明,降幂编码遗传算法解决了重码问题,计算效率、收敛速度和求解精度较遗传算法有显著改善。To solve traveling salesman problem using genetic algorithm with the node serial number directly,it needed a lot of time to deal with the duplicated code caused by crossover and mutation.A new genetic algorithm with descending order code was put forward.According to the node location information,the encoding and decoding methods were designed,the operators of crossover and mutation in this code system were constructed.A multi-objective model of traveling salesman problem was established.The weights of distance and cost were determined by means of principal components analysis through comparing with the fitness diversity of individual in each generation.Experiments showed that the proposed algorithm could solve the problem of duplicated code,it had great improvement on calculation efficiency,convergence rate and precision of solution.

关 键 词：算法理论 降幂编码 遗传算法 旅行商问题 多目标决策 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]