A new genetic algorithm for the SET k-cover problem in wireless sensor networks

The SET k-cover problem is an NP-complete combinatorial optimization problem, which is derived from constructing energy efficient wireless sensor networks (WSNs). The goal of the problem is to find a way to divide sensors into disjoint cover sets, with every cover set being able to fully cover an area and the number of cover sets maximized. Instead of using deterministic algorithms or simple genetic algorithms (GAs), this paper presents a hybrid approach of a GA and a stochastic search. This approach comprises two core modules. The first is the interaction module, which is applied to improve the quality of the population through interaction of individuals. The second is the self construction module, which is a stochastic search procedure running without interaction of individuals. The interaction module is implemented as a combination of selection and crossover, which can efficiently exploit the solutions currently found. The self-construction module includes an adjusted mutation operation and three additional operations. This module is the main force to explore the solution space which can eliminate the inefficiency of using classical GA operations to explore the solution space. Experimental results show that the propose algorithm performs better than the other existing approaches.