6533b7d1fe1ef96bd125ca5e
RESEARCH PRODUCT
Shaping communities of local optima by perturbation strength
Franz RothlaufMatthias HerrmannSebastian HerrmannGabriela Ochoasubject
Mathematical optimization021103 operations researchIterated local searchFitness landscapeComputer Science::Neural and Evolutionary Computation0211 other engineering and technologiesPerturbation (astronomy)02 engineering and technologyLocal optima networksLocal optimum0202 electrical engineering electronic engineering information engineeringPerturbation operator020201 artificial intelligence & image processingMathematicsdescription
Recent work discovered that fitness landscapes induced by Iterated Local Search (ILS) may consist of multiple clusters, denoted as funnels or communities of local optima. Such studies exist only for perturbation operators (kicks) with low strength. We examine how different strengths of the ILS perturbation operator affect the number and size of clusters. We present an empirical study based on local optima networks from NK fitness landscapes. Our results show that a properly selected perturbation strength can help overcome the effect of ILS getting trapped in clusters of local optima. This has implications for designing effective ILS approaches in practice, where traditionally only small perturbations or complete restarts are applied, with the middle ground of intermediate perturbation strengths largely unexplored.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-07-01 | Proceedings of the Genetic and Evolutionary Computation Conference |