Research Article
Combining Genetic Algorithm with Variable Neighborhood Search for MAX-SAT
@INPROCEEDINGS{10.4108/eai.27-2-2017.152347, author={Noureddine Bouhmala and Kjell Ivar \`{U}verg\ae{}rd}, title={Combining Genetic Algorithm with Variable Neighborhood Search for MAX-SAT}, proceedings={First EAI International Conference on Computer Science and Engineering}, publisher={EAI}, proceedings_a={COMPSE}, year={2017}, month={3}, keywords={genetic algorithm variable neighborhood search maxi-mum satisfiability problem.}, doi={10.4108/eai.27-2-2017.152347} }- Noureddine Bouhmala
Kjell Ivar Øvergård
Year: 2017
Combining Genetic Algorithm with Variable Neighborhood Search for MAX-SAT
COMPSE
EAI
DOI: 10.4108/eai.27-2-2017.152347
Abstract
Metaheuristics used to tackle different optimization prob-lems that arise in various fields aim at finding a tactical interplay be-tween diversification and intensification to overcome local optimality. In this paper, a genetic algorithm (GA) combined with variable neighbor-hood search (VNS) is proposed for solving the maximum satisfiability problem. VNS systematically changes different neighborhoods within a local search. The idea is that a local optimum reached within one neighborhood structure is not necessarily the same local optimum of another neighborhood structure, thus the search can systematically explore differ-ent search areas which are defined by different neighborhood structures. Results comparing the genetic with and without VNS are presented. In addition, GA combined with VNS is compared against state-of-the-art algorithms in order to show its effectiveness.