Heuristic combinatorial optimization by simulated Darwinian evolution: a polynomial time algorithm for the Traveling Salesman Problem |
| |
Authors: | B K Ambati J Ambati M M Mokhtar |
| |
Institution: | (1) New York University, 10003 New York, NY, USA;(2) Health Science Center, State Univeristy of New York, 11203 Brooklyn, NY, USA;(3) IBM, 20877 Gaithersburg, MD, USA |
| |
Abstract: | A genetic algorithm simulating Darwinian evolution is proposed to yield near-optimal solutions to the Traveling Salesman Problem. Noting that Darwinian evolution is itself an optimization process, we propose a heuristic algorithm that incorporates the tenets 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|