摘要
为解决采用结点序号编码的遗传算法在求解旅行商问题时,需要花费大量时间处理交叉和变异操作带来的重码问题,提出一种新的降幂编码遗传算法。根据结点位置信息,设计降幂编码与解码算法,并设计降幂编码的交叉和变异算子。建立一个多目标旅行商问题模型,分析每一代个体适应度值的差异性,采用主成分分析法确定路程和费用权重。实验结果表明,降幂编码遗传算法解决了重码问题,计算效率、收敛速度和求解精度较遗传算法有显著改善。
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.
出处
《计算机工程与设计》
CSCD
北大核心
2014年第6期1988-1993,2003,共7页
Computer Engineering and Design
基金
国家自然科学基金项目(51275365)
关键词
算法理论
降幂编码
遗传算法
旅行商问题
多目标决策
algorithmic theory
descending order code
genetic algorithm
traveling salesman problem
multi-objective decision
