技術をかじる猫

適当に気になった技術や言語を流すブログ。

迷路の最短ルートを蟻コロニー最適化で解く

という事でやってみた。
参考書はコレ。

機械学習と深層学習 Pythonによるシミュレーション

機械学習と深層学習 Pythonによるシミュレーション

どこで使おうかと悩んでたら、社内勉強会で「迷路の最短経路を探せ」という問題があったので、応用してみた。
ただし、元のコードは、一定以下に薄いフェロモンを無視しているように見えるが、こちらでは面倒なのでそれをしてない。

https://github.com/Sunao-Yoshii/StudyDocs/blob/master/python/dokaku_ase20181027/ant_colony.py

パット見正しく動いて層には見えるがはてさて?

蟻コロニー最適化法は、迷路でも巡回サラリーマンでもいいのだけど、要するに最も短いルートはどのルートかを計算するアルゴリズム

蟻はフェロモンを地面に塗って、道しるべをつけるけど、これは一定の割合で蒸発して消えてしまう。
その道を参考にしつつ、後続の蟻が少しづつ道を外れたりして、フェロモンの濃いルートが少しづつ短い方によるというもの。

道に元々あったフェロモンは、一定割合で縮小、移動距離の二乗に反比例する形で新しいフェロモンを上塗りするという挙動を繰り返す。
作り自体は単純なので見れ