Extending population oriented extremal optimisation to permutation problems

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Author:
Extremal optimisation in its canonical form is based on the manipulation of a single solution. This solution is changed iteratively by gradually replacing poor components of it so that over time it improves. Many successful evolutionary optimisers are population based, so it appears a reasonable exercise to extend extremal optimisation in this way. Scaling it up to an entire population presents many challenges, and only a few works have examined possible models. In this paper, a recent approach is expanded upon which extends the approach from assignment type problems (such as the generalised assignment problem) to permutation oriented ones. Using the asymmetric travelling salesman problem as a test case, it is found that improvements over a canonical extremal optimisation algorithm were realised.
Original languageEnglish
Pages (from-to)38-43
Number of pages6
JournalInternational Journal of Applied Mathematics and Informatics
Volume11
Publication statusPublished - 2017

Fingerprint

Traveling salesman problem

Cite this

@article{77e4e3c644244d32a299c0ade86b8f5a,
title = "Extending population oriented extremal optimisation to permutation problems",
abstract = "Author:Extremal optimisation in its canonical form is based on the manipulation of a single solution. This solution is changed iteratively by gradually replacing poor components of it so that over time it improves. Many successful evolutionary optimisers are population based, so it appears a reasonable exercise to extend extremal optimisation in this way. Scaling it up to an entire population presents many challenges, and only a few works have examined possible models. In this paper, a recent approach is expanded upon which extends the approach from assignment type problems (such as the generalised assignment problem) to permutation oriented ones. Using the asymmetric travelling salesman problem as a test case, it is found that improvements over a canonical extremal optimisation algorithm were realised.",
author = "Marcus Randall",
year = "2017",
language = "English",
volume = "11",
pages = "38--43",
journal = "International Journal of Applied Mathematics and Informatics",
issn = "2074-1278",
publisher = "North Atlantic University Union NAUN",

}

Extending population oriented extremal optimisation to permutation problems. / Randall, Marcus.

In: International Journal of Applied Mathematics and Informatics, Vol. 11, 2017, p. 38-43.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Extending population oriented extremal optimisation to permutation problems

AU - Randall, Marcus

PY - 2017

Y1 - 2017

N2 - Author:Extremal optimisation in its canonical form is based on the manipulation of a single solution. This solution is changed iteratively by gradually replacing poor components of it so that over time it improves. Many successful evolutionary optimisers are population based, so it appears a reasonable exercise to extend extremal optimisation in this way. Scaling it up to an entire population presents many challenges, and only a few works have examined possible models. In this paper, a recent approach is expanded upon which extends the approach from assignment type problems (such as the generalised assignment problem) to permutation oriented ones. Using the asymmetric travelling salesman problem as a test case, it is found that improvements over a canonical extremal optimisation algorithm were realised.

AB - Author:Extremal optimisation in its canonical form is based on the manipulation of a single solution. This solution is changed iteratively by gradually replacing poor components of it so that over time it improves. Many successful evolutionary optimisers are population based, so it appears a reasonable exercise to extend extremal optimisation in this way. Scaling it up to an entire population presents many challenges, and only a few works have examined possible models. In this paper, a recent approach is expanded upon which extends the approach from assignment type problems (such as the generalised assignment problem) to permutation oriented ones. Using the asymmetric travelling salesman problem as a test case, it is found that improvements over a canonical extremal optimisation algorithm were realised.

M3 - Article

VL - 11

SP - 38

EP - 43

JO - International Journal of Applied Mathematics and Informatics

JF - International Journal of Applied Mathematics and Informatics

SN - 2074-1278

ER -