Tags:Generalized Arc Consistency, Global Optimization and Metaheuristics
Abstract:
Domain filtering techniques such as Generalized Arc Consistency (GAC) are powerful tools to prune partially inconsistent assignments in a branch-and-prune scheme. Although such techniques are usually applied to exact approaches, we show that metaheuristic algorithms can benefit from domain filtering. In this paper, we propose a variation of the well-known AC3 algorithm that iteratively approximates GAC over the structural information of the constraint network. We integrate the algorithm with an interval-based Differential Evolution (DE) to tackle numerical constrained global optimization problems. Our method consists of a hybrid approach: at first, the interval-based DE iteratively explores the search domain generating a population of interval boxes; then, these boxes are pruned by the local consistency algorithm; at last, a real-based black box DE is used as a local search within each box. The experimental results, over a subset of COCONUT Benchmark instances with up to 100 dimensions, show that the use of the proposed domain filtering to prune the boxes can improve the quality of the solutions by 37.15%, at the cost of 7.82% in processing time. The results indicate the benefits of integrating constraint propagation techniques and metaheuristic algorithms to tackle optimization problems.
A Hybrid Approach Integrating Generalized Arc Consistency and Differential Evolution for Global Optimization