このページは機械翻訳を使用して翻訳されました。最新版の英語を参照するには、ここをクリックします。
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の実行時
カウンターをリセットする
流域としきい値のカウンターを 0 に設定します。
ソリューションセットの更新
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以上の距離にある可能性があります。
流域半径と閾値の更新
現在の
fmincon実行の終了フラグが正の場合:開始ポイント
pのスコア値にしきい値を設定します。xpの流域半径を、既存の半径 (存在する場合) の最大値とpとxp間の距離に等しく設定します。
反復表示へのレポート
GlobalSearchDisplayプロパティが'iter'の場合、fminconが実行されるすべてのポイントは、GlobalSearch反復表示に 1 行を作成します。
fminconが実行されない場合
カウンターの更新
pを含む各ベイスンのカウンターを増やします。他のすべての盆地のカウンターを0にリセットします。score(
p) >=localSolverThresholdの場合、しきい値カウンターを増分します。それ以外の場合は、カウンターを0にリセットします。大きなカウンター値に反応する
カウンターが
MaxWaitCycleに等しい各盆地については、盆地の半径に1–BasinRadiusFactorを掛けます。カウンターを0にリセットします。(MaxWaitCycleとBasinRadiusFactorは両方ともGlobalSearchオブジェクトの設定可能なプロパティです。)しきい値カウンターが
MaxWaitCycleに等しい場合は、しきい値を増やします。新しいしきい値 = しきい値 +
PenaltyThresholdFactor*(1+ abs(しきい値)).カウンターを
0にリセットします。反復表示へのレポート
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 オブジェクトのベクトル (すべてが正のローカル ソルバー終了フラグに対応) を作成します。
局所解を目的関数の値 (
Fval) で最低から最高の順に並べ替えます。lsqnonlinおよびlsqcurvefitローカル ソルバーの場合、目的関数は残差のノルムです。最も低い（最良）
Fvalから始めて、局所解jをループします。次の両方を満たす解
kをすべて見つけます。|Fval(k) - Fval(j)| <= FunctionTolerance*max(1,|Fval(j)|)|x(k) - x(j)| <= XTolerance*max(1,|x(j)|)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.
