【焼きなまし法を高速に動かそう！】近傍解の生成 / 評価にかかる計算量を少なくすることで焼きなまし法を改良してみた

## 必要なライブラリをインポート
import numpy as np
import random
import copy
import math
np.random.seed(42)

## コストの合計を計算する関数を定義
def calculate_total_cost(cost_matrix, assignment):
    total_cost = 0
    for i, j in enumerate(assignment):
        total_cost += cost_matrix[i][j]
    return total_cost

## 近傍解を生成する関数を定義
def generate_neighbor(assignment):
    neighbor = copy.deepcopy(assignment)
    i, j = random.sample(assignment, 2)
    neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
    return neighbor

## 焼きなまし法を実装する関数を定義
def simulated_annealing(cost_matrix, initial_temp, cooling_rate, max_iter):
    # 初期解の生成（ランダムな割り当て）
    current_assignment = list(range(len(cost_matrix)))
    random.shuffle(current_assignment)
    current_cost = calculate_total_cost(cost_matrix, current_assignment)    
    # 最良解の初期化
    best_assignment = copy.deepcopy(current_assignment)
    best_cost = current_cost
    # 温度の初期化
    temperature = initial_temp
    # 最大反復回数（max_iter）まで繰り返し操作を行う
    print("------------------------計算開始")
    for iteration in range(max_iter):
        neighbor = generate_neighbor(current_assignment)  # generate_neighbor関数を使って近傍解の生成
        neighbor_cost = calculate_total_cost(cost_matrix, neighbor)  # calculate_total_cost関数を使って近傍解の目的関数値を計算    
        # 目的関数値の差の計算
        delta_E = neighbor_cost - current_cost
        # 解の受け入れ判定
        if delta_E < 0:
            # 目的関数値が改善された場合は受け入れる
            current_assignment = neighbor
            current_cost = neighbor_cost
            # その時点での最良解より目的関数値が小さかったら再良解を更新
            if neighbor_cost < best_cost:
                best_assignment = neighbor
                best_cost = neighbor_cost
        else:
            # 目的関数値が悪化した場合は確率的に受け入れる
            acceptance_prob = math.exp(-delta_E / temperature)  # 受け入れる確率を計算
            if random.random() < acceptance_prob:  # 0以上1以下のランダムに生成した実数が確率値より小さかったら解を受け入れる
                current_assignment = neighbor
                current_cost = neighbor_cost
        # 温度の更新
        temperature *= cooling_rate   
        # 終了条件（温度が十分低くなった場合）
        if temperature < 1e-20:
            break
        # デバッグ用: 進捗表示
        if iteration % 1000 == 0:
            print(f"反復回数 {iteration}: 目的関数値 = {best_cost}")
    print("------------------------計算終了")
    return best_assignment, best_cost

## 問題例を入力して結果を出力する
# コスト行列を設定
n = 10 # 割当問題のサイズ
cost_matrix = np.random.randint(1, 11, size=(n, n))  # コスト行列を計算
# パラメータの設定
initial_temperature = 1000
cooling_rate = 0.995
max_iterations = 10001
# 焼きなまし法の実行
best_assignment, best_cost = simulated_annealing(cost_matrix, initial_temperature, cooling_rate, max_iterations)
# 結果の表示
print("最良の割り当て:", best_assignment)
print("目的関数値:", best_cost)

        neighbor = generate_neighbor(current_assignment)  # generate_neighbor関数を使って近傍解の生成

## 近傍解を生成する関数を定義
def generate_neighbor(assignment):
    neighbor = copy.deepcopy(assignment)
    i, j = random.sample(assignment, 2)
    neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
    return neighbor

 neighbor = copy.deepcopy(assignment)

## 近傍解を生成する関数を定義
def generate_neighbor(assignment):
    neighbor = assignment.copy()
    i, j = random.sample(assignment, 2)
    neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
    return neighbor

        neighbor = generate_neighbor(current_assignment)  # generate_neighbor関数を使って近傍解の生成
        neighbor_cost = calculate_total_cost(cost_matrix, neighbor)  # calculate_total_cost関数を使って近傍解の目的関数値を計算    
        # 目的関数値の差の計算
        delta_E = neighbor_cost - current_cost

## コストの合計を計算する関数を定義
def calculate_total_cost(cost_matrix, assignment):
    total_cost = 0
    for i, j in enumerate(assignment):
        total_cost += cost_matrix[i][j]
    return total_cost

    for i, j in enumerate(assignment):
        total_cost += cost_matrix[i][j]

## 必要なライブラリをインポート
import numpy as np
import random
import copy
import math  # mathモジュールの追加
np.random.seed(42)

## コストの合計を計算する関数を定義
def calculate_total_cost(cost_matrix, assignment):
    total_cost = 0
    for i, j in enumerate(assignment):
        total_cost += cost_matrix[i][j]
    return total_cost

## 焼きなまし法を実装する関数を定義
def simulated_annealing(cost_matrix, initial_temp, cooling_rate, max_iter):
    # 初期解
    current_assignment = list(range(len(cost_matrix)))
    random.shuffle(current_assignment)
    current_cost = calculate_total_cost(cost_matrix, current_assignment)
    
    # 最良解
    best_assignment = current_assignment.copy()  # 一度だけコピー
    best_cost = current_cost
    
    temperature = initial_temp
    
    for iteration in range(max_iter):
        # 交換する2つの位置を選択するだけ（コピーなし）
        i1, i2 = random.sample(range(len(current_assignment)), 2)
        
        # 現在の割り当て値
        j1 = current_assignment[i1]
        j2 = current_assignment[i2]
        
        # コスト差分の計算
        delta_E = (cost_matrix[i1][j2] + cost_matrix[i2][j1]) - (cost_matrix[i1][j1] + cost_matrix[i2][j2])
        
        # 解の受け入れ判定
        if delta_E < 0 or random.random() < math.exp(-delta_E / temperature):
            # 受け入れる場合は現在の解を実際に変更
            current_assignment[i1], current_assignment[i2] = current_assignment[i2], current_assignment[i1]
            current_cost += delta_E
            
            # 最良解の更新
            if current_cost < best_cost:
                best_assignment = current_assignment.copy()  # 最良解の時だけコピー
                best_cost = current_cost

        
        # 温度の更新
        temperature *= cooling_rate
        # 終了条件（温度が十分低くなった場合）
        if temperature < 1e-20:
            break
        # デバッグ用: 進捗表示
        if iteration % 1000 == 0:
            print(f"反復回数 {iteration}: 目的関数値 = {best_cost}")
    
    print("------------------------計算終了")
    return best_assignment, best_cost

## 問題例を入力して結果を出力する
# コスト行列を設定
n = 10 # 割当問題のサイズ
cost_matrix = np.random.randint(1, 11, size=(n, n))  # コスト行列を計算
# パラメータの設定
initial_temperature = 1000
cooling_rate = 0.995
max_iterations = 10001
# 焼きなまし法の実行
best_assignment, best_cost = simulated_annealing(cost_matrix, initial_temperature, cooling_rate, max_iterations)
# 結果の表示
print("最良の割り当て:", best_assignment)
print("目的関数値:", best_cost)