Extremal Optimisation for Assignment Type Problems

There are no files associated with this record.

Title Extremal Optimisation for Assignment Type Problems
Author Randall, Marcus; Hendtlass, Tim; Lewis, Andrew
Book Title Biologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications
Editor Andrew Lewis, Sanaz Mostaghim and Marcus Randall
Year Published 2009
Place of publication Berlin
Publisher Springer-Verlag
Abstract Extremal optimisation is an emerging nature inspired meta-heuristic search technique that allows a poorly performing solution component to be removed at each iteration of the algorithm and replaced by a random value. This creates opportunity for assignment type problems as it enables a component to be moved to a more appropriate group. This may then drive the system towards an optimal solution. In this chapter, the general capabilities of extremal optimisation, in terms of assignment type problems, are explored. In particular, we provide an analysis of the moves selected by extremal optimisation and show that it does not suffer from premature convergence. Following this we develop a model of extremal optimisation that includes techniques to a) process constraints by allowing the search to move between feasible and infeasible space, b) provide a generic partial feasibility restoration heuristic to drive the solution towards feasible space, and c) develop a population model of the meta-heuristic that adaptively removes and introduces new members in accordance with the principles of self-organised criticality. A range of computational experiments on prototypical assignment problems, namely generalised assignment, bin packing, and capacitated hub location, indicate that extremal optimisation can form the foundation for a powerful and competitive meta-heuristic for this class of problems.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.springerlink.com/
Alternative URI http://dx.doi.org/10.1007/978-3-642-01262-4_6
Chapter Number 6
Page from 139
Page to 164
ISBN 978-3-642-01261-7
Date Accessioned 2009-09-21
Date Available 2010-08-19T07:04:52Z
Language en_AU
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Optimisation
URI http://hdl.handle.net/10072/29401
Publication Type Book Chapters
Publication Type Code b1

Show simple item record

Griffith University copyright notice