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

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). ACM. https://doi.org/10.1145/3071178.3071269