A Memetic Algorithm for the Minimum Weighted k-Cardinality Tree Subgraph Problem
Maria Josep Blesa, Pablo Moscato, Fatos Xhafa · 2001
In this paper we present a memetic algorithm for the minimum weighted $k$-cardinality tree subgraph problem. This problem is of relevance to both theory and it has also several industrial applications. Recently, it attracted the attention of several researchers and it is being extensively studied. A breadth of different techniques has been applied to this problem, among them different heuristics that try to give approximate solutions for this NP-hard problem. Memetic algorithms have proved to be good alternative for approximately solving hard combinatorial problems. We present a memetic algorithm to the problem with the enhanced feature of including Tabu Search individual step for local optimization. We also provide an implementation of the algorithm based on generic programming and object oriented programming paradigms. An important aspect of our implementation is that it is obtained from a \\textit{template} for memetic algorithms from which we can easily instantiate other implementations of memetic algorithms for other problems of interest. We evaluate how good the memetic algorithm works for the minimum weighted $k$-cardinality tree subgraph problem by comparing our implementation with other known implementations which are the best heuristic methods available in the literature for the problem.