Skip to main content

Python implementation of coupled simulated annealing (CSA)

Project description

Build Status PyPI

The original paper describing Coupled Simulated Annealing (CSA) can be found here:

ftp://ftp.esat.kuleuven.be/sista/sdesouza/papers/CSA2009accepted.pdf

Essentially, CSA is like multiple simulated annealing (i.e. m independent SA processes run in parallel), except that the acceptance probability at each step is calculated as a function of the current state across all m processes. For a more complete description of the general CSA algorithm, see Description of CSA below.

Installation

Using pip:

pip install pycsa

Directly from GitHub:

pip install -e git+https://github.com/structurely/csa.git

Usage

See examples/travelling_salesman.ipynb for an example of CSA applied to the travelling salesman problem (TSP).

Contributing

Feel free to submit pull requests and issues.

License

See LICENSE.txt.

Description of CSA

Suppose we are trying optimize (meaning minimize, in this case) some function my_function() which takes x as input and outputs a float.

We are going to run m processes in parallel. Therefore x_i will denote the current solution for the mth process.

Definitions

Before describing the algorithm, we will need to define the following functions and parameters:

  • energy_func(tac, ...) is a function which takes tac (the acceptance “temperature”) and the quantities my_function(x_1), ..., my_function(x_m) as input and outputs a float. That is, energy_func represents the “energy” of the current solution set x_1, ..., x_m.

  • generation_schedule(tgen, iteration) is a function which takes tgen (the generation “temperature”) and the number of the current iteration as input. The generation_schedule function determines how much tgen is decreased at each iteration. A typical choice for generation_schedule is just to multiply the current value of tgen by 0.9999.

  • default_tgen is the initial value given to tgen.

  • acceptance_schedule(tac, iteration) is a function which takes tac (the acceptance “temperature”) and the number of the current iteration as input. This function determines how much tac will be decreased at each iteration. A typical choice for acceptance_schedule is just to multiply tac by 0.99.

  • default_tac is the initial value given to tac.

  • random_probe(i, tgen) is a function which produces a random value for each x_i according to some distribution which depends on tgen.

  • acceptance_prob(tac, current_state, x_i, y_i) is a function that outputs a number between 0 and 1.

  • n the number of inner iterations (how many times we repeat steps 2 and 3 over each overall iteration).

  • N the number of outer iterations.

    NOTE: The choices for energy_func(), generation_schedule(), acceptance_schedule(), and random_probe() are what distinguish the particular classes of CSA algorithms.

The algorithm

  1. Initialization
  • Assign random initial solutions to x_1, …, x_m.
  • Let gamma = energy_func(my_function(x_1), ..., my_function(x_m)).
  • Set tgen = default_tgen.
  • Set tac = default_tac.
  • Set the inner iteration index j = 0.
  • Set the outer iteration index k = 0.
  1. Generation
  • For each i in (1, ..., m):
    • Generate a “probing” solution y_i = x_i + e, where e is randomly generated from the function random_probe(i, tgen).
  1. Acceptance
  • For each i in (1, ..., m):
    • If my_function(y_i) < my_function(x_i), set x_i = y_i.
    • Else, set p = acceptance_prob(gamma, x_i, y_i). Then sample r from a uniform(0, 1) distribution and set x_i = y_i if r < p, otherwise keep x_i = x_i.
  • Now update gamma = energy_func(my_function(x_1), ..., my_function(x_m)).
  • Increment j += 1.
  • If j < n, go back to step 2, otherwise set j = 0 and continue to step 4.
  1. Cooling
  • Decrease the “temperatures” tgen and tac according to their respective schedules, i.e. we set tgen = generation_schedule(tgen, k) and tac = acceptance_schedule(tac, k).
  • Increment k += 1.
  1. Stop
  • Stop if the stopping criteria is met or if k >= N. Otherwise return to step 2.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for pycsa, version 0.1.2
Filename, size File type Python version Upload date Hashes
Filename, size pycsa-0.1.2.tar.gz (5.6 kB) File type Source Python version None Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page