NP困難な抽象空間を探索する蟻の行列【統計力学の不思議世界探索】#34
蟻コロニー最適化(ACO: Ant Colony Optimization)をご存じだろうか？
私のフォロワーなら見たことある人が多いかもしれない。(4分ほどの動画ですが、蟻コロニー最適化の説明は↓この動画に任せます。)
これは、単に蟻の行列ができて嬉しいというだけでなく、巡回セールスマン問題や最小全域木問題の効率的な探索にも使われる。それだけでなく、経路探索などとは全然関係なさそうな問題に対しても見事に抽象化して適用し、あっさりと解決してしまう、そんな鮮烈な驚きのある論文を紹介したい。
統計力学の不思議世界探索、今回紹介する論文はこちら。
Ant Colony Optimizationに関する基礎的研究
09-0141.pdf
(蟻コロニー最適化のきちんとした定式化は、本論文の2章をご覧ください。)
(初の日本語論文の紹介！)
次のような問題を考える。
支間長が$${l_1, l_2}$$の支点があり、その4点から十字に梁を渡してその梁全体にかかる荷重(どの部位にも均等にqの重さが掛かるとする)に耐えつつも、梁の総材量は極力少なくしたいという問題。建物の屋根や床を支える構造などとして至る所にある。よくNP困難問題(効率的に解決するアルゴリズムは存在せず、近似解法に頼るか試行錯誤して最適解に近づけるしかない問題)になることでお馴染み(?)の設計最適化問題の一種だ。
支間長が l1, l2 の支点に十字に梁を渡す。交点は互いにちょうど半分の位置とする。
長さ$${l_1, l_2}$$の梁の断面積はそれぞれ$${A_1, A_2}$$とし、総材料は$${OBS＝A_1l_1+A_2l_2}$$と書ける。これが最小化したい目的関数(OBS)である。
変えられる2つの変数$${A_1, A_2}$$について、本実験ではそれぞれ1～32の値を試してみる。1024(=32×32)通り全部試せばいいと思われるかもしれないが、蟻コロニー最適化なら試行数はもっと減らせる。
蟻に探索させるパラメータ空間の経路として次のような2パターンを考える。
巣と餌場の往復のように、スタート地点から何度も左右に往復しながらフェロモンを付着させ、フェロモンの多い道を高確率で選ぶ
考え方として、行き返りで経路が変わることもある左のタイプⅠと、行き返りで経路は同じに制限する右のタイプⅡが考えられる。
この図では簡略化されているが、スタート以外各層には32個のノードがある。
どのパラメータで目的関数(梁の総材料)が最小になり、かつ、梁が折れずに耐えられるかは蟻たちにはわからず、最初はランダムに経路を選ぶ。蟻1匹1匹が左右端に着く毎に、その選ばれた経路のパラメータで梁のシミュレーションを行い、梁が折れたらその蟻のパラメータ空間の探索はそこで終わり、梁が折れなかったら目的関数が小さいほど濃いフェロモンをパラメータ空間の経路に残す。次の往復からはフェロモンの濃い経路ほど高確率で選び、同様の往復をする。
梁は、片方だけでも細すぎると耐えられず折れてしまうので、その条件として下図のようにどちらの軸も値が小さすぎる(軸に近い)ところは非許容量域となる。均等に近い太さで支え合う部分ではもう少し強くなるが、そのあたりはやってみないとわからない。(このシミュレーションが大変なために1024(=32×32)通りの全探索は難しく、素早く最適解を見つけるために蟻コロニー最適化を使っているという問題設定。図2，3の経路は1024往復もしなくても最適解に近づけそうだ。)
A1, A2ともに、1～32の範囲を試してみる。
どちらも細すぎると折れてしまうという境界線が、左上と右下の太線。
本論文には、理論計算による境界線が全て書いてあるが、蟻たちにとっては境界は不明なのでこう改変した。
この32×32マスに、最初はランダムに点を打ち、各点で耐荷重を計算して梁が折れてしまうなら非許容量領域、梁が折れないなら材料が少ないほど濃いフェロモンがパラメータ空間の経路に残される。
勘違いしないでほしいのは図5の平面でフェロモンの濃い点へと探索するのではなく、図2，3の経路上でフェロモンの濃い経路へ探索するということ。つまり$${A_1}$$と$${A_2}$$それぞれでフェロモンの濃い経路が選択されるので、図5の平面でいうと斜め移動は起こらずマンハッタン距離的な移動が行われる。(本論文では、斜め移動もできるように改良したものも紹介されるが、本記事では割愛。)
最初に打たれた点のうち、フェロモンの濃い点の近くが次の世代では探索され、次以降の世代も同様に繰り返される。蟻が10匹の場合は、10点だけの点描という”解像度”だが、世代を繰り返すごとに10点だけの点描でも最適解がありそうな場所に範囲を絞って解像度を上げていくというイメージ。(蟻の経路選択は確率的なので、局所最適に陥ってしまわないように外れたところを探索する蟻も稀にいる。)
タイプⅠ、Ⅱそれぞれの経路設定で蟻の個体数を変えて、シミュレーションした結果が図6。
各点、乱数を変えた5回の平均値
タイプⅠなら20匹程度、タイプⅡなら15匹程度でかなり最適解近くにまで落ち着く。
蟻の動きのランダム要素と局所最適の存在によって、必ずしもぴったり最適解にたどり着けるわけではないが、驚異的なほど計算量を削減しつつもかなり最適解に近づくことができるのが蟻コロニー最適化の威力だ。
冒頭にもちょっと書いたが、NP困難問題に対して、試行錯誤して最適解に近づけるという人力でやるしかなさそうな営みを、1回1回の試行を単純な仕組みの蟻にやらせてアルゴリズム的に仕立て上げたのが蟻コロニー最適化と言えそうだ。
蟻一匹の試行は雑だが、フェロモンによって少しづつ最適に近づくように傾斜を掛けた上で、何百回も計算をやり直すことで最適解に近づける。やり直す分無駄な計算をしてしまっているようにも思うが、フェロモンによる傾斜のおかげで、全探索してきっちり計算するよりはずっと速く最適解に近づくことができる。
蟻は目が見えなくてもフェロモンを辿れば歩いて行けるので、実空間でなくても抽象的な空間でも歩いて行けるのが強みとも言える。
本論文では、実空間から梁のパラメータ空間へと1段階抽象化することによって、蟻コロニー最適化を意外なものに転用している。
このような十字の梁の最適化問題以外にも、巡回セールスマン問題や集合被覆問題など経路探索とは関係なさそうなものまで多くのNP困難問題に対して、かなり計算量少なく最適解に近づくことのできる手法として蟻コロニー最適化は研究されている。
この1段抽象化するというような見事な概念操作による難問解決は、山を一つ越えたら雪が全くなく快走できる世界になってしまうような、理論物理や数学をやっていてこの上ない爽快感を得られる瞬間だと思う。
ちょっと前に見て感心したが、↓これはさらに、抽象空間のトポロジー的性質を利用して証明をするという見事な概念操作の事例。
告知
当方、花粉症のため集中力が持たず、5月ごろまで更新が不定期もしくはほぼない状態が続くかもしれません。