猫ちゃんによる最適化(をしたかった)

この記事は、物工/計数 Advent Calendar 2021 21日目の記事です！

はじめまして、計数B3のゲータレードです。自分は群知能、特にCSO (Cat Swarm Optimization)について書きたいと思います。 短い記事ですので、ぜひ最後まで見ていってください！

0.  群知能 とは

群知能とは、鳥や魚の群のように、個々の相互作用は単純でありながら、集団としては複雑な振る舞いを見せる現象 (創発現象) を模した計算手法のことです。

例として、蟻群の生態を模したACO (Ant Colony Optimization) というアルゴリズムは、巡回セールス問題などの組合せ最適化問題において、近似最適解を生み出すことができます。

本記事では、猫の生態を模したCSO (Cat Swarm Optimization) というアルゴリズムを扱います。提案論文はこちらになります。

1. CSOについて

このアルゴリズムで用いられる猫の生態は、「ほとんどの時間を怠けているように見えるが、常に周囲に気を配っており、標的を見つけたら即座に動き出す」というものです.　以下では前者の状態を seeking mode 、後者の状態を tracing mode と呼びます。

では、多変数関数の最適化におけるCSOの手順を見ていきましょう。かなり省略しているので、興味のある方は原文をお読みください。

1. 空間を制限し、そこに猫(点)をランダムにばら撒きます。この時、それぞれの猫には固有の速度がランダムに渡されます。
2. ランダムに、猫を seeking mode と tracing mode に割り振ります。
3. それぞれの猫を評価します(つまり、その点での関数の値を計算する)。そして、ベストな猫を選び、記憶します。
4. それぞれの猫ごとに行動します。seeking mode の猫は自分の付近に移動し、tracing mode の猫はベストな猫に向かって移動します。
5. 終了条件(反復回数の上限に達したなど)を確認し、満たしていなければ、ステップ2から4を繰り返します。

2. CSOの検証

では実際にCSOを行なってみます。「 空間に猫を放ち、1000回移動を繰り返す」というのを行い、もっとも良かった猫を出力します。テスト関数に関しては、この論文からお借りしました。また、比較対象として、群知能の有名なアルゴリズムである、PSO (Particle Swarm Optimization)とABC (Artificial Bee Colony algorithm)も実装しました。

結果ですが、CSOは5次元くらいまでなら複雑な関数でも問題ない感じでした。ただ、ABCの方が高速かつ高次元にも対応できるという悲しい結末でしたね...　これに関しては自分のCSOの実装が不適切であった可能性も大いにあります。あと、パラメーターチューニングをしっかり行えば変わってくるかもしれません（私は力尽きました）。PSO < CSO <<< ABCみたいな感じでした。

「実装も検証もうまくいったー！」という記事の予定でしたが、なかなかうまくいかないものですね。

今回用意したPSO、ABC、CSOのコードはここに置いておくので、よかったら試してみてください。

3. まとめ

最後にまとめとして、こちらの論文のConclusionの概説を載せます。

・CSOは局所的探索 (seeking mode) と大域的探索 (tracing mode) を分離して行うので、探索 (exploration) と活用 (exploitation) のバランスが取りやすく、群知能の中では未だに強力なアルゴリズムである

・収束が速いという長所を持つ一方で、局所解に陥りやすくもあり、パラメーターを動的にするといった改善が有効かもしれない

群知能には、動的な関数や不連続関数の最適化に向いているという特徴があります。またアルゴリズムを通して、自然への畏敬の念を感じられたりして興味深いですね。ここまで読んでいただきありがとうございました！

余談ですが、おそらくこの記事を読んだほとんどの人が、「猫」というワードに釣られたのだと思います。そんなアナタは、ぜひ「カワイスギクライシス」というマンガを読みましょう！

参考資料

CSOの実装において、Surdoiu Tudor Marian さんのコードを参考にしました（というか、こちらをそのまま用いた方が精度が良かったです）。PSOの実装においては、こちらの記事を参考にしました。