Hi,
I just want to make sure that I understand the mechanics of the NSGA-II (the non-dominating sorting genetic algorithm) for a multiobjective optimization problem, since the resources I have (I am not satisfied with, I would be grateful if anyone can recommend me a good paper or source to read more about the NSGA-II)
Here is what I got so far:
1- We start with a random population lets call P_0 of N individuals
2- Generate an off-spring population Q_0 of size N from P_0 by using binary tournament selection, crossover and mutation)
3- Let R_0=P_0 U Q_0
While (itr
Offspring in NSGA-II is generated using crossover and mutation operators. The purpose of crossover and mutation is different. You can find more details on NSGA-II in the following books and articles,
Deb, K. (2001). Multi-objective optimization using evolutionary algorithms (Vol. 16). John Wiley & Sons.
Coello, C. A. C., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary algorithms for solving multi-objective problems. New York: Springer.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197.
Sharma, A. K., & Mukherjee, I. (2019). Enhanced multi-objective solution approach for multiple quality characteristics optimisation problems considering predictive uncertainties. International Journal of Quality & Reliability Management.
In NSGA-II, parents are selected using binary tournament selection. Other selection operators can also be used. In binary tournament selection, 2 solutions the are selected at random and then their Pareto rank is compared. Solution with better rank is retained. If both solutions belong to same rank, their crowding distance is compared. A solution with high crowding distance is retrained. This is repeated until the Parent pool (whose size is specified by you) is filled.
Once the Parent pool is completely filled by solutions, crossover and mutation operators are performed on to generate offspring. You can select any two random parents for crossover and any single random parent for mutation froom the Parent pool.
To generate off-spring you need first to select parents there are several techniques to select them, for example, roulette wheel selection will try to select the parents with the highest fitness. After selection, you need to cross over the parents to generate the off-springs. Once you generated the new set of children you need to apply mutation and also copy over the best n parent from the old generation to the new generation.
While performing crossover and mutation to obtain new chromosomes/ solutions, in case of crossover, the parent chromosomes are to selected randomly from the population P_0; and in case of mutation, the chromosome to be mutated is to be selected randomly from P_0.
I disagree with the answer given by Ammar Aljodah, as roulette wheel selection is a selection process to obtain new population from the existing one in case of single objective optimization problems.
You need to first apply the nondominated sorting. Then, calculate the crowding distance for each nondominated instance and sort the solutions based on the crowded comparison operator. Next, generate offspring population from this set using selection, mutation and crossover operators.
Can we choose any relevant selection strategy or should it necessarily be only tournamenent selection
I am a bit muddled up with respect to tournament selection..
Should the population set size be the same as the size of the offspring?
If that is the case, why do we need a tournament selection strategy to form a mating pool- we might as well as directly use the entire population as a whole?
- Badges
- Science topic