Two population-based optimization algorithms for minimum weight connected dominating set problem

Minimum weight connected dominating set (MWCDS) is a very important NP-Hard problem used in many applications such as backbone formation, data aggregation, routing and scheduling in wireless ad hoc and sensor networks. Population-based approaches are very useful to solve NP-Hard optimization problems. In this study, a hybrid genetic algorithm (HGA) and a population-based iterated greedy (PBIG) algorithm for MWCDS problem are proposed. To the best of our knowledge, the proposed algorithms are the first population-based algorithms to solve MWCDS problem on undirected graphs. HGA is a steady-state procedure which incorporates a greedy heuristic with a genetic search. PBIG algorithm refines the population by partially destroying and greedily reconstructing individual solutions. We compare the performance of the proposed algorithms with other greedy heuristics and brute force methods through extensive simulations. We show that our proposed algorithms perform very well in terms of MWCDS solution quality and CPU time. (C) 2017 Elsevier B.V. All rights reserved.