Simulated Annealing using tqdm
Project description
Simulated Annealing package for Python using tqdm
- Flat structure (no class definition needed to descripe problem).
- Using
tqdm
for progress statistics. - Return statistics of used neighbour functions.
Installation
pip install frigidum
Dependencies
tqdm
3.4.0 or later.- For some examples,
numpy
is required.numpy
is not set as a requirement and therefore is not installed during installation.
Basic Example
import frigidum
import random
def random_start():
return 10**4 + random.random()
def random_small_step(x):
return x + 0.1 * (random.random() - .2)
def random_big_step(x):
return x + 10 * (random.random() - .2)
def obj(x):
return x**2
local_opt = frigidum.sa(random_start=random_start,
neighbours=[random_small_step, random_big_step],
objective_function=obj,
T_start=10**5,
T_stop=0.000001,
repeats=10**4,
copy_state=frigidum.annealing.naked)
Usage
Arguments
random_start
: function which returns a random start / state.objective_function
: objective function to minimize.neighbours
: list of neighbour functions, for one use [neighbour]. For each proposal, a neighbour is randomly selected (equal weights).T_start
: Starting temperature.T_stop
: Stopping temperature.alpha
: Lower temperature by this factor, after repeats proposals.repeats
: at each temperature lowering by factoralpha
, do repeats proposals.copy
=frigidum.annealing.copy
,frigidum.annealing.deepcopy
,frigidum.annealing.naked
, or custom - the copy method.
Output & Return
- During annealing; prints the
- Temperature
T
. - Movements proportion
M
, e.g.0.1
means 10% of all proposal got accepted and changed the objective value in the lastrepeats
. - Minimum Found Objective value
O_min
and last accepted Objective valueO_current
- Temperature
- During annealing; progress statistics provided by
tqdm
, such as estimated remaining time. - returns tuple
(best_found_state, objective_function(best_found_state) )
when done.
Movements
A movement is a when a proposed state is accepted, and the objective function has changed. For each batch of repeats, the proportion of movements are displayed. The number of movements differ with the number of accepted proposals, as a accepted proposal might not necessary change the objective function value.
-
In the early phase of annealing, movements should happen >90%.
-
In the last phase of annealing, movements should happen <10%.
Movements are useful to determine the starting- and stopping temperature; T_start
& T_stop
, with the above guidelines.
Copy'ing of States
3 most important copy methods are included in the annealing
module,
def copy(state):
return state.copy()
def deepcopy(state):
return state.deepcopy()
def naked(state):
return state
In the example, naked
with the argument copy_state=frigidum.annealing.naked
is used,
- use
copy_state=frigidum.annealing.copy
forcopy()
, - use
copy_state=frigidum.annealing.deepcopy
fordeepcopy()
, - use
copy_state=frigidum.annealing.naked
ifa = b
would already create a copy, or if the neighbour function return copies.
General Advice with Simulated Annealing
- Movements-to-set-Temperature - Use the movements statistics to set the starting and stopping temperature.
- Neighbours-have-Impact - Focus on the neighbour function, not the cooling scheme or acceptance variations.
- Human-inspired-Neighbours - To get inspiration for random neighbours, try solve a similar problem yourself.
- Neighbour-Combinations - Try multiple neighbours together, combinations usually work well. The
neighbours
argument expects a list of neighbours. After a run, statistics are displayed. Don't discard a neighbour just by its statistics, it might be a catalyst for a different neighbours. - Coarse-Neighbours - Try add neighbours, that might work well when warm (large simple steps).
- Smooth-Neighbours - Try add neighbours, that might work well when cold (small steps/smart steps).
- Local-Opt-Neighbours - Try add neighbours, that find a hyper local minima with local greedy algorithm.
- Delete-and-Fix-Neighbours - Try add neighbours, that deletes/removes a local solution and fix it again.
- Brazen-Overwrite-Neighbours - Try add neighbours, that overwrite a part of the solution rigorously.
- It is difficult to predict the effect of a random neighbour, ideas usually don't survive the outcome of experiments.- When conditions apply, stay within the feasible zone when possible. -or
- Only anneal on either condition or objective, not both at the same time.
Examples
The Rastrigin Function
https://en.wikipedia.org/wiki/Rastrigin_function
from frigidum.examples import rastrigin
frigidum.sa(random_start=rastrigin.random_start,
objective_function=rastrigin.rastrigin_function,
neighbours=[rastrigin.random_small_step, rastrigin.random_big_step],
copy_state=frigidum.annealing.naked,
T_start=100,
T_stop=0.00001,
repeats=10**4)
The Traveling Salesman Problem on pcb442
the pcb442
is a TSP problem with 442 cities/vertices, from http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html. The known solution tsp.opt_sol
has objective function value of about 50783.54
. Note we use post_annealing = tsp.local_search_2opt
to possibly improve the solution with the 2-opt algorithm, post annealing.
from frigidum.examples import tsp
local_opt = frigidum.sa(random_start=tsp.random_start,
objective_function=tsp.objective_function,
neighbours=[tsp.euclidian_bomb_and_fix, tsp.route_bomb_and_fix, tsp.random_disconnect_vertices_and_fix],
copy_state=frigidum.annealing.naked,
T_start=10**3,
T_stop=0.001,
repeats=10**2,
post_annealing = tsp.local_search_2opt)
To-Do:
- Add TSP as example
- Multi threading (N simultaneous anneals)
- Drilling (after repeats, re-repeat with low temp)
- Re-Annealing.
- Anneal
A
times, and return the best ofA
, with stats onmean, std, min, max
- Re-Annealing with
N
challengers. - Temperature dependent proposals.
- Stopping criterea for objective, i.e. stop when objective value is below certain threshold (often 0).
- Post-Cooling function. Often the output of annealing needs minor fixes, prettify, or remove redundant entries.
- (?) Auto-set start Temperature (Based on >90% movements)
- (?) Auto-stop (Based on <10% movements)
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.