Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems
by Raymond R. Hill, Chaitr Hiremath
International Journal of Operational Research (IJOR), Vol. 1, No. 1/2, 2005

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.

Online publication date: Wed, 20-Jul-2005

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Operational Research (IJOR):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com