Python implementation of coupled simulated annealing (CSA)

## Project description

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 `m`th 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

**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`.

**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)`.

- Generate a “probing” solution

**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`.

- If
- 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.

**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`.

**Stop**

- Stop if the stopping criteria is met or if
`k >= N`. Otherwise return to step 2.

## 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.

Filename, size | File type | Python version | Upload date | Hashes |
---|---|---|---|---|

Filename, size pycsa-0.1.1-py2-none-any.whl (8.3 kB) | File type Wheel | Python version py2 | Upload date | Hashes View |