JP / EN

Rastrigin Function

離散数学と連続数学のハイブリッド法による「悪魔の関数」の攻略

$$f(x) = 10n + \sum_{i=1}^{n} \left[ x_i^2 - 10 \cos(2\pi x_i) \right]$$

Rastrigin Function
Global Minimum: $f(x) = 0$ at $x_i = 0$

1. 対象となる関数とその形状（ラストリギン関数）

最適化アルゴリズムの性能を評価する際、世界中の研究者を悩ませる有名なベンチマーク関数があります。それが「ラストリギン関数（Rastrigin function）」です。

一見するとシンプルな二次関数にコサイン波が足し合わされただけの式ですが、全体としては中心（すべての変数が0の地点）に向かってすり鉢状になっているものの、その表面にはコサイン波に起因する「無数の偽の谷底（局所解）」が規則正しく並んでいます。最適化アルゴリズムは、この無数のトラップを回避しながら、中心にあるたった一つの「真の谷底」を探し当てなければなりません。

2. 連続数学によるアプローチ（ニュートン法とホモトピー法）

① ニュートン法での試み
手始めに、この関数を偏微分して極値問題に置き換え、ニュートン法での求解を実施しました。なお、このニュートン法の実行には、当研究室で構築した「SPICE指向型解析法」を用いています。
結果として、初期値を真の解である0に設定した場合は当然求まりましたが、そこから少しでも外れた初期値を与えると、すぐ隣にある偽の谷底（極値解）にはまってしまい、真の解は全く求まりませんでした。傾き（微分）に従って下へ向かうという連続数学の性質上、途中の谷を登って抜け出すことができないためです。

② ホモトピー法での試み
そこで、初期値への依存性を解消するため、ホモトピー法を試しました。こちらも実装手段としてSPICE指向型解析法を用いています。

  • 不動点ホモトピー法： アルゴリズムとしては動作したものの、結局は局所解に引き込まれてしまい、大域的な正解には至りませんでした。
  • ニュートンホモトピー法： 関数の激しい起伏により、計算過程で Timestep too small のエラーが発生し、動作させることができませんでした。
Heat Equation Result - Spatial Distribution

図2：不動点ホモトピーによる解曲線追跡の様子

3. 離散数学（モンテカルロ法・GA）の導入

連続数学の概念だけでこの関数を解くのは難しいと考え、傾きや連続性を前提としない「離散数学」の概念を導入することにしました。空間全体を確率的に探索するプログラム（モンテカルロ法および遺伝的アルゴリズム：GA）を新たに作成し、検証を行いました。

結果として、局所解のトラップを飛び越え、真の解が存在する正しい谷のエリアに到達するなど、非常に良い結果が得られました。しかし、大まかな正解エリアには辿り着くものの、そこから谷のどん底をミリ単位で特定するような「ピッタリとした解」に行き着くには至りませんでした。

4. 解決策：離散数学と連続数学のハイブリッド法

「離散数学は大域的な探索に強いが、微調整が苦手」「連続数学は局所解に弱いが、ピンポイントの精度は圧倒的である」。

この特性を踏まえ、プログラムのアプローチを大きく転換しました。
「まずは離散数学（GAやモンテカルロ法）を用いて大まかな初期値を求め、そこから連続数学（ニュートン法）にバトンタッチして解を求める」というハイブリッド手法です。

5. 実行結果

この手法を用いた結果、見事に真の解を求めることができました。
前半の離散数学的アプローチが数多の罠を回避して安全な谷底付近まで到達し、そこから引き継いだ連続数学的アプローチ（ニュートン法）が、わずか数回の反復で極限の精度まで一直線に滑り降りました。

以下は、自作プログラムによる5変数版ラストリギン関数の実行ログです。

=== Newton's Method Finished ===
Final Score (Fitness): 0.0000000000
x1 = -0.0000000
x2 = 0.0000000
x3 = 0.0000000
x4 = -0.0000000
x5 = -0.0000000
Dr.WataWata Insight：

それぞれの数学的アプローチの特性を深く理解し、適材適所で組み合わせること（GA + NEWTON）により、単一の手法では到達が困難だった「悪魔の関数」の攻略に成功しました。

6. 新たなソルバー「MAL-Seeker」の開発へ

今回の実験を通じ、離散数学と連続数学を融合させたアプローチは効果があることが分かりました。

これまでSPICEの制御構文等を用いて様々な解析を行ってきましたが、このハイブリッド・アーキテクチャのポテンシャルを最大限に引き出すため、この度、C言語による独自のソルバー「MAL-Seeker（マル・シーカー）」の開発に本格着手することにします。

当Laboratoryの新たなコアエンジンとして、今後の研究をさらに加速させていきます。

7. 解析環境

  • 解析エンジン： 自作ハイブリッド・ソルバー (C言語)
  • PC： MacBook
  • OS： macOS Monterey 12.7.6
  • CPU： 1.2GHz デュアルコア Intel Core m5
  • メモリ： 8GB