Philipp Rohlfshagen
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.
- T. Back, A. E. Eiben, and N. A. L. van der Vaart. An empirical study on gas "without parameters ". In Proceedings of the 6th International Conference on Parallel Problem Solving from Nature pages 315--324. Springer, 2000. Google Scholar
Digital Library
- 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.Google Scholar
- S. J. Freeland and L. D. Hurst. The genetic code is one in a million. J. Mol. Evol. 47:238--248, 1998.Google ScholarCross Ref
- A. Herbet and A. Rich. RNA processing and the evolution of eukaryotes. Nature Genetics 21:265--269, 1999.Google Scholar
- J. H. Holland. Adaptation in Natural and Artifical Systems University of Michigan Press, Ann Arbor, MI, 1975. Google ScholarDigital Library
- Y. Jun, L. Xiande, and H. Lu. Evolutionary game algorithm for multiple knapsack problem. In Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology pages 424--427. IEEE, 2003. Google ScholarDigital Library
- S. Khuri, T. Bäck, and J. Heitkötter. The zero/one multiple knapsack problem and genetic algorithms. In E. Deaton, D. Oppenheim, J. Urban, and H. Berghel, editors, Proceedings of the 1994 ACM Symposium of Applied Computation proceedings pages 188--193. ACM Press, 1994. Google ScholarDigital Library
- S. Kimbrough, M. Lu, D. Wood, and D. J. Wu. Exploring a two-market genetic algorithm. In GECCO0-2002: Proceedings of the Genetic and Evolutionary Computation Conference pages 415--422, California, 2002. Morgan Kaufmann.Google Scholar
- M. Mitchell. An Introduction to Genetic Algorithms MIT Press, 1996. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- ExGA II: an improved exonic genetic algorithm for the multiple knapsack problem
Recommendations
A genetic algorithm for the minimum generating set problem
Graphical abstractDisplay Omitted HighlightsWe propose a novel formulation for the MGS problem based on multiple knapsack.The so-conceived MGS problem is solved by a novel GA.The GA embeds an intelligent construction method and specialized crossover ...
Biased random-key genetic algorithms for combinatorial optimization
Random-key genetic algorithms were introduced by Bean (ORSA J. Comput. 6:154---160, 1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. ...
An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems
Bat algorithm is a population metaheuristic proposed in 2010 which is based on the echolocation or bio-sonar characteristics of microbats. Since its first implementation, the bat algorithm has been used in a wide range of fields. In this paper, we ...
Comments