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 language | English |
---|---|
Title of host publication | Progress in Artificial Life. Third Australian Conference, ACAL 2007 Proceedings |
Editors | Marcus Randall, Hussein Abbass, Janet Wiles |
Place of Publication | Gold Coast, Australia |
Pages | 369-380 |
Number of pages | 12 |
Volume | 4828 |
DOIs | |
Publication status | Published - 2007 |
Event | 3rd Australian Conference on Artificial Life, ACAL 2007 - Gold Coast, Australia Duration: 4 Dec 2007 → 6 Dec 2007 Conference number: 3 http://www.springer.com/gp/book/9783540769309 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 4828 |
ISSN (Print) | 03029743 |
ISSN (Electronic) | 16113349 |
Conference
Conference | 3rd Australian Conference on Artificial Life, ACAL 2007 |
---|---|
Abbreviated title | ACAL |
Country/Territory | Australia |
City | Gold Coast |
Period | 4/12/07 → 6/12/07 |
Internet address |