| 一种改进的遗传算法在TSP问题中的应用 |
| |
| 引用本文： | 王永贵,曲海成,赵婉彤.一种改进的遗传算法在TSP问题中的应用[J].辽宁工程技术大学学报(自然科学版),2011,30(2):263-267. |
| |
| 作者姓名： | 王永贵 曲海成 赵婉彤 |
| |
| 作者单位： | 1. 辽宁工程技术大学,软件学院,辽宁,葫芦岛,125105
2. 中共鞍山市委党校,辽宁,鞍山,114003 |
| |
| 基金项目： | 辽宁省教育厅基金资助项目(2009A350) |
| |
| 摘 要： | 为了解决旅行商(TSP)不能够在多项式时间内求得最优解的问题,从仿生学的角度入手,重新设计了从问题域到算法域的编码和解码方法,应用"排列法"来初始化种群;并设计了两种染色体操作算子:顺序交换算子和合法交叉算子,保证了种群在进化过程中染色体的合法性;在种群进化选择方面,设计了一个新的更加仿生的选择算子——"灾难算子",并与经典算法的"轮盘赌"选择法相结合,作为改进算法的选择算子,进一步提高了算法的收敛速度。实验表明,改进后的遗传算法能更准确地找到最优解。
|
| 关 键 词： | NP完全问题 遗传算法 排列法 顺序交换算子 合法交叉算子 灾难算子 |
Research on an improved Genetic Algorithm for TSP problem |
| |
| WANG Yonggui,QU Haicheng,ZHAO Wantong.Research on an improved Genetic Algorithm for TSP problem[J].Journal of Liaoning Technical University (Natural Science Edition),2011,30(2):263-267. |
| |
| Authors: | WANG Yonggui QU Haicheng ZHAO Wantong |
| |
| Institution: | WANG Yonggui1,QU Haicheng1,ZHAO Wantong2(1.School of Software,Liaoning Technical University,Huludao 125105,China,2.Party School,CPC Anshan Committee,Anshan 114003,China) |
| |
| Abstract: | Traveling Salesman Problem(TSP) cannot be solved with an optimal solution in an algorithm within the polynomial time.In order to solve this problem,from the aspect of bionics,this study redesigns the encoding and decoding methods from problem domain to algorithm domain;uses permutation method to initialize the population;and designs two kinds of chromosomes operator: 1) the order swapping operator and 2) the legal crossing operator to ensure the legitimacy of chromosomes for the populations in evolutionary ... |
| |
| Keywords: | NPC problem genetic algorithm permutation method order swapping operator legal crossing operator disaster operator |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
