巡回セールスパーソン問題
ビジネスパーソンが，都市Aから，都市B，C，Dを訪問して，本店Aに戻りたい．総移動距離が最短になる順序を見出すのが，巡回セールスパーソン問題です．4都市なら，すべての経路を列挙して試すことが可能です．すべての解を試すことを，ブルートフォース探索または全探索といいます．現実的な時間で実行できれば，最適を保証できます．ただ，一般的な\(n\)都市問題には，いくつの経路があるでしょうか？\((n-1)!\)個の経路が存在する．ビジネスパーソンが，米国の50州のそれぞれにある1つの都市を訪問する必要があるとき，\(49! = 6.1 \times 10^{62}\)になります．大規模な問題を全探索で解決することは不可能に近いです．さて，どうやって解決しましょうか．
蟻コロニー最適化
ひとつの手段が蟻コロニー最適化です．蟻が都市を移動しながら，経路にフェロモンを付着させることをコンピュータ上でプログラムします．フェロモンは，蓄積だけでなく，蒸発もします．蟻が，現在の都市から他の都市に移動する確率は，都市間のフェロモンの量に比例するようにします．最短経路を見つけることが目的であるため，遠くの都市より近くの都市に移動する可能性が高いようにします．
実験
ベルリンの52か所を回る実験結果をご紹介します．
参考
本ページは，以下の教科書とサンプルコードをもとに，最適化の振る舞いを可視化しました．
- Dan Simon, Evolutionary Optimization Algorithms: Biologically-Inspired and Population-Based Approaches to Computer Intelligence, John Wiley & Sons, 2013
- https://academic.csuohio.edu/simond/EvolutionaryOptimization/