 |
|
This scheduler is based on the Non-dominated Sorting Genetic Algorithm II (NSGA-II) developed by prof. K. Deb et al. (2000, KanGAL Report No. 200001) at Kanpur Genetic Algorithms Laboratory (KanGAL).
NSGA-II is a fast and elitist multi-objective evolutionary algorithm. Its main features are:
A fast non-dominated sorting procedure is implemented. Sorting the individuals of a given population according to the level of non-domination is a complex task: non-dominated sorting algorithms are in general computationally expensive for large population sizes. The adopted solution performs a clever sorting strategy.
NSGA-II implements elitism for multiobjective search, using an elitism-preserving approach. Elitism is introduced storing all non-dominated solutions discovered so far, beginning from the initial population. Elitism enhances the convergence properties towards the true Pareto-optimal set.
A parameter-less diversity preservation mechanism is adopted. Diversity and spread of solutions is guaranteed without use of sharing parameters, since NSGA-II adopts a suitable parameter-less niching approach. It is used the crowding distance, which estimates the density of solutions in the objective space, and the crowded comparison operator, which guides the selection process towards a uniformly spread Pareto frontier.
The constraint handling method does not make use of penalty parameters. The algorithm implements a modified definition of dominance in order to solve constrained multi-objective problems efficiently.
NSGA-II allows both continuous ("real-coded") and discrete ("binary-coded") design variables. The original feature is the application of a genetic algorithm in the field of continuous variables.
Note:
The NSGA-II version implemented in modeFRONTIERTM recognizes automatically real-coded and binary-coded variables: it distinguishes them according to the value specified in the Base field. Continuous (real-coded) variables have a Base equal to 0, while discrete (binary-coded) variables have a Base equal to a positive integer. In the latter case the user can define directly the discretization to be adopted (setting the Base value): on the contrary in the original C version of NSGA-II algorithm the user has to define the number of bits to be assigned to each binary-coded variable.
The user must specify:
Number of Generations: this value defines the maximum size of the run.
Crossover Probability: this parameter specifies the occurrence probability of the Classical Cross-Over operator.
In the case of binary-coded variables the Cross-Over operator exchanges some genetic material between two individuals, cutting the DNA binary strings at a random location and then pasting together the opposite segments belonging to the different individuals.
For real-coded variables NSGA-II uses a Simulated Binary Cross-Over operator (see K. Deb and R. B. Agrawal, 1995): this operator emulates the behavior of the classical binary cross-over, handling directly the real-coded variables, with no need to code the continuous variables into any arbitrary binary base.
Mutation Probability for Real-Coded Vectors: this value gives the probability that real-coded variables are randomly changed.
As in the case of Cross-Over operator applied to real-coded variables, the Mutation operator for real-coded variables is a Simulated Binary Mutation operator: it mimics the behavior of the binary operator in the field of continuous variables.
The maximum allowed value for this parameter is pm=1/N, where N is the number of the real-coded variables. If an exceeding value is set (e.g. the default value 1), then the algorithm resets the parameter value to pm, casting out a warning message. It is safe to use the default value, 1, and then let the reduction occur.
Mutation Probability for Binary Strings: this value gives the probability that binary-coded variables are randomly changed.
The maximum allowed value for this parameter is pm=1/L, where L is the DNA string length of the binary-coded variables. If an exceeding value is set (e.g. the default value 1), then the algorithm resets the parameter value to pm, casting out a warning message. It is safe to use the default value, 1, and then let the reduction occur.
Distribution Index for Real-Coded Crossover: The Distribution Index for Simulated Binary Cross-Over operator is a parameter that defines the shape of the probability distribution for the Cross-Over operator. For small values, points far away from the parents are likely to be chosen, whereas for large values, only points closer to the parents are likely to be chosen (see K. Deb and R. B. Agrawal, 1995). Therefore small values imply a broad search, and then increase the algorithm robustness; on the contrary, large values limit the search to a narrow region, obtaining better precision (accuracy) in the solution.
Distribution Index for Real-Coded Mutation: The meaning of this parameter is analogous to what is outlined above. The Distribution Index for Simulated Binary Mutation operator defines the shape of the probability distribution for the Mutation operator. For small values, the randomly perturbed point is likely to be far away from the original unperturbed point, while for large values, the perturbed point is likely to be closer to the original point.
Crossover Type for Binary-Coded Variables: two selections - Simple or Uniform - are possible for this field.
Simple: this is the usual Classical Cross-Over operator. This operator cuts the DNA binary strings of two individuals at a single random location, and then pastes together the opposite segments belonging to the different individuals.
Uniform: this operator scans the two parents DNA binary strings, performing a random selection between the two bits values for each single location.
Random Generator Seed: the modification of this value allows the execution of different runs starting from the same initial population. The Seed is an integer number used for sequence repeatability. If two MOSA Sequences are evaluated with the same seed, they will generate and return identical sequences of numbers. If the seed value is 0, the sequence is automatically seeded to a value based on the machine clock.
[1] Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. 2000, A Fast and Elitist Multi-Objective Genetic Algorithm-NSGA-II, KanGAL Report Number 2000001
[2] Deb, K. and Agrawal, R. B. 1995, Simulated binary crossover for continuous search space, Complex Systems, 9, 115
