ランダム探索 `random_search`#

random_search はパラメータ空間をランダムに探索し、\(f(x)\) の最小値を探索するアルゴリズムです。高次元問題など、グリッドサーチなどの他の手法が困難なときに有効な手法です。ランダム探索はMPI並列化に対応しており、サンプル点を各プロセスに割り振って自明並列計算を行います。擬似乱数列に加え、Sobol列などの quasi-random sequence にも対応しています。

前準備#

MPI 並列を行う場合は、 mpi4py をインストールしておく必要があります。

$ python3 -m pip install mpi4py

quasi-random sequence を使う場合は scipy をインストールしておく必要があります。

$ python3 -m pip install scipy

入力パラメータ#

`[algorithm]` セクション#

name

形式: 文字列

説明: ランダム探索の場合は random_search と記述します。

`[algorithm.mode]` セクション#

探索モードを定義します。このセクションを省略した場合は、擬似乱数(random)が指定されたものとします。

mode

形式: 文字列

説明: 擬似乱数列(random) または quasi-random sequence (quasi-random) を指定します。
sequence

形式: 文字列

説明: quasi-random sequence の場合、使用する数列のタイプを指定します。対応している数列は
- sobol: Sobol sequence
- halton: Halton sequence
- latin: Latin Hypercube
です。詳細は scipy.stats.qmc の対応する項目の説明を参照してください。

`[algorithm.param]` セクション#

探索パラメータ空間を定義します。

min_list

形式: 実数のリスト。長さはdimensionの値と一致させます。

説明: パラメータが取りうる最小値。
max_list

形式: 実数のリスト。長さはdimensionの値と一致させます。

説明: パラメータが取りうる最大値。
num_points

形式: 整数。

説明: ランダムにサンプリングする点の数。
unit_list

形式: 実数のリスト。長さはdimensionの値と一致させます。

説明: 各パラメータの単位。探索アルゴリズム中では、各パラメータをそれぞれこれらの値で割ることで、簡易的な無次元化・正規化を行います。定義しなかった場合にはすべての次元で 1.0 となります。

[algorithm] セクション内には以下のパラメータを設定できます。

seed

形式: 整数。

説明: パラメータ生成に用いる擬似乱数のシード。 quasi-random sequence の場合は数列のスクランブルに用いられ、 seed を指定すると生成される点列が再現可能になります。点列は MPI の並列数によらず同一になります。

出力ファイル#

`ColorMap.txt`#

各サンプル点での候補パラメータと、その点での目的関数の値が記載されたファイルです。データは、入力ファイルの [algorithm] セクションにある label_list で定義された変数(省略時は x1, x2, ...)の順番で記載され、最後に目的関数の値が記載されます。

以下、出力例です。

5.155393 -2.203493 187.944291
-3.792974 -3.545277 3.179381
0.812700 1.146536 108.254643
5.574174 1.838125 483.841834
2.986880 1.842838 0.436331
...

リスタート#

コンストラクタの引数 run_mode に実行モードを指定します。以下はそれぞれ odatse コマンドの引数の --init, --resume, --cont に対応します。各モードの動作は次のとおりです。

"initial" (デフォルト)

初期化して実行します。チェックポイント機能が有効な場合、以下のタイミングで実行時の状態をファイルに出力します。
1. 指定した数のサンプル点を評価したとき、または指定した実行時間が経過したとき
2. 実行の終了時
"resume"

実行が中断した際に、最も新しいチェックポイントから実行を再開します。並列数などの計算条件は前と同じにする必要があります。探索点の数を変更した場合はエラーとなります (再開はチェックポイントを保存した計算の続きを実行するものであるため)。点を増やす場合は --cont を、別の計算として実行する場合は --init を使用してください。
"continue"

前回の実行の状態を引き継ぎ、サンプル点数を新しい入力の num_points まで拡張して実行します。評価済みの点は再利用され、追加分の点のみが新たに評価されます。 continue モードは擬似乱数 (random) と、点列が入れ子構造を持つ準乱数 sobol および halton で利用できます（長い数列の先頭 \(N\) 点は短い数列の点と一致します）。 latin はラテン超方格計画が入れ子構造を持たないため利用できません。latin の場合は新規に計算を開始してください。探索モード・数列の種類・min_list / max_list は前回の実行から変更しないでください。

アルゴリズム解説#

ランダム探索は、探索パラメータの各次元について min_list と max_list で定められた範囲から一様乱数を用いてパラメータ \(x\) を num_points 個生成し、それぞれについてソルバーを呼び出して目的関数 \(f(x)\) を評価します。

MPI 並列実行時には、生成された候補点群をプロセス数で等分割し、各プロセスが担当する点を並列に評価します。

グリッド型探索 (mapper) と異なり、パラメータ空間を規則的に離散化するのではなく一様ランダムにサンプリングするため、次元数が増えても格子点数が指数的に増加する問題（次元の呪い）を回避できます。一方で、最適解の精密な特定には向かないため、他の最適化手法の事前探索として利用されることが多いです。

ランダム探索 random_search#