Title

Extremal optimisation with a penalty approach for the multidimensional knapsack problem

Date of this Version

12-1-2008

Document Type

Conference Paper

Publication Details

Interim status: Citation only.

Gomez-Meneses, P. & Randall, M. (2008). Extremal optimisation with a penalty approach for the multidimensional knapsack problem. Paper presented at the Simulated Evolution and Learning: 7th international conference, SEAL 2008, Melbourne, Australia.

Access the publisher's website.

2008 HERDC submission. FoR code: 0103

© Copyright Springer-Verlag Berlin Heidelberg, 2008

Abstract

The extremal optimisation (EO) meta-heuristic is a recent form of search that is suitable for combinatorial optimisation problems. EO has been applied to problems such as graph partitioning, spin glass, and graph colouring. However, only a relatively small amount of work has been done on other combinatorial problems particularly those having constraints. This paper examines the issue of satisfying constraints with a penalty approach using the multidimensional knapsack problem. An EO model is presented which finds solutions through the analysis of the number of overloaded constraints. This approach allows the solution state move between feasible and infeasible spaces. The results show that the new algorithm is able to obtain optimal results for small problems and finds competitive solutions for large problems.

This document is currently not available here.

Share

COinS
 

This document has been peer reviewed.