In multi-modal and multi-objective evolutionary optimization, it is very important maintain a diversified population. Niching, crowding and sharing techniques are among the most popular. Which are their key differences? Which other techniques exist for this purpose? What seminar paper or survey could you recommend on this topic?
Niching is a general term for encouraging an evolutionary algorithm to explore multiple solutions. You might also see this referred to as diversity preservation or speciation.
Crowding is one approach to niching, and it achieves it by replacing similar existing individuals when adding new solutions to the population. There are both deterministic and probabilistic variants.
Fitness sharing is another approach. This uses a fitness penalty to penalise solutions that are similar to other solutions, encouraging exploration in new areas of the search space. Unlike crowding, it requires a distance metric to be defined.
Some pointers:
"Fitness Sharing and Niching Methods Revisited" (http://dx.doi.org/10.1109/4235.735432).
"The Crowding Approach to Niching in Genetic Algorithms"
(http://dl.acm.org/citation.cfm?id=1450302)
Another popular method is geographical segregation. This involves explicitly sub-dividing the population in some manner, and then allowing the sub-populations to evolve in different directions. Island models use a small number of sub-populations. Cellular (or fine-grained) approaches use many. See, for instance, "Parallel Genetic Algorithms" (http://www.liacs.nl/assets/PDF/pit.95.pdf)
I've also used population clustering. This uses a clustering algorithm to create a new set of sub-populations at each generation. See http://eprints.whiterose.ac.uk/3419/
Hello,
You can view this interesting paper "Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications" of Zitzler. E, 1999.
Regards.
Amin.
Niching is a general term for encouraging an evolutionary algorithm to explore multiple solutions. You might also see this referred to as diversity preservation or speciation.
Crowding is one approach to niching, and it achieves it by replacing similar existing individuals when adding new solutions to the population. There are both deterministic and probabilistic variants.
Fitness sharing is another approach. This uses a fitness penalty to penalise solutions that are similar to other solutions, encouraging exploration in new areas of the search space. Unlike crowding, it requires a distance metric to be defined.
Some pointers:
"Fitness Sharing and Niching Methods Revisited" (http://dx.doi.org/10.1109/4235.735432).
"The Crowding Approach to Niching in Genetic Algorithms"
(http://dl.acm.org/citation.cfm?id=1450302)
Another popular method is geographical segregation. This involves explicitly sub-dividing the population in some manner, and then allowing the sub-populations to evolve in different directions. Island models use a small number of sub-populations. Cellular (or fine-grained) approaches use many. See, for instance, "Parallel Genetic Algorithms" (http://www.liacs.nl/assets/PDF/pit.95.pdf)
I've also used population clustering. This uses a clustering algorithm to create a new set of sub-populations at each generation. See http://eprints.whiterose.ac.uk/3419/
Simply put, Niching is a class of methods that try to converge to more than one solution during a single run.
They try to avoid indeividual concentration by using several mechanisms.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Artificial Intelligence