Digital Reactor
数値計算・最適化

シミュレーテッドアニーリングで解く巡回セールスマン問題

シミュレーテッドアニーリングで解く巡回セールスマン問題

はじめに

都市が30あれば、すべての都市を1回ずつ回って出発地に戻る巡回路は 29!/229!/2 通り、およそ 4.4×10304.4 \times 10^{30} に上ります。この中から総移動距離が最小の訪問順を探すのが巡回セールスマン問題（TSP, traveling salesman problem）です。総当たりが現実的でない以上、良い近似解を現実的な時間で得る解法が要ります。シミュレーテッドアニーリング（simulated annealing、SA）は金属の焼きなましを模したアルゴリズムで、実装が短く済むわりに多くの場合で良好な近似解を返します。Pythonで実装し、経路が縮んでいく過程をアニメーションで確かめます。

対象読者:

  • 組合せ最適化問題に興味がある方
  • シミュレーテッドアニーリングの基本的な仕組みを知りたい方
  • 巡回セールスマン問題の近似解法を探している方
  • Pythonを用いてアルゴリズム実装の基礎を学びたい方

記事のポイント:

  • 巡回セールスマン問題とシミュレーテッドアニーリングの概要を説明
  • 2-opt 近傍を用いた効率的な探索方法を紹介
  • Pythonによる実装例を提示し、可視化によって最適化の過程を直感的に理解
  • アルゴリズムの長所と短所、今後の課題について言及

巡回セールスマン問題とは

巡回セールスマン問題（TSP）は、複数の都市をそれぞれ1回ずつ訪問して出発地に戻るとき、総移動距離が最小になる訪問順を求める問題です。都市の数を NN とすると可能な経路は (N−1)!/2(N-1)! / 2 通りあり、都市数とともに爆発的に増えるため、すべてを調べ上げる方法は使えません。

TSPの代表的な解法

TSPの解法は、最適解を保証する厳密解法と、計算時間を優先する近似解法に大別できます。

解法カテゴリー具体的な手法特徴
厳密解法分枝限定法、動的計画法、整数計画法最適解を保証するが、問題規模が大きいと計算時間が膨大になる
近似解法遺伝的アルゴリズム、蟻コロニー最適化、タブーサーチ、シミュレーテッドアニーリング必ずしも最適解は得られないが、現実的な時間で良好な解を求められる

以降で扱うのは近似解法の一つ、シミュレーテッドアニーリングです。実装が短く、調整するパラメータも実質的には初期温度と冷却率の2つで済みます。悪化する移動も確率的に受け入れるため局所最適解から抜け出せて、メモリ使用量もわずかです。

シミュレーテッドアニーリングとは

名前の由来である焼きなまし（アニーリング）は、金属を高温に加熱してから時間をかけて冷やし、内部構造を安定させる処理です。急冷すると局所的な歪みが残りますが、徐冷すればより安定な低エネルギー状態に落ち着きます。この過程を最適化アルゴリズムに写し取ったのがSAで、物理と探索の要素は次のように対応します。

物理的アニーリング最適化アルゴリズム(SA)
物質の状態解の候補
エネルギーコスト関数（目的関数）
温度探索の多様性を制御するパラメータ
冷却温度を下げる操作

局所解脱出のメカニズム

SAは、次のフローで局所最適解からの脱出を試みます。

file

1回の反復でやることは単純です。現在の解を少し変更して近傍解を作り、それを受け入れるかどうかを判定します。コストが改善していれば必ず受理し、悪化していても温度に応じた確率で受理します。この温度を反復のたびに下げていくため、序盤は悪い解も高い確率で受け入れて広く探索し、終盤は改善だけを受け入れて局所的に詰める、という動きになります。

数式で表すと、現在の解のコストを f(x)f(x)、近傍解のコストを f(x′)f(x') としたとき、その差 Δf=f(x′)−f(x)Δf = f(x') - f(x) が負であれば（改善すれば）必ず受理、正であれば（悪化すれば）確率 P(Δf)=exp⁡(−Δf/T)P(Δf) = \exp(-Δf/T) で受理します。ここで、TT は温度を表すパラメータです。

2-opt近傍を使ったPython実装

TSPを解くSAをPythonで書くと、次のようになります。

import numpy as np
import random
from typing import List, Tuple

class SimulatedAnnealing:
    def __init__(self, cities: np.ndarray, initial_temp: float = 100, 
                 cooling_rate: float = 0.995):
        self.cities = cities
        self.n_cities = len(cities)
        self.initial_temp = initial_temp
        self.cooling_rate = cooling_rate

    def calculate_distance(self, route: List[int]) -> float:
        """指定された経路の総距離を計算"""
        total_distance = 0
        for i in range(self.n_cities):
            city1 = self.cities[route[i]]
            city2 = self.cities[route[(i + 1) % self.n_cities]]
            total_distance += np.sqrt(np.sum((city1 - city2) ** 2))
        return total_distance

    def get_neighbor(self, route: List[int]) -> List[int]:
        """2-optによる近傍解の生成"""
        i, j = sorted(np.random.randint(0, self.n_cities, 2))
        new_route = route.copy()
        new_route[i:j] = reversed(route[i:j])
        return new_route

    def solve(self, n_iterations: int = 10000) -> Tuple[List[int], List[float]]:
        """シミュレーテッドアニーリングでTSPを解く"""
        current_route = list(range(self.n_cities))
        current_distance = self.calculate_distance(current_route)
        best_route = current_route.copy()
        best_distance = current_distance

        temp = self.initial_temp
        distances = [current_distance]

        for _ in range(n_iterations):
            neighbor_route = self.get_neighbor(current_route)
            neighbor_distance = self.calculate_distance(neighbor_route)

            # 移動判定
            delta = neighbor_distance - current_distance
            if delta < 0 or np.random.random() < np.exp(-delta / temp):
                current_route = neighbor_route
                current_distance = neighbor_distance

                if current_distance < best_distance:
                    best_route = current_route.copy()
                    best_distance = current_distance

            distances.append(current_distance)
            temp *= self.cooling_rate

        return best_route, distances

近傍解の生成には2-opt法を使っています。ランダムに選んだ2点間の経路を反転する操作で、経路の交差をほどくのに向いています。温度は初期値を initial_temp とし、反復のたびに冷却率 cooling_rate を掛けて指数関数的に下げます。受理判定は前述のとおりで、改善なら必ず、悪化なら np.exp(-delta / temp) の確率で移動します。

30都市で最適化の過程を見る

30都市をランダムに配置し、SAで経路を最適化します。

左図は巡回路の変化で、赤点が都市、青線が経路です。初期状態では経路が何本も交差していますが、2-optの反転で交差が少しずつ解消され、経路が短くなっていきます。右図は総距離の推移で、横軸が反復回数です。高温の序盤は悪化する移動も受け入れるため距離が大きく上下し、温度が下がるにつれて変動が収まり、終盤はほとんど動かなくなります。温度が探索の広さを制御している様子が、この2枚から読み取れます。

裏を返せば、パラメータ次第でこの動きは崩れます。初期温度が高すぎると悪化を受け入れる期間が長引いて収束が遅くなり、冷却が速すぎると探索が早く固まって局所最適解に陥りやすくなります。問題の規模に応じてこの2つを調整すれば、アルゴリズム自体の構造は単純なまま使い回せます。

まとめ

シミュレーテッドアニーリングは、100行に満たない実装で30都市のTSPに実用的な近似解を返しました。探索の広さは温度スケジュールで調整でき、保持する状態も現在の解と最良解だけで済むため、組合せ最適化の近似解法として最初に試す候補に向いています。この先を考えるなら、100都市を超える規模での評価、時間枠のような制約条件への対応、温度スケジュールの自動調整、3-optなど別の近傍操作との比較が発展の方向になります。

問題の性質によっては他の解法が向くこともあります。遺伝的アルゴリズムは複数の解を並列に探索できるためマルチコアでの高速化が容易で、蟻コロニー最適化は交通量のような事前知識を経路の重みとして組み込みやすく、動的に変化する道路網上の経路探索に向きます。まずは上の実装に手元の地点データを与え、初期温度と冷却率を数通り振って総距離の推移を見比べると、この手法で足りるかどうかの見当がつきます。

関連記事

← 技術ブログ一覧へ