Bees Swarm Optimization Metaheuristic Guided by Decomposition for Solving MAX-SAT

Youcef Djenouri, Zineb Habbas, Wassila Aggoune-Mtalaa

2016

Abstract

Decomposition methods aim to split a problem into a collection a collection of smaller interconnected sub-problems. Several research works have explored decomposition methods for solving large optimization problems. Due to its theroretical properties, Tree decomposition has been especially the subject of numerous successfull studies in the context of exact optimization solvers. More recently, Tree decomposition has been successfully used to guide the Variable Neighbor Search (VNS) local search method. Our present contribution follows this last direction and proposes two approaches called BSOGD1 and BSOGD2 for guiding the Bees Swarm Optimization (BSO) metaheuristic by using a decomposition method. More pragmatically, this paper deals with the MAX-SAT problem and uses the Kmeans algorithm as a decomposition method. Several experimental results conducted on DIMACS benchmarks and some other hard SAT instances lead to promising results in terms of the quality of the solutions. Moreover, these experiments highlight a good stability of the two approaches, more especially, when dealing with hard instances like the Parity8 family from DIMACS. Beyond these first promising results, note that this approach can be easily applied to many other optimization problems such as the Weighted MAX-SAT, the MAX-CSP or the coloring problem and can be used with other decomposition methods as well as other metaheuristics.

Paper Citation

in Harvard Style

Djenouri Y., Habbas Z. and Aggoune-Mtalaa W. (2016). Bees Swarm Optimization Metaheuristic Guided by Decomposition for Solving MAX-SAT . In Proceedings of the 8th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-758-172-4, pages 472-479. DOI: 10.5220/0005810004720479

in Bibtex Style

@conference{icaart16,
author={Youcef Djenouri and Zineb Habbas and Wassila Aggoune-Mtalaa},
title={Bees Swarm Optimization Metaheuristic Guided by Decomposition for Solving MAX-SAT},
booktitle={Proceedings of the 8th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2016},
pages={472-479},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005810004720479},
isbn={978-989-758-172-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 8th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - Bees Swarm Optimization Metaheuristic Guided by Decomposition for Solving MAX-SAT
SN - 978-989-758-172-4
AU - Djenouri Y.
AU - Habbas Z.
AU - Aggoune-Mtalaa W.
PY - 2016
SP - 472
EP - 479
DO - 10.5220/0005810004720479