Simulated Annealing: Theory and Python Implementation

import numpy as np
import matplotlib.pyplot as plt

def rastrigin(x):
    """Rastrigin function"""
    return 10 * len(x) + np.sum(x**2 - 10 * np.cos(2 * np.pi * x))

def simulated_annealing(objective, dim, bounds=(-5.12, 5.12),
                        T_init=100.0, alpha=0.995, max_iter=10000):
    """Simulated Annealing for continuous optimization"""
    x = np.random.uniform(*bounds, size=dim)
    best_x = x.copy()
    best_f = objective(x)
    current_f = best_f

    T = T_init
    history = [best_f]

    for i in range(max_iter):
        sigma = 0.5 * (T / T_init)
        x_new = x + np.random.normal(0, sigma, size=dim)
        x_new = np.clip(x_new, *bounds)

        new_f = objective(x_new)
        delta = new_f - current_f

        if delta <= 0 or np.random.random() < np.exp(-delta / T):
            x = x_new
            current_f = new_f
            if current_f < best_f:
                best_x = x.copy()
                best_f = current_f

        T *= alpha
        history.append(best_f)

    return best_x, best_f, history

# --- Run ---
np.random.seed(42)
best_x, best_f, history = simulated_annealing(rastrigin, dim=10)
print(f"Best fitness: {best_f:.6f}")

# --- Convergence plot ---
plt.figure(figsize=(10, 5))
plt.plot(history)
plt.xlabel('Iteration')
plt.ylabel('Best Objective Value')
plt.title('Simulated Annealing on Rastrigin Function (10D)')
plt.yscale('log')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt

def total_distance(tour, cities):
    """Compute total tour distance"""
    n = len(tour)
    dist = 0
    for i in range(n):
        dist += np.linalg.norm(cities[tour[i]] - cities[tour[(i + 1) % n]])
    return dist

def two_opt_swap(tour, i, j):
    """2-opt swap: reverse tour[i:j+1]"""
    new_tour = tour.copy()
    new_tour[i:j+1] = tour[i:j+1][::-1]
    return new_tour

def sa_tsp(cities, T_init=1000.0, alpha=0.9995, max_iter=100000):
    """Simulated Annealing for TSP"""
    n = len(cities)
    tour = list(range(n))
    np.random.shuffle(tour)

    current_dist = total_distance(tour, cities)
    best_tour = tour.copy()
    best_dist = current_dist
    T = T_init
    history = [best_dist]

    for _ in range(max_iter):
        i, j = sorted(np.random.choice(n, 2, replace=False))
        new_tour = two_opt_swap(tour, i, j)
        new_dist = total_distance(new_tour, cities)

        delta = new_dist - current_dist
        if delta <= 0 or np.random.random() < np.exp(-delta / T):
            tour = new_tour
            current_dist = new_dist
            if current_dist < best_dist:
                best_tour = tour.copy()
                best_dist = current_dist

        T *= alpha
        history.append(best_dist)

    return best_tour, best_dist, history

# --- Run ---
np.random.seed(42)
n_cities = 30
cities = np.random.rand(n_cities, 2) * 100

best_tour, best_dist, history = sa_tsp(cities)
print(f"Best distance: {best_dist:.2f}")

# --- Visualization ---
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

tour_cities = cities[best_tour + [best_tour[0]]]
axes[0].plot(tour_cities[:, 0], tour_cities[:, 1], 'b-o', markersize=5)
axes[0].set_title(f'Best Tour (distance={best_dist:.2f})')
axes[0].set_aspect('equal')
axes[0].grid(True, alpha=0.3)

axes[1].plot(history)
axes[1].set_xlabel('Iteration')
axes[1].set_ylabel('Best Distance')
axes[1].set_title('SA Convergence on TSP')
axes[1].grid(True, alpha=0.3)

plt.tight_layout()
plt.show()