Dakota is an open-source optimizer with many functionalities. It is excellently documented, but because of the wealth of options available, a fair amount of reading is required to get started. In this article I describe the essential mechanisms of the
moga optimizer, a multiple-objective genetic algorithm, as it is implemented in Dakota 6.10.
I use Dakota to perform computational fluid dynamics (CFD) studies; in this context the evaluations are computationally expensive, and the settings I describe may need to be adapted to other use cases.
moga optimizer starts with an initial population (generation
0). It will select the best individuals in this population, creating generation
1; after which the genetic optimization process will begin.
By default, the initial population is created with randomly-selected input parameters, with
pop_size individuals. An initial population may be specified (with
initial_pop); the size of this database overrides
pop_size if it is larger than
pop_size; otherwise, randomly-generated individuals will be added until
pop_size is reached. If
pop_size is not specified, its default value of 50 is applied silently.
Fully-random selection of input parameters is not a very good way to initialize a genetic optimization, because it does not ensure that the domain of combinations of variables is uniformly sampled. Some individuals may be very similar one to another, and entire areas may be left unexplored (a major problem for genetic optimization). To prevent this, a trick is to first configure Dakota to perform a parameter study, using the
lhs (latin-hypersquare) algorithm. In that preliminary study, the evaluation is a dummy script returning always the same response. The summary output of the preliminary study, stripped of its dummy output values, is then used as the input for the genetic optimizer, seeding it with a well-balanced group.
0 has been created and evaluated, selection takes place. The selection process is the same throughout the optimization process; I will describe it further down. One obtains generation
1, and the genetic optimization loop may begin.
The genetic optimization loop
The principle of genetic optimization is not complicated. The algorithm creates new individuals by combining features of the best-performing individuals, and then weeds out the least performing individuals. There is no “learning” involved, nor are any models developed to model the response in relation to the input. The algorithm does not know why any given individual performs well or not. It also does not attempt to obtain a uniform coverage of the Pareto front, nor fill “gaps” in the domain of responses or inputs.
moga loop is best described with a diagram, and shown below.
The population of generation
i is used to create new individuals through mutation, and new individuals through crossover. Those new individuals are evaluated, and added to the pool of individuals. The best-performing members of this complete pool are then selected, forming generation
For each new individual to be generated through mutation,
moga will pick one individual at random within the population of the generation (some individuals may end up being chosen several times). The input parameters of this individual will be “fuzzied” according to configuration settings, to create a new mutated child. I used
mutation_type offset_normal mutation_scale = 0.15 mutation_rate = 0.15
as reasonable-first-guess settings.
The number of new individuals created through mutation is
n_gen × mutation_rate. Once they have been created,
moga checks whether any duplicates exist, and flushes them.
Note that the documentation suggests that
population_size is used as the base size, but this is incorrect (the bug has been reported). The size of the current generation determines the number of individuals generated through mutation.
mutation_rate can be larger than 1.
Crossover (also called recombination) is a form of averaging, where some input parameters of selected individuals are averaged out to create new individuals. In Dakota’s
moga, crossover is configured to take groups of
num_parents parents, and average them out in different ways to create each time
num_children. I chose
crossover_type shuffle_random num_parents = 2 num_offspring = 2 crossover_rate = 0.8
as reasonable settings.
Moga will divide the population of the generation in exclusive groups of randomly-picked
num_parents individuals each, and take them in turn to produce
num_children every time, until the requested number of individuals is attained. If not enough individuals are generated, then
moga proceeds to split the population into new groups and continue generating children.
While mutation and crossover are performed sequentially in time, in terms of population flows, they are performed in parallel, each taking the starting population of generation
i as a source. Within one generation, the individuals created through mutation are not crossed-over, and the children generated through crossover are not mutated.
The number of new individuals created through crossover is
((population / num_parents) * num_offspring ) * crossover_rate. After that,
moga checks for duplicates. Offsprings which duplicate the existing source population or one another are removed (“flushed”) before the evaluation is started.
Note that the documentation again incorrectly suggests that
population_size, not the size of the current generation, is used as the base number (the bug has been reported).
crossover_rate can be larger than 1.
Once a list of new individuals has been created by both the mutation and crossover module, they are sent for evaluation, first in a group of
concurrent_eval members, and then one by one as evaluations complete.
Dakota does not have a time-out feature, and will wait endlessly for all evaluations to complete. Conversely, if one evaluation does not complete correctly and outputs a
response that Dakota cannot process, Dakota will exit immediately (this is OK, because Dakota has excellent restart capabilities).
Once the evaluation of all the individuals has completed, Dakota will add them to the pool of individuals with which generation
i was started, and then proceed to choose what part of the pool will be carried on to the next generation. I chose
fitness_type layer_rank replacement_type below_limit = 5 shrinkage_fraction = 0.5
as reasonable settings. As such, Dakota will select all the individuals within
below_limit Pareto fronts to continue to the next generation. If the number of individuals is smaller than
n_geni × shrinkage_factor, it will increase the number of Pareto fronts until that number is attained.
We obtain a number
n_geni+1 of individuals, which now constitute generation
i+1, and the loop is started again.