Date of this Version


Document Type

Conference Paper

Publication Details

Accepted version

Randall, M. (2013). Multiple local neighbourhood search for extremal optimisation. Paper presented at MIC 2013: The X Metaheuristics International Conference, 4-8 August, Singapore, 278-287.

Access the conference website

© Copyright The Author, 2013


Extremal optimisation (EO) uses a somewhat unusual mechanism to transform one solution into another. This consists of computing a probabilistic worst solution component value, and changing it to a random value. While simple and avoiding problems with premature convergence, it is mostly incompatible with combinatorial problems, particularly those requiring permutations as solution structures. This paper demonstrates that standard local search operators (e.g., 1-opt, 2-opt and 3-opt – used singly or from a neighbourhood) can be readily integrated into the canonical EO framework, without compromising the integrity of the original algorithm. The idea, in some senses may be viewed as a quasi-memetic algorithm. In particular, the primary purpose of this paper is the application and analysis of multiple local search operator neighbourhoods. Issues of solution component ranking techniques and methods for generating local transition operator endpoints are also examined. The difficult and under used asymmetric travelling salesman problem is employed to test these concepts. Results indicate that the simultaneous use of local search operators provides for improved performance over operators used individually.



This document has been peer reviewed.


To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.