Population extremal optimisation for discrete multi-objective optimisation problems

M. Randall, A. Lewis

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)
35 Downloads (Pure)

Abstract

The power to solve intractable optimisation problems is often found through population based evolutionary methods. These include, but are not limited to, genetic algorithms, particle swarm optimisation, differential evolution and ant colony optimisation. While showing much promise as an effective optimiser, extremal optimisation uses only a single solution in its canonical form – and there are no standard population mechanics. In this paper, two population models for extremal optimisation are proposed and applied to a multi-objective version of the generalised assignment problem. These models use novel intervention/interaction strategies as well as collective memory in order to allow individual population members to work together. Additionally, a general non-dominated local search algorithm is developed and tested. Overall, the results show that improved attainment surfaces can be produced using population based interactions over not using them. The new EO approach is also shown to be highly competitive with an implementation of NSGA-II.

Original languageEnglish
Pages (from-to)390-402
Number of pages13
JournalInformation Sciences
Volume367-368
DOIs
Publication statusPublished - 1 Nov 2016

Fingerprint

Extremal Optimization
Discrete Optimization
Multiobjective Optimization Problems
Multiobjective optimization
Ant colony optimization
Generalized Assignment Problem
Particle swarm optimization (PSO)
NSGA-II
Local Search Algorithm
Mechanics
Canonical form
Population Model
Differential Evolution
Genetic algorithms
Interaction
Particle Swarm Optimization
Data storage equipment
Genetic Algorithm
Optimization Problem
Optimization problem

Cite this

@article{68ea292879e84dcd80d45af24f4855b6,
title = "Population extremal optimisation for discrete multi-objective optimisation problems",
abstract = "The power to solve intractable optimisation problems is often found through population based evolutionary methods. These include, but are not limited to, genetic algorithms, particle swarm optimisation, differential evolution and ant colony optimisation. While showing much promise as an effective optimiser, extremal optimisation uses only a single solution in its canonical form – and there are no standard population mechanics. In this paper, two population models for extremal optimisation are proposed and applied to a multi-objective version of the generalised assignment problem. These models use novel intervention/interaction strategies as well as collective memory in order to allow individual population members to work together. Additionally, a general non-dominated local search algorithm is developed and tested. Overall, the results show that improved attainment surfaces can be produced using population based interactions over not using them. The new EO approach is also shown to be highly competitive with an implementation of NSGA-II.",
author = "M. Randall and A. Lewis",
year = "2016",
month = "11",
day = "1",
doi = "10.1016/j.ins.2016.06.013",
language = "English",
volume = "367-368",
pages = "390--402",
journal = "Information Sciences - Applications",
issn = "0020-0255",
publisher = "Elsevier",

}

Population extremal optimisation for discrete multi-objective optimisation problems. / Randall, M.; Lewis, A.

In: Information Sciences, Vol. 367-368, 01.11.2016, p. 390-402.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Population extremal optimisation for discrete multi-objective optimisation problems

AU - Randall, M.

AU - Lewis, A.

PY - 2016/11/1

Y1 - 2016/11/1

N2 - The power to solve intractable optimisation problems is often found through population based evolutionary methods. These include, but are not limited to, genetic algorithms, particle swarm optimisation, differential evolution and ant colony optimisation. While showing much promise as an effective optimiser, extremal optimisation uses only a single solution in its canonical form – and there are no standard population mechanics. In this paper, two population models for extremal optimisation are proposed and applied to a multi-objective version of the generalised assignment problem. These models use novel intervention/interaction strategies as well as collective memory in order to allow individual population members to work together. Additionally, a general non-dominated local search algorithm is developed and tested. Overall, the results show that improved attainment surfaces can be produced using population based interactions over not using them. The new EO approach is also shown to be highly competitive with an implementation of NSGA-II.

AB - The power to solve intractable optimisation problems is often found through population based evolutionary methods. These include, but are not limited to, genetic algorithms, particle swarm optimisation, differential evolution and ant colony optimisation. While showing much promise as an effective optimiser, extremal optimisation uses only a single solution in its canonical form – and there are no standard population mechanics. In this paper, two population models for extremal optimisation are proposed and applied to a multi-objective version of the generalised assignment problem. These models use novel intervention/interaction strategies as well as collective memory in order to allow individual population members to work together. Additionally, a general non-dominated local search algorithm is developed and tested. Overall, the results show that improved attainment surfaces can be produced using population based interactions over not using them. The new EO approach is also shown to be highly competitive with an implementation of NSGA-II.

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

U2 - 10.1016/j.ins.2016.06.013

DO - 10.1016/j.ins.2016.06.013

M3 - Article

VL - 367-368

SP - 390

EP - 402

JO - Information Sciences - Applications

JF - Information Sciences - Applications

SN - 0020-0255

ER -