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

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.