Combining Genetic Algorithm with Variable Neighborhood Search for MAX-SAT

Variable Neighborhood Search (VNS) is a simple meta-heuristic that systematically changes the size and type of neighborhood during the search process in order to escape from local optima. In this paper, a variable-neighborhood-genetic-based-algorithm is proposed for the maximum satisfiability problem (MAX-SAT). Most of the work published earlier on VNS starts from the first neighborhood and moves on to higher neighborhoods without controlling and adapting the ordering of neighborhood structures. The order in which the neighborhood structures have been proposed in this work enables the genetic algorithm with a better mechanism for performing diversification and intensification. A set of benchmark problem instances is used to compare the effectiveness of the proposed algorithm against the standard genetic algorithm. This paper reports promising results when the proposed hybrid algorithm is compared with state-of-the art solvers.