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

Raymond R. Hill and Chaitr Hiremath

International Journal of Operational Research, 2005, vol. 1, issue 1/2, 145-159

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. (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=7438 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:1:y:2005:i:1/2:p:145-159

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().