Combining Interval Methods with Evolutionary Algorithms for Global Optimization - ENAC - École nationale de l'aviation civile Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Combining Interval Methods with Evolutionary Algorithms for Global Optimization

Charlie Vanaret
Jean-Baptiste Gotteland
Nicolas Durand
Jean-Marc Alliot
• Fonction : Auteur

Résumé

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.

Dates et versions

hal-01066902 , version 1 (29-09-2014)

Identifiants

• HAL Id : hal-01066902 , version 1

Citer

Charlie Vanaret, Jean-Baptiste Gotteland, Nicolas Durand, Jean-Marc Alliot. Combining Interval Methods with Evolutionary Algorithms for Global Optimization. SCAN 2014, 16th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, Sep 2014, Würzburg, Germany. pp 162-163. ⟨hal-01066902⟩

Collections

330 Consultations
99 Téléchargements