Main Content

このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。

GlobalSearchとMultiStartの仕組み

ローカルソルバーの複数回実行

GlobalSearch と MultiStart は、グローバル最小値または複数の最小値を見つけるための同様のアプローチを採用しています。どちらのアルゴリズムも、複数の開始点からローカル ソルバー (fmincon など) を開始します。アルゴリズムは複数の開始点を使用して、複数の吸引域をサンプリングします。詳細については、引き込み領域を参照してください。

ソルバーオブジェクトの違い

GlobalSearch と MultiStart アルゴリズムの概要 には、GlobalSearch および MultiStart アルゴリズムのスケッチが含まれています。

GlobalSearch と MultiStart アルゴリズムの概要

GlobalSearch と MultiStart の主な違いは次のとおりです。

  • GlobalSearch は、開始点を生成するために散布検索メカニズムを使用します。MultiStart は、境界内に均一に分散された開始点、またはユーザーが指定した開始点を使用します。

  • GlobalSearch は開始点を分析し、これまでに見つかった最良の局所最小値を改善する可能性が低い開始点を拒否します。MultiStart はすべての開始点 (または、オプションで、境界または不等式制約に関して実行可能なすべての開始点) を実行します。

  • MultiStart は、ローカル ソルバーの選択肢を提供します: fmincon、fminunc、lsqcurvefit、または lsqnonlin。GlobalSearch アルゴリズムは fmincon を使用します。

  • MultiStart は並列実行が可能で、ローカル ソリューションのために開始ポイントを複数のプロセッサに分散します。MultiStart を並列で実行するには、 Global Optimization Toolbox で並列処理を使用する方法 を参照してください。

使用するソルバーの決定

これらのソルバー オブジェクト間の違いは、どちらを使用するかという次の決定に要約されます。

  • GlobalSearch を使用して、単一のプロセッサ上で単一のグローバル最小値を最も効率的に見つけます。

  • MultiStart を使用して次を行います。

    • 複数の局所最小値を見つけます。

    • 並行して実行します。

    • fmincon 以外のソルバーを使用してください。

    • 全体的な最小値を徹底的に検索します。

    • あなた自身の出発点を探索してください。

グローバルサーチアルゴリズム

アルゴリズムの説明については、Ugray et al. [1] を参照してください。

GlobalSearch オブジェクトを run すると、アルゴリズムは次の手順を実行します。

x0からfminconを実行する

GlobalSearch は、problem 構造で指定した開始点から fmincon を実行します。この実行が収束すると、GlobalSearch は、吸引域の半径の初期推定値の開始点と終了点を記録します。さらに、GlobalSearch は、スコア 関数で使用するための最終的な目的関数値を記録します (ステージ1スタートポイントを取得して実行 を参照)。

スコア関数は、ある時点での目的関数値の合計と制約違反の合計の倍数です。したがって、実行可能なポイントのスコアはその目的関数の値に等しくなります。制約違反の倍数は最初は 1000 です。GlobalSearch は実行中に倍数を更新します。

トライアルポイントを生成する

GlobalSearch は、散布検索アルゴリズムを使用して、NumTrialPoints 試行ポイントのセットを生成します。トライアルポイントは潜在的な開始点です。散布検索アルゴリズムの説明については、Glover [2] を参照してください。GlobalSearch は、設定した有限境界内で試行ポイントを生成します (lb および ub)。無制限のコンポーネントには人工的な境界が課せられます: lb = -1e4 + 1、ub = 1e4 + 1。この範囲は原点を中心に対称ではないため、原点は散布検索に含まれません。片側境界を持つコンポーネントには、無限側に課された人工境界があり、lb < ub を維持するために有限境界によってシフトされます。

ステージ1スタートポイントを取得して実行

GlobalSearch は、NumStageOnePoints 個の試行ポイントのセットのスコア関数を評価します。次に、最高スコアのポイントを取得し、そのポイントから fmincon を実行します。GlobalSearch は、検査するポイントのリストから NumStageOnePoints 試行ポイントのセットを削除します。

流域、カウンター、しきい値を初期化する

localSolverThreshold は、最初はソリューション ポイントにおける 2 つの目的関数値のうち小さい方です。解決ポイントは、x0 から始まる fmincon ソリューションと、ステージ 1 の開始ポイントです。これらのソリューション ポイントが両方とも存在しないか実行不可能な場合、localSolverThreshold は最初はステージ 1 の開始ポイントのペナルティ関数値になります。

GlobalSearch ヒューリスティック仮定は、吸引盆地が球形であるというものです。x0 からの解点とステージ 1 からの解点の吸引域の初期推定値は、解点を中心とした球体です。各球の半径は、初期点から解点までの距離です。これらの推定流域は重複する可能性があります。

アルゴリズムに関連付けられたカウンターのセットが 2 つあります。各カウンターは、次の連続した試行ポイントの数です。

  • 引力の盆地内に横たわる。各洗面台にカウンターが1つずつあります。

  • スコア関数が localSolverThreshold より大きい。スコアの定義については、x0からfminconを実行する を参照してください。

すべてのカウンターは最初は 0 です。

メインループの開始

GlobalSearch はリストから残りの試行ポイントを繰り返し調べ、次の手順を実行します。時間を継続的に監視し、経過時間が MaxTime 秒を超えると検索を停止します。

ステージ2のトライアルポイントを調べてfminconが実行されるかどうかを確認します

試行ポイントを p と呼び出します。次の条件が満たされる場合は、p から fmincon を実行します。

  • p は既存の流域内に存在しません。各流域 i の基準は次のとおりです。

    |p - center(i)| > DistanceThresholdFactor * radius(i).

    DistanceThresholdFactor はオプションです (デフォルト値は 0.75)。

    radius は、流域の半径としきい値の更新および 大きなカウンター値への反応で更新される推定半径です。

  • スコア(p) < localSolverThreshold 。

  • (オプション) p は、境界制約および/または不等式制約を満たします。このテストは、GlobalSearch オブジェクトの StartPointsToRun プロパティを 'bounds' または 'bounds-ineqs' に設定した場合に発生します。

fmincon の実行時

  1. カウンターをリセット

    流域としきい値のカウンターを 0 に設定します。

  2. ソリューションセットの更新

    fmincon が p から開始して実行される場合、収束を示す肯定的な終了フラグが生成される可能性があります。その場合、GlobalSearch は GlobalOptimSolution オブジェクトのベクトルを更新します。解点をxp、目的関数値をfpと呼びます。2つのケースがあります:

    • 目的関数値fqを持つ他のすべての解点xqについては、

      |xq - xp| > XTolerance * max(1,|xp|)

      または

      |fq - fp| > FunctionTolerance * max(1,|fp|).

      この場合、GlobalSearch は GlobalOptimSolution オブジェクトのベクトルに新しい要素を作成します。各オブジェクトに含まれる情報の詳細については、GlobalOptimSolution を参照してください。

    • 目的関数値fqを持つ他の解点xqについては、

      |xq - xp| <= XTolerance * max(1,|xp|)

      と

      |fq - fp| <= FunctionTolerance * max(1,|fp|).

      この場合、GlobalSearch は xp を xq と同等とみなします。GlobalSearch アルゴリズムは、X0 ポイントのセル配列に p を追加して、xq の GlobalOptimSolution を変更します。

      このアップデートでは、小さな調整が 1 つ行われる可能性があります。xq の終了フラグが 1 より大きく、 xp の終了フラグが 1 の場合、 xp が xq に置き換えられます。この置き換えにより、同じ流域内のいくつかのポイントが xp から XTolerance 以上の距離になることがあります。

  3. 流域半径と閾値の更新

    現在の fmincon 実行の終了フラグが正の場合:

    1. 開始点pのスコア値にしきい値を設定します。

    2. xp の流域半径を、既存の半径（存在する場合）と p と xp の間の距離の最大値に設定します。

  4. 反復表示へのレポート

    GlobalSearch Display プロパティが 'iter' の場合、fmincon が実行するすべてのポイントによって、GlobalSearch 反復表示に 1 行が作成されます。

fmincon が実行されない場合

  1. カウンターの更新

    p を含むすべてのベイスンのカウンターを増分します。他のすべての盆地のカウンターを 0 にリセットします。

    score(p) >= localSolverThreshold の場合、しきい値カウンターを増分します。それ以外の場合は、カウンターを 0 にリセットします。

  2. 大きなカウンター値に反応する

    カウンターが MaxWaitCycle に等しい各盆地については、盆地の半径に 1 – BasinRadiusFactor を掛けます。カウンターを 0 にリセットします。(MaxWaitCycle と BasinRadiusFactor は両方とも GlobalSearch オブジェクトの設定可能なプロパティです。)

    しきい値カウンターが MaxWaitCycle に等しい場合は、しきい値を増やします。

    新しいしきい値 = しきい値 + PenaltyThresholdFactor*(1 + abs(しきい値)).

    カウンターを 0 にリセットします。

  3. 反復表示へのレポート

    200 番目の試行ポイントごとに、GlobalSearch 反復表示に 1 行が作成されます。

GlobalOptimSolutionを作成する

MaxTime 秒に達するか試行ポイントがなくなると、GlobalSearch は GlobalOptimSolution オブジェクトのベクトルを作成します。(これらのポイントは、正の fmincon 終了フラグに対応します。) GlobalSearch は、ベクトルを目的関数の値によって、最低 (最良) から最高 (最悪) の順に並べます。これでアルゴリズムは終了です。

マルチスタートアルゴリズム

MultiStart オブジェクトを run すると、アルゴリズムは次の手順を実行します。

入力の検証

MultiStart は入力引数の有効性をチェックします。チェックには、問題の入力に対してローカル ソルバーを 1 回実行することが含まれます。並列で実行する場合でも、MultiStart はこれらのチェックをシリアルで実行します。

開始点を生成する

MultiStartを次の構文で呼び出すと

[x,fval] = run(ms,problem,k)

整数 k の場合、MultiStart は、RandomStartPointSet オブジェクトを使用した場合とまったく同じように k - 1 開始点を生成します。このアルゴリズムは、problem 構造の x0 開始点も使用するため、合計 k 開始点になります。

RandomStartPointSet オブジェクトには、オブジェクト内に保存されるポイントがありません。代わりに、MultiStart は list を呼び出し、problem 構造によって指定された境界内でランダムなポイントを生成します。無制限のコンポーネントが存在する場合、list は RandomStartPointSet オブジェクトの ArtificialBound プロパティによって指定された人工的な境界を使用します。

CustomStartPointSet オブジェクトを指定した場合、MultiStart は開始点を生成せず、オブジェクト内の点を使用します。

フィルター開始点（オプション）

MultiStart オブジェクトの StartPointsToRun プロパティを 'bounds' または 'bounds-ineqs' に設定すると、MultiStart は実行不可能な開始点からローカル ソルバーを実行しません。この文脈では、「実行不可能」とは、境界を満たさない開始点、または境界と不等式制約の両方を満たさない開始点を意味します。

StartPointsToRun のデフォルト設定は 'all' です。この場合、MultiStart は実行不可能な開始点を破棄しません。

ローカルソルバーを実行する

MultiStart は、StartPointsToRun フィルターを通過するポイントから開始して、problem.solver で指定されたローカル ソルバーを実行します。MultiStart が並列で実行されている場合、開始点がワーカー プロセッサに 1 つずつ送信され、ワーカー プロセッサがローカル ソルバーを実行します。

ローカル ソルバーは、各反復で、MultiStart が計算を開始してから MaxTime 秒が経過したかどうかを確認します。そうであれば、MultiStart は解決策を報告せずにその反復を終了します。

ローカル ソルバーが停止すると、MultiStart は正のローカル ソルバー終了フラグに対応する結果を保存し、次のステップに進みます。

反復表示へのレポート.  MultiStart Display プロパティが 'iter' の場合、ローカル ソルバーが実行するすべてのポイントによって、MultiStart 反復表示に 1 行が作成されます。

停止条件を確認する

MultiStart は開始ポイントがなくなると停止します。また、合計実行時間が MaxTime 秒を超えると停止します。

GlobalOptimSolution オブジェクトを作成する

MultiStart が停止条件に達すると、アルゴリズムは次のように GlobalOptimSolution オブジェクトのベクトル (すべて正のローカル ソルバー終了フラグに対応) を作成します。

  1. ローカル ソリューションを目的関数値 (Fval) で最低から最高の順に並べ替えます。lsqnonlin および lsqcurvefit ローカル ソルバーの場合、目的関数は残差のノルムです。

  2. 最も低い（最良）Fval から始めて、ローカル ソリューション j をループします。

  3. 両方を満たす k のすべての解を見つけます。

    |Fval(k) - Fval(j)| <= FunctionTolerance*max(1,|Fval(j)|)

    |x(k) - x(j)| <= XTolerance*max(1,|x(j)|)

  4. j、Fval(j)、j のローカル ソルバー output 構造、および j とすべての k の開始点のセル配列を記録します。これらのポイント k をローカル ソリューションのリストから削除します。この点は、GlobalOptimSolution オブジェクトのベクトル内の 1 つのエントリです。

結果として得られる GlobalOptimSolution オブジェクトのベクトルは、Fval によって最低 (最良) から最高 (最悪) の順に並べられます。

反復表示へのレポート.  すべてのローカルソリューションを検査した後、MultiStart は反復表示に要約を表示します。この概要には、収束したローカル ソルバー実行の数、収束に失敗した数、およびエラーが発生した数が含まれます。

参考文献

[1] Ugray, Zsolt, Leon Lasdon, John C. Plummer, Fred Glover, James Kelly, and Rafael Martí. Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization. INFORMS Journal on Computing, Vol. 19, No. 3, 2007, pp. 328–340.

[2] Glover, F. “A template for scatter search and path relinking.” Artificial Evolution (J.-K. Hao, E.Lutton, E.Ronald, M.Schoenauer, D.Snyers, eds.). Lecture Notes in Computer Science, 1363, Springer, Berlin/Heidelberg, 1998, pp. 13–54.

[3] Dixon, L. and G. P. Szegö. “The Global Optimization Problem: an Introduction.” Towards Global Optimisation 2 (Dixon, L. C. W. and G. P. Szegö, eds.). Amsterdam, The Netherlands: North Holland, 1978.

関連するトピック