Extremal optimisation with a penalty approach for the multidimensional knapsack problem

Pedro Gómez-Meneses, Marcus Randall

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

Extremal Optimization
Multidimensional Knapsack Problem
Penalty
Graph Partitioning
Spin glass
Graph Coloring
Combinatorial optimization
Spin Glass
Combinatorial Problems
Coloring
Combinatorial Optimization Problem
Optimization Model
Metaheuristics

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
Gómez-Meneses, Pedro ; Randall, Marcus. / Extremal optimisation with a penalty approach for the multidimensional knapsack problem. Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings. Vol. 5361 LNAI 2008. pp. 229-238 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{d60ae11430f34510b510476b0948b250,
title = "Extremal optimisation with a penalty approach for the multidimensional knapsack problem",
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.",
author = "Pedro G{\'o}mez-Meneses and Marcus Randall",
year = "2008",
doi = "10.1007/978-3-540-89694-4_24",
language = "English",
isbn = "3540896937",
volume = "5361 LNAI",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "229--238",
booktitle = "Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings",

}

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, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5361 LNAI, pp. 229-238, 7th International Conference on Simulated Evolution and Learning, SEAL 2008, Melbourne, VIC, Australia, 7/12/08. https://doi.org/10.1007/978-3-540-89694-4_24

Extremal optimisation with a penalty approach for the multidimensional knapsack problem. / Gómez-Meneses, Pedro; Randall, Marcus.

Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings. Vol. 5361 LNAI 2008. p. 229-238 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5361 LNAI).

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

TY - GEN

T1 - Extremal optimisation with a penalty approach for the multidimensional knapsack problem

AU - Gómez-Meneses, Pedro

AU - Randall, Marcus

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=58349096546&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-89694-4_24

DO - 10.1007/978-3-540-89694-4_24

M3 - Conference contribution

SN - 3540896937

SN - 9783540896937

VL - 5361 LNAI

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 229

EP - 238

BT - Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings

ER -

Gómez-Meneses P, Randall M. 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. 2008. p. 229-238. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-89694-4_24