MATLABのGlobal Optimization ToolboxのGlobalSearchのアルゴリズムについて（最小値探査、第二歩）

（この記事はGemini 3.0 Pro (2025年12月10日)によって作成しました）

GlobalSearchのアルゴリズムについて概略を下記の記事で説明しました。

この記事では、MathWorks公式ドキュメント「GlobalSearchとMultiStartの仕組み」に基づき、GlobalSearchのアルゴリズムについて分かりやすく解説します。

一言で言うと、GlobalSearchは**「無駄な計算を省きながら、効率よく全体（グローバル）の最小値を探す」ための賢いアルゴリズムです。単純にたくさんの場所から計算をスタートするのではなく、「見込みのある場所」だけを選んで詳細な計算（局所探索）を行う**のが最大の特徴です。

以下に、アルゴリズムの具体的な流れをステップごとに説明します。

---

GlobalSearch アルゴリズムの実行フロー（大枠）

GlobalSearchの処理は、大きく分けて**「初期段階（準備）」と「メインループ（選別と探索）」**の2段階で進みます。

1. 初期段階：基準となる解を見つける

まず最初に、以下の手順でいくつかの解を見つけ、探索の「基準」を作ります。

• ユーザー指定点 ($x_0$) からの実行:
  まず、ユーザーが設定した初期点 $x_0$ から局所ソルバー（fmincon）を実行し、最初の局所解を見つけます。
• トライアルポイント（試行点）の生成:
  散布探索 (Scatter Search) という手法を使い、探索範囲内に多数の点（デフォルトで1000個など）をばら撒きます。これらを「トライアルポイント」と呼びます。
• ステージ1（有望な点の最初の選抜）:
  トライアルポイントの中から一部（例: 200個など）を選び、関数値を評価します。その中で最もスコアが良い（値が小さい）1点だけを選び、そこから fmincon を実行してもう一つの局所解を得ます。

これにより、少なくとも1つか2つの局所解が得られ、それらが「既知の解」として登録されます。

2. フィルタリングの準備：引き込み領域（Basin of Attraction）

ここがGlobalSearchの賢いポイントです。
見つかった局所解の周りには、「そこからスタートしたら結局同じ解にたどり着くであろう領域」があると仮定します。これを引き込み領域 (Basin of Attraction) と呼びます。

• GlobalSearchは、解を中心とした球状の範囲を引き込み領域として仮定し、半径を設定します。

3. メインループ（ステージ2）：有望な点だけを探索する

残りのトライアルポイントを一つずつチェックし、以下の条件を両方満たす場合のみ、そこから fmincon を実行します。

1. 「既知の引き込み領域」の外にあるか？
   • すでに探索済みの解の近く（引き込み領域内）にある点は、「計算してもどうせ同じ解に行き着く」と判断され、スキップされます。
2. スコア（関数の値）が十分良いか？
   • 現在の「しきい値（これまでの最良解に近い値）」よりも、その点の関数値が小さく（良く）ないと、探索する価値がないと判断され、スキップされます。

4. 結果の更新と調整

条件を満たして fmincon を実行した場合、その結果に応じて情報を更新します。

• 新しい解が見つかった場合:
  それを新たな「既知の解」としてリストに加え、新しい引き込み領域を設定します。
• 既存の解と同じだった場合:
  引き込み領域の半径を広げます（もっと遠くからでもこの解にたどり着くことが分かったため）。

また、長時間新しい解が見つからない場合は、探索条件が厳しすぎる可能性があるため、引き込み領域の半径を小さくしたり、しきい値を緩めたりして、探索を行いやすくする自動調整（ヒューリスティック）も行われます。

GlobalSearch アルゴリズムの実行フロー（それぞれの詳細）

1. 初期段階：基準となる解を見つける
2. フィルタリングの準備：引き込み領域（Basin of Attraction）
3. メインループ（ステージ2）：有望な点だけを探索する
4. 結果の更新と調整
   についてそれぞれ詳細に説明します。

1. 初期段階：基準となる解を見つける

**「初期段階：基準となる解を見つける」というステップは、GlobalSearchが本格的な探索（メインループ）に入る前の「準備運動」兼「ベースライン作り」**にあたる非常に重要な工程です。

この段階の目的は、**「手当たり次第に計算する前に、とりあえず有望そうな解を確保し、比較の基準（しきい値）を作る」**ことにあります。

具体的な処理の流れをさらに細かく、MATLABの内部動作（パラメータ含む）に即して解説します。

詳細プロセス：初期段階 (Initialization)

このフェーズは、以下の3つのサブステップで進行します。

1.1. ユーザー指定点 ($x_0$) の徹底解析

まず最初に、ユーザーが fmincon に渡した初期点（StartPoint または $x_0$）を最優先で処理します。

• 動作: アルゴリズムは、$x_0$ からスタートして fmincon（局所探索）を最後まで実行します。
• 目的: ユーザーが「ここら辺に解がありそう」と指定した点は、最も信頼性が高いためです。
• 結果: ここで1つ目の「局所解（ローカルミニマム）」が見つかります。もしGlobalSearchが失敗しても、少なくともこの解は確保されます。

1.2. 散布探索（Scatter Search）による点のばら撒き

次に、探索空間全体に候補点を生成します。

• 動作: 設定された境界内（lb, ub）に、トライアルポイントと呼ばれる多数の点を生成します。
  • デフォルトでは 1000個 (NumTrialPoints) 生成されます。
  • これらは単純なランダムではなく、散布探索 (Scatter Search) アルゴリズムを用いて、空間全体にまんべんなく、効率的に配置されるように計算されています。

1.3. 第1ステージ（Stage 1）の選抜と実行

生成された1000個の点すべてに対して fmincon を行うのは時間がかかりすぎます。そこで、まずは「味見」を行います。

• 選抜: 1000個のトライアルポイントの中から、最初の 200個 (NumStageOnePoints) をピックアップします。
• 評価（味見）: この200点について、関数の値（スコア）だけを計算します。
  • 重要: ここではまだ fmincon は走らせません。単にその場所の高さ（$f(x)$）を測るだけです。
• 最良点の特定: 200個の中で、最もスコアが良かった（値が最小だった）1点だけを選び出します。
• 実行: その選ばれた「ベストな1点」からスタートして、fmincon を実行します。
  • これにより、2つ目の「局所解」が見つかります。

---

この初期段階が終わった時点でどうなっているか？

このプロセスが完了すると、GlobalSearchは以下の情報を持った状態でメインループ（後半戦）へ突入します。

1. 確保済み解リスト:
   • ユーザー指定点からの解（1つ）
   • 散布点の中で一番良かった点からの解（1つ）
   • 合計 2つの局所解 が手元にあります。
2. しきい値（ScoreThreshold）の設定:
   • 見つかった解の関数値をもとに、「これより値が悪かったら計算する価値なし」という基準（しきい値）が設定されます。
3. 引き込み領域（Basin）の仮定:
   • 見つかった2つの解の周辺は「もう探索済み」と見なされ、半径 $r$ の球状のエリア（引き込み領域）が定義されます。

なぜこの手順が必要なのか？

もしこの初期段階がなく、いきなりメインループに入ると、「何が良い値なのか」の基準がないため、無駄な計算（質の悪い点からの探索）を大量に行ってしまう可能性があります。

最初に「ユーザーの予想」と「ランダムな点のベスト」の2つを解析しておくことで、**「最低でもこのレベルより良い解を探す」**という明確な基準ができ、その後の探索効率が劇的に向上するのです。

2. フィルタリングの準備：引き込み領域（Basin of Attraction）

**「フィルタリングの準備：引き込み領域（Basin of Attraction）」**について詳しく解説します。

ここは、GlobalSearchが**「以前と同じ答えにたどり着く無駄な計算」を徹底的に回避するための仕組み**です。

概念的なイメージ（物理的な意味）と、MATLABが内部で行っている計算（アルゴリズム的な処理）の2つの側面から説明します。

2.1. 概念的なイメージ：「谷」と「雨粒」

最適化問題を「山岳地帯」に例えると非常に分かりやすくなります。

• 関数の最小値: 「谷底」です。
• fmincon（局所探索）: 「ボール（または雨粒）」が斜面を転がって谷底に落ちていくプロセスです。

引き込み領域（Basin of Attraction）とは：
ある特定の「谷底」に行き着くことになる、すべての斜面の範囲のことです。

• もしボールを「谷Aの斜面」のどこかに置けば、必ず「谷底A」に転がり落ちます。
• この「谷Aの斜面全体」が、谷底Aの引き込み領域です。

GlobalSearchの狙い：
「すでに谷底Aを見つけているなら、谷Aの斜面（引き込み領域）の途中からボールを転がすのは時間の無駄だ」と考えます。なぜなら、計算しても結局知っている「谷底A」に着くだけだからです。

2.2. MATLAB内部での処理：実際どう計算しているのか？

しかし、数学的に正確な「斜面の形（真の引き込み領域）」を知るには、地形全体を計算しなければならず、本末転倒です。
そこでGlobalSearchは、**「円（球）」を使って引き込み領域を大まかに推定（近似）**します。

手順 A：見つけた解に「半径」を与える

初期段階で局所解（谷底）が見つかると、GlobalSearchはその点を中心とした球状のエリアを定義し、「ここはもう調べた谷のエリアだ」とマークします。

• 中心: 見つかった局所解（$x^*$）
• 半径: $r$（最初は小さく設定されます）

この球の内側が、GlobalSearchが認識する**「仮想的な引き込み領域」**となります。

手順 B：トライアルポイントの選別（フィルタリング）

新しいトライアルポイント（$x_{trial}$）を評価する際、以下の判定を行います。

• 判定: 「この点は、既知の解（$x^*$）から半径 $r$ の内側にあるか？」
  • Yesの場合: 「この点からスタートしても、どうせ $x^*$ に吸い寄せられるだけだろう」と判断し、fmincon を実行せずにスキップします。
  • Noの場合: 「まだ知らない谷に行くかもしれない」と判断し、次のステップ（スコアによる判定）に進みます。

2.3. さらに賢い機能：「半径」の自動学習

ここがこのアルゴリズムの最も優れた点ですが、この半径（引き込み領域の推定サイズ）は固定ではなく、探索中に成長します。

もし、半径の外側にある点から fmincon を実行した結果、**「結局、既知の解と同じ場所にたどり着いてしまった」**場合、アルゴリズムは次のように学習します。

「おっと、予想よりもこの谷（引き込み領域）は広かったようだ。もっと遠くからでもここに落ちてくるのか」

そして、**その解の「引き込み領域の半径」を拡大（更新）**します。
これにより、探索が進めば進むほどフィルターの精度が上がり、無駄な計算がより強力にカットされるようになります。

「2. フィルタリングの準備：引き込み領域（Basin of Attraction）」のまとめ

• 概念: 「そこからスタートしたら同じゴールに着く範囲」のこと。
• 実装: MATLABは、解を中心とした「球（半径）」でこれを近似しています。
• 効果: 「既知の解の近く（半径内）」にある点からの再計算をスキップし、未知の領域の探索にリソースを集中させます。

3. メインループ（ステージ2）：有望な点だけを探索する

「メインループ（ステージ2）：有望な点だけを探索する」は、GlobalSearchのアルゴリズムの中で、実際に最も時間をかけて探索を行う中核部分です。

初期段階で「2つの局所解」と「比較基準（しきい値）」を手に入れた後、残りの数百〜数千個のトライアルポイント（試行点）を一つずつ精査していきます。

ここでは、**「2つの厳しい関門（フィルター）」**を突破したエリート点だけが fmincon（局所探索）を実行される権利を得ます。

---

ステージ2の具体的な処理フロー

残っているトライアルポイント（リストの残りすべて）に対して、順番に以下のプロセスを行います。

第1の関門：場所のフィルター（引き込み領域チェック）

まず、その点の「位置」をチェックします。

• 判定: 「この点は、すでに見つかっている局所解の**引き込み領域（Basin of Attraction）**の中にあるか？」
• Yesの場合: すでに知っている解にたどり着く可能性が高いため、即座にスキップします（計算しません）。
• Noの場合: 第2の関門へ進みます。

第2の関門：値のフィルター（スコアチェック）

次に、その点の「ポテンシャル（関数値）」をチェックします。

• 判定: 「この点の関数値 $f(x)$ は、**しきい値（ScoreThreshold）**よりも小さい（良い）か？」
• Noの場合（値が悪い）:
  • 「場所は新しいかもしれないが、スタート地点での値が悪すぎる（山が高すぎる）。ここから降りても、今のベスト記録を更新するような深い谷底には行かないだろう」と判断され、スキップされます。
• Yesの場合（値が良い）:
  • 「場所も新しいし、値も有望だ」と判断され、ようやく合格となります。

---

合格後の処理：fmincon の実行と「学習」

2つの関門を突破した点についてのみ、実際に fmincon を実行して局所探索を行います。その結果に応じて、GlobalSearchは自身の知識をアップデート（学習）します。

ここでの結果は主に2パターンです。

ケースA：新しい局所解が見つかった（発見！）

探索の結果、これまで知らなかった新しい谷底（局所解）にたどり着いた場合です。

1. リストに追加: 新しい解を「既知の解リスト」に加えます。
2. 半径の設定: 新しい解の周りに、初期サイズの引き込み領域（半径）を設定します。
3. しきい値の更新: もしこの解が非常に優れた値（グローバル最小値候補）であれば、しきい値（ScoreThreshold）を厳しく（小さく）します。
   • 意味: 「もっと良い解が見つかったから、次からはこれより良くないやつは相手にしないぞ」と基準を上げることで、今後の探索を高速化します。

ケースB：結局、既知の解と同じだった（再確認）

場所フィルターをすり抜けて探索したのに、転がり落ちた先が「すでに知っている解」だった場合です。

1. 半径の拡大: 「フィルターをすり抜けたということは、この解の引き込み領域はもっと広かったんだな」と学習し、その解の引き込み領域の半径を拡大します。
   • 意味: 次回以降、この周辺の点が「場所フィルター」でより確実に弾かれるようになり、無駄が減ります。

---

「3. メインループ（ステージ2）」のまとめ：ステージ2の賢さ

このステージ2の動きを人間に例えると、**「ベテランの金脈探し」**のようなものです。

1. 初期段階: とりあえず数箇所掘ってみて、金が出る基準を知る。
2. メインループ: 新しい場所を候補にする際、
   • 「そこはもう掘った場所の近くだからダメ（場所フィルター）」
   • 「そこの地表の土を見る限り、金が出そうな気配がない（値フィルター）」
   • 「未開拓の場所で、かつ地表の気配も良い場所だけ掘ろう（fmincon実行）」

さらに、掘ってみて「やっぱり前の穴と繋がってた」と分かれば、「この穴の範囲はもっと広いぞ」と地図（半径）を修正し、探索の精度をどんどん高めていくのがGlobalSearchの特徴です。

4. 結果の更新と調整

**「4. 結果の更新と調整」**について詳しく解説します。

ここは、fmincon（局所探索）を実行した結果を受けて、**「GlobalSearchが賢くなる（学習する）」**フェーズです。

単に解を保存するだけでなく、**「次回の探索をより効率的にするため、フィルターの基準（地図としきい値）を書き換える」**作業が行われます。

大きく分けて、以下の3つのパターンのいずれかの処理が行われます。

---

パターンA：新しい解が見つかった場合（新規開拓）

fmincon が収束した先が、今までリストになかった「未知の場所」だった場合です。

1. 解の登録:
   • 見つかった解（位置と関数値）を「既知の解リスト」に追加します。
   • もしこれが今までで一番良い解（グローバル最小値）なら、暫定チャンピオンとして記録します。
2. 新しい引き込み領域の作成:
   • この新しい解を中心とした**新しい引き込み領域（半径 $r$）**を設定します。
   • これにより、次回からこの近くの点は「探索済み」として扱われるようになります。
3. しきい値（ScoreThreshold）の厳格化:
   • より良い解が見つかると、アルゴリズムは**「合格ライン」を引き上げます**（値を小さくします）。
   • 論理: 「こんなに深い谷（良い解）が見つかったんだから、これより浅い谷（悪い値）の探索に時間を使うのはやめよう」という判断です。

パターンB：既知の解と同じだった場合（再確認・学習）

fmincon を実行してみたけれど、たどり着いた先が「すでに知っている解」だった場合です。
これは一見「無駄足」に見えますが、GlobalSearchにとっては**「引き込み領域の広さを知るための重要なデータ」**になります。

1. 半径（Radius）の拡大:
   • スタート地点とゴールの解との距離を測ります。
   • その解の引き込み領域の半径を、「スタート地点が含まれるサイズ」まで拡大します。
2. 効果:
   • 論理: 「フィルターをすり抜けて計算してしまったが、実はここもこの解の縄張り（引き込み領域）だったのか。じゃあ地図を広げておこう」
   • 次回以降: この広げられた半径の内側にある点は、次回から「場所フィルター」で確実に弾かれるようになり、計算コストが削減されます。

パターンC：解が見つからなかった場合（失敗）

fmincon が収束しなかった（発散した、エラーが出た）場合です。

• この場合は特にリストへの追加や半径の更新は行わず、単にその試行を破棄して次の点の処理に移ります。

---

全体的な調整：しきい値の自動調整

上記の個別の更新に加え、GlobalSearchは探索の進み具合を見て、全体的な**「しきい値（ScoreThreshold）」**の調整も行います。

• 基準: 現在の最良解（Global Minimum）の値 ($f_{best}$) と、トライアルポイント全体の分布をもとに計算されます。
  • 数式イメージ: ScoreThreshold $\approx f_{best} + \text{オフセット}$
• 動き:
  • 探索が進んで $f_{best}$ が更新される（より小さくなる）と、連動して ScoreThreshold も下がります。
  • これにより、探索終盤になるほど審査が厳しくなり、「逆転の可能性がない点」は徹底的に無視されるようになります。

---

「4. 結果の更新と調整」のまとめ：このステップの意味

この「結果の更新と調整」があるおかげで、GlobalSearchは計算を進めるごとに以下のように進化します。

1. 地図が正確になる:
   • 最初は小さな円（半径）しかなかったのが、探索が進むにつれて円が大きくなり、お互いに重なり合い、空間の「どこに行けばどの解に落ちるか」のカバー率が上がります。
2. 目が肥える（基準が厳しくなる）:
   • 最初は「とりあえず何でもいいから探そう」だったのが、良い解が見つかるにつれて「これ以下の質のものは見ない」と選り好みが激しくなり、計算時間を節約します。

この**「自己学習機能」**こそが、単純なマルチスタート（ランダム探索）と比べて圧倒的に高速である理由です。

全体のまとめ：なぜGlobalSearchは効率的なのか？

通常の「マルチスタート（MultiStart）」手法が、用意した全ての点から馬鹿正直に計算を実行しようとするのに対し、GlobalSearchは以下の2つのフィルターを持っています。

1. 場所のフィルター: 「すでに見つけた解と同じ場所に行きそうな点は計算しない」
2. 値のフィルター: 「値が悪すぎて見込みのない点は計算しない」

これにより、計算コストのかかる fmincon（局所探索）の実行回数を大幅に減らしつつ、広い範囲から効率的に大域的最適解（グローバルミニマム）を探し出すことができます。