SHO is a didactic Python framework for implementing metaheuristics (or evolutionary computation, or search heuristics).
Its main objective is to free students from implementing boring stuff and allow them to concentrate on single operator implementation.
The framework implements a simple sensor placement problem and handle metaheuristics manipulating solutions represented as numerical vectors or bitstrings.
Author: Johann Dreo firstname.lastname@example.org ⓒ Thales group
The main interface is implemented in
New algorithms should be integrated within this file and the interface should not be modified.
One may add arguments, but not remove or change the contracts of the existing ones.
snp_landscape.py is an example that plots the objective function
and a greedy search trajectory for a simple problem with only two dimensions.
The design pattern of the framework is a functional approach to composition. The goal is to be able to assemble a metaheuristic, by plugging atomic functions in an algorithm template.
The base of the pattern is a function that contains the main loop
of the algorithm, and call other functions called "operators".
Example of those algorithms are in the
For instance, the
random algorithm depends on an objective function
an initialization operator
init and a stopping criterion operator
Some operator do not depend on the way solutions are encoded
(like the stopping criterions) and some operators do depend on the encoding.
The former are defined in their own modules while the later are defined
in the module corresponding to their encoding (either
As they are assembled in an algorithm that do not know their internal
in advance, an operators needs to honor an interface.
For instance, the
init operator's interface takes no input parameter
and returns a solution to the problem.
However, some operator may need additional parameters to be passed. To solve this problem, the framework use an interface capture pattern.
There is two ways to capture the interface: either with a functional approach, either with an object-oriented approach. You can use the one you prefer, the advice is to use the functional approach when you can implement your operator as a stateless function, and the object-oriented approach when you need àour operator to manage a state.
The functional capture helpers are implemented in the
Basically, a function in this module capture the operator function's full
interface and returns a function having the expected interface of the
The implicit rule is to use positional arguments for mandatory parameters on which the operator is defined, and keyword arguments for parameters which are specific to the operator.
The object-oriented approach does not need helpers,
you just need to define a "functor" class,
that is, a class which implements the
This special function member allows to call an instance of a class
as if it was a function.
__call__ method should honor the targeted operator interface.
To pass fixed parameters, use the
There is an example of an operator implemented this way
steady class in the
Two example algorithms are provided: a
Several useful stopping criterions are provided.
The corresponding encoding-dependent operators are also provided,
for both numeric and bitstring encodings.
snp.py file shows how to assemble either a numeric greedy solver
or a bitstring greedy solver.
To setup your own solver, add your algorithm(s) into the
then assemble its instance under its name into
For instance, if you created the
you will be able to immediatly assemble
One should be able to call your solvers with
python3 snp.py --solver num_annealing,
Most exercises consists in adding a single function in an existing module (or your own module) and use assemble it in the main executable.
Implement a simulated annealing.
You can use
Implement an evolutionary algorithm.
You can use
Implement an expected run time empirical cumulative density function.
You can execute
ert.pywhich will plot 3 ert for two algorithms. You can also use
draw_ert.pywith -N option for the number of run and optionally -v option to choose a target value (if not use will draw a surface for all target)
Implement a simple design of experiment to determine the best solver.
You can use
try_solver.pyto list the different parameter you want to try and get the best parameter (you can chose the alogorithms at the begenin of the script)
Provide a solver for a competition.
For the competion, symply use my
I have had the following penalisation to
num.pyat the end of
if len(sol) > dim: s *= 0.5 for v in sol: if v < 0: s += v/domain_width if v >= domain_width: s -= (v-domain_width)/domain_width