Enhancements to extremal optimisation for generalised assignment

Marcus Randall*

*Corresponding author for this work

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

9 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
Country/TerritoryAustralia
CityGold Coast
Period4/12/076/12/07
Internet address

Fingerprint

Dive into the research topics of 'Enhancements to extremal optimisation for generalised assignment'. Together they form a unique fingerprint.

Cite this