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

被引：12

作者：

韩丽霞 ^{[1
]}

王宇平 ^{[2
]}

机构：

[1] 西安电子科技大学理学院数学系

[2] 西安电子科技大学计算机学院

来源：

系统工程理论与实践 | 2007年 / 12期

关键词：

遗传算法; 旅行商问题; 全局收敛性;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

对旅行商(TSP)问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例(城市规模从14到1000)进行了计算机仿真,结果表明算法是有效的.

引用

页码：145 / 150

页数：6

共 3 条

[1] Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems [J].

David Applegate ;

Robert Bixby ;

Vašek Chvátal ;

William Cook .

Mathematical Programming, 2003, 97 :91-153

[2]

Combining simulated annealing with local search heuristics[J] . Olivier C. Martin,Steve W. Otto.Annals of Operations Research . 1996 (1)

[3]

Toward minimal restriction of genetic coding and crossovers for the 2-D eunclidean TSP. Jung S,Moon B R. IEEE Transactionon Evolutionary Computation . 2002

← 1 →