A hybrid multi-objective extremal optimisation approach for multi-objective combinatorial optimisation problems

Pedro Gómez-Meneses, Marcus Randall, Andrew Lewis

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

5 Citations (Scopus)

Abstract

Extremal optimisation (EO) is a relatively recent nature-inspired heuristic whose search method is especially suitable to solve combinatorial optimisation problems. To date, most of the research in EO has been applied for solving single-objective problems and only a relatively small number of attempts to extend EO toward multi-objective problems. This paper presents a hybrid multi-objective version of EO (HMEO) to solve multi-objective combinatorial problems. This new approach consists of a multi-objective EO framework, for the coarse-grain search, which contains a novel multi-objective combinatorial local search framework for the fine-grain search. The chosen problems to test the proposed method are the multi-objective knapsack problem and the multi-objective quadratic assignment problem. The results show that the new algorithm is able to obtain competitive results to SPEA2 and NSGA-II. The non-dominated points found are well-distributed and similar or very close to the Pareto-front found by previous works.

Original languageEnglish
Title of host publication2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010
DOIs
Publication statusPublished - 2010
Event2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010 - Barcelona, Spain
Duration: 18 Jul 201023 Jul 2010

Conference

Conference2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010
CountrySpain
CityBarcelona
Period18/07/1023/07/10

Fingerprint

Multiobjective Combinatorial Optimization
Extremal Optimization
Combinatorial optimization
Multiobjective Optimization Problems
Multiobjective optimization
Combinatorial Optimization Problem
Multi-objective Optimization
Quadratic Assignment Problem
NSGA-II
Pareto Front
Heuristic Search
Knapsack Problem
Combinatorial Problems
Heuristic Method
Search Methods
Local Search

Cite this

Gómez-Meneses, P., Randall, M., & Lewis, A. (2010). A hybrid multi-objective extremal optimisation approach for multi-objective combinatorial optimisation problems. In 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010 [5586194] https://doi.org/10.1109/CEC.2010.5586194
Gómez-Meneses, Pedro ; Randall, Marcus ; Lewis, Andrew. / A hybrid multi-objective extremal optimisation approach for multi-objective combinatorial optimisation problems. 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010. 2010.
@inproceedings{eee40f10c7164344a446f9d264141e5f,
title = "A hybrid multi-objective extremal optimisation approach for multi-objective combinatorial optimisation problems",
abstract = "Extremal optimisation (EO) is a relatively recent nature-inspired heuristic whose search method is especially suitable to solve combinatorial optimisation problems. To date, most of the research in EO has been applied for solving single-objective problems and only a relatively small number of attempts to extend EO toward multi-objective problems. This paper presents a hybrid multi-objective version of EO (HMEO) to solve multi-objective combinatorial problems. This new approach consists of a multi-objective EO framework, for the coarse-grain search, which contains a novel multi-objective combinatorial local search framework for the fine-grain search. The chosen problems to test the proposed method are the multi-objective knapsack problem and the multi-objective quadratic assignment problem. The results show that the new algorithm is able to obtain competitive results to SPEA2 and NSGA-II. The non-dominated points found are well-distributed and similar or very close to the Pareto-front found by previous works.",
author = "Pedro G{\'o}mez-Meneses and Marcus Randall and Andrew Lewis",
year = "2010",
doi = "10.1109/CEC.2010.5586194",
language = "English",
isbn = "9781424469109",
booktitle = "2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010",

}

Gómez-Meneses, P, Randall, M & Lewis, A 2010, A hybrid multi-objective extremal optimisation approach for multi-objective combinatorial optimisation problems. in 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010., 5586194, 2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010, Barcelona, Spain, 18/07/10. https://doi.org/10.1109/CEC.2010.5586194

A hybrid multi-objective extremal optimisation approach for multi-objective combinatorial optimisation problems. / Gómez-Meneses, Pedro; Randall, Marcus; Lewis, Andrew.

2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010. 2010. 5586194.

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

TY - GEN

T1 - A hybrid multi-objective extremal optimisation approach for multi-objective combinatorial optimisation problems

AU - Gómez-Meneses, Pedro

AU - Randall, Marcus

AU - Lewis, Andrew

PY - 2010

Y1 - 2010

N2 - Extremal optimisation (EO) is a relatively recent nature-inspired heuristic whose search method is especially suitable to solve combinatorial optimisation problems. To date, most of the research in EO has been applied for solving single-objective problems and only a relatively small number of attempts to extend EO toward multi-objective problems. This paper presents a hybrid multi-objective version of EO (HMEO) to solve multi-objective combinatorial problems. This new approach consists of a multi-objective EO framework, for the coarse-grain search, which contains a novel multi-objective combinatorial local search framework for the fine-grain search. The chosen problems to test the proposed method are the multi-objective knapsack problem and the multi-objective quadratic assignment problem. The results show that the new algorithm is able to obtain competitive results to SPEA2 and NSGA-II. The non-dominated points found are well-distributed and similar or very close to the Pareto-front found by previous works.

AB - Extremal optimisation (EO) is a relatively recent nature-inspired heuristic whose search method is especially suitable to solve combinatorial optimisation problems. To date, most of the research in EO has been applied for solving single-objective problems and only a relatively small number of attempts to extend EO toward multi-objective problems. This paper presents a hybrid multi-objective version of EO (HMEO) to solve multi-objective combinatorial problems. This new approach consists of a multi-objective EO framework, for the coarse-grain search, which contains a novel multi-objective combinatorial local search framework for the fine-grain search. The chosen problems to test the proposed method are the multi-objective knapsack problem and the multi-objective quadratic assignment problem. The results show that the new algorithm is able to obtain competitive results to SPEA2 and NSGA-II. The non-dominated points found are well-distributed and similar or very close to the Pareto-front found by previous works.

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

U2 - 10.1109/CEC.2010.5586194

DO - 10.1109/CEC.2010.5586194

M3 - Conference contribution

SN - 9781424469109

BT - 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010

ER -

Gómez-Meneses P, Randall M, Lewis A. A hybrid multi-objective extremal optimisation approach for multi-objective combinatorial optimisation problems. In 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010. 2010. 5586194 https://doi.org/10.1109/CEC.2010.5586194