Runtime Analysis of Crowding Mechanisms for Multimodal Optimization
| Autor: | Edgar Covantes Osuna, Dirk Sudholt |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
Optimization problem Fitness function Probabilistic logic 02 engineering and technology Function (mathematics) Crowding Theoretical Computer Science Random search Computational Theory and Mathematics Exponential growth 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Software Selection (genetic algorithm) |
| Zdroj: | IEEE Transactions on Evolutionary Computation. 24:581-592 |
| ISSN: | 1941-0026 1089-778X |
| Popis: | Many real-world optimization problems lead to multimodal domains and require the identification of multiple optima. Crowding methods have been developed to maintain population diversity, to investigate many peaks in parallel and to reduce genetic drift. We present the first rigorous runtime analyses of probabilistic crowding and generalized crowding, embedded in a ( $\mu +1$ ) EA. In probabilistic crowding the offspring compete with their parent in a fitness-proportional selection. Generalized crowding decreases the fitness of the inferior solution by a scaling factor during selection. We consider the bimodal function TwoMax and introduce a novel and natural notion for functions with bounded gradients. For a broad range of such functions we prove that probabilistic crowding needs exponential time with overwhelming probability to find solutions significantly closer to any global optimum than those found by random search. Even when the fitness function is scaled exponentially, probabilistic crowding still fails badly. Only if the exponential’s base is linear in the problem size, probabilistic crowding becomes efficient on TwoMax. A similar threshold behavior holds for generalized crowding on TwoMax with respect to the scaling factor. Our theoretical results are accompanied by experiments for TwoMax showing that the threshold behaviors also apply to the best fitness found. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|