Study on a novel genetic algorithm for the combinatorial optimization problem

被引：0

作者：

Dang, Jian-wu ^{[1
]}

Wang, Yang-ping ^{[1
]}

Zhao, Shu-xu ^{[1
]}

机构：

[1] Lanzhou Jiaotong Univ, Sch Elect & Informat Engn, Lanzhou 730070, Peoples R China

来源：

2007 INTERNATIONAL CONFERENCE ON CONTROL, AUTOMATION AND SYSTEMS, VOLS 1-6 | 2007年

关键词：

evolution algorithm; traveling salesman problem; multi-traveling salesman problem; time complexity;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A genetic algorithm simulating Darwinian evolution is proposed to yield near-optimal solutions to the multiple traveling salesmen problem (MTSP). A new transformation of the N-city M-salesmen MTSP to the standard traveling salesman problem (TSP) is introduced. The transformed problem is represented by a city-position map with (N+M-1)(-cities) and a single fictitious Salesman. Nothing that Darwinian evolution is itself an optimization process; we propose a heuristic algorithm that incorporates the tents of natural selection. The time complexity of this algorithm is equivalent to the fastest sorting scheme. Computer simulations indicate rapid convergence is maintained even with increasing problem complexity. This methodology can be adapted to tackle a host of other combinatorial problems.

引用

页码：1377 / 1380

页数：4