First EAI International Conference on Computer Science and Engineering

Research Article

Combining Genetic Algorithm with Variable Neighborhood Search for MAX-SAT

Download500 downloads
  • @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
Noureddine Bouhmala1,*, Kjell Ivar Øvergård1
  • 1: University College of Southeast Norway, Department of Maritime Technology and Innovation
*Contact email: nouredine.bouhmala@hbv.no

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.