-
Notifications
You must be signed in to change notification settings - Fork 6
Non dominated Sorting Genetic Algorithm II
The version of this algorithm that has been implemented in JEAF is the original described in [1] . Please refer to this document for details.
The NSGA-II is an improvement of a previous algorithm developed by the same authors called NSGA. NSGA, and other multi-objective evolutionary algorithms following the same principles, received three mayor criticisms:
- The non-dominated sorting of the population has a high complexity of O(MN3), being M the number of objectives and N the number of individuals in the population.
- These algorithms do not consider the use of elitism strategies, which prevent the loss of good solutions, and can hence be a key factor in speeding up the search.
- Additional parameters must be set for ensuring diversity, mostly with the help of a sharing parameter.
NSGA-II addresses those issues, and additionally, suggests a simple constraint-handling strategy for constrained multi-objective optimization that can be also used in any other EA.
The population is sorted using the so called fast-non-dominated-sort. To this purpose, for each individual i, an integer value holding the number of solutions that dominate i is created (domination count) and a set Si with the individuals dominated by the individual i is calculated. With those parameters, each individual is assigned a rank representing the front to which it belongs. The Pareto front has rank 0. Those individuals dominated only by individuals from the Pareto front have rank 1. Generalizing, the individuals dominated only by individuals of rank r have rank r+1. This sorting procedure has a computational complexity of O(MN2), although it increments the spatial complexity from O(N) to O(N2). The best solutions have always rank 0 with this approach, so elitism is naturally fitted within the sort.
The diversity of the population is preserved by a parameterless crowded-comparison approach. The density of individuals surrounding a particular individual i is calculated as the perimeter of the hypercube formed by taking the nearest individuals to i as the hypercube's vertices. This quantity is called the crowding distance. The ranks and the crowding distance lead to the crowded-comparison operator, which in turn guides the selection process. An individual is considered to be better than an other if and only if it has a lower rank or, having the same rank, if it has a higher crowding distance.
The constraint-handling strategy modifies the definition of domination between two individuals i and j. The individual i dominates j if an only if any of the following is true:
- i is feasible and j is not.
- i and j are both not feasible, but i has a “smaller overall constraint violation”.
- i and j are both feasible and i dominates j (usual Pareto domination).
The replace operator tries to copy individuals beginning with the lowest front (front 0, Pareto front) upwards. The whole front is copied to the next population if there is enough place. If the size of the current front is greater than the available space left in the next population, the individuals of the front are sorted by descending crowding distance and only the first few individuals needed for completing the next population are copied.
- 10-06-2013: The RemainingFrontSelectionPlugin were added to JEAF with the aim of providing an interface which subclasses implements the necessary methods to select individuals of the last front to be part of the new population. Different methods could be implemented, for that reason we have created an interface.