Extremal optimisation with a penalty approach for the multidimensional knapsack problem

Pedro Gómez-Meneses*, Marcus Randall

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

4 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationSimulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings
Pages229-238
Number of pages10
Volume5361 LNAI
DOIs
Publication statusPublished - 2008
Event7th International Conference on Simulated Evolution and Learning, SEAL 2008 - Melbourne, VIC, Australia
Duration: 7 Dec 200810 Dec 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5361 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference7th International Conference on Simulated Evolution and Learning, SEAL 2008
CountryAustralia
CityMelbourne, VIC
Period7/12/0810/12/08

    Fingerprint

Cite this

Gómez-Meneses, P., & Randall, M. (2008). Extremal optimisation with a penalty approach for the multidimensional knapsack problem. In Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings (Vol. 5361 LNAI, pp. 229-238). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5361 LNAI). https://doi.org/10.1007/978-3-540-89694-4_24