Simulated Annealing

🔥 Vibe Prompt

"Solve TSP with 20 cities using SA. Compare final tour length vs greedy algorithm."

import math, random

cities = [(random.randint(0,100), random.randint(0,100)) for _ in range(20)]

def dist(a, b): return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
def tour_len(tour): return sum(dist(tour[i], tour[i+1]) for i in range(-1, len(tour)-1))

def simulated_annealing(cities, temp_start=1000, temp_end=0.01, cooling=0.995):
    tour = cities[:]
    random.shuffle(tour)
    best = tour[:]
    
    temp = temp_start
    while temp > temp_end:
        i, j = sorted(random.sample(range(len(tour)), 2))
        tour[i:j] = reversed(tour[i:j])
        delta = tour_len(tour) - tour_len(best)
        if delta < 0:
            best = tour[:]
        elif random.random() >= math.exp(-delta / temp):
            tour[i:j] = reversed(tour[i:j])  # Undo
        temp *= cooling
    return best

# Compare
greedy = cities[:]
random.shuffle(greedy)
sa_tour = simulated_annealing(cities)

print(f"Greedy: {tour_len(greedy):.0f}")
print(f"SA:     {tour_len(sa_tour):.0f}")
print(f"Improvement: {(1-tour_len(sa_tour)/tour_len(greedy))*100:.1f}%")

Applications

• VLSI circuit layout
• Job shop scheduling
• Protein folding
• Airport gate assignment

Key Points

• Understand the core concepts thoroughly
• Practice with hands-on code examples
• Apply knowledge to real-world problems
• Review and reinforce through exercises

Further Learning

• Official documentation
• Open source projects on GitHub
• Community forums and discussions
• Related courses and tutorials

What Is Simulated Annealing?

Simulated Annealing (SA) is a probabilistic optimization algorithm inspired by the annealing process in metallurgy — heating metal and slowly cooling it to reduce defects.

Why Not Just Use Gradient Descent?

| Problem | Gradient Descent | Simulated Annealing | |---------|-----------------|-------------------| | Local minima | ❌ Gets stuck | ✅ Can escape via random jumps | | Discrete search space | ❌ Needs continuous | ✅ Works with any space | | Derivative required | ✅ Yes | ❌ No gradient needed | | Combinatorial problems | ❌ No | ✅ TSP, scheduling, etc. |

The Cooling Schedule

$$T(t) = T_0 \cdot \alpha^t$$

Where:

• $T_0$ = initial temperature (high → explores freely)
• $\alpha$ = cooling rate (typically 0.95-0.99)
• $t$ = iteration number

| Temperature | Acceptance Probability | Behavior | |-------------|----------------------|----------| | High (T₀) | ~100% | Accepts any move — explores globally | | Medium | ~50% | Balances exploration and exploitation | | Low (near 0) | ~0% | Only accepts improvements — hill climbs |

Python Implementation

import math
import random

def simulated_annealing(
    initial_state,
    cost_func,
    neighbor_func,
    T0=100.0,
    alpha=0.995,
    max_iter=10000
):
    """Simulated Annealing optimizer."""
    current = initial_state
    current_cost = cost_func(current)
    best = current
    best_cost = current_cost
    T = T0
    
    for iteration in range(max_iter):
        # Generate neighbor
        neighbor = neighbor_func(current)
        neighbor_cost = cost_func(neighbor)
        
        # Calculate cost difference
        delta = neighbor_cost - current_cost
        
        # Accept if better, or accept with probability if worse
        if delta < 0 or random.random() < math.exp(-delta / T):
            current = neighbor
            current_cost = neighbor_cost
            
            # Update best
            if current_cost < best_cost:
                best = current
                best_cost = current_cost
        
        # Cool down
        T *= alpha
        
        if iteration % 1000 == 0:
            print(f"Iter {iteration}: T={T:.2f}, best={best_cost:.4f}")
    
    return best, best_cost

# Example: Traveling Salesman Problem (TSP)
# Minimize total distance between 10 random cities

def generate_cities(n=10):
    return [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(n)]

def total_distance(route, cities):
    dist = 0
    for i in range(len(route)):
        x1, y1 = cities[route[i]]
        x2, y2 = cities[route[(i + 1) % len(route)]]
        dist += math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
    return dist

def random_swap(route):
    new_route = route.copy()
    i, j = random.sample(range(len(route)), 2)
    new_route[i], new_route[j] = new_route[j], new_route[i]
    return new_route

cities = generate_cities(10)
initial = list(range(10))
random.shuffle(initial)

best_route, best_dist = simulated_annealing(
    initial_state=initial,
    cost_func=lambda r: total_distance(r, cities),
    neighbor_func=random_swap,
    T0=100.0,
    alpha=0.995,
    max_iter=10000
)

print(f"\nBest distance: {best_dist:.2f}")
print(f"Best route: {best_route}")

Parameters Guide

| Parameter | Typical Range | Effect | |-----------|---------------|--------| | Initial temperature (T₀) | 10-1000 | Higher = more exploration | | Cooling rate (α) | 0.90-0.999 | Higher = slower cooling, better results | | Max iterations | 1000-100000 | More iterations = better but slower | | Reheat | Optional | Reset temperature to escape stuck states |

Summary

Simulated Annealing solves optimization problems by mimicking the physical annealing process. It accepts worse solutions with decreasing probability to escape local minima.

Key takeaways: | Simulated Annealing: inspired by metallurgy — heat then slowly cool | | Accepts worse solutions with probability exp(-Δ/T) — escapes local minima | | High temperature → explores; Low temperature → exploits | | No gradient needed — works with discrete, combinatorial, continuous spaces | | Cooling rate α = 0.995 is a good starting point | | TSP solved: swap two cities randomly to generate neighbors | | SA is simple to implement and often finds near-optimal solutions |

Next Chapter: Particle Swarm

The next chapter covers Particle Swarm Optimization.