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

by 望月 優輝 / Yuki Mochizuki
Contents
  1. はじめに
  2. 巡回セールスマン問題とは
  3. TSPの代表的な解法
  4. シミュレーテッドアニーリングとは
  5. アルゴリズムの実装
  6. 実験結果
  7. 考察
  8. まとめと今後の課題

はじめに

巡回セールスマン問題（TSP）は、組合せ最適化の代表的な問題です。本記事では、シミュレーテッドアニーリング（SA）を用いてTSPを解く方法を解説します。SAは、金属の焼きなましを模倣したアルゴリズムで、実装が容易でありながら、多くの場合に良好な近似解を得ることができます。Pythonによる実装例を示し、最適化の過程をアニメーションで可視化します。

この記事を書いたひと

デジタルリアクタ合同会社 代表
機械学習・統計、数値計算などの領域を軸としたソフトウェアエンジニアリングを専門としています。スタートアップからグローバル企業まで、さまざまなスケールの企業にて、事業価値に直結する計算システムを設計・構築してきました。主に機械学習の応用分野において、出版・発表、特許取得等の実績があり、また、IT戦略やデータベース技術等の情報処理に関する専門領域の国家資格を複数保有しています。九州大学理学部卒業。日本ITストラテジスト協会正会員。

対象読者:

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

記事のポイント:

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

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

巡回セールスマン問題（TSP）は、以下のような問題です。

  • セールスマンが複数の都市を訪問する。
  • 各都市を1回ずつ訪問し、出発した都市に戻る。
  • 総移動距離を最小にする経路を求める。

都市の数を N とすると、可能な経路の数は (N-1)! / 2 となり、都市数が多くなると爆発的に増加するため、効率的な解法が必要です。

TSPの代表的な解法

TSPに対しては、以下のような様々な解法が提案されています。

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

本記事では、近似解法の一つであるシミュレーテッドアニーリング（SA）に焦点を当てます。SAは以下の理由から、TSPの解法として優れています。

  • 実装が比較的簡単。
  • パラメータの調整が容易。
  • 局所最適解から脱出するメカニズムを持つ。
  • メモリ使用量が少ない。

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

シミュレーテッドアニーリング（SA）は、金属の焼きなまし（アニーリング）を模倣した最適化アルゴリズムです。

焼きなましのプロセス:

  • 金属を高温に加熱する。
  • 徐々に冷却することで、金属の内部構造を安定化させる。
  • 急冷すると局所的な歪みが残るが、徐冷することでより安定な状態（低エネルギー状態）になる。

SAの最適化アルゴリズムへの応用:

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

局所解脱出のメカニズム

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

file

  • 近傍解生成: 現在の解を少し変更して新しい解（近傍解）を生成。
  • 受理判定:
    • 近傍解のコストが改善されていれば、必ず受理。
    • コストが悪化していても、温度に応じた確率で受理。
  • 温度制御:
    • 高温時: 悪い解も高確率で受理し、広範囲を探索。
    • 低温時: 良い解のみを受理し、局所的に最適化。

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

アルゴリズムの実装

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都市をランダムに配置し、SAで経路を最適化する実験を行います。

最適化過程のアニメーション

このアニメーションは、SAによる最適化の過程を示しています。

  • 左図: 巡回路の改善の様子
    • 赤点: 都市
    • 青線: 巡回路
    • 初期状態では経路が交差している
    • 徐々に交差が解消され、経路が短くなっていく
  • 右図: 経路の総距離の変化
    • 横軸: 反復回数
    • 縦軸: 総距離
    • 初期は大きく変動するが、徐々に収束していく

アニメーションから、以下のような特徴が観察できます。

  • 探索の多様性:
    • 高温時（初期）: 大きな変更を許容し、様々な経路を探索。
    • 低温時（終盤）: 小さな変更のみを受け入れ、局所的に最適化。
  • 解の改善:
    • 経路の交差が徐々に解消。
    • 温度低下とともに改善の頻度が減少。
  • 収束:
    • 初期: 距離が大きく変動（広範囲を探索）。
    • 中盤: 緩やかな改善が続く。
    • 終盤: ほとんど変化しなくなる（局所最適解に収束）。

考察

実験結果から、以下のことが言えます。

  • 効率的な探索: 2-optによる近傍操作と温度制御により、効率的に良好な解を探索できる。
  • パラメータの影響:
    • 初期温度が高すぎると収束が遅い。
    • 冷却率が大きすぎると局所最適解に陥りやすい。
    • 適切なパラメータ設定が重要。
  • 実装の容易さ:
    • アルゴリズムの構造がシンプル
    • パラメータ数が少なく、調整が比較的容易
    • メモリ使用量が少ない

まとめと今後の課題

シミュレーテッドアニーリングは、巡回セールスマン問題に対して効果的な近似解法であることが確認できました。シンプルな実装で実用的な解を得られ、温度制御による探索範囲の調整が可能です。少ないメモリ使用量で効率的な計算ができることも利点です。

今後の課題としては、以下のような点が挙げられます。

  • より大規模な問題（例えば100都市以上）への適用と評価。
  • 時間枠制約など、他の制約条件への対応。
  • 温度スケジュールの自動調整。
  • 3-optなど、他の近傍操作との比較検討。

また、問題の特性や要求によっては、遺伝的アルゴリズムや蟻コロニー最適化などの他の解法が適している場合もあります。例えば、遺伝的アルゴリズムは複数の解を並列に探索できるため、マルチコアプロセッサを活用した高速化が容易です。蟻コロニー最適化は、経路に関する事前知識（交通量データなど）を重みとして組み込みやすく、現実世界の道路網のような動的に変化するネットワーク上の経路探索に適しています。問題の性質や制約を考慮して、適切な解法を選択することが重要です。

お気軽にご相談ください！

弊社のデジタル技術を活用し、貴社のDXをサポートします。

基本的な設計や実装支援はもちろん、機械学習・データ分析・3D計算などの高度な技術が求められる場面でも、最適なソリューションをご提案します。

初回相談は無料で受け付けております。困っていること、是非お聞かせください。

サービスの詳細はこちら
お問い合わせフォームへ

 

関連投稿:

確率的最適化アルゴリズムの実装と比較：遺伝的アルゴリズムと勾配降下法 数値積分の実装と比較：台形法からガウス求積法まで Graph Neural Networksを用いた異常検知入門 時系列データの予測：LSTMとTransformerの性能比較