Evolutionary Algorithms (EAs), popular population-based stochastic
search-methods, have the tendency to lose diversity within their population of
feasible solutions and to converge into a single solution. Niching methods,
the extension of EAs to multi-modal optimization, address this issue by
maintaining the diversity of certain properties within the population - and this
way they allow parallel convergence into multiple good solutions in multimodal
domains. To this end, niching methods have been studied mainly within the field
of Genetic Algorithms (GAs). The research in this direction has yielded various
successful methods which have been shown to find multiple solutions efficiently,
but naturally were limited to low-dimensional real-valued problems. Evolution
Strategies (ES) are a canonical EA for real-valued function optimization,
due to their straightforward encoding, their specific variation operators, the
self-adaptation of their mutation distribution as well as to their high
performance in this domain in comparison with other methods on benchmark
problems. The higher the dimensionality of the search space, the more suitable a
task becomes for an ES.
The study of niching is challenging both from the theoretical point of view
and from the practical point of view. The theoretical challenge is two-fold -
maintaining the diversity within a population-based stochastic algorithm from
the computational perspective, but also having an insight into speciation
theory from the biological perspective. The practical aspect provides a
real-world motivation for this problem - there is an increasing interest of the
applications' community in providing the decision maker with multiple solutions
with different conceptual designs, for single- or multi-objective
search spaces.
[LEFT] An analogy: find the best runners with the highest genetic diversity among
each other. [CENTER]
Natural speciation: illustration. [RIGHT] Speciation table: butterflies.
Literature
Niching in Evolutionary Algorithms
Shir, O.M.: Niching in Evolutionary Algorithms. In: Handbook of Natural Computing: Theory, Experiments, and Applications. Springer-Verlag, Berlin-Heidelberg, Germany (2012) 1035-1069
Evolution Strategies
Th. Bäck. Evolutionary algorithms in
theory and practice. Oxford University Press, New York, NY, USA, 1996.
H.-G. Beyer and H.-P. Schwefel. Evolution strategies a comprehensive
introduction. Natural Computing: an international journal, 1(1), 2002.
Derandomized Evolution Strategies
N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in
evolution strategies. Evolutionary Computation, 9(2), 2001. (CMA-ES)
C. Igel, T. Suttorp, and N. Hansen. A computational efficient covariance
matrix update and a (1+1)-CMA for evolution strategies. In Proceedings of
the Genetic and Evolutionary Computation Conference (GECCO 2006). ACM Press, 2006.
N. Hansen, A. Ostermeier, and A. Gawelczyk. On the adaptation of
arbitrary normal mutation distributions in evolution strategies: The
generating set adaptation. In Proceedings of the Sixth International
Conference on Genetic Algorithms (ICGA6), 1995.
A. Ostermeier, A. Gawelczyk, and N. Hansen. Step-size adaptation based
on non-local use of selection information. In Parallel Problem Solving from
Nature (PPSN3), 1994.
A. Ostermeier, A. Gawelczyk, and N. Hansen. A derandomized approach to
self adaptation of evolution strategies. Technical report, 1993.
Classical Niching Concepts
S. Mahfoud. Niching Methods for Genetic Algorithms. PhD thesis,
University of Illinois at Urbana Champaign, 1995.
K.A de Jong.: An analysis of the behavior of a class of genetic adaptive
systems. PhD thesis, 1975.
D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for
multimodal function optimization. In Proceedings of the Second International
Conference on Genetic Algorithms on Genetic algorithms and their
application, Mahwah, NJ, USA, 1987. Lawrence Erlbaum Associates, Inc.
B. Miller and M. Shaw. Genetic algorithms with dynamic niche sharing for
multimodal function optimization. In Proceedings of the 1996 IEEE
International Conference on Evolutionary Computation (ICEC'96), New York,
NY, USA, 1996.
Niching in Evolution Strategies
Ofer M. Shir and Thomas Bäck. Niching with
Derandomized Evolution Strategies in Artificial and Real-World Landscapes.
Natural Computing: An International Journal, Springer. 8(1) (2009) 171--196
Ofer M. Shir, PhD Dissertation: Niching in
Derandomized Evolution Strategies and its Applications in Quantum Control; A
Journey from Organic Diversity to Conceptual Quantum Designs. Thesis
Universiteit Leiden. ISBN: 978-90-6464-256-2. Printed in The Netherlands,
2008.
pdf
The Niche Radius Problem
Jelasity, M.: Uego, an abstract niching technique for global
optimization. In: Parallel Problem Solving from Nature - PPSN V. Volume
1498., Amsterdam, Springer (1998)
Gan, J., Warwick, K.: Dynamic niche clustering: A fuzzy variable radius
niching technique for multimodal optimisation in GAs. In: Proceedings of the
2001 Congress on Evolutionary Computation CEC2001, COEX, World Trade Center,
159 Samseong-dong, Gangnam-gu, Seoul, Korea, IEEE Press (2001)
A.D. Cioppa, C.D. Stefano and A. Marcelli.: On the role of population
size and niche radius in fitness sharing. IEEE Trans. Evolutionary
Computation 8 (2004)
Ofer M. Shir, Michael Emmerich and Thomas Bäck.
Adaptive Niche-Radii and Niche-Shapes Approaches for Niching with the
CMA-ES. Evolutionary Computation, MIT Press. 18(1) (2010) 97--126
Clustering-Based
F. Streichert, G. Stein, H. Ulmer and A. Zell. A clustering based niching ea for multimodal search spaces.
In Proceedings of the International Conference Evolution Artificielle, volume 2936 of Lecture Notes in Computer Science, 2003.
O. Aichholzer, F. Aurenhammer, B. Brandtstätter, T. Ebner, H. Krasser, and C. Magele. Niching Evolution Strategy with Cluster Algorithms.
Miscellaneous
Deb, K., Goldberg, D.E.: An investigation of niche and species formation
in genetic function optimization. In: Proceedings of the third international
conference on Genetic algorithms, San Francisco, CA, USA, Morgan Kaufmann
Publishers Inc. (1989)
M. Preuss, L. Schönemann and M.
Emmerich: Counteracting genetic drift and disruptive recombination in (μ,
λ)-ea on multimodal fitness landscapes. In: GECCO '05: Proceedings of the
2005 conference on Genetic and evolutionary computation, New York, NY, USA,
ACM Press (2005).
Illustration: Niching in Action
Tracking 4 minima on the Fletcher-Powell n=2 landscape with the Mahalanobis-CMA+ routine: avi.
