An Improved Genetic Algorithm for Set Cover using Rosenthal Potential

A major issue with heuristics for set-cover problem is that they tend to get stuck in a local optimum typically because a large local move is necessary to find a better solution. A recent theoretical result shows that replacing the objective function by a proxy (which happens to be Rosenthal potential function) allows escaping such local optima even with small local moves albeit at the cost of an approximation factor. The Rosenthal potential function thus has the effect of smoothing the optimization landscape appropriately so that local search works. In this paper, we use this theoretical insight to design a simple but robust genetic algorithm for weighted set cover. We modify the fitness function as well as the crossover operator of the genetic algorithm to leverage the Rosenthal potential function. We show empirically this greatly improves the quality of the solutions obtained especially in examples where large local moves are required.Our results are better than existing state of the art genetic algorithms and also comparable in performance with the recent local search algorithm NuSC (carefully engineered for set cover) on benchmark instances. Our algorithm, however, performs better than NuSC on simple synthetic instances where starting from an initial solution, large local moves are necessary to find a solution that is close to optimal. For such instances, our algorithm is able to find near optimal solutions whereas NuSC either takes a very long time or returns a much worse solution.