Simulated Annealing

🔥 Vibe Prompt

"Solve TSP with Simulated Annealing: 50 random cities, show route optimization animation."

import random, math

def simulated_annealing(cities, initial_temp=1000, cooling_rate=0.995, stop_temp=0.01):
    n = len(cities)
    def dist(i, j): return math.sqrt((cities[i][0]-cities[j][0])**2 + (cities[i][1]-cities[j][1])**2)
    def total_dist(route): return sum(dist(route[i], route[(i+1)%n]) for i in range(n))
    
    current = list(range(n))
    random.shuffle(current)
    current_dist = total_dist(current)
    best, best_dist = current[:], current_dist
    temp = initial_temp
    
    while temp > stop_temp:
        i, j = random.sample(range(n), 2)
        new = current[:]
        new[i], new[j] = new[j], new[i]
        new_dist = total_dist(new)
        delta = new_dist - current_dist
        if delta < 0 or random.random() < math.exp(-delta/temp):
            current, current_dist = new, new_dist
            if current_dist < best_dist:
                best, best_dist = current[:], current_dist
        temp *= cooling_rate
    return best, best_dist

cities = [(random.random()*100, random.random()*100) for _ in range(50)]
route, dist = simulated_annealing(cities)
print(f"Best distance: {dist:.2f}")

Chapter Summary

Understand core concepts and principles
Master implementation methods and techniques
Familiar with common issues and solutions
Able to apply in real projects

Implementation Example

Basic Example

# This section provides a complete implementation example

Steps

Setup: Configure development environment
Data: Prepare required data
Implementation: Build core functionality
Testing: Verify correctness
Optimization: Improve performance

Common Errors

| Error Type | Cause | Solution | |------------|-------|----------| | Compilation | Syntax | Check code syntax | | Runtime | Environment | Verify dependencies installed | | Logic | Algorithm | Step-by-step debugging | | Performance | Efficiency | Use profilers |

Code Example

import sys

def main():
    print("Hello, World!")

if __name__ == "__main__":
    main()

References

Official documentation
API reference
Open source examples
Community discussions

Algorithm Pseudocode

function SimulatedAnnealing(initial_state, cost_func, neighbor_func, T0, alpha, max_iter):
    current = initial_state
    current_cost = cost_func(current)
    best = current
    best_cost = current_cost
    T = T0
    
    for i = 1 to max_iter:
        neighbor = neighbor_func(current)
        neighbor_cost = cost_func(neighbor)
        delta = neighbor_cost - current_cost
        
        if delta < 0 or random() < exp(-delta / T):
            current = neighbor
            current_cost = neighbor_cost
            if current_cost < best_cost:
                best = current
                best_cost = current_cost
        
        T = T * alpha
    
    return best, best_cost

Advanced Cooling Schedules

| Schedule | Formula | Behavior | |----------|---------|----------| | Exponential | $T(t) = T_0 \cdot \alpha^t$ | Fast cooling, standard choice | | Linear | $T(t) = T_0 - \beta \cdot t$ | Simple, may cool too fast | | Logarithmic | $T(t) = T_0 / \log(t + 1)$ | Very slow cooling, high quality | | Adaptive | $T(t)$ adjusts based on acceptance rate | Best quality, complex to tune |

Adaptive Cooling

def adaptive_cooling(T, acceptance_rate, target_rate=0.5):
    """Adjust temperature to maintain target acceptance rate."""
    if acceptance_rate > target_rate:
        # Too many acceptances → cool faster
        return T * 0.95
    elif acceptance_rate < target_rate * 0.5:
        # Too few acceptances → heat up
        return T * 1.05
    else:
        return T * 0.99

Applications

| Domain | Problem | Why SA Works | |--------|---------|-------------| | Logistics | Vehicle routing | Combinatorial, no gradient | | Chip design | VLSI layout | Huge search space | | Finance | Portfolio optimization | Non-convex objective | | AI | Neural network architecture | Discrete choices | | Engineering | Structural design | Complex constraints |

Summary

Simulated Annealing is a versatile optimization algorithm that escapes local minima by accepting worse solutions with decreasing probability. Simple to implement, works on any problem with a cost function.

Key takeaways: | SA escapes local minima by accepting worse solutions with probability exp(-delta / T) | | Temperature schedule: exponential cooling (T = T₀ × α^t) is the standard | | Adaptive cooling adjusts temperature based on acceptance rate | | Linear cooling: T = T₀ - β·t (simple but may cool too fast) | | Logarithmic cooling: T = T₀ / log(t+1) (slow but high quality) | | Works on combinatorial problems (TSP, scheduling) where gradient descent fails | | Applications: logistics, VLSI, finance, AI, engineering | | No gradient needed — only a cost function and neighbor generator |

Next Chapter: Particle Swarm

The next chapter covers Particle Swarm Optimization.

Tuning SA Parameters

| Scenario | T₀ | α | Max Iter | |----------|-----|-----|----------| | Small problem (10 variables) | 10 | 0.99 | 1,000 | | Medium problem (100 variables) | 100 | 0.995 | 10,000 | | Large problem (1000+ variables) | 1000 | 0.999 | 100,000 |

Rule of Thumb

Set T₀ so that ~80% of bad moves are accepted initially
Set α so that T drops to near 0 by the end of the run
Run multiple times with different random seeds
Use the best result, not the last result

You've completed this chapter! Next: Particle Swarm Optimization.