Implementing Tailored Evolutionary Algorithms with LEAP
The Prebuilt Algorithms , ea_solve(), generational_ea(), and asynchronous.steady_state() may not be sufficient to address your problem. This could be that you want to access the state of objects outside the pipeline during a run, or that you want to add complex bookkeeping not easily supported by a prebuilt, among many other possible reasons.
This leaves assembling a bespoke evolutionary algorithm (EA) using low-level LEAP components. Generally, to do that you will need to do the following:
Come up with a suitable representation for your problem
What is the genome going to look like? Is it an indirect representation like a binary representation that must be decoded? Or a phenotypic, or direct representation, such as a real-valued vector? Or something else?
How are genomes going to be decoded into a phenotypic representation suitable for the associated Problem class?
Is the default Individual class suitable? Or will one of its subclasses be more appropriate? Will you have to write your own to keep additional state?
Define a Problem sub-class
Implement a loop wrapped around a pipeline of appropriate pipeline operators
Determine what output to generate
Optionally visualizing a run
These will be described in more detail in the following sub-sections.
Deciding on a suitable representation
The first design decision you will have to make is how to best represent your problem. There are two broad categories of representations, genotypic and phenotypic. A genotypic representation is a form of indirect representation whereby problem values use data that must be decoded into values that make sense to the associated Problem class you will also define. One popular example is using a binary encoding that must be decoded into values, usually integers or real-value sequences, that can then be used by a Problem instance to evaluate an individual. (However, there are some problems that directly use the binary sequences without having to interpret the values, such as the MaxOnes problem.) A phenotypic representation is able to directly represent problem relevant values in some way, usually as a vector of real-values that correspond to problem parameters.
Decoders for binary representations
If you use a binary representation, then you will almost certainly need to
define an associated decoder to convert binary sequences within Individual
genomes into values that the associated Problem can use. A variety of
premade binary decoders can be found in leap_ec.binary_rep.decoders,
and these can be used to convert binary sequences to integers or real values.
Gray code versions of binary decoders are also included.
Note
Gray encoding Gray encoding is an alternative integer representation that use binary sequences. Gray encoding resolves the issue where bit flip mutation of higher order bits would greatly change the values, whereas a Grey encoded binary integer will only change the value a small amount regardless of which bit was flipped in the binary sequence. (See also: Grey code)
Impact on representation on choice of pipeline operators
There will be two areas where you representation choice is going to have an impact on the code you write. First is in how you initialize individuals with random genomes. The second will be mutation and possibly crossover pipeline operators tailored to that representation. The mutation and crossover pipeline operators are generally going to be specific to the underlying representation. For example, bit flip mutation is relevant to binary representations, and a Gaussian mutation is appropriate for real-value representations. There are sub-packages for integer, real, and binary representations that have an ops.py that will contain pertubation (mutation) operators appropriate for the associated representation.
LEAP supports three numeric representations
There are three numeric representations supported by LEAP, that for binary,
integer, and real values. You can find initializers that create random values
for those value types in their respective sub-packages. You can find them
in leap_ec.binary_rep.initializers, leap_ec.int_rep.initializers,
and leap_ec.real_rep.initializers, respectively.
Support for exotic representations
LEAP is flexible enough to support other, more exotic representations, such as graphs and matrices. However, you will have to write your own initializers and mutation (and possibly crossover) operators to support such novel genome types.
Defining a Problem subclass
The Problems are where you implement how to evaluate an individual to solve your problem. You will need to create a Problem sub-class and implement its evaluate() member function accordingly.
Problem is an abstract base class (ABC), so you must subclass from it. Moreover, there are a number of Problem subclasses, so you will need to pick one that is the best fit for your situation. More than likely you will subclass from ScalarProblem since it supports real-valued fitnesses and it handles fitnesses that are NaNs, which can happen if you use RobustIndividual or DistributedIndividual and an exception is thrown during evaluation. (I.e., it was impossible to assign a fitness because the evaluation failed, so we signal that by assigning NaN as the fitness.)
If you use ScalarProblem or one of its subclasses, you will also have to specify whether it is a maximization problem via the boolean parameter passed into the class constructor.
There are a number of example Problem implementations that can be found in real_rep.problems many of which are popular benchmarks.
Possibly defining or choosing a special Individual subclass
Individuals encapsulate a posed solution to a problem and an associated fitness after evaluation. For most situations the default Individual class should be fine. However, you can also use RobustIndividual if you want individuals to handle exceptions that may be thrown during evaluation. If you are using the synchronous or asynchronous distributed evaluation support, then you may consider using DistributedIndividual, which itself is a subclass of RobustIndividual, but also assigns a UUID to each individual, a unique birth ID integer, and start and stop evaluation times in UNIX epoch time.
Of course, if none of those Individual classes meet your needs, you can freely create your own Individual subclass. For example, you may want a subclass that performs additional bookkeeping, such as perhaps maintaining links to its parents and any clones (offspring).
Putting all that together
Now that you have chosen a representation, an associated Decoder, a Problem, and an Individual class, you are now ready to assemble those components into a functional evolutionary algorithm. Generally, your code will follow this pattern:
parents ← create_initial_random_population()
While not done:
offspring ← toolz.pipe(parents, *pipeline_ops)
parents ← offspring
That is, first a population of parents are randomly created, and then we fall into a loop where we create offspring from those parents by generation until we are done with some sort of arbitrary stopping criteria. Within the loop the old parents are replaced with the offspring. There is, of course, a lot more nuance to that with actual evolutionary algorithms, but that captures the essence of EAs.
The part where the offspring are created merits more discussion. We rely on toolz.pipe() to take a source of individuals, the current parents, from which to generate a set of offspring. Individuals are selected by demand from the given sequent of pipeline operators, where each of these operators will manipulate the individuals that pass through them in some way. This concept is described in more detail in Operator Pipeline.
Evolutionary algorithm examples
There are a number of examples to steer by found in examples/simple. In particular:
simple_ep.py – simple example of an Evolutionary Program
simple_es.py – simple example of an Evolutionary Strategy
simple_ga.py – simple example of a Genetic Algorithm
simple_ev.py – simple example of an Evolutionary Algorithm as defined in Ken De Jong’s Evolutionary Computation: A Unified Approach.