DAKOTA Multi-Objective Genetic Algorithm (MOGA)

Version
JEGA v2.0

Description
MOGA uses a non-dominated sorting algorithm to perform Pareto search to find a set of best designs for multi-objective problems. This algorithm supports a mixture of real and discrete variables and general constraints.

More Information
The basic steps of the genetic algorithm are as follows:

1. Initialize the population (by randomly generating population members with or without duplicates allowed, or by flat-file initialization)
2. Evaluate the initial population members (calculate the values of the objective function(s) and constraints for each population member)
3. Perform crossover (several crossover types are available)
4. Perform mutation (several mutation types are available)
5. Evaluate the new population members.
6. Assess the fitness of each member of the population so as to select members to be replaced in next step.
7. Replace population with members selected to continue in the next generation.
8. Apply niche pressure to the population to generate a more even and uniform sampling by encouraging differentiation along the Pareto frontier.
9. Test for convergence by evaluating stopping criteria. If fitness has not stopped improving, continue; else stop optimization based on fitness tracker evaluation.

References
DAKOTA Version 5.0 Reference Manual

CrossoverPoints: The number of points at which crossover should be performed. This option is used in conjunction with all CrossoverTypes except ShuffleRandom. The option should have a positive integer value as a negative value would enable the algorithm to use unlimited CrossoverPoints.

CrossoverRate: All crossover types take a CrossoverRate. The crossover rate is used to calculate the number of crossover operations that take place. The number of crossovers is equal to the rate * PopulationSize. Thus the option accepts values between 0 and 1 only.

CrossoverType: Controls what approach is employed for combining parent genetic information to create offspring.

• MultiPointBinary crossover requires an integer number, N, of CrossoverPoints. This crossover type performs a bit switching crossover at N CrossoverPoints in the binary encoded genome of two designs. Thus, crossover may occur at any point along a solution chromosome (in the middle of a gene representing a design variable, for example).
• MultiPointParameterizedBinary crossover is similar in that it performs a bit switching crossover routine at N CrossoverPoints. However, this crossover type performs crossover on each design variable individually. So the individual chromosomes are crossed at N locations.
• MultiPointReal crossover performs a variable switching crossover routing at N CrossoverPoints in the real real valued genome of two designs. In this scheme, crossover only occurs between design variables (chromosomes).
• ShuffleRandom performs crossover by choosing design variables at random from a specified number of parents enough times that the requested number of children are produced. For example, consider the case of 3 parents producing 2 children. This operator would go through and for each design variable, select one of the parents as the donor for the child. So it creates a random shuffle of the parent design variable values. The relative numbers of children and parents are controllable to allow for as much mixing as desired. The more parents involved, the less likely that the children will wind up exact duplicates of the parents.

NumOffspring: The number of offspring to generate from the crossover operation. The option is used in conjunction with ShuffleRandom CrossoverType. NumOffsprings must have positive integer value.

NumParents: Specifies the number of parents used while cross over operation. The option is used in conjunction with ShuffleRandom CrossoverType. NumParents must have positive integer value.

MutationRate: Controls the rate at which mutations occur. See MutationType for specific use of this option. The option accepts values between 0 and 1.

MutationScale: A fraction in the range (0, 1) and is meant to help control the amount of variation that takes place when a variable is mutated. Please refer MutationType for more information on exact use of this option.

MutationType:

• ReplaceUniform introduces random variation by first randomly choosing a design variable of a randomly selected design and reassigning it to a random valid value for that variable. No consideration of the current value is given when determining the new value. The number of mutations for the ReplaceUniform mutator is the product of the MutationRate and the PopulationSize.
• BitRandom introduces random variation by first converting a randomly chosen variable of a randomly chosen design into a binary string. It then flips a randomly chosen bit in the string from a 1 to a 0 or visa versa. In this mutation scheme, the resulting value has more probability of being similar to the original value. The number of mutations performed is the product of the MutationRate, the number of design variables, and the PopulationSize.
• The offset mutators all act by adding an "offset" random amount to a variable value. The random amount has a mean of zero in all cases. The OffsetNormal mutator introduces random variation by adding a Gaussian random amount to a variable value. The random amount has a standard deviation dependent on the MutationScale. MutationScale is multiplied by the range of the variable being mutated to serve as standard deviation. OffsetCauchy is similar to OffsetNormal, except that a Cauchy random variable is added to the variable being mutated. The mutation_scale also defines the standard deviation for this mutator. Finally, OffsetUniform adds a uniform random amount to the variable value. For the offset_uniform mutator, the MutationScale is interpreted as a fraction of the total range of the variable. The range of possible deviation amounts is +/- 1/2 * (MutationScale * variable range). The number of mutations for all offset mutators is defined as the product of MutationRate and PopulationSize.

BelowLimit: If BelowLimit ReplacementType is selected, it will only keep designs that are dominated by fewer than this limiting value of other designs. The option accepts values greater than 0.

FitnessType: The FitnessType for MOGA may be DominationCount or LayerRank. Both have been specifically designed to avoid problems with aggregating and scaling objective function values and transforming them into a single objective. Instead, the DominationCount fitness assessor works by ordering population members by the negative of the number of designs that dominate them. The values are negated in keeping with the convention that higher fitness is better. The LayerRank fitness assessor works by assigning all non-dominated designs a layer of 0, then from what remains, assigning all the non-dominated a layer of 1, and so on until all designs have been assigned a layer. Again, the values are negated for the higher is better fitness convention. Use of the BelowLimit selector with the DominationCount fitness assessor has the effect of keeping all designs that are dominated by fewer then a limiting number of other designs subject to the shrinkage limit. Using it with the LayerRank fitness assessor has the effect of keeping all those designs whose layer is below a certain threshold again subject to the shrinkage limit.

InitializationType: defines the type of initialization for the population of the algorithm. There are three types:

• SimpleRandom creates initial solutions with random variable values according to a uniform random number distribution. It gives no consideration to any previously generated designs. The number of designs is limited by the PopulationSize.
• UniqueRandom is the same as SimpleRandom, except that when a new solution is generated, it is checked against the rest of the solutions. If it duplicates any of them, it is rejected. This thus ensure uniqueness of the population.
• FlatFile allows the initial population to be read from a flat file. If FlatFile is specified, a file name must be given.

NichingDistance: This option is used in conjunction with NichingType. It states the distance between designs for either Radial or Distance nicher. Thus the option must have a value greater than 0.

NichingType: The job of a niche pressure operator is to encourage diversity along the Pareto frontier as the algorithm runs. This is typically accomplished by discouraging clustering of design points in the performance space. In MOGA algorithm, the application of niche pressure occurs as a secondary selection operation. The nicher is given a chance to perform a pre-selection operation prior to the operation of the selection (replacement) operator, and is then called to perform niching on the set of designs that were selected by the selection operator. Currently, the only niche pressure operators available are the Radial nicher and the Distance nicher. The Radial niche pressure applicator works by enforcing a minimum Euclidean distance between designs in the performance space at each generation. The algorithm proceeds by starting at (or one of) the extreme designs along objective dimension 0 and marching through the population removing all designs that are too close to the current design. One exception to the rule is that the algorithm will never remove an extreme design which is defined as a design that is maximal or minimal in all but 1 objective dimension (for a classical 2 objective problem, the extreme designs are those at the tips of the non-dominated frontier). The Distance nicher enforces a minimum distance in each dimension. The designs that are removed by the nicher are not discarded. They are buffered and re-inserted into the population during the next pre-selection operation. This way, the selector is still the only operator that discards designs and the algorithm will not waste time "re-filling" gaps created by the nicher. The Radial nicher requires as input a vector of fractions with length equal to the number of objectives. The elements of the vector are interpreted as percentages of the non-dominated range for each objective defining a minimum distance to all other designs. All values should be in the range (0, 1). The minimum allowable distance between any two designs in the performance space is the Euclidian (simple square-root-sum-of-squares calculation) distance defined by these percentages. The Distance nicher has a similar input vector requirement, only the distance is the minimum distance in each dimension.

PopulationSize: Only sets the size of the initial population. The population size may vary in the JEGA methods according to the type of operators chosen for a particular optimization run. Option accepts positive integer values.

ReplacementType: Controls the way designs are selected for the new generation

• In RouletteWheel replacement, each design is conceptually allotted a portion of a wheel proportional to its fitness relative to the fitness of the other Designs. Then, portions of the wheel are chosen at random and the designs occupying those portions are duplicated into the next population. Those Designs allotted larger portions of the wheel are more likely to be selected (potentially many times).
• UniqueRouletteWheel replacement is the same as RouletteWheel replacement, with the exception that a design may only be selected once.
• The BelowLimit selector attempts to keep all designs for which the negated fitness is below a certain limit. The values are negated to keep with the convention that higher fitness is better. The inputs to the BelowLimit selector are the limit as a real value, and a ShrinkagePercentage as a real value. The ShrinkagePercentage defines the minimum amount of selections that will take place if enough designs are available. It is interpreted as a percentage of the population size that must go on to the subsequent generation. To enforce this, BelowLimit makes all the selections it would make anyway and if that is not enough, it takes the remaining that it needs from the best of what is left (effectively raising its limit as far as it must to get the minimum number of selections). It continues until it has made enough selections. The ShrinkagePercentage is designed to prevent extreme decreases in the population size at any given generation, and thus prevent a big loss of genetic diversity in a very short time. Without a shrinkage limit, a small group of "super" designs may appear and quickly cull the population down to a size on the order of the limiting value. In this case, all the diversity of the population is lost and it is expensive to re-diversify and spread the population.
• The Elitist selector simply chooses the required number of designs taking the most fit. For example, if 100 selections are requested, then the top 100 designs as ranked by fitness will be selected and the remaining will be discarded.

Seed: The seed option defines the starting seed for the random number generator. The algorithm uses random numbers heavily but a specification of a random seed will cause the algorithm to run identically from one trial to the next so long as all other input specifications remain the same. The option accepts integer values greater than or equal to 1.

ShrinkagePercentage: Defines the minimum amount of selections that will take place if enough designs are available. It is interpreted as a percentage of the population size that must go on to the subsequent generation. Thus option requires a real value between 0 and 1.

ConvergenceTolerance: The convergence tolerance specification provides a real value for controlling the termination of iteration. This option defines the threshold value on relative change in the objective function that indicates convergence for the problem. Option must have a value greater than 0.

ConvergenceType:MOGA monitors various changes in the non-dominated frontier from generation to generation. If the changes fall below a user specified threshold for a number of generations, the algorithm stops. This option (metric_tracker) is on by default. If this option is turned off, MOGA will run until the maximum number of iterations or function evaluations is reached.

MaxFunctionEvaluations: Function evaluation is the call to Analyzer to evaluate the objective function at the specified points. The maximum number of function evaluations is an integer limit for evaluations that the algorithm can attain. Algorithm can terminate with this criterion if no other criteria are satisfied. A single iteration can contain multiple function evaluations. MaxFunctionEvaluations must be a positive integer value.

MaxIterations: A single iteration will have multiple offset evaluations. This is the integer limit on number of iterations the algorithm can actually run. Option must have a positive integer value.

NumGenerations: The number of generations over which the metric value should be tracked. Convergence will be attained if the recorded metric is below PercentChange for NumGenerations consecutive generations. Thus the option must have a positive integer value.

PercentChange: The PercentChange is the threshold beneath which convergence is attained whereby it is compared to the metric value computed using MetricTracker. The option must have a value between 0 and 1.

FlatFile: The initial population can be specified by pointing to a file location.

Output: This option controls the level of verbosity of messages user can receive from DAKOTA. The options go from Silent to Debug with increasing amount of messages returned from the infrastructure. View Output > Details should show the messages from DAKOTA infrastructure.

IntermediateFilesPath: User can specify the location where the intermediate files of optimization should be generated. By default files are written to the user's temporary directory.

PrintEachPop: It serves as a flag and if supplied, the population at each generation will be printed to a file named "population<GEN#>.dat" where <GEN#> is the number of the current generation in the IntermediateFilesPath directory.

TabularGraphicsData: Turning this option to true generates a file named dakota_tabular in IntermediateFilesPath directory. This file has the values of design variables, constraints and objective function for each evaluation stored in a tabular format.