Linear Proposal Operators and Stochastic Search Geometry in SOMA and Differential Evolution

あなたは、起伏や隠れた窪地がある広大で霧に包まれた谷の中で、最も低い地点を探そうとしていると想像してください。マップの全体像は見えず、「下」を指し示すコンパスも持っていません。これは、コンピュータが「ブラックボックス」最適化問題を解決しようとする際の日常的な姿です。これを行うために、科学者たちは進化アルゴリズムと呼ばれる特別なプログラムを使用します。これは、仮想の探索者たち（「集団」）が徘徊するデジタル生態系のようなものです。彼らはただランダムに歩いているわけではありません。彼らは互いに学び合います。一部の探索者は「リーダー」（これまでに最高の場所を見つけた者）であり、他の探索者は彼らに近づこうとしたり、あるいはさらに良いものを見つけるために他の探索者の経路と自分たちの経路を混ぜ合わせたりします。「SOMA」（自己組織化移動アルゴリズム）と「差分進化（Differential Evolution, DE）」と呼ばれる2つの有名な探索チームがあります。これらは古くから存在していますが、しばしばそれ自体が「ブラックボックス」として扱われてきました。仕組みは分かっていても、探索者が一歩一歩どのように動いているのかという正確な幾何学的なプロセスまでは理解されていないのです。

Vojtěch NovákとIvan Zelinkaによるこの論文は、これらのブラックボックスを分解して、中の歯車を覗き見ることを目的としています。探索者が動き、疲れ、入れ替わるという混沌としたプロセス全体を観察する代わりに、著者たちは「移動」の部分と「判定」の部分を切り離しました。彼らは、これらのアルゴリズムが新しいステップを提案する方法は、見た目よりもずっと単純で数学的であることを発見しました。彼らは、システム全体が混沌としているように感じられても、探索者の動きを直線と単純な数式（線形演算子）を用いて記述できることを見出したのです。この隠された幾何学を理解することで、彼らは、どの方向にどれくらいの距離を跳ぶべきかを正確に把握した、よりスマートなバージョンの探索者を構築することができました。これにより、谷の底を見つける能力が大幅に向上しました。

「提案」と「審判」のマジック

あなたが、0から100の間で秘密の数字を当てるゲームをしていると想像してください。あなたには助けてくれる友人たちのチームがいます。従来の方法では、プロセス全体がぼやけています。友人が数字を提案し、あなたがそれが正しいか確認し、もし高すぎれば修正し、そして誰がゲームに残るかを決める……といった具合です。なぜ友人が特定の数字を提案したのかを判断するのは困難です。

この論文の著者たちは、実際にはここで2つの異なるステップが起きていることに気づき、それらを別々に扱うべきだと考えました。

1. 提案（「もし〜だったら」）: 友人が、自分の現在地とリーダーの現在地に基づいて、新しい数字を提案します。このステップは純粋に幾何学的です。それは地図上に線を引くようなものです。
2. 選択（「審判」）: あなたはその提案を見て、「これは今持っているものより良いか？」と判断します。このステップは、具体的な問題（「適合度」）に依存しており、非線形で複雑です。

この論文の大きなブレイクスルーは、SOMAと差分進化の両方において、提案のステップが実はシンプルで綺麗な直線であることを見出した点にあります。ゲーム全体が複雑に感じられても、新しい候補を生成するという行為は、単純な数学的操作なのです。つまり、現在の位置を取り、リーダーを見つめ、その直線に沿って一定の距離を移動することに過ぎません。

ジャンプの幾何学

著者たちは、これを証明するために巧妙なトリックを用いました。彼らは「移動者（ミグラント）」と「リーダー」を空間上の2点として想定しました。そして、新しい位置が魔法のような予測不能なジャンプではないことを示しました。それは正確に線形変換なのです。

次のように考えてみてください。あなたが点Aに立っていて、あなたのリーダーが点Bにいるとき、アルゴリズムは単にどこへ行くかを「推測」するわけではありません。アルゴリズムはあなたとリーダーの間に直線を描きます。そして、その線上のどこか一点を選びます。

• 補間（Interpolation）: あなたとリーダーの中間地点を選びます。
• 投影（Projection）: リーダーがいるまさにその地点を選びます。
• オーバーシュート（Overshooting）: リーダーの背後までチェックするために、まるでスピードが出すぎて走り抜けてしまったかのように、リーダーを通り越した地点を選びます。

論文では、この動きがいくつかの単純な「つまみ」によって制御されていることを示しています。

• パス・パラメータ ($t$): 線に沿ってどれくらい進むか？
• マスク（PRTまたはCR）: これは、特定の方向からの視界を遮るサングラスのようなものです。もしマスクが「北の方向には動くな」と言えば、探索者は東、南、または西にしか動きません。これにより、一度に一部の座標だけが変化する「疎（スパース）」な動きが生まれます。

著者たちは、マスクをランダムなコイン投げ（ベルヌーイ分布）として扱うことで、探索者の平均的な振る舞いを計算することができました。彼らは以下のような数式を導き出しました。

• 平均して、探索者はどれくらいの距離をジャンプするか？
• ジャンプにおける「広がり」や不確実性はどの程度か？
• 探索者は実際にいくつの方向（次元）に動くのか？

彼らはさらに、「マスク（サングラス）」は単に方向をランダムに遮るのではなく、特定の形状の不確実性を生み出すことも発見しました。マスクの確率が低いと、探索者は非常に少ない方向へ動きます。確率が高いと、多くの方向へ動きます。最も「混沌とした（分散が高い）」動きが発生するのは、マスクが完全に開いているときでも閉じているときでもなく、50%に設定されているときです。

より優れた探索者の構築：新しいバリアント

著者たちは、動きの背後にある数学を理解した後、単に理論に留まりませんでした。彼らはこれらの数式を用いて、改良された3つの新しいバージョンのSOMAを構築しました。

1. 幾何学制御型SOMA (GC-SOMA):
   どの方向に動くかを推測する代わりに、このバージョンではユーザーが「探索者に正確に5つの方向に動いてほしい」や「リーダーの90%の地点まで到達してほしい」といった指示を出せます。アルゴリズムは、これらの特定の幾何学的目標を達成するために必要な設定（マスク確率とパス長）を、数学的数式を用いて算出します。これは、車に対して「正確に50マイル走れ」と伝え、車のコンピュータがアクセルをどれくらい踏むべきかを判断するようなものです。

2. 回転認識型SOMA (RA-SOMA):
   標準的なアルゴリズムは、グリッド線（南北東西）に沿って移動します。しかし、もし谷が傾いていたらどうでしょう？ もし最良の経路が斜めだったら？ 標準的なアルゴリズムは、グリッド線に縛られているため、そのような状況では苦戦します。RA-SOMAは探索者グループ全体を観察し、彼らがいる谷の「形状」を把握し、その形状に合わせて動きを回転させます。これは、グリッドに従って歩くのをやめ、山が傾いていることに気づいて斜めに登り始めるハイカーのようなものです。これにより、このアルゴリズムは非常にトリッキーで捻じれた問題を解く能力が向上します。

3. iL-SHOMA-RA:
   これは、回転のテクニックと他のスマートな機能を組み合わせた「スーパーチャージ版」です。これは過去にうまくいった動き（成功履歴）を記憶し、解に近づくにつれて探索者の数を徐々に減らしていきます（集団削減）。これは、100人の捜索隊でスタートし、宝に近づくにつれてほとんどの人を帰らせ、精鋭のスカウトだけを残して、彼らが完璧な方向に歩ませるようなものです。

結果：本当に機能するのか？

著者たちは、これら新しい探索者を、異なる形状と難易度を持つ有名な24種類の「谷」（BBOBベンチマークと呼ばれます）でテストしました。彼らは、オリジナルのSOMAおよび最高峰の差分進化アルゴリズム（iL-SHADEなど）と比較しました。

結果は明確でした。

• オリジナルは劣る: 未修正の標準的なSOMAは、通常、最もパフォーマンスが低いものでした。動作が遅く、しばしば行き詰まってしまいます。
• 新しいバージョンは強力: 3つの新しいバージョン（GC-SOMA、RA-SOMA、iL-SHOMA-RA）はすべて、オリジナルよりも優れた性能を示しました。
• 回転が鍵: **回転認識型（Rotation-Aware）**バージョンは、低次元の問題（変数5または10）において主役となりました。場合によっては、最高の差分進化アルゴリズムをも打ち負かしました。これは、「移動を問題の形状に合わせて傾ける」ことが大きな利点であることを証明しています。
• 予算（計算量）が重要: 「スーパーチャージ版」（iL-SHOMA-RA）は、コンピュータの計算時間が限られている（計算予算が少ない）場合に特に優れた性能を発揮しました。迅速に良い解を見つけ出すことができました。
• 万能薬ではない: しかし、論文では、これらの新手法がすべてで勝ったわけではないことも慎重に述べています。非常に高次元（変数20）や特定のタイプの問題では、確立された差分進化アルゴリズムの方が依然として優れていました。これらの新手法は、あらゆる最適化における「正解」ではありませんが、古いSOMAに対する劇的な改善です。

なぜこれが重要なのか

この論文が重要なのは、これらのアルゴリズムに対する私たちの考え方を変えたからです。長い間、私たちはこれらを謎めいたブラックボックスとして扱ってきました。この論文はその箱を開け、中の歯車を見せてくれました。それは、「移動」の部分が実は単純な線形数学操作であることを証明しています。

幾何学を理解することで、私たちは推測することをやめ、設計を開始できます。単にランダムな設定がうまくいくことを期待するのではなく、アルゴリズムがどのように動くべきかを正確に指示できるのです。著者たちは、ジャンプの「形状（幾何学）」を制御することで、これらのアルゴリズムをより効率的にできることを示しました。

論文は、これらの新手法は大きな一歩ではあるものの、物語はまだ終わっていないと結論付けています。最適なアルゴリズムは、特定の問題、変数の数、そして利用可能な時間によって異なります。しかし、今や私たちは、より優れた探索者を構築するための地図とコンパスを手にしています。著者たちは、将来的には、これらの幾何学的なアイデアが、より複雑でノイズが多く、制約のある環境でどのように機能するかを探求すべきだと示唆していますが、現時点では、混沌とした探索を精密で数学的に導かれた旅へと変えることに成功したのです。