A hybrid evolutionary algorithm for traveling salesman problem
- Resource Type
- Conference
- Authors
- White, C.M.; Yen, G.G.
- Source
- Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753) Evolutionary computation Evolutionary Computation, 2004. CEC2004. Congress on. 2:1473-1478 Vol.2 2004
- Subject
- Computing and Processing
Evolutionary computation
Traveling salesman problems
Cities and towns
Genetic algorithms
Simulated annealing
Space exploration
Testing
Optimization methods
NP-hard problem
Convergence
- Language
This work details the development of a hybrid evolutionary algorithm for solving the traveling salesman problem (TSP). The strategy of the algorithm is to complement and extend the successful results of a genetic algorithm (GA) using a distance preserving crossover (DPX) by incorporating memory in the form of ant pheromone during the city selection process. The synergistic combination of the DPX-GA with city selection based on probability determined by both distance and previous success incorporates additional information into the search mechanism. This combination into a hybrid GA facilitates finding quality solutions for TSP problems with lower computation complexity. This study represents a preliminary investigation with direct comparison to show the feasibility and promise of this hybrid approach.