ExGA II: an Improved Exonic Genetic Algorithm for the Multiple Knapsack Problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Colleges, School and Institutes

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.

Details

Original languageEnglish
Title of host publicationGECCO '07 Proceedings of the 9th annual conference on Genetic and evolutionary computation
Publication statusPublished - 7 Jul 2007
Event9th Genetic and Evolutionary Computation Conference (GECCO 2007) - London, United Kingdom
Duration: 7 Jul 200711 Jul 2007

Conference

Conference9th Genetic and Evolutionary Computation Conference (GECCO 2007)
Country/TerritoryUnited Kingdom
CityLondon
Period7/07/0711/07/07

Keywords

  • repair functions, multiple knapsack problem, Genetic algorithms, molecular genetics