一种改进的遗传算法解决旅行商问题  

Modified Genetic Algorithm for Traveling Salesman Problem

作　　者：杨照选[1] 贺建民[2] 周晓兰 

机构地区：[1]解放军理工大学通信工程学院,江苏南京210007 [2]解放军理工大学指挥自动化学院,江苏南京210007 [3]总参军训和兵种部自动化工作站,北京100851

出　　处：《解放军理工大学学报（自然科学版）》2004年第5期30-33,共4页Journal of PLA University of Science and Technology(Natural Science Edition)

摘　　要：标准遗传算法在解决旅行商问题时效率不高 ,容易陷于局部最优解。为了解决这一问题 ,提出了一种改进的遗传算法。改进后的算法在选择操作时 ,采取了精英个体保留策略和锦标赛方法 ,扩大染色体的选择范围 ,加大了适应度好的染色体被选中的概率 ;交叉操作时加入父染色体中边的信息 ;在参数选择上 ,使交叉概率和变异概率与染色体的个体适应值联系 ,保护适应度好的染色体进入下一代。用程序实现了两种算法 ,通过比较 。Traditional genetic algorithms have low efficiency and tend to be trapped by local optimizations. An improvement is proposed to solve this problem. Elitism and 2-tournament selection are used to expand the selection of chromosomes, so that the ones with better fitness have more chances to be selected. Crossover operation adds the edge information of parents chromosomes. Crossover and multation probability are related to individual fitness, and this guaratees that chromosomes with better fitness can survive into the next generation. Two algorithms are implementd. Experiments show that the new algorithm improvs the efficiency of the traveling salesman problem.

关 键 词：旅行商问题 模式定理 标准遗传算法 改进遗传算法 

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