Simulated Annealing (SA)

A module for parallel Simulated Annealing. A Synchronous Approach with Occasional Enforcement of Best Solution.

Original paper: Onbaşoğlu, E., Özdamar, L. (2001). Parallel simulated annealing algorithms in global optimization. Journal of global optimization, 19(1), 27-50..

alternate text

What can you use?

  • Multi processing: ✔️

  • Discrete spaces: ✔️

  • Continuous spaces: ✔️

  • Mixed Discrete/Continuous spaces: ✔️

Parameters

class neorl.evolu.sa.SA(mode, bounds, fit, cooling='fast', chain_size=10, Tmax=10000, Tmin=1, chi=0.1, move_func=None, reinforce_best='soft', lmbda=1.5, alpha=1.5, threshold=10, ncores=1, seed=None)[source]

Parallel Simulated Annealing

Parameters

  • mode – (str) problem type, either min for minimization problem or max for maximization

  • bounds – (dict) input parameter type and lower/upper bounds in dictionary form. Example: bounds={'x1': ['int', 1, 4], 'x2': ['float', 0.1, 0.8], 'x3': ['float', 2.2, 6.2]}

  • fit – (function) the fitness function

  • cooling – (str) cooling schedule, choose fast, boltzmann, cauchy,``equilibrium``. The equilibrium mode is only valid with ncores > 1 (See Notes below)

  • chain_size – (int) number of individuals to evaluate in the chain every generation (e.g. like npop for other algorithms)

  • Tmax – (int) initial/maximum temperature

  • Tmin – (int) final/minimum temperature

  • chi – (float or list of floats) probability of perturbing every attribute of the input x, ONLY used if move_func=None. For ncores > 1, if a scalar is provided, constant value is used across all ncores. If a list of size ncores is provided, each core/chain uses different value of chi (See Notes below)

  • move_func – (function) custom self-defined function that controls how to perturb the input space during annealing (See Notes below)

  • reinforce_best – (str) an option to control the starting individual of the chain at every generation. Choose None, hard, soft (See Notes below).

  • lmbda – (float) ONLY used if cooling = equilibrium, control the cooling rate, and the speed at which the algorithm converges.

  • alpha – (float) ONLY used if cooling = equilibrium, control the initial temperature of the cooling schedule.

  • threshold – (float) ONLY used if cooling = equilibrium. The threshold (in %) for the acceptance rate of solution under which the algorithm stops running.

  • ncores – (int) number of parallel processors (ncores > 1 is required for cooling = equilibrium)

  • seed – (int) random seed for sampling

evolute(ngen, x0=None, verbose=False)[source]

This function evolutes the SA algorithm for number of generations.

Parameters

  • ngen – (int) number of generations to evolute

  • x0 – (list of lists) initial samples to start the evolution (len(x0) must be equal to ncores)

  • verbose – (int) print statistics to screen

Returns

(tuple) (best individual, best fitness, and dictionary containing major search results)

Example

from neorl import SA
import matplotlib.pyplot as plt
import random

#Define the fitness function
def FIT(individual):
    """Sphere test objective function.
    """
    y=sum(x**2 for x in individual)
    return y

#Setup the parameter space (d=5)
nx=5
BOUNDS={}
for i in range(1,nx+1):
    BOUNDS['x'+str(i)]=['float', -100, 100]

#define a custom moving function
def my_move(x, **kwargs):
    #-----
    #this function selects two random indices in x and perturb their values
    #-----
    x_new=x.copy()
    indices=random.sample(range(0,len(x)), 2)
    for i in indices:
        x_new[i] = random.uniform(BOUNDS['x1'][1],BOUNDS['x1'][2])
    
    return x_new

#setup and evolute a serial SA
sa=SA(mode='min', bounds=BOUNDS, fit=FIT, chain_size=50, chi=0.2, Tmax=10000,
      move_func=my_move, reinforce_best='soft', cooling='boltzmann', ncores=1, seed=1)

#setup and evolute parallel SA with `equilibrium` cooling
#sa=SA(mode='min', bounds=BOUNDS, fit=FIT, chain_size=20, chi=0.2, Tmax=10000, threshold = 1, lmbda=0.05,
#      move_func=my_move, reinforce_best='soft', cooling='equilibrium', ncores=8, seed=1)

x_best, y_best, sa_hist=sa.evolute(ngen=100, verbose=1)

#plot different statistics
plt.figure()
plt.plot(sa_hist['accept'], '-o', label='Acceptance')
plt.plot(sa_hist['reject'], '-s', label='Rejection')
plt.plot(sa_hist['improve'], '-^', label='Improvement')
plt.xlabel('Generation')
plt.ylabel('Rate (%)')
plt.legend()
plt.show()

Notes

  • Temperature is annealed between Tmax and Tmin if any of the following cooling schedules is used: fast, cauchy, and boltzmann.

  • A special cooling schedule equilibrium is supported, which is associated with the following arguments:

    1. The initial temperature is determined by \(T_0=Max (\alpha * STD(\vec{E}_0), Tmin)\), where \(STD(\vec{E}_0)\) is the standard deviation of the finesses of the initial chains. A tolerance is applied to the temperature if the standard deviation converged to zero.

    2. alpha is the parameter above that controls the initial temperature of SA.

    3. lmbda expresses the cooling rate or the speed of the temperature decay. Larger values lead to faster cooling.

    4. The threshold (in %) expresses the acceptance rate threshold under which the SA stops running. For example, if threshold=10, when the mean of acceptance rate of all chains falls below 10%, SA terminates. For zero threshold, SA will terminate when all chains no longer accept any new solution.

    5. The equilibrium cooling option is activated for parallel SA chains only, i.e. when ncores > 1.

  • Custom move_func is allowed by following the input/output format in the example above. If None the default moving function is used, which is controlled by the chi parameter. Therefore, chi is used ONLY if move_func=None.

  • chi controls the probability of perturbing an attribute of the individual. For example, for d=4, \(\vec{x}=[x_1,x_2,x_3,x_4]\), for every \(x_i\), a uniform random number \(U[0,1]\) is compared to chi, if U[0,1] < chi, the attribute is perturbed. Otherwise, it remains fixed.

  • For every generation, a total of chain_size individuals are executed. Therefore, look for an optimal balance between chain_size and ngen.

  • Option reinforce_best allows enforcing a solution from the previous generation to use as a chain startup in the next generation. Three options are available for this argument:

    1. None: No solution is enforced. The last chain state is preserved to the next generation.

    2. hard: the best individual in the chain is used as the initial starting point.

    3. soft: an energy-based sampling approach is utilized to draw an individual from the chain to start the next generation.

  • Total number of cost evaluations for SA is chain_size * (ngen + 1).

  • If ncores > 1, parallel SA chains are initialized to accelerate the calculations.

  • If ncores > 1 and move_func=None, parallel SA chains can have different chi values, provided as a list/vector.