An Immune Metaheuristics for Large Instances of the Weighted Feedback Vertex Set Problem

An immune metaheuristic has been developed for solving the Weighted Feedback Vertex Set problem, known to be a NP-complete problem, which finds applicability in many real-world problems. The algorithm takes inspiration by the immune system, and it is based on three main immune operators, such as cloning, hypermutation and aging. In addition to these operators a local search has been also designed with the goal to refine in deterministic way all solutions produced by the stochasticity of these operators. This local search has proved to be fruitful and effective, improving considerably both the performances of immune algorithm and its learning ability. For evaluate the robustness and efficiency of the proposed algorithm several experiments have been performed on a total of 60 graph instances of different large dimensions (from 100 to 529 vertices). Each of these instances shows different topologies; different problem dimensions; different graph density; and different weights on the vertices. The algorithm has been also compared with other three metaheuristics that represent the state-of-the-art on this problem: (1) memetic algorithm based on a genetic algorithm (MA); (2) tabu search metaheuristic (XTS); and (3) iterative tabu search (ITS). From this comparison emerges that the immune metaheuristic has been able to reach the global best solution on 46 instances, unlike of MA that instead found it in only 23 over 60. Furthermore, interestingly that the proposed immune algorithm, among the 46 instances, was able to improve the results with respect to the well known values on 25 instances of these.