一种求解TSP问题的单亲遗传算法  

A Partheno Genetic Algorithm for Traveling Salesman Problem

作　　者：王斌[1] 李元香[1] 王治[2] 

机构地区：[1]武汉大学软件工程国家重点实验室,武汉430072 [2]上海贝尔阿尔卡特股份有限公司,上海200070

出　　处：《计算机科学》2003年第5期73-75,共3页Computer Science

基　　金：国家自然科学基金(69703011);教育部骨干教师资助计划

摘　　要：In this paper, a kind of Partheno Genetic Algorithm(PGA)based on Path Representation scheme is pro-posed for solving Traveling Salesman Problem(TSP). This algorithm employs only mutation and selection operatorsto produce the offspring, instead of traditional crossover operator. A specific mutation operator is designed combiningthe insertion operator with inversion operator, which ensures its strong searching capability. This algorithm simu-lates the recurrence of nature evolution process, while providing fewer control parameters. Experiments based onChinese 144 cities(CHN144)and 7 instances selected from TSPLIB are used to test the performance of this algorithm.They prove that it can reach the satisfying optimization at a faster speed. Especially, for the CHN144, the best pathit finds is better than any other available one.In this paper, a kind of Partheno Genetic Algorithm (PGA) based on Path Representation scheme is proposed for solving Traveling Salesman Problem(TSP). This algorithm employs only mutation and selection operators to produce the offspring, instead of traditional crossover operator. A specific mutation operator is designed combining the insertion operator with inversion operator, which ensures its strong searching capability. This algorithm simulates the recurrence of nature evolution process, while providing fewer control parameters. Experiments based on Chinese 144 cities(CHN144)and 7 instances selected from TSPLIB are used to test the performance of this algorithm. They prove that it can reach the satisfying optimization at a faster speed. Especially, for the CHN144, the best path it finds is better than any other available one.

关 键 词：单亲遗传算法 TSP问题 PGA算法 运筹学 解 

分 类 号：O22[理学—运筹学与控制论] O242.23[理学—数学]