A hybrid algorithm based on Tabu Search and Immune Algorithm for k-cardinality tree problems

A k-cardinality tree problem (KCTP) is to find a subtree with exactly k edges in an undirected, connected, weighted graph, such that the sum of weights is minimal. KCTP has been proved to be an NP-hard combinatorial optimization problem. In this paper, a hybrid algorithm (TSIA) based on Tabu Search (TS) and Immune Algorithm (IA) is presented for solving KCTP. The immune system inspired operator enforces diversity in the population of solutions. Numerical results demonstrate that the proposed algorithm is competitive to existing state-of-art algorithms in both precision and computing time.