Extremal optimisation for assignment type problems

Marcus Randall, Tim Hendtlass, Andrew Lewis

Research output: Chapter in Book/Report/Conference proceedingChapterResearchpeer-review

8 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationBiologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications
Pages139-164
Number of pages26
Volume210
DOIs
Publication statusPublished - 2009

Publication series

NameStudies in Computational Intelligence
Volume210
ISSN (Print)1860949X

Fingerprint

Bins
Restoration
Experiments

Cite this

Randall, M., Hendtlass, T., & Lewis, A. (2009). Extremal optimisation for assignment type problems. In Biologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications (Vol. 210, pp. 139-164). (Studies in Computational Intelligence; Vol. 210). https://doi.org/10.1007/978-3-642-01262-4_6
Randall, Marcus ; Hendtlass, Tim ; Lewis, Andrew. / Extremal optimisation for assignment type problems. Biologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications. Vol. 210 2009. pp. 139-164 (Studies in Computational Intelligence).
@inbook{f5d5c5436f2f4c2ea0534a881a64b19a,
title = "Extremal optimisation for assignment type problems",
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.",
author = "Marcus Randall and Tim Hendtlass and Andrew Lewis",
year = "2009",
doi = "10.1007/978-3-642-01262-4_6",
language = "English",
isbn = "9783642012617",
volume = "210",
series = "Studies in Computational Intelligence",
pages = "139--164",
booktitle = "Biologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications",

}

Randall, M, Hendtlass, T & Lewis, A 2009, Extremal optimisation for assignment type problems. in Biologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications. vol. 210, Studies in Computational Intelligence, vol. 210, pp. 139-164. https://doi.org/10.1007/978-3-642-01262-4_6

Extremal optimisation for assignment type problems. / Randall, Marcus; Hendtlass, Tim; Lewis, Andrew.

Biologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications. Vol. 210 2009. p. 139-164 (Studies in Computational Intelligence; Vol. 210).

Research output: Chapter in Book/Report/Conference proceedingChapterResearchpeer-review

TY - CHAP

T1 - Extremal optimisation for assignment type problems

AU - Randall, Marcus

AU - Hendtlass, Tim

AU - Lewis, Andrew

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

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

U2 - 10.1007/978-3-642-01262-4_6

DO - 10.1007/978-3-642-01262-4_6

M3 - Chapter

SN - 9783642012617

VL - 210

T3 - Studies in Computational Intelligence

SP - 139

EP - 164

BT - Biologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications

ER -

Randall M, Hendtlass T, Lewis A. Extremal optimisation for assignment type problems. In Biologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications. Vol. 210. 2009. p. 139-164. (Studies in Computational Intelligence). https://doi.org/10.1007/978-3-642-01262-4_6