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.