Solving Weighted Constraint Satisfaction Problems Using a new Self-Adaptive Discrete Firefly Algorithm
Mahdi Bidar, Malek Mouhoub · 2019
A Weighted Constraint Satisfaction Problem (WCSP) is a Constraint Satisfaction Problem in which preferences between solutions are considered, meaning that some solutions are more preferred than others and the optimal solution is the one with minimum weight. Such problems are usually dealt with classical complete methods like bucket elimination techniques. However, since these problems are NP-hard the complete methods will require exponential time in addition to a memory space cost. Therefore, approximation methods such as metaheuristics are a good alternative as they are capable of tackling hard to solve combinatorial problems in a very efficient running time. In this regard, we propose a new self-adaptive discrete Firefly algorithm for solving WCSPs. While, like any other approximation algorithm, our method does not guarantee the optimality of the solution returned, the experiments we conducted on randomly generated WCSP instances, demonstrate its ability in returning the optimal solution in a very efficient running time.