README.md 4.55 KB
Newer Older
nojhan's avatar
nojhan committed
1
2

SHO — Stochastic Heuristics Optimization
nojhan's avatar
nojhan committed
3
========================================
nojhan's avatar
nojhan committed
4
5
6
7
8
9
10
11
12
13
14

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.

Johann Dreo's avatar
Johann Dreo committed
15
Author: Johann Dreo <johann@dreo.fr>.
nojhan's avatar
nojhan committed
16

nojhan's avatar
nojhan committed
17
Executable
nojhan's avatar
nojhan committed
18
----------
nojhan's avatar
nojhan committed
19
20
21
22
23
24
25
26
27
28

The main interface is implemented in `snp.py`.
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.

The file `snp_landscape.py` is an example that plots the objective function
and a greedy search trajectory for a simple problem with only two dimensions.


Architecture
nojhan's avatar
nojhan committed
29
------------
nojhan's avatar
nojhan committed
30
31
32
33
34

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.

nojhan's avatar
nojhan committed
35
36

### Operators
nojhan's avatar
nojhan committed
37
38
39
40
41
42
43
44

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 `algo` module.

For instance, the `random` algorithm depends on an objective function `func`,
an initialization operator `init` and a stopping criterion operator `again`.

nojhan's avatar
nojhan committed
45
46

### Encoding
nojhan's avatar
nojhan committed
47
48
49
50
51
52
53

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 `num` or `bit`).


nojhan's avatar
nojhan committed
54
### Interface capture
nojhan's avatar
nojhan committed
55
56
57
58
59
60
61

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.
62
63
64
65
66
67
68
69
70
71
72
73
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.


#### Function capture

The functional capture helpers are implemented in the `make` module.
nojhan's avatar
nojhan committed
74
75
76
77
78
79
80
81
Basically, a function in this module capture the operator function's full
interface and returns a function having the expected interface of the
operator.

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.

nojhan's avatar
nojhan committed
82

83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#### Object-oriented capture

The object-oriented approach does not need helpers,
you just need to define a "functor" class,
that is, a class which implements the `__call__` interface.
This special function member allows to call an instance of a class
as if it was a function.

The `__call__` method should honor the targeted operator interface.
To pass fixed parameters, use the `__init__` constructor.

There is an example of an operator implemented this way
as the `steady` class in the `sho/iters.py` file.


nojhan's avatar
nojhan committed
98
Exercises
nojhan's avatar
nojhan committed
99
---------
nojhan's avatar
nojhan committed
100

nojhan's avatar
nojhan committed
101
### Setup
nojhan's avatar
nojhan committed
102
103
104
105
106
107
108
109
110

Two example algorithms are provided: a `random` search
and a `greedy` search.
Several useful stopping criterions are provided.
The corresponding encoding-dependent operators are also provided,
for both numeric and bitstring encodings.
The `snp.py` file shows how to assemble either a numeric greedy solver
or a bitstring greedy solver.

nojhan's avatar
nojhan committed
111
112
113
114
115
116
117
118
To setup your own solver, add your algorithm(s) into the `algo.py` module,
then assemble its instance under its name into `snp.py`.
For instance, if you created the `annealing` algorithm,
you will be able to immediatly assemble `num_annealing` and `bit_annealing`.

One should be able to call your solvers with `python3 snp.py --solver num_annealing`,
for instance.

nojhan's avatar
nojhan committed
119

nojhan's avatar
nojhan committed
120
### List of exercises
nojhan's avatar
nojhan committed
121

nojhan's avatar
nojhan committed
122
123
Most exercises consists in adding a single function in an existing module
(or your own module) and use assemble it in the main executable.
nojhan's avatar
nojhan committed
124

nojhan's avatar
nojhan committed
125
126
127
128
129
1. Implement a simulated annealing.
2. Implement an evolutionary algorithm.
3. Implement an expected run time empirical cumulative density function.
4. Implement a simple design of experiment to determine the best solver.
5. Provide a solver for a competition.
nojhan's avatar
nojhan committed
130