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.


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].