A Hybrid Genetic Algorithm with Boltzmann Convergence Properties |
| |
Authors: | W. C. Jackson J. D. Norgard |
| |
Affiliation: | (1) Satellite Systems, SpaceDev, Inc., 92064 Poway, CA, USA;(2) Department of Electrical and Computer Engineering, University of Colorado, 80933 Colorado Springs, CO, USA |
| |
Abstract: | Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. This work was supported by the University of Colorado at Colorado Springs. |
| |
Keywords: | Combinatorial optimization Genetic algorithms Hybrid algorithms Simulated annealing |
本文献已被 SpringerLink 等数据库收录! |
|