A Hybrid Genetic Algorithm for Minimum Weight Dominating Set Problem

Minimum Weight Dominating Set (MWDS) belongs to the class of NP-hard graph problem which has several real life applications especially in wireless networks. In this paper, we present a new hybrid genetic algorithm. Also, we propose a new heuristic algorithm for MWDS to create initial population. We test our hybrid genetic algorithm on (Jovanovic et al., Proceedings of the 12th WSEAS international conference on automatic control, modeling and simulation, 2010) [3] data set. Then the results are compared with existing algorithms in the literature. The experimental results show that our hybrid genetic algorithm can yield better solutions than these algorithms and faster than these algorithms.