About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
First EAI International Conference on Computer Science and Engineering

Research Article

Combining Genetic Algorithm with Variable Neighborhood Search for MAX-SAT

Download2023 downloads
Cite
BibTeX Plain Text
  • @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.

Keywords
genetic algorithm variable neighborhood search maxi-mum satisfiability problem.
Published
2017-03-09
Publisher
EAI
http://dx.doi.org/10.4108/eai.27-2-2017.152347
Copyright © 2016–2025 EAI
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL