DAKOTA Coliny Evolutionary Algorithm (EA)

Description
Coliny Evolutionary Algorithm is a very flexible implementation of the genetic algorithm. This is a derivative free algorithm that handles both discrete and continuous design variables. It uses a simple penalty scheme to handle constraint violations.

More Information
Basic steps of evolutionary algorithm are as follows:

  1. Select an initial population randomly and perform function evaluations on these individuals
  2. Perform selection for parents based on relative fitness
  3. Apply crossover and mutation to generate new individuals from the selected parents
    • Apply crossover with a fixed probability from two selected parents
    • If crossover is applied, apply mutation to the newly generated individual with a fixed probability
    • If crossover is not applied, apply mutation with a fixed probability to a single selected parent
  4. Perform function evaluations on the new individuals
  5. Perform replacement to determine the new population
  6. Return to step 2 and continue the algorithm until convergence criteria are satisfied or iteration limits are exceeded

The Evolutionary algorithm decides on the initial population based on the InitializationType. The algorithm generates up to PopulationSize number of designs randomly at the start. Once population is fixed, the FitnessType option guides the process of selection of parents for crossover. The CrossoverType controls what approach is employed for combining parent genetic information to create offspring, and the CrossoverRate specifies the probability of a crossover operation being performed to generate a new offspring. The MutationType option controls what approach is employed in randomly modifying continuous design variables within the Evolutionary Algorithm population. Once crossover is complete for the parent designs the ReplacementType option helps the algorithm decide how current population and newly generated solutions would combine to form the new population. Thus the algorithm completes one cycle. Algorithm again performs selection based on relative fitness to loop through the steps until one of the termination criterions is encountered.

References
DAKOTA Version 5.0 Reference Manual

Control Parameters

CrossoverRate: This option specifies the probability of a crossover operation being performed to generate a new offspring. This option along with CrossoverType helps decide how much variation can be created in the population to generate offsprings by the algorithm. This option is a probability and so must have a value between 0 and 1.

ConstraintPenalty: Constraint penalty is a multiplier on constraint violations. Option should have a positive real value.

CrossoverType: The CrossoverType controls what approach is employed for combining parent genetic information to create offspring. The different CrossoverTypes available are:

  • TwoPoint crossover divides each parent into three regions, where offspring are created from the combination of the middle region from one parent and the end regions from the other parent. Since the Coliny EA does not utilize bit representations of variable values, the crossover points only occur on coordinate boundaries, never within the bits of a particular coordinate. (need more info)
  • Uniform crossover creates offspring from random combination of co ordinates from two parents. This would turn up to be an entirely random point which may or may not be in the vicinity of the two parents.
  • Blend crossover means that the new individual will be generated randomly along the multidimensional vector connecting the two parents. This may lead to a better design point if parents are on two sides of a local minima.

MutationRange: Use the mutation range to control OffsetUniform MutationType used for discrete parameters. It provides the range for the addition or subtraction of an integer value from original discrete value of offspring.s co ordinate. This option thus controls the deviation of co ordinate values for discrete variables using offset mutation. Offset mutation means adding a random variable to a given coordinate value.

MutationRate: The MutationRate controls the probability of mutation being performed on an individual, both for new individuals generated by crossover (if crossover occurs) and for individuals from the existing population. Thus this is a value between 0 and 1.

MutationScale: When mutation is performed, all dimensions of each individual are mutated. The MutationScale specifies a scale factor which scales continuous mutation offsets; this is a fraction of the total range of each dimension, so MutationScale is a relative value between 0 and 1.

MutationType: The MutationType controls what approach is employed in randomly modifying continuous design variables within the EA population. Each of the mutation methods generates coordinate-wise changes to individuals, usually by adding a random variable to a given coordinate value (an "offset" mutation), but also by replacing a given coordinate value with a random variable (a "replace" mutation). Discrete design variables are always mutated using the OffsetUniform method. The OffsetNormal, OffsetCauchy, and OffsetUniform mutation types are "offset" mutations in that they add a 0-mean random variable with a normal, cauchy, or uniform distribution, respectively, to the existing coordinate value. These offsets are limited in magnitude by MutationScale option. The ReplaceUniform mutation is a special case, i.e. it is not limited by MutationScale; rather it generates a replacement value for a coordinate using a uniformly distributed value over the total range for that coordinate. This type of mutation type thus gives freedom to the algorithm to generate truly random points.

NonAdaptive: The Coliny EA method uses self-adaptive mutation, which modifies the mutation scale dynamically. Thus based on the evolution strategies the algorithm thinks it can adopt, it changes the mutation scale dynamically. The NonAdaptive option serves as a flag which can be used to deactivate the self-adaptation. Intuitively the deactivation of the flag may actually facilitate global search as algorithm would not be dragged towards a local minima.

FitnessType: Use this option while selecting parents for crossover. It determines how strongly differences in objective function (fitness) are considered to accomplish the selection. The LinearRank setting uses a linear scaling of probability of selection based on the rank order of each individual's objective function within the population. Thus the better the rank of an individual higher is the likelihood of it being selected for crossover irrespective of the actual value of the objective function. The MeritFunction setting uses a proportional scaling of probability of selection based on the relative value of each individual's objective function within the population. This thus ensures that we favor the very best designs more.

InitializationType: The InitializationType defines the type of initialization for the population of the Evolutionary 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 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.

NewSolutionsGenerated: Number of new designs to be created using selection, crossover and mutation procedures. This option must have a positive integer value less than the PopulationSize.

PopulationSize: Population size specifies how many individuals will comprise the EA's population. This value should always be a positive integer.

ReplacementSize: This is an integer value which decides how many of a population will be replaced by newly generated individuals. This value thus should be positive and less than PopulationSize.

ReplacementType: The ReplacementType option controls how current population and newly generated individuals are combined to create a new population. Different types are:

  • Random creates a new population using (a) ReplacementSize randomly selected individuals from the current population, and (b) PopulationSize - ReplacementSize individuals randomly selected from among the newly generated individuals that are created for each generation. This setting thus does not value fitness and is entirely random.
  • CHC creates a new population using (a) the ReplacementSize best individuals from the combination of the current population and the newly generated individuals, and (b) PopulationSize - ReplacementSize individuals randomly selected from among the remaining individuals in this combined pool. The CHC setting is the preferred selection for many engineering problems. Thus this setting selects best individuals and the remaining individuals randomly.
  • Elitist creates a new population using (a) the ReplacementSize best individuals from the current population, (b) and PopulationSize - ReplacementSize individuals randomly selected from the newly generated individuals. It is possible in this case to lose a good solution from the newly generated individuals if it is not randomly selected for replacement; however, the default NewSolutionsGenerated value is set such that the entire set of newly generated individuals will be selected for replacement.

Seed: The random seed control provides a mechanism for making a stochastic optimization repeatable. That is, the use of the same random seed in identical studies will generate identical results. Seed value should be an integer value greater than or equal to 1.

ConvergenceTolerance: The convergence tolerance specification provides a real value for controlling the termination of iteration. This control defines the threshold value on relative change in the objective function that indicates convergence. Value must be greater than zero for all cases.

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 like evaluating points from a selected population. MaxFunctionEvaluations must be a positive integer value.

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

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

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.

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 algorithm. The user can see the objective function values, constraint violations, design variable values, etc. for all iterations when Debug is selected for this option. The detailed information can help user analyze the design space and algorithm convergence better.

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.