ランダム検索

ランダム探索 (RS) は、問題の勾配を最適化する必要がない数値最適化手法のグループであり、連続または微分可能でない関数にも使用できます。このような最適化手法は、直接探索法、導関数フリー法、またはブラックボックス法とも呼ばれます。

アンダーソンは 1953 年に、パラメータ探索空間に一定の順序またはパターンで分布する一連の推測値、たとえば指数分布の間隔/ステップを持つ交絡設計を使用して、問題の最大値または最小値を見つける方法の進歩についてレビューしました。^[1]この探索は各パラメータに対して順次実行され、最後のシーケンスから最良の推測値を繰り返し改良します。パターンは、すべてのパラメータのグリッド (階乗) 探索、各パラメータの順次探索、またはその両方の組み合わせです。この方法は、アンダーソンの論文に記載されている多くの科学者によって、化学反応の実験条件をスクリーニングするために開発されました。サンプルの数学モデルの一般的な非線形回帰の順次手順を再現する MATLAB コードは、こちら (JCFit @ GitHub) にあります。^[2]

「ランダム検索」という名前は、基本的な数学的分析とともにRSの初期プレゼンテーションを行ったRastrigin ^[3]に由来しています。RSは、現在の位置を囲む 超球面からサンプリングされた検索空間内のより良い位置に反復的に移動することによって機能します。

ここで説明するアルゴリズムは、ローカル ランダム検索の一種であり、各反復は前の反復の候補ソリューションに依存します。検索空間全体からサンプリングする代替ランダム検索方法 (たとえば、純粋なランダム検索や均一なグローバル ランダム検索) もありますが、この記事では説明しません。

ランダム探索は人工ニューラルネットワークにおけるハイパーパラメータの最適化に使用されている。 ^[4]

検索空間の適切な部分が体積の 5% を占める場合、検索空間で適切な構成に遭遇する確率は 5% です。60 の構成を試した後、少なくとも 1 つの適切な構成が見つかる確率は 95% を超えます ( 、反確率を使用)。 ${\displaystyle 1-0.95^{60}=0.953>0.95}$

f : ℝ ⁿ  → ℝ を最小化すべき適応度関数またはコスト関数とする。x ∈  ℝ n^を探索空間内の位置または候補解とする。基本的な RS アルゴリズムは次のように記述できる。

1. 検索空間内のランダムな位置でx を初期化します。
2. 終了基準が満たされるまで (たとえば、実行された反復回数や適切な適合度に達するまで)、次の操作を繰り返します。
   1. 現在の位置x を囲む指定された半径の超球面から新しい位置yをサンプリングします(たとえば、超球面をサンプリングするためのMarsaglia の手法を参照してください)。
   2. f ( y ) <  f ( x )の場合は、 x  =  yに設定して新しい位置に移動する。

真のランダム検索は完全に運によるもので、非常にコストがかかるものから非常に幸運なものまでさまざまですが、構造化されたランダム検索は戦略的です。文献では、検索空間で構造化されたサンプリングを使用した RS のさまざまなバリエーションが紹介されています。

• フリードマン・サベージ法：初期推定値と境界の間に空間パターンを持つ推定値のセットで各パラメータを順次検索します。^[5]指数分布ステップの例は、MATLABコード（JCFit @ GitHub）で確認できます。^{[2]このサンプルコードは}、Levenberg–Marquardtアルゴリズムよりも1〜2桁遅く収束しますが、GitHubにも例が提供されています。
• 固定ステップサイズランダム探索（FSSRS）は、固定半径の超球面からサンプリングするRastrigin ^{[3]の基本アルゴリズムです。}
• ^{シューマーとシュタイグリッツ[6]}による最適ステップサイズランダム探索（OSSRS）は、主に、高速に収束できるように超球面の半径を最適に調整する方法に関する理論的な研究です。OSSRSの実際の実装では、繰り返しサンプリングしてこの最適半径を近似する必要があり、実行コストが高くなります。
• シューマーとシュタイグリッツによる適応ステップサイズランダム探索（ASSRS）^[6]は、ハイパースフィアの半径を経験的に適応させようとします。2つの新しい候補ソリューションが生成されます。1つは現在の公称ステップサイズで、もう1つはより大きなステップサイズです。より大きなステップサイズは、より大きな改善につながる場合にのみ、新しい公称ステップサイズになります。数回の反復でどちらのステップでも改善につながらない場合は、公称ステップサイズが縮小されます。
• ^{SchrackとChoit [7]}による最適化相対ステップサイズランダム探索（ORSSRS）は、単純な指数関数的減少によって最適なステップサイズを近似します。ただし、減少係数を計算する式はやや複雑です。

• ランダム最適化は、超球面ではなく正規分布からサンプリングする、密接に関連した最適化手法のファミリーです。
• Luus–Jaakolaは、サンプリングに均一分布を使用し、サンプリング範囲を指数関数的に減少させる簡単な式を使用する、密接に関連した最適化手法です。
• パターン検索は、指数関数的に減少するステップ サイズを使用して、検索空間の軸に沿ってステップを実行します。