My Blog.

Simulated Annealing

Definition

Simulated Annealing (SA) is a probabilistic optimisation algorithm inspired by the annealing process in metallurgy. It is used to find an approximate global optimum in a large search space by iteratively exploring solutions and allowing occasional steps to worse solutions to escape local optima.

Key Concepts

  1. Annealing Process: A physical process involving heating and controlled cooling of a material to remove defects and optimize its structure.
  2. Objective Function: The function that needs to be minimized or maximized in the optimization problem.
  3. Temperature: A parameter controlling the probability of accepting worse solutions, analogous to the temperature in physical annealing.
  4. Cooling Schedule: A plan for gradually reducing the temperature during the optimization process.
  5. Acceptance Probability: The probability of accepting a worse solution, which decreases as the temperature decreases.

Detailed Explanation

Simulated Annealing is a versatile optimization technique applicable to various complex problems. It mimics the physical annealing process to search for optimal solutions by allowing controlled randomization.

Annealing Process:

  • Heating and Cooling: In metallurgy, annealing involves heating a material to a high temperature and then slowly cooling it to remove defects and optimize its structure. Simulated Annealing translates this concept to optimization by gradually reducing the "temperature" of the system.

Algorithm Steps:

  1. Initialisation: Start with an initial solution ( S_0 ) and an initial temperature ( T_0 ).
  2. Iteration:
    • Generate Neighbor: Generate a neighboring solution ( S' ) from the current solution ( S ).
    • Objective Function Evaluation: Evaluate the objective function ( f(S') ) and ( f(S) ).
    • Acceptance Criterion: If ( f(S') ) is better than ( f(S) ), accept ( S' ). If ( f(S') ) is worse, accept ( S' ) with a probability ( P = \exp\left(\frac{f(S) - f(S')}{T}\right) ).
    • Update: Update the current solution to ( S' ) and reduce the temperature according to the cooling schedule.
  3. Termination: Repeat the iteration until the system is "frozen," i.e., no further significant changes occur or a maximum number of iterations is reached.

Cooling Schedule:

  • The cooling schedule is crucial for the algorithm's performance. Common schedules include linear, geometric, and logarithmic cooling:
    • Linear: ( T = T_0 - k \cdot \text{iteration} )
    • Geometric: ( T = T_0 \cdot \alpha^{\text{iteration}} ) (with ( 0 < \alpha < 1 ))
    • Logarithmic: ( T = \frac{T_0}{\log(1 + \text{iteration})} )

Acceptance Probability:

  • At high temperatures, the probability of accepting worse solutions is high, allowing the algorithm to explore the search space widely.
  • As the temperature decreases, the acceptance probability decreases, focusing the search on the local area around the best solutions found.

Applications:

  • Traveling Salesman Problem: Finding the shortest possible route that visits a set of cities and returns to the origin city.
  • Scheduling: Optimising job schedules to minimise total completion time or maximise resource utilisation.
  • Function Optimisation: Finding the global minimum or maximum of complex, multimodal functions.

Links to Resources

Diagrams

Notes and Annotations

  • Summary of key points:

    • Simulated Annealing is a probabilistic optimisation algorithm inspired by the physical annealing process.
    • It uses a temperature parameter and a cooling schedule to explore the search space and avoid local optima.
    • The algorithm is widely applicable to complex optimization problems in various fields.

  • Personal annotations and insights:

    • Simulated Annealing's strength lies in its ability to escape local optima, making it suitable for problems with complex landscapes.
    • The choice of cooling schedule and initial temperature significantly impacts the algorithm's performance and convergence speed.
    • Real-world applications demonstrate the versatility of Simulated Annealing in solving practical optimization problems.
    • Understanding the principles of Simulated Annealing provides a foundation for exploring other advanced optimization techniques.

Backlinks

  • Linked from Unit III Associative LearningUnit III Associative LearningOverview Associative learning is the focus of this unit, which begins with an introduction to the concept and its significance in neural networks. You'll study Hopfield networks and their error performance, as well as simulated annealing processes. The unit covers Boltzmann machines and Boltzmann learning, including state transition diagrams and the problem of false minima. Stochastic update methods and simulated annealing are also discussed. Finally, the unit explores basic functional units of