Enhancements to extremal optimisation for generalised assignment

Marcus Randall*

*Corresponding author for this work

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

5 Citations (Scopus)

Abstract

Extremal optimisation (EO) is a relatively new meta-heuristic technique that is based on the principles of self organising criticality. It allows for a poorly performing solution component to be removed at each iteration of the algorithm and be replaced by a random one. Over time, improvements emerge and the system is driven towards good quality solutions. There has been very little literature concerning EO and combinatorial optimisation and relatively few computational results have been reported. In this paper, an enhanced model of EO, which allows the traversal feasible and infeasible spaces, is presented. This improved version is able to operate on single solutions as well as populations of solutions. In addition to local search, a simple partial feasibility restoration heuristic is introduced. The computational results for the generalised assignment problem indicate that it provides significantly better quality solutions over a sophisticated ant colony optimisation implementation.

Original languageEnglish
Title of host publicationProgress in Artificial Life. Third Australian Conference, ACAL 2007 Proceedings
EditorsMarcus Randall, Hussein Abbass, Janet Wiles
Place of PublicationGold Coast, Australia
Pages369-380
Number of pages12
Volume4828
DOIs
Publication statusPublished - 2007
Event3rd Australian Conference on Artificial Life, ACAL 2007 - Gold Coast, Australia
Duration: 4 Dec 20076 Dec 2007
Conference number: 3
http://www.springer.com/gp/book/9783540769309

Publication series

NameLecture Notes in Computer Science
Volume4828
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference3rd Australian Conference on Artificial Life, ACAL 2007
Abbreviated titleACAL
CountryAustralia
CityGold Coast
Period4/12/076/12/07
Internet address

Fingerprint

Extremal Optimization
Assignment
Enhancement
Computational Results
Generalized Assignment Problem
Combinatorial Optimization
Self-organizing
Criticality
Restoration
Metaheuristics
Local Search
Heuristics
Ant colony optimization
Combinatorial optimization
Iteration
Partial
Model

Cite this

Randall, M. (2007). Enhancements to extremal optimisation for generalised assignment. In M. Randall, H. Abbass, & J. Wiles (Eds.), Progress in Artificial Life. Third Australian Conference, ACAL 2007 Proceedings (Vol. 4828 , pp. 369-380). (Lecture Notes in Computer Science; Vol. 4828 ). Gold Coast, Australia. https://doi.org/10.1007/978-3-540-76931-6_32
Randall, Marcus. / Enhancements to extremal optimisation for generalised assignment. Progress in Artificial Life. Third Australian Conference, ACAL 2007 Proceedings. editor / Marcus Randall ; Hussein Abbass ; Janet Wiles. Vol. 4828 Gold Coast, Australia, 2007. pp. 369-380 (Lecture Notes in Computer Science).
@inproceedings{3809683798bc4ef8bbfd4f3721ba562c,
title = "Enhancements to extremal optimisation for generalised assignment",
abstract = "Extremal optimisation (EO) is a relatively new meta-heuristic technique that is based on the principles of self organising criticality. It allows for a poorly performing solution component to be removed at each iteration of the algorithm and be replaced by a random one. Over time, improvements emerge and the system is driven towards good quality solutions. There has been very little literature concerning EO and combinatorial optimisation and relatively few computational results have been reported. In this paper, an enhanced model of EO, which allows the traversal feasible and infeasible spaces, is presented. This improved version is able to operate on single solutions as well as populations of solutions. In addition to local search, a simple partial feasibility restoration heuristic is introduced. The computational results for the generalised assignment problem indicate that it provides significantly better quality solutions over a sophisticated ant colony optimisation implementation.",
author = "Marcus Randall",
year = "2007",
doi = "10.1007/978-3-540-76931-6_32",
language = "English",
isbn = "9783540769309",
volume = "4828",
series = "Lecture Notes in Computer Science",
pages = "369--380",
editor = "Marcus Randall and Hussein Abbass and Janet Wiles",
booktitle = "Progress in Artificial Life. Third Australian Conference, ACAL 2007 Proceedings",

}

Randall, M 2007, Enhancements to extremal optimisation for generalised assignment. in M Randall, H Abbass & J Wiles (eds), Progress in Artificial Life. Third Australian Conference, ACAL 2007 Proceedings. vol. 4828 , Lecture Notes in Computer Science, vol. 4828 , Gold Coast, Australia, pp. 369-380, 3rd Australian Conference on Artificial Life, ACAL 2007, Gold Coast, Australia, 4/12/07. https://doi.org/10.1007/978-3-540-76931-6_32

Enhancements to extremal optimisation for generalised assignment. / Randall, Marcus.

Progress in Artificial Life. Third Australian Conference, ACAL 2007 Proceedings. ed. / Marcus Randall; Hussein Abbass; Janet Wiles. Vol. 4828 Gold Coast, Australia, 2007. p. 369-380 (Lecture Notes in Computer Science; Vol. 4828 ).

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

TY - GEN

T1 - Enhancements to extremal optimisation for generalised assignment

AU - Randall, Marcus

PY - 2007

Y1 - 2007

N2 - Extremal optimisation (EO) is a relatively new meta-heuristic technique that is based on the principles of self organising criticality. It allows for a poorly performing solution component to be removed at each iteration of the algorithm and be replaced by a random one. Over time, improvements emerge and the system is driven towards good quality solutions. There has been very little literature concerning EO and combinatorial optimisation and relatively few computational results have been reported. In this paper, an enhanced model of EO, which allows the traversal feasible and infeasible spaces, is presented. This improved version is able to operate on single solutions as well as populations of solutions. In addition to local search, a simple partial feasibility restoration heuristic is introduced. The computational results for the generalised assignment problem indicate that it provides significantly better quality solutions over a sophisticated ant colony optimisation implementation.

AB - Extremal optimisation (EO) is a relatively new meta-heuristic technique that is based on the principles of self organising criticality. It allows for a poorly performing solution component to be removed at each iteration of the algorithm and be replaced by a random one. Over time, improvements emerge and the system is driven towards good quality solutions. There has been very little literature concerning EO and combinatorial optimisation and relatively few computational results have been reported. In this paper, an enhanced model of EO, which allows the traversal feasible and infeasible spaces, is presented. This improved version is able to operate on single solutions as well as populations of solutions. In addition to local search, a simple partial feasibility restoration heuristic is introduced. The computational results for the generalised assignment problem indicate that it provides significantly better quality solutions over a sophisticated ant colony optimisation implementation.

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

U2 - 10.1007/978-3-540-76931-6_32

DO - 10.1007/978-3-540-76931-6_32

M3 - Conference contribution

SN - 9783540769309

VL - 4828

T3 - Lecture Notes in Computer Science

SP - 369

EP - 380

BT - Progress in Artificial Life. Third Australian Conference, ACAL 2007 Proceedings

A2 - Randall, Marcus

A2 - Abbass, Hussein

A2 - Wiles, Janet

CY - Gold Coast, Australia

ER -

Randall M. Enhancements to extremal optimisation for generalised assignment. In Randall M, Abbass H, Wiles J, editors, Progress in Artificial Life. Third Australian Conference, ACAL 2007 Proceedings. Vol. 4828 . Gold Coast, Australia. 2007. p. 369-380. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-540-76931-6_32