Local search enabled extremal optimisation for continuous inseparable multi-objective benchmark and real-world problems

Marcus Randall, Andrew Lewis, Jan Hettenhausen, Timoleon Kipouros

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

2 Citations (Scopus)
68 Downloads (Pure)

Abstract

Local search is an integral part of many meta-heuristic strategies that solve single objective optimisation problems. Essentially, the meta-heuristic is responsible for generating a good starting point from which a greedy local search will find the local optimum. Indeed, the best known solutions to many hard problems (such as the travelling salesman problem) have been generated in this hybrid way. However, for multiple objective problems, explicit local search strategies are relatively under studied, compared to other aspects of the search process. In this paper, a generic local search strategy is developed, particularly for problems where it is difficult or impossible to determine the contribution of individual solution components (often referred to as inseparable problems). The meta-heuristic adopted to test this is extremal optimisation, though the local search technique may be used by any meta-heuristic. To supplement the local search strategy a diversification strategy that draws from the external archive is incorporated into the local search strategy. Using benchmark problems, and a real-world airfoil design problem, it is shown that this combination leads to improved solutions.

Original languageEnglish
Title of host publication2014 International conference on computational science
EditorsD Abramson, M Lees, VV Krzhizhanovskaya, J Dongarra, PMA Sloot
Place of PublicationCairns
PublisherElsevier
Pages1904-1914
Number of pages11
Volume29
DOIs
Publication statusPublished - 2014
Event14th Annual International Conference on Computational Science - Cairns, Cairns, Australia
Duration: 10 Jun 201412 Jun 2014

Publication series

NameProcedia Computer Science
PublisherELSEVIER SCIENCE BV
Volume29
ISSN (Print)1877-0509

Conference

Conference14th Annual International Conference on Computational Science
CountryAustralia
CityCairns
Period10/06/1412/06/14

Cite this

Randall, M., Lewis, A., Hettenhausen, J., & Kipouros, T. (2014). Local search enabled extremal optimisation for continuous inseparable multi-objective benchmark and real-world problems. In D. Abramson, M. Lees, VV. Krzhizhanovskaya, J. Dongarra, & PMA. Sloot (Eds.), 2014 International conference on computational science (Vol. 29, pp. 1904-1914). (Procedia Computer Science; Vol. 29). Cairns: Elsevier. https://doi.org/10.1016/j.procs.2014.05.175
Randall, Marcus ; Lewis, Andrew ; Hettenhausen, Jan ; Kipouros, Timoleon. / Local search enabled extremal optimisation for continuous inseparable multi-objective benchmark and real-world problems. 2014 International conference on computational science. editor / D Abramson ; M Lees ; VV Krzhizhanovskaya ; J Dongarra ; PMA Sloot. Vol. 29 Cairns : Elsevier, 2014. pp. 1904-1914 (Procedia Computer Science).
@inproceedings{4e0332d364f84fefa8212bdc300501e2,
title = "Local search enabled extremal optimisation for continuous inseparable multi-objective benchmark and real-world problems",
abstract = "Local search is an integral part of many meta-heuristic strategies that solve single objective optimisation problems. Essentially, the meta-heuristic is responsible for generating a good starting point from which a greedy local search will find the local optimum. Indeed, the best known solutions to many hard problems (such as the travelling salesman problem) have been generated in this hybrid way. However, for multiple objective problems, explicit local search strategies are relatively under studied, compared to other aspects of the search process. In this paper, a generic local search strategy is developed, particularly for problems where it is difficult or impossible to determine the contribution of individual solution components (often referred to as inseparable problems). The meta-heuristic adopted to test this is extremal optimisation, though the local search technique may be used by any meta-heuristic. To supplement the local search strategy a diversification strategy that draws from the external archive is incorporated into the local search strategy. Using benchmark problems, and a real-world airfoil design problem, it is shown that this combination leads to improved solutions.",
author = "Marcus Randall and Andrew Lewis and Jan Hettenhausen and Timoleon Kipouros",
year = "2014",
doi = "10.1016/j.procs.2014.05.175",
language = "English",
volume = "29",
series = "Procedia Computer Science",
publisher = "Elsevier",
pages = "1904--1914",
editor = "D Abramson and M Lees and VV Krzhizhanovskaya and J Dongarra and PMA Sloot",
booktitle = "2014 International conference on computational science",
address = "Netherlands",

}

Randall, M, Lewis, A, Hettenhausen, J & Kipouros, T 2014, Local search enabled extremal optimisation for continuous inseparable multi-objective benchmark and real-world problems. in D Abramson, M Lees, VV Krzhizhanovskaya, J Dongarra & PMA Sloot (eds), 2014 International conference on computational science. vol. 29, Procedia Computer Science, vol. 29, Elsevier, Cairns, pp. 1904-1914, 14th Annual International Conference on Computational Science, Cairns, Australia, 10/06/14. https://doi.org/10.1016/j.procs.2014.05.175

Local search enabled extremal optimisation for continuous inseparable multi-objective benchmark and real-world problems. / Randall, Marcus; Lewis, Andrew; Hettenhausen, Jan; Kipouros, Timoleon.

2014 International conference on computational science. ed. / D Abramson; M Lees; VV Krzhizhanovskaya; J Dongarra; PMA Sloot. Vol. 29 Cairns : Elsevier, 2014. p. 1904-1914 (Procedia Computer Science; Vol. 29).

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

TY - GEN

T1 - Local search enabled extremal optimisation for continuous inseparable multi-objective benchmark and real-world problems

AU - Randall, Marcus

AU - Lewis, Andrew

AU - Hettenhausen, Jan

AU - Kipouros, Timoleon

PY - 2014

Y1 - 2014

N2 - Local search is an integral part of many meta-heuristic strategies that solve single objective optimisation problems. Essentially, the meta-heuristic is responsible for generating a good starting point from which a greedy local search will find the local optimum. Indeed, the best known solutions to many hard problems (such as the travelling salesman problem) have been generated in this hybrid way. However, for multiple objective problems, explicit local search strategies are relatively under studied, compared to other aspects of the search process. In this paper, a generic local search strategy is developed, particularly for problems where it is difficult or impossible to determine the contribution of individual solution components (often referred to as inseparable problems). The meta-heuristic adopted to test this is extremal optimisation, though the local search technique may be used by any meta-heuristic. To supplement the local search strategy a diversification strategy that draws from the external archive is incorporated into the local search strategy. Using benchmark problems, and a real-world airfoil design problem, it is shown that this combination leads to improved solutions.

AB - Local search is an integral part of many meta-heuristic strategies that solve single objective optimisation problems. Essentially, the meta-heuristic is responsible for generating a good starting point from which a greedy local search will find the local optimum. Indeed, the best known solutions to many hard problems (such as the travelling salesman problem) have been generated in this hybrid way. However, for multiple objective problems, explicit local search strategies are relatively under studied, compared to other aspects of the search process. In this paper, a generic local search strategy is developed, particularly for problems where it is difficult or impossible to determine the contribution of individual solution components (often referred to as inseparable problems). The meta-heuristic adopted to test this is extremal optimisation, though the local search technique may be used by any meta-heuristic. To supplement the local search strategy a diversification strategy that draws from the external archive is incorporated into the local search strategy. Using benchmark problems, and a real-world airfoil design problem, it is shown that this combination leads to improved solutions.

UR - http://www.sciencedirect.com/journal/procedia-computer-science/vol/29/suppl/C

U2 - 10.1016/j.procs.2014.05.175

DO - 10.1016/j.procs.2014.05.175

M3 - Conference contribution

VL - 29

T3 - Procedia Computer Science

SP - 1904

EP - 1914

BT - 2014 International conference on computational science

A2 - Abramson, D

A2 - Lees, M

A2 - Krzhizhanovskaya, VV

A2 - Dongarra, J

A2 - Sloot, PMA

PB - Elsevier

CY - Cairns

ER -

Randall M, Lewis A, Hettenhausen J, Kipouros T. Local search enabled extremal optimisation for continuous inseparable multi-objective benchmark and real-world problems. In Abramson D, Lees M, Krzhizhanovskaya VV, Dongarra J, Sloot PMA, editors, 2014 International conference on computational science. Vol. 29. Cairns: Elsevier. 2014. p. 1904-1914. (Procedia Computer Science). https://doi.org/10.1016/j.procs.2014.05.175