NSGA II can be act as a single objective or multi objective optimizer depended on your decision

The fitness function is associated with the problem being solved and not with the metaheuristic. If you have a multiobjective problem, then you can solve it using NSGA-II. If the problem is single objective, a simpler method should be used.

Thanks, my understanding is that there is no explicit for the multiobjectie optimization problems in NSGA algorithm. The goodness of fit is based on the non-domination ranks of solutions. Is that correct?

NSGA-II is based on the concept of Pareto optimality. therefore the objective functions should be evaluated separately . I used NSGA-II in a problem involving 4 objectives.

For more details check my paper:

Optimal Lighting Arrangements for Nighttime Highway Construction Projects

https://www.researchgate.net/publication/255642952_Optimal_Lighting_Arrangements_for_Nighttime_Highway_Construction_Projects

For an excellent description of NSGA-II, check this paper by the founder of NSGA-II

http://sci2s.ugr.es/sites/default/files/files/Teaching/OtherPostGraduateCourses/MasterEstructuras/bibliografia/Deb_NSGAII.pdf

Article Optimal Lighting Arrangements for Nighttime Highway Construc...

Hi Khaled,

I reviewed your paper. Very helpful. My question is that you mentioned that:

To my best on knowledge, binary tournament selection is employed to select the pair of parents. That is, randomly to random solution selected, the one with better rank would be one of the parent and the second one selected exactly based on the same process.

May you please explain about the selection process of parents in your paper? Also, how you evaluated the fitness functions? you mean objective functions?

Thanks,

There is no a fitness function as it, NSGA-II is based on Pareto dominance to form a set of fronts. In NSGA-II, the solutions to perform the crossover and mutation are chosen from the first front. If the first front doesn't fulfill all the parents needed then they are chosen from the second front, and so on. If the size of the n front exceeds the number of solutions required for the parents then the remaining parents are chosen using the crowding distance.

So basically the Pareto dominance and the crowding distance are the functions which are used as a fitness for parents selection.

For a deep review of NSGA-II check the original paper: http://repository.ias.ac.in/83498/1/2-a.pdf

[Update: selection operator]

After the fast non-dominated sort you will have the solutions ranked in fronts. The set of parents contains those solutions which are in the first fronts.

The binary tournament consider all the solutions in the set of parents. In the binary tournament are considered first the rank, and then the crowding distance. From the paper we have:

That is, between two solutions with differing non-domination ranks we prefer the point with the lower rank. Otherwise, if both the points belong to the same front then we prefer the point which is located in a region with lesser number of points (the size of the cuboid inclosing it is larger).

Strictly, in the binary tournament you select two random solutions from the set of parents the winner solution is the first parent, then another binary tournament is performed in the same way, and the winner is the second parent. Now you have two parents to perform a crossover operator and generate the offspring.

Or you can chose randomly two solutions form the parents set and perform a crossover. Or perform the crossover only with parents of the same front (rank).

Or perform the crossover with the solutions in an ordered way, crossover two parents with the same rank and the best crowding distance. Or implement your own selection operator. That is the part of the research, and experimentation. What is better?, in complexity, performance, spread, diversity, etc.

My best regards.

Thanks Jose,

I was under impression that selection the new population is based on the binary tournament selection. That is, randomly a random solution (from the whole population not ONLY from the first front) selected, the one with better rank would be one of the parent and the second one selected exactly based on the same process.

May you please explain the process of the selection?

Thanks,

Hi Juan,

You mentioned that:

And to select the  solution in P(t+1) you begin with the members of the first front, then those of the second front and so on until you reach the size of the population (when you have a tie, i.e. there are more solutions than available places in the population you use the crowding distance as a secondary criteria to select which solution is selected).

However my understanding is that two solutions are randomly drawn from the current population to choose a parent by binary tournament selection. If the two solutions have different ranks, the better solution with the higher rank is chosen as a parent. If they have the same rank, the better solution with a larger value of crowding distance is chosen as a parent.

What you exactly mean by beginning from the first front? How you want to do that?

Thanks

Juan, 

My question is concerned with the selection of the two parents. My understanding is that two parents are selected randomly from the current population by binary tournament selection. That is, two solutions selected and the one with better rank and crowding distance would be one of the parent. The second parent would selected exactly the same. Is that correct?  

Regarding the fitness function, I believe there is no explicit fitness function the same as single-objective optimization. Rather the fitness of the solutions is based on their ranks. Is that correct?

Thanks,

Arash

Hi，

     You may read the works of Prof. He(ADMM methods ofr multiobjective optimization),

Maybe this will help you.

     His homepage:(http://math.nju.edu.cn/~hebma/) and Publications [1],[15],[23].

Regards!

Jianchao

Hi Arash,

Please look at my work on multi-objective optimization on sewer networks. If you still find issues, please bug me.

Regards,

Upaka

In NSGA-II, you will have more than one objective function to evaluate each individual. So the question is how to optimize in a way that both objective functions are going to be optimized at the same time?

In NSGA-II, for each individual is defined a dominance levels which are related to the objective functions (values of this individual). Also, crowding distance is used for diversity (estimation of the cuboid).

In the figure below, I used google charts to plot each level with different color, and the stroked circle around the colored points represents the crowding distance. 

http://i.imgur.com/reA3Zou.png

So, in the selection method, you will not be using the individual fitness to chose between them. Using tournament selection (roulette wheel if NRGA) you will have two cases:

I will resume what I remember from the NSGA-II procedure.

1 Generate first population (called pop) of N individuals and define domination levels and CD

     2 While actual generation is less than max number of generation

          3 Generate new population (called new_pop) of N individuals 

          4 Combine pop and new_pop (called comb_pop) into a new population of N*2 individuals (elitism guaranteed). Define dominations level and CD of comb_pop

          5 pop = new Population(); /* pop will receive the choosen individuals from comb_pop */

          6 for each level

                    7 if level has fewer individuals than pop.size(), 

                              then include all individuals from this level to pop

                       else 

                              order individuals by increasing crowding distance, loop through then include while pop.size() < N 

         7 if is the last iteration

                    print Pareto

http://i.imgur.com/reA3Zou.png

Along the lines of all these answers it's highly important to physically interpret the points in Pareto curve. Some real world problems have better answers from just infeasible solutions than the feasible solutions. 

@UPaka Rathnayake if "infeasible solutions" are better answers they should be considered in the optimization procedure. In other words, your search space would contain not only the feasible solutions.

 Well what I mean was; not the final fitness values. Sometimes it might be better to look at the all fitness file too. Sometimes just infeasible solutions give better results in practice. For example, look at the optimization of a water network where the hydraulic model linked to MOEA. The hydraulic model has many assumptions to simplify the hydraulic model. But that doesn't count in optimization n MOEA. That's why we found some just infeasible solutions in all fitness file produces better practical results; however, in some cases. But this is never a norm. Just sometimes!