Evolutionary Optimization Algorithms¶
An Evolutionary Algorithm (EA) uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination and selection. Candidate solutions to the optimization problem play the role of individuals in population and the fitness function determines the quality of the solution. Evolution of the population then takes place after the repeated application of the above operators.
A General Evolutionary Optimization Algorithm¶
A typical evolutionary optimization algorithm consists of the following four operations: reproduction, mutation, recombination and selection and elitism. These operations are usually performed in the following order with many variations:
Note
Randomly generate a population \(\longrightarrow\) Parents
While not (Termination criterion):
Calculate the fitness of all Parents
Best \(E\) Parents \(\longrightarrow\) Elites
\(\emptyset\longrightarrow\) Children
While #(Children) < #(Parents):
Use fitness to probabilistically select pairs of Parents for recombination
Recombine (Mate) Parents to create Children \(c_1, c_2\)
\(Children\cup\{c_1, c_2\}\)
Randomly mutate Children
\(Children~\cup~Elites\longrightarrow Parents\)
Best \(N\) Parents \(\longrightarrow\) Parents
The above algorithm is implemented in eoa.EOA. An instance of this class requires two mandatory inputs: (1) population which is a list, consisting of all possible individuals, and (2) fitness which is a function that accepts a list of individuals and returns an OrderedDict with individuals as its keys and their fitness as values.
The individuals are assumed to be python tuples, typically generated by aml.Words. An instance of aml.Words requires a list of alphabets letters. If one requires a restiction on those letters that can appear at the end of a tuple or at the begining (as well as other positions in a tuple) then they should be indicated as parameters first and last. The parameter repeat indicated whether consecutive appearance of letters is allowed or not. The method Words.Generate takes a parameter as the length of tuples and produces the list of all legitimate tuples of a given length.
The first step in the above algorithm is selecting a random subset of the population as initial parents. One may consider various factors to impact on the initial parents such as the length of individuals, initial letters, etc. The default selection strategy for eoa.EOA is simply selecting a random population of a certain size. This behaviour can be changed by specifying the init_pop parameter of the EOA class (default eoa.UniformRand). init_pop accepts user-defined classes as input, but it assumes that the user-defined class implements a __call__ method whose first input should be the parent instance of the EOA class, which iplies that the user-defined class has access to all properties of the parent EOA instance. This remains the default coding MO for other user-defined classes that will be accepted by EOA. The __call__ should return an OrderedDict whose keys are individuals from population and their values are their fitness, that may have been calculated before and stores in EOA.evals which itself is an OrderedDict of similar type.
The eoa.EOA requires a termination criterion too. The defaulkt tewrmination criterion is set to be reaching a certain number of generations. This can be modified by specifying a user-defined termination class. A user-defined termination criterion is a class that implements __call__ which accepts the parent instance of the EOA. The default termination criterion is eoa.MaxGenTermination which checks whether the max_generations is reached or not. The max_generations can be specified on initialization of the EOA instance by setting the max_generations. The __call__ method should return a boolean indicating the satisfaction of the termination criterion.
To Select mating parents and produce their children, eoa.EOA uses a class provided to the instance of the EOA via recomb parameter. The default class is eoa.UniformCrossover. UniformCrossover uses the parents fitness to bias toward those that are most fit for mating and selects them probabilistically, the higher the fitness value, the higher the chance of finding a mate. After the pairing procedure, we then recombine the pairs \((p_1, p_2)\) to produce two children. The default procedure, chooses a random integer \(1\leq l\leq\max(\#(p_1), \#(p_2))\), put identity functions at the beginning of the shorter parent to make their length equal. Then cut them at \(l^{th}\) position and combine the initial part of \(p_1\) with later part of \(p_2\) and initial part of \(p_2\) with later part of \(p_1\) to produce children.
| \(p_1\): | \(g_1\) | … | \(g_{l-1}\) | \(g_l\) | … | \(g_n\) |
| \(p_2\): | \(h_1\) | … | \(h_{l-1}\) | \(h_l\) | … | \(h_n\) |
\(\Downarrow\)
| \(c_1\): | \(g_1\) | … | \(g_{l-1}\) | \(h_l\) | … | \(h_n\) |
| \(c_2\): | \(h_1\) | … | \(h_{l-1}\) | \(g_l\) | … | \(g_n\) |
If \(\#(p1)=\#(p_2)=1\), then UniformCrossover simply puts \(c_1=(p_1, p_2)\) and \(c_2=(p_2, p_1)\).
Note that a user-defined mating class needs to implement a __call__ method which accepts the parent EOA instance and sets its children method as an OrderedDict whose keys are the individuals and their values are their fitness. It is recommended to sort the children dictionary by its values before returning.
The next step is mutation. This process assures that even isolated individuals in the population has a chance to be explored. The default behaviour of eoa.EOA is implemented as eoa.Mutation which uses mutation_prob (default = 0.05) to randomly changes entities of each child. More accurately, each element of a child, will be changed into another (legitimate) element with probability mutation_prob. Again, the default behaviour can be modified by specifying a user-defined class which implement a __call__ method accepting the parent instance of EOA and modifies its .children dictionary and their fitness.
The last step in this implementation is called elitism. The purpose of the elitism is to keep those parents that are better fit compare to some of the children among the next generation parents. The default behaviour of eoa.EOA is implemented as eoa.Elites and can be modified by assigning a user-defined class to elitism parameter of eoa.EOA. The user-defined class requires to implement a __call__ method that accepts the parent EOA instance and modifies the parent’s children.
Example¶
The following is a synthetic example on a small set of letters and a fitness based on ASCI code and length of individuals:
# prepare the whole population
P = Words(['a', 'b', 'c', 'd', '1', '2'], last=['1', '2', '3'], repeat=True)
Pop = P.Generate(1) + P.Generate(2) + P.Generate(3) + P.Generate(4) +
P.Generate(5) + P.Generate(6) + P.Generate(7)
# initiate the EOA instance
gen = EOA(population=Pop, fitness=sfit, num_parents=100, mutation_prob=.1, term_genes=['1', '2'])
# run the EOA
gen()
# get the most fit individual found and print
best = next(reversed(tst.children))
print(best, tst.children[best])
produces the following output:
100%|##########| 50/50 [00:00<00:00, 769.22it/s]
('1', '1', '1', '1', '1', '1', '1') 10.149999999999999