Simulated annealing is an uninformed search technique to optimise the global minima of a function. It has become a popular approach over the last two decades due to its ease of implementation, convergence qualities, and use of hill-climbing motions to escape local optima. It is primarily used to solve discrete optimization issues and, to a lesser extent, continuous optimization problems. In this article, we will be discussing simulated annealing with a small implementation to understand the working of this technique. Using this method, we will find out the minima of a given function. Following are the topics to be covered.

Table of contents

1. About Local optimization
2. About Simulated Annealing
3. Working of Simulated Annealing
4. Implementing Simulated Annealing to optimise a function

Simulated Annealing is a meta-heuristic local search algorithm capable of escaping from local optima. Let’s start by understanding Local Optimization.

About Local optimization

A combinatorial optimization issue is defined by defining a collection of solutions and a cost function that assigns a numerical value to each option. An optimum solution is one that has the lowest possible cost (there may be more than one such solution). Local optimization aims to improve on an arbitrary solution to such a problem by a series of incremental, local improvements. 

To begin defining a local optimization algorithm, provide a way for perturbing solutions in order to acquire various solutions. The neighbourhood of ‘A’ refers to the set of solutions that may be acquired in one such step from a given solution ‘A’. The algorithm then executes the basic loop, leaving the precise techniques for selecting a solution (S) and untested neighbour (S’) to implementation details. 

Although S does not have to be the best solution after the loop is completed, it will be locally optimal in the sense that none of its neighbours has a lower cost. The hope is that locally optimum will work. Below is the image with a set of steps for calculating the local optimization.

Are you looking for a complete repository of Python libraries used in data science, check out here.

About Simulated Annealing

Simulated annealing is named after the physical annealing process with solids, in which a crystalline solid is heated and then gently cooled until it obtains the most regular possible crystal lattice structure and is, therefore, free of crystal flaws. 

The final arrangement results in a solid with higher structural integrity if the cooling schedule is suitably slow. Simulated annealing connects this sort of thermodynamic behaviour to the search for global minima in a discrete optimization problem. It also presents an algorithmic method for leveraging such a relationship. 

The values for two solutions (the present solution and a freshly picked solution) are compared at each iteration of a simulated annealing process applied to a discrete optimization problem. Improving solutions are always accepted, whereas a subset of non-improving (inferior) solutions are allowed with the goal of escaping local optima and reaching global optima. 

The likelihood of accepting non-improving solutions is determined by a temperature parameter, which is normally non-increasing with each algorithm iteration.

The essential algorithmic aspect of simulated annealing is that it allows for the escape of local optima via hill-climbing steps (i.e., moves which worsen the objective function value). As the temperature parameter approaches zero, hill climbing moves become less common, and the solution distribution associated with the inhomogeneous Markov chain that models the algorithm’s behaviour converges to a form in which all probability is concentrated on the set of globally optimal solutions (provided that the algorithm is convergent; otherwise the algorithm will converge to a local optimum, which may or may not be globally optimal).

Working of Simulated Annealing

Several definitions are required to characterise the special aspects of a simulated annealing approach for discrete optimization problems.

Consider a collection of all potential solutions, often known as the solution space. Then, on the solution space, create an objective function. The purpose is to determine the global minimum that exists in the set of solutions. To verify that a global minimum exists, the goal function must be constrained. For the collection of solutions, define a neighbourhood function. As a result, neighbouring solutions are associated with each solution and can be obtained in a single iteration of a local search algorithm.

Simulated annealing begins with a solution chosen from a collection of solutions. A neighbouring solution is subsequently created, either at random or according to a predefined rule. The Metropolis acceptance criterion is used to represent how a thermodynamic system progresses from the current solution or state to a candidate solution with the lowest energy content. 

Based on the acceptance probability, the candidate solution is chosen as the current solution. This acceptance probability is the fundamental building block of the search process in simulated annealing. If the temperature is gradually lowered, the system can approach an equilibrium (stationary state) with each repetition.

The objective functions are specified, and the energy associated with solutions is denoted. The equilibrium is determined by the Boltzmann distribution. It might be defined as the likelihood of the system being in a state with an energy function (the objective function) at a certain temperature, where the probability is proportional to the total of all conceivable functions. 

If the likelihood of creating a candidate solution from the solution’s neighbours is one, then a non-negative square stochastic matrix with transition probabilities may be created. These transition probabilities define a set of solutions produced by an inhomogeneous Markov chain. 

Implementing Simulated Annealing to optimise a function

Let’s implement simulated annealing by computing a blind search to optimise the minima of the function and observe the progress.

Import necessary libraries

import numpy as np
import matplotlib.pyplot as plt

Defining the objective function for which the optimization has to be performed. We’ll use a straightforward one-dimensional objective function with boundaries [-10,10] with the optima at 0.0.

def objective(x):
  return x[0]**2.0
r_min, r_max = -10.0, 10.0
inputs = np.arange(r_min, r_max, 0.1)
results = [objective([x]) for x in inputs]
plt.plot(inputs, results)
x_optima = 0.0
plt.axvline(x=x_optima, ls='--', color='red')
plt.show()

Following that, we may have a clearer understanding of how the metropolitan acceptance criterion changes with temperature throughout time. The criteria are temperature dependent, but it is also dependent on how different the objective evaluation of the new point is from the present working solution. As a result, we’ll plot the criterion for a few distinct “differences in objective function value” to show how they affect acceptance probability.

iterations = 120
initial_temp = 12
iterations = [i for i in range(iterations)]
temperatures = [initial_temp/float(i + 1) for i in iterations]
differences = [0.01, 0.1, 0.5, 1.0]
for d in differences:
  metropolis = [np.exp(-d/t) for t in temperatures]
  label = 'diff=%.2f' % d
  plt.plot(iterations, metropolis, label=label)
 
plt.xlabel('Iteration')
plt.ylabel('Metropolis Criterion')
plt.legend()
plt.show()

The plot is divided into four lines to represent the four disparities between the new poorer option and the current functioning solution. As one may predict, the wider the disparity, the less likely the model is to accept the worse option regardless of algorithm repetition. We can also see that the chance of accepting inferior answers reduces with algorithm iteration in all circumstances.

Let’s build a simulated annealing function

def simulated_annealing(objective, bounds, n_iterations, step_size, temp):
  best = bounds[:, 0] + np.random.rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
  best_eval = objective(best)
  curr, curr_eval = best, best_eval
  scores = list()
  for i in range(n_iterations):
    candidate = curr + np.random.randn(len(bounds)) * step_size
    candidate_eval = objective(candidate)
    if candidate_eval < best_eval:
      best, best_eval = candidate, candidate_eval
      scores.append(best_eval)
      print('>%d f(%s) = %.5f' % (i, best, best_eval))
    diff = candidate_eval - curr_eval
    t = temp / float(i + 1)
    metropolis = np.exp(-diff / t)
    if diff < 0 or np.random.rand() < metropolis:
      curr, curr_eval = candidate, candidate_eval
  return [best, best_eval, scores]

Now that we know how the temperature and metropolis acceptance criterion behave over time, we can use simulated annealing for our test problem.

np.random.seed(10)
bounds = np.asarray([[-10.0, 10.0]])
n_iterations = 1000
step_size = 0.1
temp = 12
best, score, scores = simulated_annealing(objective, bounds, n_iterations, step_size, temp)
print('Completed...')
print('f(%s) = %f' % (best, score))

Start by seeding the pseudorandom number generator. This is not essential in general, but it is necessary in this case to ensure that the same sequence of random numbers is produced each time the method is performed so that the results may be plotted afterwards.

The algorithm will search for 1,000 iterations with a step size of 0.1 in this example. The starting temperature will be 12.0. Because the search technique is more sensitive to the annealing schedule than the beginning temperature, initial temperature settings are nearly arbitrary.

Plotting the progress report

plt.figure(figsize=(10,5))
plt.plot(scores, '.-')
plt.xlabel('Improvement Number')
plt.ylabel('Evaluation f(x)')
plt.show()

During the hill-climbing search, a line plot is constructed to display the objective function assessment for each improvement. During the search, we can see roughly 78 changes to the objective function evaluation, with substantial changes at first and very modest to unnoticeable changes near the conclusion as the algorithm settled on the optima.

Final Verdict

Simulated annealing optimization methods may be used to solve both single-objective and multi-objective optimization problems. It’s been used in disciplines as diverse as process system engineering, operations research, and smart materials. With this hands-on implementation article, we have understood the working of Simulated annealing to optimise a function approximation.

References

• Link to the above code
• Paper on Simulated Annealing