A Hybrid Immune Algorithm for the Weighted Feedback Vertex Set problem

A hybrid immunological algorithm based on the clonal selection principle of the immune system, for the Weighted Feedback Vertex Set problem (WFVS). Finding the minimum feedback vertex set in a graph is an important combinatorial problem that has a variety of real applications. The proposed algorithm, developed in Python using NetworkX library, has been tested on different instances of the problem. Each instance is characterized by the number of vertices (size), the number of edges and a range of values for the weight of the vertices. Various experimental results show how the proposed immunological algorithm is efficient in terms of accuracy as it reaches or approximates the various optimal values of instances. These results confirm also the robustness of the algorithm whose effectiveness does not appear to be influenced either by the range of assigned weights, or by the nodes or graph classes used.

  • Job : Development, Python
  • Date : Sep 2017
  • Agency : University of Catania