In the field of multiobjective evolutionary optimization and solving multimodal problems there many algorithms are introduced up until now but some like NSGA-I, NSGA-II,SPEA-I and SPEA-II are much more famous than others. In NSGA-II as I read in some papers the concept of crowding distance is used instead of fitness sharing that is used in its predecessor, NSGA-I.
I want to know the cons and pros of fitness sharing and crowding distance when you compare them and despite the lower order of calculation of NSGA-II, what is the drawback of using the crowding distance method in it?
Thanks in advance.
The difference is obvious instead of finding the non-dominated front of the created offspring population only, in NSGA-II Parents and offspring are combined to form one set of size 2N. Then a non-dominated sorting is used to to classify the entire population. a new population is created from different fronts . The crowding distance (based on sorting the values of many objective functions) is calculated to get an estimate of the density of solutions surrounding a particular solution i in the population.
The crowding distance and ranking is used in the tournament selection for reproduction instead of using fitness only.
The advantage of using NSGA-II is no extra niching parameter is reuired. But, the disadvantage is when the latter generations, when more than N members belong to the first non-dominated set in the combined parent-offspring population, some packed Pareto- optimal solutions may give their places to other non-dominated yet non-Pareto-optimal solutions.
Dear Matthieu, it happens that at each evolutionary generation a set of non-dominated solutions regarding the current population is obtained but these solutions may not be in the true Pareto optimal set.
http://www.sciencedirect.com/science/article/pii/S1568494606000809
This formulation of the crowding distance presents an instability in the produced results when the front F includes some individuals sharing the same fitness.
Assuming an unstable sort, the crowding distance assigned to individuals sharing the same fitness can vary between calculations Most implementations, including Deb's reference implemen ation, use an unstable quicksort to sort the individuals
- Badges
- Science topic
- Similar topics
- Linguistics
- Philology
- Classical Philology
- Manuscripts