🐜 アントコロニー最適化 (ACO) - TSP デモ

このデモについて

目的

アントコロニー最適化 (ACO) により、巡回セールスマン問題 (TSP) の近似解探索の様子を可視化します。

遷移確率

未訪問都市 j への遷移確率は (τ_ij)^α(η_ij)^β に比例します。η は 1/距離、τ はフェロモン量、α・β はそれぞれの重みです。

フェロモン更新

各イテレーションで蒸発率 ρ で減衰し、各アリの経路に Q/L (L は経路長) を付与します。加えて最良経路へ弱い強化を行っています。

パラメータ

• 都市数: キャンバス上の都市の数。多いほど経路探索が難しくなる。
• アリ数/イテレーション: 1反復で経路を構築するアリの数。多いほど探索の幅は広がるが計算量が増える。
• 速度: 描画の更新速度。数値が大きいほど速く進行。
• 打ち切り: 指定反復数に到達すると自動停止（実験時間の制御に便利）。
• α (アルファ): フェロモン τ の重み。大きいほど過去に強化された道を選びやすくなる（集約）。
• β (ベータ): ヒューリスティック η=1/距離 の重み。大きいほど近い都市を優先する（貪欲）。
• ρ (ロー): 蒸発率 0..1。大きいほどフェロモンが早く減少し、探索が拡散傾向に。
• Q: フェロモン付与量の係数。各アリの経路に Q/L を加算（L は経路長）。
• フェロモン表示: グラフ上の薄紫線で τ を可視化。非表示にすると最良経路のみ表示。
• 都市番号表示: 各都市のインデックスを表示/非表示。

操作

・「都市をランダム生成」で初期配置を作成。キャンバスをクリックして都市を追加できます。
・開始/一時停止、パラメータ調整、リセットが可能です。