面向组合优化问题的一种全新遗传算法  

Improved genetic algorithm in solving TSP problem

作　　者：路平[1] 葛小伟[1] 侯黎强[1] 

机构地区：[1]西安卫星测控中心,陕西西安710043

出　　处：《计算机工程与设计》2006年第23期4579-4580,4603,共3页Computer Engineering and Design

摘　　要：提出了一种全新的遗传算法,并结合组合优化领域的典型难题——TSP问题,设计了编码、交叉及变异等遗传算子,克服了传统遗传算法的编码及遗传操作未能够充分反映及利用遗传信息的缺陷,较大程度上降低了传统遗传搜索中存在的盲目性,搜索速度得到明显提高。最后将本遗传算法应用于20个城市的TSP问题求解,计算结果证明了该遗传算法的收敛质量满足要求,收敛速度明显优于许多现有的算法。A new genetic algorithm is proposed to solve the problem of TSP （traveling salesman problem）. The genetic operators of coding and crossover and mutation are redesigned, and the drawbacks of that the coding and genetic operations of SGA could not fully reflect the genetic information are overcomed, and the randomicity of traditional genetic search is greatly reduced. The experimental results show the new GA has great advantage over many existing genetic algorithms.

关 键 词：遗传算法 TSP 组合优化 NP 全局搜索算法 人工智能 非线性问题 自适应搜索 

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