面向旅行商问题的一种改进遗传算法  

An Improved Genetic Algorithm for Traveling Salesman Problem

作　　者：丁华福[1] 刘晓路[1] 唐远新[1] 石福斌[1] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,黑龙江哈尔滨150080

出　　处：《计算机技术与发展》2011年第6期51-54,共4页Computer Technology and Development

基　　金：黑龙江省教育科研项目(11531049)

摘　　要：针对传统遗传算法解决组合优化领域的典型难题——旅行商问题时存在的缺陷与不足,对传统遗传算法加以改进。引入了种群熵和基因座多样性来测度种群的多样性,并利用求得的测度值修改了个体的适应度,达到了预期目的。还提出启发式交叉算子、二分局部搜索、自适应遗传参数,使该算法在提高搜索效率与解质量方面取得了综合平衡。在算法的仿真和测试中,改进后的算法明显优于传统的遗传算法。这表明,该算法具有良好的可行性和实用性。By analyzing the deficiency of traditional genetic algorithm in solving the traveling salesman problem,one representative problem of the combination optimization,the algorithm structure of traditional genetic algorithm was improved.Entropy and the locus of population diversity are introduced to measure the population diversity in this paper,and the measure values obtained are used to modify the fitness of the individual to achieve the desired purpose.Also introduces self-adjust adapt value and proposing heuristic crossover operation,second detach local searching and self-adapt genetic parameter,the algorithm achieved a balance between quality and efficiency.According to the analysis and test,the improved genetic algorithm can get the better result than the traditional genetic algorithm.This shows that the method has better feasibility and practicability.

关 键 词：遗传算法 种群多样性 启发式交叉算子 二分局部搜索 自适应遗传参数 

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