摘要
利用遗传算法求解TSP问题,通常需要使用PCX,CX和OX等特殊的交叉算子以提高算法的运行效率。针对自然数编码的方式,提出一种改进的遗传算法,即改进传统的顺序交叉算子,进行不相同子排列顺序交叉,使子代继承父代中优秀的子排列,加快算法的收敛速度。另外,采用没有重复的稳态繁殖避免早熟。实验结果表明,此改进算法对于TSP和DHC问题均具有较好的性能。
Genetic algorithm is an important method for solving traveling salesman problem.In order to improve the algorithm＇s rate,some special crossover operators are needed,such as partially matched crossover,cycle crossover and ordered crossover.In this paper,an improved GA is proposed for natural number encoding scheme.It will guarantee the rapid convergence of GA to use an improved ordered crossover_dissimilar ordered crossover,which makes the offspring inherits the best arrange of its parents. Otherwise,steady state reproduction without duplicates is used to avoid precocity.The results show that the proposed algorithm is effective for both TSP and DHC.
出处
《计算机工程与应用》
CSCD
北大核心
2007年第6期65-68,共4页
Computer Engineering and Applications
基金
安徽省自然科学基金 (the Natural Science Foundation of Anhui Province of China under Grant No.050460402)
安徽省高等学校青年教师科研资助计划(No.2005jq1035) 。
关键词
旅行商问题
遗传算法
交叉算子
顺序交叉
traveling salesman problem
genetic algorithm
crossover operator
ordered crossover
