9.2 Simulated annealing

Simulated annealing is a powerful optimization technique inspired by the physical process of metal cooling. It tackles complex problems by allowing occasional "uphill" moves, helping it escape local optima and find near-optimal solutions in rugged search landscapes.

The algorithm balances exploration and exploitation through a temperature parameter that controls acceptance of worse solutions. As the temperature decreases, the search focuses on promising areas, mimicking the gradual formation of an optimal crystalline structure in cooling metal.

Overview of simulated annealing

• Probabilistic optimization technique inspired by the physical process of annealing in metallurgy
• Solves complex combinatorial optimization problems by iteratively improving solutions while allowing occasional "uphill" moves
• Balances exploration and exploitation in the search space, enabling escape from local optima

Physical annealing analogy

• Mimics the controlled cooling process used to create defect-free crystalline structures in metals
• Starts with high-temperature molten metal, allowing atoms to move freely and gradually cool to form a stable, low-energy state
• Slow cooling allows the system to reach a global minimum energy state, while rapid cooling may result in suboptimal local minima

Algorithm components

Objective function

Top images from around the web for Objective function

• 

  Travelling salesman problem - Wikipedia View original

  Is this image relevant?

• 

  Travelling salesman problem - Wikipedia View original

  Is this image relevant?

• 

  File:Example The travelling salesman problem (TSP) tree seartch P1.gif - Wikimedia Commons View original

  Is this image relevant?

• 

  Travelling salesman problem - Wikipedia View original

  Is this image relevant?

• 

  Travelling salesman problem - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Objective function

• 

  Travelling salesman problem - Wikipedia View original

  Is this image relevant?

• 

  Travelling salesman problem - Wikipedia View original

  Is this image relevant?

• 

  File:Example The travelling salesman problem (TSP) tree seartch P1.gif - Wikimedia Commons View original

  Is this image relevant?

• 

  Travelling salesman problem - Wikipedia View original

  Is this image relevant?

• 

  Travelling salesman problem - Wikipedia View original

  Is this image relevant?

1 of 3

• Mathematical expression quantifying the quality of a solution in the optimization problem
• Guides the search process by providing a measure to compare different solutions
• Often represents the cost or fitness to be minimized or maximized (total distance in traveling salesman problem)

State space

• Set of all possible solutions to the optimization problem
• Defines the landscape over which the algorithm searches for the optimal solution
• Can be discrete (permutations) or continuous (real-valued parameters)

Neighbor function

• Generates new candidate solutions by making small modifications to the current solution
• Defines the local search neighborhood and impacts the algorithm's ability to explore the state space
• Typically problem-specific (swapping two cities in traveling salesman problem)

Temperature schedule

• Controls the rate at which the system cools during the annealing process
• Determines the balance between exploration and exploitation as the search progresses
• Crucial for the algorithm's performance and convergence properties

Acceptance probability

• Determines whether a new solution is accepted or rejected based on its quality and current temperature
• Allows occasional acceptance of worse solutions to escape local optima
• Typically uses the Metropolis criterion or Boltzmann distribution

Simulated annealing process

Initial solution generation

• Creates a starting point for the optimization process
• Can be random or based on problem-specific heuristics
• Quality of initial solution impacts convergence speed but not final result

Neighbor solution selection

• Applies the neighbor function to generate a candidate solution
• Explores the local search space around the current solution
• May involve random perturbations or systematic modifications

Solution evaluation

• Calculates the objective function value for the new candidate solution
• Determines the change in quality (delta E) between current and candidate solutions
• Guides the decision-making process for acceptance or rejection

Acceptance criteria

• Applies the acceptance probability function to decide whether to accept the new solution
• Always accepts improvements (downhill moves)
• Probabilistically accepts worse solutions based on temperature and quality difference

Temperature reduction

• Decreases the temperature according to the cooling schedule
• Reduces the probability of accepting worse solutions as the search progresses
• Gradually transitions from exploration to exploitation

Temperature schedule strategies

Linear cooling

• Decreases temperature linearly over time: T(t) = T0 - αt
• Simple to implement and understand
• May cool too quickly for complex problems

Exponential cooling

• Reduces temperature exponentially: T(t) = T0 * α^t
• Widely used due to its effectiveness in many problems
• Allows for faster initial exploration and slower final exploitation

Logarithmic cooling

• Decreases temperature logarithmically: T(t) = T0 / log(1 + t)
• Theoretically guarantees convergence to global optimum
• Often too slow for practical use in finite-time scenarios

Acceptance probability functions

Metropolis criterion

• Accepts new solutions with probability: P(ΔE, T) = min(1, exp(-ΔE / T))
• Allows occasional uphill moves to escape local optima
• Becomes more selective as temperature decreases

Boltzmann distribution

• Generalizes the Metropolis criterion: P(ΔE, T) = 1 / (1 + exp(ΔE / T))
• Provides a smoother transition between acceptance probabilities
• Can be more effective in certain problem domains

Parameter tuning

Initial temperature

• Sets the starting temperature for the annealing process
• Should be high enough to allow exploration of the entire search space
• Can be estimated based on the average change in objective function value

Cooling rate

• Determines how quickly the temperature decreases
• Balances exploration and exploitation phases
• Typically set between 0.8 and 0.99 for exponential cooling

Iterations per temperature

• Specifies the number of solution evaluations at each temperature level
• Allows the system to reach quasi-equilibrium before cooling
• May vary based on problem size and complexity

Advantages and limitations

Pros of simulated annealing

• Ability to escape local optima and find near-global optimal solutions
• Applicable to a wide range of optimization problems
• Relatively simple to implement and understand
• Can handle discrete and continuous search spaces

Cons of simulated annealing

• Sensitive to parameter settings (initial temperature, cooling rate)
• May converge slowly for large or complex problems
• No guarantee of finding the global optimum in finite time
• Performance can vary between runs due to stochastic nature

Applications in combinatorial optimization

Traveling salesman problem

• Finds the shortest route visiting all cities exactly once
• Simulated annealing effectively handles large instances
• Can produce near-optimal solutions for problems with thousands of cities

Graph coloring

• Assigns colors to graph vertices such that no adjacent vertices share the same color
• Simulated annealing can find good colorings for large and dense graphs
• Useful in scheduling, register allocation, and frequency assignment problems

Job shop scheduling

• Optimizes the allocation of jobs to machines while minimizing total completion time
• Simulated annealing handles complex constraints and objectives
• Applicable in manufacturing, project management, and resource allocation

Variants and extensions

Parallel simulated annealing

• Utilizes multiple processors or threads to explore the search space simultaneously
• Improves convergence speed and solution quality for large-scale problems
• Requires careful synchronization and information sharing between parallel processes

Quantum annealing

• Leverages quantum effects to perform optimization
• Potentially solves certain problems faster than classical simulated annealing
• Implemented in specialized hardware (D-Wave quantum computers)

Comparison with other metaheuristics

Simulated annealing vs genetic algorithms

• Simulated annealing operates on a single solution, while genetic algorithms maintain a population
• Genetic algorithms use recombination and mutation, simulated annealing uses local modifications
• Simulated annealing may converge faster for some problems, genetic algorithms for others

Simulated annealing vs tabu search

• Tabu search uses memory structures to guide the search, simulated annealing relies on randomness
• Tabu search actively avoids revisiting recent solutions, simulated annealing allows backtracking
• Tabu search may perform better in highly constrained problems, simulated annealing in rugged landscapes

Implementation considerations

Coding strategies

• Efficient data structures for representing solutions and neighborhoods
• Caching objective function values to avoid redundant calculations
• Implementing problem-specific heuristics for initial solution generation and neighborhood exploration

Performance optimization

• Parallelization techniques for multi-core processors or distributed systems
• Adaptive cooling schedules that adjust based on search progress
• Hybrid approaches combining simulated annealing with other optimization methods

Convergence analysis

Asymptotic convergence

• Theoretical guarantees of convergence to global optimum with infinite time
• Requires specific conditions on cooling schedule and neighbor function
• Logarithmic cooling schedules provide strongest convergence properties

Finite-time behavior

• Analysis of solution quality within practical time constraints
• Trade-off between convergence speed and solution optimality
• Empirical studies on problem-specific performance and parameter sensitivity