%0 Journal Article
%T Hybridization of Interval CP and Evolutionary Algorithms for Optimizing Difficult Problems
%A Charlie Vanaret
%A Jean-Baptiste Gotteland
%A Nicolas Durand
%A Jean-Marc Alliot
%J Mathematics
%D 2015
%I arXiv
%R 10.1007/978-3-319-23219-5_32
%X The only rigorous approaches for achieving a numerical proof of optimality in global optimization are interval-based methods that interleave branching of the search-space and pruning of the subdomains that cannot contain an optimal solution. State-of-the-art solvers generally integrate local optimization algorithms to compute a good upper bound of the global minimum over each subspace. In this document, we propose a cooperative framework in which interval methods cooperate with evolutionary algorithms. The latter are stochastic algorithms in which a population of candidate solutions iteratively evolves in the search-space to reach satisfactory solutions. Within our cooperative solver Charibde, the evolutionary algorithm and the interval-based algorithm run in parallel and exchange bounds, solutions and search-space in an advanced manner via message passing. A comparison of Charibde with state-of-the-art interval-based solvers (GlobSol, IBBA, Ibex) and NLP solvers (Couenne, BARON) on a benchmark of difficult COCONUT problems shows that Charibde is highly competitive against non-rigorous solvers and converges faster than rigorous solvers by an order of magnitude.
%U http://arxiv.org/abs/1510.04914v1