ExGA II: an improved exonic genetic algorithm for the multiple knapsack problem

ABSTRACT

ExGA I, a previously presented genetic algorithm, successfully solved numerous instances of the multiple knapsack problem (MKS) by employing an adaptive repair function that made use of the algorithm's modular encoding. Here we present ExGA II, an extension of ExGA I that implements additional features which allow the algorithm to perform more reliably across a larger set of benchmark problems. In addition to some basic modifications of the algorithm's framework, more specific extensions include the use of a biased mutation operator and adaptive control sequences which are used to guide the repair procedure. The success rate of ExGA II is superior to its predecessor, and other algorithms in the literature, without an overall increase in the number of function evaluations required to reach the global optimum. In fact, the new algorithm exhibits a significant reduction in the number of function evaluations required for the largest problems investigated. We also address the computational cost of using a repair function and show that the algorithm remains highly competitive when this cost is accounted for.

REFERENCES

• 1: Thomas Bäck , A. E. Eiben , N. A. L. van der Vaart, An Empirical Study on GAs "Without Parameters", Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.315-324, September 18-20, 2000
• 2: C. Cotta and J. M. Troya. A hybrid genetic algorithm for the 0-1 multiple knapsack problem. In G. D. Smith, N. C. Steele, and R. F. Albrecht, editors, Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms pages 250--254. Springer, 1997.
• 3: S. J. Freeland and L. D. Hurst. The genetic code is one in a million. J. Mol. Evol. 47:238--248, 1998.
• 4: A. Herbet and A. Rich. RNA processing and the evolution of eukaryotes. Nature Genetics 21:265--269, 1999.
• 5: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 6: Ye Jun , Liu Xiande , Han Lu, Evolutionary Game Algorithm for Multiple Knapsack Problem, Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology, p.424, October 13-17, 2003
• 7: Sami Khuri , Thomas Bäck , Jörg Heitkötter, The zero/one multiple knapsack problem and genetic algorithms, Proceedings of the 1994 ACM symposium on Applied computing, p.188-193, March 06-08, 1994, Phoenix, Arizona, United States [doi>10.1145/326619.326694]
• 8: Steven O. Kimbrough , Ming Lu , David Harlan Wood , Dong-Jun Wu, Exploring A Two-market Genetic Algorithm, Proceedings of the Genetic and Evolutionary Computation Conference, p.415-422, July 09-13, 2002
• 9: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996
• 10: P. Rohlfshagen and J. A. Bullinaria. An exonic genetic algorithm with RNA editing inspired repair function for the multiple knapsack problem. In Proceedings of the UK Workshop on Computational Intelligence (UKCI 2006)pages 17--24, Leeds, UK, 2006.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Experimentation, Performance

Keywords:
genetic algorithms, molecular genetics, multiple knapsack problem, repair functions