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

An Improved Genetic Algorithm for Solving Travel Salesman Problem

作　　者：刘荷花[1] 崔超[2] 陈晶[3] 

机构地区：[1]太原大学计算机系,山西太原030009 [2]齐齐哈尔大学应用技术学院,黑龙江齐齐哈尔161005 [3]齐齐哈尔市第一中学,黑龙江齐齐哈尔161005

出　　处：《北京理工大学学报》2013年第4期390-393,共4页Transactions of Beijing Institute of Technology

基　　金：国家自然科学基金资助项目(60475022);山西省科技厅软科学资助项目(2011041022-03)

摘　　要：针对在解决旅行商问题时标准遗传算法效率不高,很容易陷入局部最优解的问题,提出了一种改进的遗传算法.根据种群个体的多样性和分布情况,提出了判定遗传算法截止代数的方法.研究结果表明,通过加入了初始化信息,改进交差算子,可提高遗传算法的精确性和收敛性.Standard genetic algorithm in solving the traveling salesman problem （TSP） is not efficient since it is easy to fall into local optimal solution. To improve the efficiency of genetic algorithm, this paper presents an improved genetic algorithm. First, according to the diversity of individuals and the population distribution, the method to determine the cut-off algebraic of genetic algorithm is proposed. Second, by adding initialization information and improving cross- operator, the accuracy and convergence of the genetic algorithm could be improved.

关 键 词：遗传算法 旅行商(TSP) 截止代数 交叉算子 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]