Hybridization of evolutionary algorithms and interval-based methods for optimizing difficult problems

L’optimisation globale fiable est dédiée à la recherche d’un minimum global en présence d’erreurs d’arrondis. Les seules approches fournissant une preuve numérique d’optimalité sont des méthodes d’intervalles qui partitionnent l’espace de recherche et éliminent les sous-espaces qui ne peuvent contenir de solution optimale. Ces méthodes exhaustives, appelées branch and bound par intervalles, sont étudiées depuis les années 60 et ont récemment intégré des techniques de réfutation et de contraction, issues des communautés d’analyse par intervalles et de programmation par contraintes. Il est d’une importance cruciale de calculer i) un encadrement précis de la fonction objectif et des contraintes sur un sous-domaine ; ii) une bonne approximation (un majorant) du minimum global. Les solveurs de pointe sont généralement des méthodes intégratives : ils invoquent sur chaque sous-domaine des algorithmes d’optimisation locale afin d’obtenir une bonne approximation du minimum global. Dans ce document, nous nous intéressons à un cadre coopératif combinant des méthodes d’intervalles et des algorithmes évolutionnaires. Ces derniers sont des algorithmes stochastiques faisant évoluer une population de solutions candidates (individus) dans l’espace de recherche de manière itérative, dans l’espoir de converger vers des solutions satisfaisantes. Les algorithmes évolutionnaires, dotés de mécanismes permettant de s’échapper des minima locaux, sont particulièrement adaptés à la résolution de problèmes difficiles pour lesquels les méthodes traditionnelles peinent à converger. Au sein de notre solveur coopératif Charibde, l’algorithme évolutionnaire et l’algorithme sur intervalles exécutés en parallèle échangent bornes, solutions et espace de recherche par passage de messages. Une stratégie couplant une heuristique d’exploration géométrique et un opérateur de réduction de domaine empêche la convergence prématurée de la population vers des minima locaux et évite à l’algorithme évolutionnaire d’explorer des sous-espaces sous-optimaux ou non réalisables. Une comparaison de Charibde avec des solveurs de pointe (GlobSol, IBBA, Ibex) sur une base de problèmes difficiles montre un gain de temps d’un ordre de grandeur. De nouveaux résultats optimaux sont fournis pour cinq problèmes multimodaux pour lesquels peu de solutions, même approchées, sont connues dans la littérature. Nous proposons une application aéronautique dans laquelle la résolution de conflits est modélisée par un problème d’optimisation sous contraintes universellement quantifiées, et résolue par des techniques d’intervalles spécifiques. Enfin, nous certifions l’optimalité de la meilleure solution connue pour le cluster de Lennard-Jones à cinq atomes, un problème ouvert en dynamique moléculaire.Reliable global optimization is dedicated to finding a global minimum in the presence of rounding errors. The only 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. The exhaustive interval branch and bound methods have been widely studied since the 1960s and have benefitted from the development of refutation methods and filtering algorithms, stemming from the interval analysis and interval constraint programming communities. It is of the utmost importance: i) to compute sharp enclosures of the objective function and the constraints on a given subdomain; ii) to find a good approximation (an upper bound) of the global minimum. State-of-the-art solvers are generally integrative methods, that is they embed 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 individuals (candidate solutions) iteratively evolves in the search-space to reach satisfactory solutions. Evolutionary algorithms, endowed with operators that help individuals escape from local minima, are particularly suited for difficult problems on which traditional methods struggle to converge. Within our cooperative solver Charibde, the evolutionary algorithm and the intervalbased algorithm run in parallel and exchange bounds, solutions and search-space via message passing. A strategy combining a geometric exploration heuristic and a domain reduction operator prevents premature convergence toward local minima and prevents the evolutionary algorithm from exploring suboptimal or unfeasible subspaces. A comparison of Charibde with state-of-the-art solvers based on interval analysis (GlobSol, IBBA, Ibex) on a benchmark of difficult problems shows that Charibde converges faster by an order of magnitude. New optimality results are provided for five multimodal problems, for which few solutions were available in the literature. We present an aeronautical application in which conflict solving between aircraft is modeled by an universally quantified constrained optimization problem, and solved by specific interval contractors. Finally, we certify the optimality of the putative solution to the Lennard-Jones cluster problem for five atoms, an open problem in molecular dynamics