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

An Improved Partheno-Genetic Algorithm for TSPs

作　　者：李倩[1] 文贵华[1] 丁月华[1] 

机构地区：[1]华南理工大学计算机应用工程研究所,广东广州510641

出　　处：《计算机工程与科学》2007年第2期89-92,109,共5页Computer Engineering & Science

摘　　要：单亲遗传算法具有操作简单、收敛较快等优点,因此被用于求解各种组合优化问题。针对旅行商问题,在早期单亲遗传算法的基础上引入了基因段贪心替换、基于相似度的家族竞争等一些控制策略,提出了一种新型、高效的单亲遗传算法。实验表明,该算法不仅能够保留收敛较快等优点,而且具备了比现有的单亲遗传算法以及改进的GT算法更强的全局寻优能力。A new improved Partheno-Genetic Algorithm（IPGA）is presented for solving TSPs.The original Partheno-Genetic Algorithm（PGA）provides simple operators and a fast solution to lots of combinatorial optimization problems,but it may suffer from local convergence and solution quality problems.Based on the weaknesses of the original PGA,IPGA integrates the original genetic operators of PGA and a new genetic operator which is called greedy gene replacing,through similarity-based family competition and other mechanisms.Then it is evaluated on several TSPs.Experimental results indicate that IPGA is a more efficient method for TSPs and its global search performance is better than other PGAs and the improved GT algorithm（IGT）.

关 键 词：单亲遗传算法 组合优化 TSP 家族竞争 

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