Combining Interval Methods with Evolutionary Algorithms for Global OptimizationReport as inadecuate

Combining Interval Methods with Evolutionary Algorithms for Global Optimization - Download this document for free, or read online. Document in PDF available to download.

1 MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l-Aérien 2 IRIT - Institut de recherche en informatique de Toulouse

Abstract : Reliable global optimization is dedicated to solving problems to optimality in the presence of rounding errors. The most successful approaches for achieving a numerical proof of optimality in global optimization are mainly exhaustive interval-based algorithms that interleave pruning and branching steps. The Interval Branch & Prune IBP framework has been widely studied and has benefitted from the development of refutation methods and filtering algorithms stemming from the Interval Analysis and Interval Constraint Programming communities. In a minimization problem, refutation consists in discarding subdomains of the search-space where a lower bound of the objective function is worse than the best known solution. It is therefore crucial: i to compute a sharp lower bound of the objective function on a given subdomain; ii to find a good approximation an upper bound of the global minimum. Many techniques aim at narrowing the pessimistic enclosures of interval arithmetic centered forms, convex relaxation, local monotonicity, etc. and will not be discussed in further detail. State-of-the-art solvers are generally integrative methods, that is they embed local optimization algorithms BFGS, LP, interior points to compute an upper bound of the global minimum over each subspace. In this presentation, we propose a cooperative approach in which interval methods collaborate with Evolutionary Algorithms EA on aglobalscale. EA are stochastic algorithms in which a population of individuals candidate solutions iteratively evolves in the search-space to reach satisfactory solutions. They make no assumption on the objective function and are equipped with nature-inspired operators that help individuals escape from local minima. EA are thus particularly suitable for highly multimodal nonconvex problems. In our approach, the EA and the IBP algorithm run in parallel and exchange bounds and solutions through shared memory: the EA updates the best known upper bound of the global minimum to enhance the pruning, while the IBP updates the population of the EA when a better solution is found. We show that this cooperation scheme prevents premature convergence toward local minima and accelerates the convergence of the interval method. Our hybrid algorithm also exploits a geometric heuristic to select the next subdomain to be processed, that compares well with standard heuristics best first, largest first. We provide new optimality results for a benchmark of difficult multimodal problems Michalewicz, Egg Holder, Rana, Keane functions. We also certify the global minimum of the open Lennard-Jones cluster problem for 5 atoms. Finally we present an aeronautical application to solve conflicts between aircraft.

Keywords : global optimization interval analysis evolutionary algorithms

Author: Charlie Vanaret - Jean-Baptiste Gotteland - Nicolas Durand - Jean-Marc Alliot -



Related documents