Title: Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems

Authors: Raymond R. Hill, Chaitr Hiremath

Addresses: Wright State University, 207 Russ Engineering Center, 3640 Col Glenn Highway, Dayton, OH 45435, USA. ' right State University, 207 Russ Engineering Center, 3640 Col Glenn Highway, Dayton, OH 45435, USA

Abstract: We develop and test a new approach for generating initial populations for the application of genetic algorithms (GA) to problems in combinatorial optimisation, specifically the multidimensional knapsack problem. We focus the empirical study of our approach on a set of two dimensional knapsack problems (2KP) used in a past study of 2KP algorithm performance. Our proposed approach for initial population generation focuses on generating populations that are stronger in terms of solution quality, solution diversity and in terms of solutions hovering near the border of feasible and infeasible solutions within the problem solution space. We report the results of a Monte Carlo experiment comparing our approach with the traditional initial population generation approach and report the results of computational tests involving 1120 2KP instances that cover a range of problem constraint characteristics. The collective of these computational results show that our proposed approach provides an initial population of sufficient quality and diversity to produce improved convergence to near optimal solutions which can equate to reduced computational burden in applications involving complex computations.

Keywords: combinatorial optimisation; heuristics; multidimensional knapsack problems; genetic algorithms; genetic algorithm convergence; initial population generation.

DOI: 10.1504/IJOR.2005.007438

International Journal of Operational Research, 2005 Vol.1 No.1/2, pp.145 - 159

Published online: 20 Jul 2005 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article