Extremal optimisation and bin packing

Tim Hendtlass, Marcus Randall

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

3 Citations (Scopus)

Abstract

Extremal Optimisation (EO) is a fairly new entrant into the realms of stochastic based optimisation techniques. Its behaviour differs from other more common algorithms as it alters a poorly performing part of the one solution used without regard to the effect this will have on the quality of the solution. While this means that its performance on assignment problems may be poor if used on its own, this same 'failing' makes it a very suitable base for a meta-heuristic. An analysis of the performance of naive EO on the classic bin packing problem is performed in this paper. Results are also presented that show that the same naive EO can be used in a meta-heuristic that performs very well.

Original languageEnglish
Title of host publicationSimulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings
Pages220-228
Number of pages9
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
Bin Packing
Bins
Metaheuristics
Bin Packing Problem
Assignment Problem
Optimization Techniques

Cite this

Hendtlass, T., & Randall, M. (2008). Extremal optimisation and bin packing. In Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings (Vol. 5361 LNAI, pp. 220-228). (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_23
Hendtlass, Tim ; Randall, Marcus. / Extremal optimisation and bin packing. Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings. Vol. 5361 LNAI 2008. pp. 220-228 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{4ff2835f54104ae9a8e87aa663270dc2,
title = "Extremal optimisation and bin packing",
abstract = "Extremal Optimisation (EO) is a fairly new entrant into the realms of stochastic based optimisation techniques. Its behaviour differs from other more common algorithms as it alters a poorly performing part of the one solution used without regard to the effect this will have on the quality of the solution. While this means that its performance on assignment problems may be poor if used on its own, this same 'failing' makes it a very suitable base for a meta-heuristic. An analysis of the performance of naive EO on the classic bin packing problem is performed in this paper. Results are also presented that show that the same naive EO can be used in a meta-heuristic that performs very well.",
author = "Tim Hendtlass and Marcus Randall",
year = "2008",
doi = "10.1007/978-3-540-89694-4_23",
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 = "220--228",
booktitle = "Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings",

}

Hendtlass, T & Randall, M 2008, Extremal optimisation and bin packing. 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. 220-228, 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_23

Extremal optimisation and bin packing. / Hendtlass, Tim; Randall, Marcus.

Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings. Vol. 5361 LNAI 2008. p. 220-228 (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 and bin packing

AU - Hendtlass, Tim

AU - Randall, Marcus

PY - 2008

Y1 - 2008

N2 - Extremal Optimisation (EO) is a fairly new entrant into the realms of stochastic based optimisation techniques. Its behaviour differs from other more common algorithms as it alters a poorly performing part of the one solution used without regard to the effect this will have on the quality of the solution. While this means that its performance on assignment problems may be poor if used on its own, this same 'failing' makes it a very suitable base for a meta-heuristic. An analysis of the performance of naive EO on the classic bin packing problem is performed in this paper. Results are also presented that show that the same naive EO can be used in a meta-heuristic that performs very well.

AB - Extremal Optimisation (EO) is a fairly new entrant into the realms of stochastic based optimisation techniques. Its behaviour differs from other more common algorithms as it alters a poorly performing part of the one solution used without regard to the effect this will have on the quality of the solution. While this means that its performance on assignment problems may be poor if used on its own, this same 'failing' makes it a very suitable base for a meta-heuristic. An analysis of the performance of naive EO on the classic bin packing problem is performed in this paper. Results are also presented that show that the same naive EO can be used in a meta-heuristic that performs very well.

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

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

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

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 - 220

EP - 228

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

ER -

Hendtlass T, Randall M. Extremal optimisation and bin packing. In Simulated Evolution and Learning - 7th International Conference, SEAL 2008, Proceedings. Vol. 5361 LNAI. 2008. p. 220-228. (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_23