AGAGD - An Adaptive Genetic Algorithm Guided by Decomposition for Solving PCSPs

Lamia Sadeg-Belkacem, Zineb Habbas, Wassila Aggoune-Mtalaa

2015

Abstract

Solving a Partial Constraint Satisfaction Problem consists in assigning values to all the variables of the problem such that a maximal subset of the constraints is satisfied. An efficient algorithm for large instances of such problems which are NP-hard does not exist yet. Decomposition methods enable to detect and exploit some crucial structures of the problems like the clusters, or the cuts, and then apply that knowledge to solve the problem. This knowledge can be explored by solving the different sub-problems separately before combining all the partial solutions in order to obtain a global one. This was the focus of a previous work which led to some generic algorithms based on decomposition and using an adaptive genetic algorithm, for solving the subproblems induced by the crucial structures coming from the decomposition. This paper aims to explore the decomposition differently. Indeed, here the knowledge is used to improve this adaptive genetic algorithm. A new adaptive genetic algorithm guided by structural knowledge is proposed. It is designed to be generic in order that any decomposition method can be used and different heuristics for the genetic operators are possible. To prove the effectiveness of this approach, three heuristics for the crossover step are investigated.

Paper Citation

in Harvard Style

Sadeg-Belkacem L., Habbas Z. and Aggoune-Mtalaa W. (2015). AGAGD - An Adaptive Genetic Algorithm Guided by Decomposition for Solving PCSPs . In Proceedings of the International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-758-074-1, pages 78-89. DOI: 10.5220/0005196400780089

in Bibtex Style

@conference{icaart15,
author={Lamia Sadeg-Belkacem and Zineb Habbas and Wassila Aggoune-Mtalaa},
title={AGAGD - An Adaptive Genetic Algorithm Guided by Decomposition for Solving PCSPs},
booktitle={Proceedings of the International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2015},
pages={78-89},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005196400780089},
isbn={978-989-758-074-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - AGAGD - An Adaptive Genetic Algorithm Guided by Decomposition for Solving PCSPs
SN - 978-989-758-074-1
AU - Sadeg-Belkacem L.
AU - Habbas Z.
AU - Aggoune-Mtalaa W.
PY - 2015
SP - 78
EP - 89
DO - 10.5220/0005196400780089