CODEWITHSUNDEEP
algorithmoptimizationselectiongenetic-algorithmevolutionary-algorithm
OckhamsRazor
OckhamsRazor

Reputation: 4906

Multiobjective Optimisation: Selection using NSGA vs Selection using VEGA

I was wondering what differences exist between the Vector Generated Genetic Algorithm (VEGA) and Nondominated Sorting Genetic Algorithm (NSGA) algorithms in the context of selection in Multi Objective Optimisation?

(I am aware that NSGA is pareto-based while VEGA is non-pareto based.)

Upvotes: 4

Views: 788

Answers (1)

deong
deong

Reputation: 3870

The differences are quite large. As you say, one is Pareto-based and the other is not. In MOO, that's a huge thing. VEGA works by partitioning the population into disjoint sets and forcing the different sets to evolve towards different single objectives. There's a bit of machinery there to help combine them into a meaningful representation of the Pareto set, but it's basically just a union of solutions with respect to different objectives. Selection is done by selecting solutions that are better with respect to their individually set objective functions.

NSGA and other Pareto-based methods are completely different. They do selection not based on any particular choice of objective, but on the properties of the solutions as compared to one another. Each such algorithm makes slightly different choices in how they perform these comparisons, and NSGA-II (you should definitely use the second version of the algorithm) does it by non-dominated sorting. Basically, you find all the non-dominated solutions and call them set #1. Then you find all the solutions that would be non-dominated if you removed the elements of set #1 -- they become set #2. You keep going until all the solutions are accounted for, and the result is something like peeling the layers of an onion. The selection procedure is then that you always select members of the lower classes (set #1, then #2, and so on). If you can't take all the elements of a particular level, you break ties by choosing solutions within that level that further from the others, the idea being that if you can't take them all, you should at least try not to pick the ones you do take from one tiny little cluster.

In general, you should be looking at Pareto-based methods. They've been the proven choice for at least 10-15 years. In particular, you should focus on elitist Pareto-based methods like NSGA-II, SPEA2, the epsilon-MOEA, and a few more recent contenders.

Upvotes: 4

Related Questions