IRIDIA Projects

Combinatorial and Real Function Optimisation

Intro

When searching for the global optimum solution to complex problems, one is generally faced with a fundamental conflict between precision, reliability and computing time: Each optimization method represents a particular compromise. At IRIDIA for several years, we have beeb trying to understand and compensate for what is lacking in standard Genetic Algorithms (GAs) and Evolutionary Strategies (ESs)

GAs and ESs

Genetic Algorithms (GAs) and Evolutionary Strategies (ESs), which are new promising optimisation methods originaly influenced by Darwinnian Selectionist theory, present unquestionable adventages and original principles such as : population-based search, recombination and stochastic mechanisms (especially the ability to 'rough out' a problem reliably by finding the most promising regions of the entire search space). However, they often represent an unsatisfactory compromise: indeed, they suffer from a certain inefficiency, characterized by a slow convergence and a lack of accuracy when a high-quality solution is required. In contrast, classical hill-climbing methods appear to realize another extreme compromise in solving the conflict: they focus solely on precision and computation time at the expense of reliability and rush to the first discovered local extremum.

At IRIDIA for several years, we have been trying to understand and compensate for what is lacking in standard Genetic Algorithms (GAs) and Evolutionary Strategies (ESs) as to render them efficient for global optimization. Standard GAs focus on the global facet of the optimization task and the lack of attention paid to the local facet often prevents them from being of practical interest for many applications. Conversely, traditional hill-climbing methods (gradient descent, Quasi-Newton methods, simplex method) mainly concentrate on local exploitation. As a rule, the more intensive the local exploitation, the stronger the need for specialized information about the function to be minimized. For classical hill-climbers, global exploitation capacities are often non-existent and, consequently, their utility can be greatly reduced if they are used as such for the optimization of functions with numerous local optima. These considerations, highlighting the complementary properties of GAs and hill-climbing methods, suggest that hybridization between both approaches may lead to improved performances. As a consequence, this has been a center of focus and a constant line of research for IRIDIA in the field of optimization.

Hybridize global and local search: In search of a good crossover between Darwin and classical optimization

Several hybrid methods which involve interwoven levels of optimization have been developed and show very satisfactory behaviour in terms of accuracy and speed on hard optimisation tasks. They are IRM (the Immune Recruitment Mechanism), Simplex-GA, HybHYb-GA and STEP (Select the Easiest Point). These optimisation methods have been applied on canonical combinatorial problems like the travelling salesman problems and others with very satisfactory results. These days, they are applied for industrial applications, for instance the optimization of automatic regulation loops in chemical and biotechnological processes

[ Hugues Bersini | Marco Dorigo | Gregory Seront | Stephane Langerman ]

Selected references

Bersini, H. and F. Varela: The Immune Recruitment Mechanism: A Selective Evolutionary Strategy
In Proceedings of the 4th International Conference on Genetic Algorithms - R. Belew and L. Booker (Eds.) - Morgan Kaufman; 1991, 520-526.
Renders, J-M. & H. Bersini: Hybridizing Genetic Algorithms with Hill-Climbing Methods for Global Optimization: Two Possible Ways.
In Proceedings of the First IEEE Conf. On Evolutionary Programming; 1994, 312-317.
Langerman False Swarzberg, S., Seront, G. and H. Bersini