Extremal optimisation with a penalty approach for the multidimensional knapsack problem

Pedro Gómez-Meneses; Marcus Randall

doi:10.1007/978-3-540-89694-4_24

Extremal optimisation with a penalty approach for the multidimensional knapsack problem

Pedro Gómez-Meneses^*, Marcus Randall

^*Corresponding author for this work

Bond Business School

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

5 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 language	English
Title of host publication	Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings
Pages	229-238
Number of pages	10
Volume	5361 LNAI
DOIs	https://doi.org/10.1007/978-3-540-89694-4_24
Publication status	Published - 2008
Event	7th International Conference on Simulated Evolution and Learning, SEAL 2008 - Melbourne, VIC, Australia Duration: 7 Dec 2008 → 10 Dec 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5361 LNAI
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	7th International Conference on Simulated Evolution and Learning, SEAL 2008
Country/Territory	Australia
City	Melbourne, VIC
Period	7/12/08 → 10/12/08

Access to Document

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

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",

note = "7th International Conference on Simulated Evolution and Learning, SEAL 2008 ; Conference date: 07-12-2008 Through 10-12-2008",

}

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 proceeding › Conference contribution › Research › peer-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

AN - SCOPUS:58349096546

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

T2 - 7th International Conference on Simulated Evolution and Learning, SEAL 2008

Y2 - 7 December 2008 through 10 December 2008

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)). doi: 10.1007/978-3-540-89694-4_24

Extremal optimisation with a penalty approach for the multidimensional knapsack problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this