Genetic optimization with Dakota 1/3: The optimization loop

Part 1: The opti­miza­tion loop
Part 2: A sand­box for exper­i­men­ta­tion
Part 3: Practice

Dako­ta is an open-source opti­miz­er with many func­tion­al­i­ties. It is excel­lent­ly doc­u­ment­ed, but because of the wealth of options avail­able, a fair amount of read­ing is required to get start­ed. In this arti­cle I describe the essen­tial mech­a­nisms of the moga opti­miz­er, a mul­ti­ple-objec­tive genet­ic algo­rithm, as it is imple­ment­ed in Dako­ta 6.10.

I use Dako­ta to per­form com­pu­ta­tion­al flu­id dynam­ics (CFD) stud­ies; in this con­text the eval­u­a­tions are com­pu­ta­tion­al­ly expen­sive, and the set­tings I describe may need to be adapt­ed to oth­er use cases.

Initialization

Dakota’s moga opti­miz­er starts with an ini­tial pop­u­la­tion (gen­er­a­tion 0). It will select the best indi­vid­u­als in this pop­u­la­tion, cre­at­ing gen­er­a­tion 1; after which the genet­ic opti­miza­tion process will begin.

By default, the ini­tial pop­u­la­tion is cre­at­ed with ran­dom­ly-select­ed input para­me­ters, with pop_size indi­vid­u­als. An ini­tial pop­u­la­tion may be spec­i­fied (with initial_pop); the size of this data­base over­rides pop_size if it is larg­er than pop_size; oth­er­wise, ran­dom­ly-gen­er­at­ed indi­vid­u­als will be added until pop_size is reached. If pop_size is not spec­i­fied, its default val­ue of 50 is applied silently.

Ful­ly-ran­dom selec­tion of input para­me­ters is not a very good way to ini­tial­ize a genet­ic opti­miza­tion, because it does not ensure that the domain of com­bi­na­tions of vari­ables is uni­form­ly sam­pled. Some indi­vid­u­als may be very sim­i­lar one to anoth­er, and entire areas may be left unex­plored (a major prob­lem for genet­ic opti­miza­tion). To pre­vent this, a trick is to first con­fig­ure Dako­ta to per­form a para­me­ter study, using the lhs (latin-hyper­square) algo­rithm. In that pre­lim­i­nary study, the eval­u­a­tion is a dum­my script return­ing always the same response. The sum­ma­ry out­put of the pre­lim­i­nary study, stripped of its dum­my out­put val­ues, is then used as the input for the genet­ic opti­miz­er, seed­ing it with a well-bal­anced group.

Once gen­er­a­tion 0 has been cre­at­ed and eval­u­at­ed, selec­tion takes place. The selec­tion process is the same through­out the opti­miza­tion process; I will describe it fur­ther down. One obtains gen­er­a­tion 1, and the genet­ic opti­miza­tion loop may begin.

The genetic optimization loop

The prin­ci­ple of genet­ic opti­miza­tion is not com­pli­cat­ed. The algo­rithm cre­ates new indi­vid­u­als by com­bin­ing fea­tures of the best-per­form­ing indi­vid­u­als, and then weeds out the least per­form­ing indi­vid­u­als. There is no “learn­ing” involved, nor are any mod­els devel­oped to mod­el the response in rela­tion to the input. The algo­rithm does not know why any giv­en indi­vid­ual per­forms well or not. It also does not attempt to obtain a uni­form cov­er­age of the Pare­to front, nor fill “gaps” in the domain of respons­es or inputs.

Dakota’s moga loop is best described with a dia­gram, and shown below.

The pop­u­la­tion of gen­er­a­tion i is used to cre­ate new indi­vid­u­als through muta­tion, and new indi­vid­u­als through crossover. Those new indi­vid­u­als are eval­u­at­ed, and added to the pool of indi­vid­u­als. The best-per­form­ing mem­bers of this com­plete pool are then select­ed, form­ing gen­er­a­tion i+1.

Mutation

For each new indi­vid­ual to be gen­er­at­ed through muta­tion, moga will pick one indi­vid­ual at ran­dom with­in the pop­u­la­tion of the gen­er­a­tion (some indi­vid­u­als may end up being cho­sen sev­er­al times). The input para­me­ters of this indi­vid­ual will be “fuzzied” accord­ing to con­fig­u­ra­tion set­tings, to cre­ate a new mutat­ed child. I used

mutation_type offset_normal
mutation_scale = 0.15
mutation_rate = 0.15

as rea­son­able-first-guess settings.

The num­ber of new indi­vid­u­als cre­at­ed through muta­tion is n_gen × mutation_rate. Once they have been cre­at­ed, moga checks whether any dupli­cates exist, and flush­es them.
Note that the doc­u­men­ta­tion sug­gests that population_size is used as the base size, but this is incor­rect (the bug has been report­ed). The size of the cur­rent gen­er­a­tion deter­mines the num­ber of indi­vid­u­als gen­er­at­ed through muta­tion. mutation_rate can be larg­er than 1.

Crossover

Crossover (also called recom­bi­na­tion) is a form of aver­ag­ing, where some input para­me­ters of select­ed indi­vid­u­als are aver­aged out to cre­ate new indi­vid­u­als. In Dakota’s moga, crossover is con­fig­ured to take groups of num_parents par­ents, and aver­age them out in dif­fer­ent ways to cre­ate each time num_children. I chose

crossover_type shuffle_random
num_parents = 2
num_offspring = 2
crossover_rate = 0.8

as rea­son­able settings.

Moga will divide the pop­u­la­tion of the gen­er­a­tion in exclu­sive groups of ran­dom­ly-picked num_parents indi­vid­u­als each, and take them in turn to pro­duce num_children every time, until the request­ed num­ber of indi­vid­u­als is attained. If not enough indi­vid­u­als are gen­er­at­ed, then moga pro­ceeds to split the pop­u­la­tion into new groups and con­tin­ue gen­er­at­ing children.

While muta­tion and crossover are per­formed sequen­tial­ly in time, in terms of pop­u­la­tion flows, they are per­formed in par­al­lel, each tak­ing the start­ing pop­u­la­tion of gen­er­a­tion i as a source. With­in one gen­er­a­tion, the indi­vid­u­als cre­at­ed through muta­tion are not crossed-over, and the chil­dren gen­er­at­ed through crossover are not mutated.

The num­ber of new indi­vid­u­als cre­at­ed through crossover is ((population / num_parents) * num_offspring ) * crossover_rate. After that, moga checks for dupli­cates. Off­springs which dupli­cate the exist­ing source pop­u­la­tion or one anoth­er are removed (“flushed”) before the eval­u­a­tion is start­ed.
Note that the doc­u­men­ta­tion again incor­rect­ly sug­gests that population_size, not the size of the cur­rent gen­er­a­tion, is used as the base num­ber (the bug has been report­ed). crossover_rate can be larg­er than 1.

Evaluation

Once a list of new indi­vid­u­als has been cre­at­ed by both the muta­tion and crossover mod­ule, they are sent for eval­u­a­tion, first in a group of concurrent_eval mem­bers, and then one by one as eval­u­a­tions complete. 

Dako­ta does not have a time-out fea­ture, and will wait end­less­ly for all eval­u­a­tions to com­plete. Con­verse­ly, if one eval­u­a­tion does not com­plete cor­rect­ly and out­puts a response that Dako­ta can­not process, Dako­ta will exit imme­di­ate­ly (this is OK, because Dako­ta has excel­lent restart capabilities).

Selection

Once the eval­u­a­tion of all the indi­vid­u­als has com­plet­ed, Dako­ta will add them to the pool of indi­vid­u­als with which gen­er­a­tion i was start­ed, and then pro­ceed to choose what part of the pool will be car­ried on to the next gen­er­a­tion. I chose

fitness_type layer_rank
replacement_type below_limit = 5
shrinkage_fraction = 0.5

as rea­son­able set­tings. As such, Dako­ta will select all the indi­vid­u­als with­in below_limit Pare­to fronts to con­tin­ue to the next gen­er­a­tion. If the num­ber of indi­vid­u­als is small­er than n_geni × shrinkage_factor, it will increase the num­ber of Pare­to fronts until that num­ber is attained.

We obtain a num­ber n_geni+1 of indi­vid­u­als, which now con­sti­tute gen­er­a­tion i+1, and the loop is start­ed again.

Part 1: The opti­miza­tion loop
Part 2: A sand­box for exper­i­men­ta­tion
Part 3: Practice