焼きなまし法（Simulated Annealing）とは？

import math
import random
import matplotlib.pyplot as plt
import japanize_matplotlib  # グラフ日本語表示用

# 評価関数（目的関数）
def f(x):
    return math.sin(x) + math.cos(0.5 * x)

# 探索空間の設定
x_min, x_max = 0.0, 10.0
step_size = 0.1  # 近傍への移動距離

print("--- 準備 ---")
print(f"探索範囲: {x_min} から {x_max}")

# --- 可視化のためのデータ生成 ---
# 探索範囲内のx値のリストを作成
x_vals = [i * step_size for i in range(int(x_max / step_size) + 1)]

# 各xに対応する評価関数f(x)の値を計算
y_vals = [f(x) for x in x_vals]

# グラフの描画
plt.figure(figsize=(10, 6))
plt.plot(x_vals, y_vals, color='#1f77b4', linewidth=2, label='目的関数 f(x)')
plt.title("評価関数 f(x) = sin(x) + cos(0.5x) の形状", fontsize=14, fontweight='bold')
plt.xlabel("変数 x", fontsize=12)
plt.ylabel("評価値 f(x)", fontsize=12)
plt.grid(True, linestyle='--', alpha=0.6)
plt.legend()
plt.show()

# 初期解（局所解に陥りやすいスタート地点として 8.0 に設定）
current_x_hc = 8.0 

while True:
    # 近傍の生成：現在の位置から左右にステップ幅だけ移動した2つの候補点
    neighbors = [current_x_hc - step_size, current_x_hc + step_size]
    
    # 探索空間の範囲内に収まっている候補点のみにフィルタリング
    valid_neighbors = [nx for nx in neighbors if x_min <= nx <= x_max]
    
    # 暫定の最良候補を現在の位置に設定
    best_neighbor = current_x_hc
    best_neighbor_score = f(current_x_hc)
    
    # 有効な近傍候補点を順番に評価
    for nx in valid_neighbors:
        score = f(nx)
        # より良いスコアが見つかれば最良近傍候補を更新
        if score > best_neighbor_score:
            best_neighbor_score = score
            best_neighbor = nx
            
    # 近傍のどれを探索しても改善しない場合はループを終了
    if best_neighbor_score <= f(current_x_hc):
        break
        
    # 現在地を最良近傍に更新
    current_x_hc = best_neighbor

print(f"山登り法の解: x = {current_x_hc:.2f}, スコア = {f(current_x_hc):.4f}")
print("❌ 課題: スタート地点によっては小さな山の頂上で止まってしまう。")

# --- 焼きなまし法（SA）のパラメータ設定 ---
initial_temp = 10.0      # 初期温度：高いほど改悪を許容する
final_temp = 0.01        # 終了温度：この温度を下回ったら探索終了
cooling_rate = 0.99      # 冷却率：1ループごとに温度に掛ける値

# 初期解（山登り法が失敗した「8.0」をスタート地点とする）
current_x = 8.0
current_score = f(current_x)

# 最良解の保持用（探索中に見つけた一番良いスコアを記憶しておく）
best_x = current_x
best_score = current_score

# 温度の初期化と乱数シードの固定（再現性のため）
T = initial_temp
random.seed(1)

print("--- 焼きなまし法の探索開始 ---")

# 温度が終了温度を下回るまでループ
while T > final_temp:
    # 近傍の生成：現在位置からランダムに少し移動した地点を次の候補とする
    nx = current_x + random.uniform(-step_size, step_size)
    
    # 探索範囲内に収める（はみ出したら境界の値にする）
    nx = max(x_min, min(nx, x_max))
    
    # 候補地点のスコアを計算し、差分を求める
    next_score = f(nx)
    delta_f = next_score - current_score
    
    # 遷移判定（メトロポリス基準）
    if delta_f > 0 or random.random() < math.exp(delta_f / T):
        # 現在位置とスコアを更新（移動を受け入れる）
        current_x = nx
        current_score = next_score
        
        # これまでのベストスコアを上回っていれば記録を更新
        if current_score > best_score:
            best_score = current_score
            best_x = current_x
            
    # 温度を下げる（冷却）
    T *= cooling_rate

print(f"焼きなまし法の最適解: x = {best_x:.2f}, スコア = {best_score:.4f}")
print("⭕ 利点: 一時的な改悪を許容することで、局所解から脱出し、大域的最適解に到達できる。")

import numpy as np

# NumPy用の評価関数の定義
def f_np(x):
    return np.sin(x) + np.cos(0.5 * x)

# グラフ描画用の背景データ生成
x_vals_np = np.linspace(0, 10, 200)
y_vals_np = f_np(x_vals_np)

# --- 焼きなまし法の軌跡シミュレーション ---
T = initial_temp
current_x_path = 8.0
path_x = [current_x_path]  # 軌跡を保存するリスト

random.seed(1)
while T > final_temp:
    nx = current_x_path + random.uniform(-step_size, step_size)
    nx = max(x_min, min(nx, x_max))
    
    delta_f = f(nx) - f(current_x_path)
    if delta_f > 0 or random.random() < math.exp(delta_f / T):
        current_x_path = nx
        
    path_x.append(current_x_path) # 現在位置を記録
    T *= cooling_rate

# 軌跡のy座標を計算
path_y = [f_np(x) for x in path_x]

# --- グラフの描画 ---
plt.figure(figsize=(10, 6))
plt.plot(x_vals_np, y_vals_np, color='#1f77b4', linewidth=2, label='目的関数 f(x)')
plt.plot(path_x, path_y, marker='o', color='orange', markersize=4, linestyle='-', alpha=0.3, label='焼きなまし法の軌跡')
plt.plot(path_x[0], path_y[0], marker='s', color='black', markersize=8, label='スタート地点')
plt.plot(path_x[-1], path_y[-1], marker='*', color='red', markersize=12, label='最終到達地点')

plt.title("焼きなまし法の探索プロセス（局所解からの脱出）", fontsize=14, fontweight='bold')
plt.xlabel("変数 x", fontsize=12)
plt.ylabel("評価値 f(x)", fontsize=12)
plt.legend()
plt.grid(True, linestyle='--', alpha=0.6)
plt.show()