Mike Preuss - Metaheuristics for Finding Multiple Solutions

More information about this series at http://www.springer.com/series/4190

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

My first encounter with the notion of multimodal optimization came in the early 1970s from discussions with my father, an acoustical engineer, regarding his approach to optimizing the acoustical properties of auditoriums used for concerts, religious services, congress halls, etc. The computational tools of his generation of engineers were slide rules and desk calculators, and so design optimization involved the manual evaluation of a relatively few, carefully chosen points in design space. Our conversations were motivated by the increasing availability of computers and their use in science and engineering and the possibility of significantly improving his time-intensive design process. It also happened to be at the time that I was doing my thesis and deeply involved in understanding how Hollands adaptive plans could be instantiated as algorithms useful for solving optimization problems.

As these initial (genetic) algorithms were developed, early notions of premature convergence emerged out of observations that most optimization problems of interest had multiple modes (optima) or equivalently, from a landscape perspective, multiple peaks and valleys and that these simple evolutionary algorithms were quite adept at quickly converging to a peak, but not necessarily the highest one. That lead to a variety of early ideas about algorithmic modifications such as crowding, fitness sharing, and niching to slow down the rate of convergence, maintain more population diversity, and improve problem-solving performance.

So, here we are, 50 years later, during which time we have seen the development of a wide variety of evolutionary algorithms far more complex and sophisticated than those simple genetic algorithms. At the same time, we continue to be confronted with multimodal optimization problems of increasing size and complexity. The result is the need for continuing the development and advancement of algorithmic techniques for solving them. This book fills an important gap and provides a valuable service with its clear introduction to the area, a precise summary of the issues, and a well-rounded survey of the current state of the art in multimodal optimization. It should be recommended reading for anyone interested in research in this area or involved in solving difficult application problems.

P.S. Those early discussions with my father led to the development of a simple evolutionary algorithm written in Basic, running on a family TRS-80, and allowed him to explore his acoustical design spaces in much more detail.

The goal of maintaining a diverse set of solutions in population-based stochastic optimization algorithms has been pursued for the past several decades. This has been driven by the need to effectively distribute their search over the design space, which in practice often has complicated mappings under an optimized quality function that can lead to premature convergence and the delivery of sub-optimal solutions if diversity is not maintained. Techniques designed specifically for achieving this goal are commonly referred to as niching techniques. Iconic niching techniques such as crowding and fitness sharing were developed as early as the 70s and 80s in the previous century by Kenneth De Jong and David Goldberg, respectively. At first, obtaining several distinct optimal solutions in one optimization run was not the primary motivation, but rather improving the chances to detect the sought single global optimum. These two goals are still intertwined in todays meta-heuristic algorithms, as it is not possible to know in practice if a solution is globally optimal without knowing other optima that may exist. Furthermore, in many application settings, it is also important to know alternative structurally distinct optimal solutions, e.g., design optimization. This is the main aim of what we see as multimodal optimization nowadays, also framed as multi-solution optimization by some researchers.

It has been common to subsume these types of algorithms by the term niching algorithms in recent decades, taking inspiration from biological niching mechanisms. However, modern evolutionary biology rather thinks of niches as the co-creation of organisms as opposed to a static setting that just has to be found. Interestingly, this perspective on population behavior and dynamics is the main motivation for quality diversity, which is nowadays a flourishing research topic area with close links to multimodal optimization. The term niching now often refers to the niching effects induced inside a standard optimization algorithm, which aims to ensure the found solutions are well distributed.