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.
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 language | English |
|---|---|
| Pages (from-to) | 38-43 |
| Number of pages | 6 |
| Journal | International Journal of Applied Mathematics and Informatics |
| Volume | 11 |
| Publication status | Published - 2017 |