Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS

Rodney O.M. Diana, Sérgio R. de Souza, Elizabeth F. Wanner, Moacir F. França Filho

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Metaheuristics for optimization based on the immune network theory are often highlighted by being able to maintain the diversity of candidate solutions present in the population, allowing a greater coverage of the search space. This work, however, shows that algorithms derived from the aiNET family for the solution of combinatorial problems may not present an adequate strategy for search space exploration, leading to premature convergence in local minimums. In order to solve this issue, a hybrid metaheuristic called VNS-aiNET is proposed, integrating aspects of the COPT-aiNET algorithm with characteristics of the trajectory metaheuristic Variable Neighborhood Search (VNS), as well as a new fitness function, which makes it possible to escape from local minima and enables it to a greater exploration of the search space. The proposed metaheuristic is evaluated using a scheduling problem widely studied in the literature. The performed experiments show that the proposed hybrid metaheuristic presents a convergence superior to two approaches of the aiNET family and to the reference algorithms of the literature. In contrast, the solutions present in the resulting immunological memory have less diversity when compared to the aiNET family approaches.
Original languageEnglish
Title of host publicationGECCO '17: proceedings of the Genetic and Evolutionary Computation Conference
Place of PublicationNew York, NY (US)
PublisherACM
Pages251-258
Number of pages8
ISBN (Electronic)978-1-4503-4939-0
ISBN (Print)978-1-4503-4920-8
DOIs
Publication statusPublished - 15 Jul 2017
EventGenetic and Evolutionary Computation Conference, GECCO '17 - Berlin, Germany
Duration: 15 Jul 201719 Jul 2017

Conference

ConferenceGenetic and Evolutionary Computation Conference, GECCO '17
CountryGermany
CityBerlin
Period15/07/1719/07/17

Fingerprint

Combinatorial optimization
Circuit theory
Scheduling
Trajectories
Data storage equipment
Experiments

Bibliographical note

-

Cite this

Diana, R. O. M., de Souza, S. R., Wanner, E. F., & França Filho, M. F. (2017). Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS. In GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference (pp. 251-258). New York, NY (US): ACM. https://doi.org/10.1145/3071178.3071269
Diana, Rodney O.M. ; de Souza, Sérgio R. ; Wanner, Elizabeth F. ; França Filho, Moacir F. / Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS. GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference . New York, NY (US) : ACM, 2017. pp. 251-258
@inproceedings{0b883ab7e0934aa3a84b6c31e37bcccb,
title = "Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS",
abstract = "Metaheuristics for optimization based on the immune network theory are often highlighted by being able to maintain the diversity of candidate solutions present in the population, allowing a greater coverage of the search space. This work, however, shows that algorithms derived from the aiNET family for the solution of combinatorial problems may not present an adequate strategy for search space exploration, leading to premature convergence in local minimums. In order to solve this issue, a hybrid metaheuristic called VNS-aiNET is proposed, integrating aspects of the COPT-aiNET algorithm with characteristics of the trajectory metaheuristic Variable Neighborhood Search (VNS), as well as a new fitness function, which makes it possible to escape from local minima and enables it to a greater exploration of the search space. The proposed metaheuristic is evaluated using a scheduling problem widely studied in the literature. The performed experiments show that the proposed hybrid metaheuristic presents a convergence superior to two approaches of the aiNET family and to the reference algorithms of the literature. In contrast, the solutions present in the resulting immunological memory have less diversity when compared to the aiNET family approaches.",
author = "Diana, {Rodney O.M.} and {de Souza}, {S{\'e}rgio R.} and Wanner, {Elizabeth F.} and {Fran{\cc}a Filho}, {Moacir F.}",
note = "-",
year = "2017",
month = "7",
day = "15",
doi = "10.1145/3071178.3071269",
language = "English",
isbn = "978-1-4503-4920-8",
pages = "251--258",
booktitle = "GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference",
publisher = "ACM",
address = "United States",

}

Diana, ROM, de Souza, SR, Wanner, EF & França Filho, MF 2017, Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS. in GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference . ACM, New York, NY (US), pp. 251-258, Genetic and Evolutionary Computation Conference, GECCO '17, Berlin, Germany, 15/07/17. https://doi.org/10.1145/3071178.3071269

Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS. / Diana, Rodney O.M.; de Souza, Sérgio R.; Wanner, Elizabeth F.; França Filho, Moacir F.

GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference . New York, NY (US) : ACM, 2017. p. 251-258.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS

AU - Diana, Rodney O.M.

AU - de Souza, Sérgio R.

AU - Wanner, Elizabeth F.

AU - França Filho, Moacir F.

N1 - -

PY - 2017/7/15

Y1 - 2017/7/15

N2 - Metaheuristics for optimization based on the immune network theory are often highlighted by being able to maintain the diversity of candidate solutions present in the population, allowing a greater coverage of the search space. This work, however, shows that algorithms derived from the aiNET family for the solution of combinatorial problems may not present an adequate strategy for search space exploration, leading to premature convergence in local minimums. In order to solve this issue, a hybrid metaheuristic called VNS-aiNET is proposed, integrating aspects of the COPT-aiNET algorithm with characteristics of the trajectory metaheuristic Variable Neighborhood Search (VNS), as well as a new fitness function, which makes it possible to escape from local minima and enables it to a greater exploration of the search space. The proposed metaheuristic is evaluated using a scheduling problem widely studied in the literature. The performed experiments show that the proposed hybrid metaheuristic presents a convergence superior to two approaches of the aiNET family and to the reference algorithms of the literature. In contrast, the solutions present in the resulting immunological memory have less diversity when compared to the aiNET family approaches.

AB - Metaheuristics for optimization based on the immune network theory are often highlighted by being able to maintain the diversity of candidate solutions present in the population, allowing a greater coverage of the search space. This work, however, shows that algorithms derived from the aiNET family for the solution of combinatorial problems may not present an adequate strategy for search space exploration, leading to premature convergence in local minimums. In order to solve this issue, a hybrid metaheuristic called VNS-aiNET is proposed, integrating aspects of the COPT-aiNET algorithm with characteristics of the trajectory metaheuristic Variable Neighborhood Search (VNS), as well as a new fitness function, which makes it possible to escape from local minima and enables it to a greater exploration of the search space. The proposed metaheuristic is evaluated using a scheduling problem widely studied in the literature. The performed experiments show that the proposed hybrid metaheuristic presents a convergence superior to two approaches of the aiNET family and to the reference algorithms of the literature. In contrast, the solutions present in the resulting immunological memory have less diversity when compared to the aiNET family approaches.

U2 - 10.1145/3071178.3071269

DO - 10.1145/3071178.3071269

M3 - Conference contribution

SN - 978-1-4503-4920-8

SP - 251

EP - 258

BT - GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference

PB - ACM

CY - New York, NY (US)

ER -

Diana ROM, de Souza SR, Wanner EF, França Filho MF. Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS. In GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference . New York, NY (US): ACM. 2017. p. 251-258 https://doi.org/10.1145/3071178.3071269