Multiple local neighbourhood search for extremal optimisation

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

Abstract

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-optand 3-opt ?used singly or from a neighborhood) can be readily integrated into the canonical EOframework, 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 neighborhoods. 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.
Original languageEnglish
Title of host publicationProceedings of the X Metaheuristics International Conference
PublisherSingapore Management University
Pages278-287
Number of pages10
Publication statusPublished - 2013
EventMetaheuristics International Conference - Singapore , Singapore , Singapore
Duration: 5 Aug 20138 Aug 2013
Conference number: 10th
http://research.larc.smu.edu.sg/mic2013/

Conference

ConferenceMetaheuristics International Conference
Abbreviated titleMIC
CountrySingapore
CitySingapore
Period5/08/138/08/13
Internet address

Fingerprint

Traveling salesman problem
Local search (optimization)

Cite this

Randall, M. (2013). Multiple local neighbourhood search for extremal optimisation. In Proceedings of the X Metaheuristics International Conference (pp. 278-287). Singapore Management University.
Randall, Marcus. / Multiple local neighbourhood search for extremal optimisation. Proceedings of the X Metaheuristics International Conference. Singapore Management University, 2013. pp. 278-287
@inproceedings{992f9260b801485893e4914adb62ad9b,
title = "Multiple local neighbourhood search for extremal optimisation",
abstract = "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-optand 3-opt ?used singly or from a neighborhood) can be readily integrated into the canonical EOframework, 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 neighborhoods. 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.",
author = "Marcus Randall",
note = "{\circledC} Copyright The Author, 2013",
year = "2013",
language = "English",
pages = "278--287",
booktitle = "Proceedings of the X Metaheuristics International Conference",
publisher = "Singapore Management University",

}

Randall, M 2013, Multiple local neighbourhood search for extremal optimisation. in Proceedings of the X Metaheuristics International Conference. Singapore Management University, pp. 278-287, Metaheuristics International Conference, Singapore , Singapore, 5/08/13.

Multiple local neighbourhood search for extremal optimisation. / Randall, Marcus.

Proceedings of the X Metaheuristics International Conference. Singapore Management University, 2013. p. 278-287.

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

TY - GEN

T1 - Multiple local neighbourhood search for extremal optimisation

AU - Randall, Marcus

N1 - © Copyright The Author, 2013

PY - 2013

Y1 - 2013

N2 - 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-optand 3-opt ?used singly or from a neighborhood) can be readily integrated into the canonical EOframework, 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 neighborhoods. 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.

AB - 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-optand 3-opt ?used singly or from a neighborhood) can be readily integrated into the canonical EOframework, 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 neighborhoods. 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.

M3 - Conference contribution

SP - 278

EP - 287

BT - Proceedings of the X Metaheuristics International Conference

PB - Singapore Management University

ER -

Randall M. Multiple local neighbourhood search for extremal optimisation. In Proceedings of the X Metaheuristics International Conference. Singapore Management University. 2013. p. 278-287