求解旅行商问题的一个新的单亲遗传算法  

A Novel Partheno-Genetic Algorithm for TSP

作　　者：韩丽霞[1] 王宇平[2] 

机构地区：[1]西安电子科技大学理学院,陕西西安710071 [2]西安电子科技大学计算机学院,陕西西安710071

出　　处：《计算机工程与科学》2006年第2期72-73,共2页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60374063)

摘　　要：本文提出了求解旅行商问题(TSP)的一个新的单亲遗传算法(PGA)。首先,定义了‘好’基因段的概念,并据此设计了一种新的、有效的基因段换位算子;同时,为提高该算子的搜索能力,结合一个局部搜索技术来改进该算子;然后,在此基础上提出了一个求解旅行商问题的一个新的单亲遗传算法。计算机仿真结果表明,该算法是有效的。A novel partheno-genetie algorithm for TSP is proposed in this paper. First, an efficient gene exchange operator is designed. In order to enhance its ability of exploration, a local search schema is integrated into the gene exchange operator. Then, a novel and effective partheno-genetic algorithm for TSP is presented based on these. Finally, the simulation results show the efficiency of the proposed algorithm.

关 键 词：旅行商问题 单亲遗传算法 局部搜索 基因换位算子 

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