A Hybrid Genetic Algorithm for the 0-1 Multiple Knapsack Problem
|
C. Cotta, J.M. Troya Third International Conference on Artificial Neural Networks and Genetic Algorithms, G.D. Smith, N.C. Steele, and R.F. Albrecht. (eds.), pp. 251-255, Springer-Verlag Wien New York, 1998 © Springer-Verlag Wien New York 1998. All rights reserved. |
|
Abstract
|
A hybrid genetic algorithm based in local search is described. Local optimisation is not explicitly performed but it is embedded in the exploration of a search metaspace. This algorithm is applied to a NP-hard problem. When it is compared with other GA-based approaches and an exact technique (a branch & bound algorithm), this algorithm exhibits a better overall-performance in both cases. Then, a coarse-grain parallel version is tested, yielding notably improved results. | |
|
 |
|
Download BibTEX entry | |
|
 |
|
Download compressed postscript version (127K) | |
[Back to publications page].