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

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

使い方を知りたい方は先にこちらをどうぞ。

この記事はGlobal Optimization ToolboxのGlobalSearchについて解説します。

中身は**「スキャッターサーチ（Scatter Search）」という手法と、ユーザーが指定したローカルソルバー（通常はfmincon）を組み合わせた、非常に論理的なOQNLP（OptQuest Non-Linear Programming）**と呼ばれるアルゴリズムに基づいています。

以下に、GlobalSearchがどのようにして効率的に大域的最小値を探し出しているのか、その内部ロジックを詳細に解説します。

---

1. GlobalSearchの基本戦略：効率性重視

GlobalSearchの最大の特徴は、**「手当たり次第に計算するのではなく、見込みのある点だけを選んでfminconを走らせる」**という点です。

単純なマルチスタート（MultiStart）は、ランダムな初期点すべてでfminconを実行するため計算コストが膨大になりますが、GlobalSearchはこれを回避するためにフィルタリングを行います。

2. 詳細な実行プロセス（アルゴリズムの流れ）

GlobalSearchは主に以下のステージを経て解を探索します。

ステップ1：初期点の散布（Scatter Search）

まず、探索空間（変数の上下限の範囲内）に多数の**トライアルポイント（Trial Points）**を生成します。

• デフォルトでは数千〜1万点レベルで生成されることもあります。
• これらはランダムではなく、空間をまんべんなく埋めるような数列（分散再帰数列など）を使って配置されます。

ステップ2：スコアリングとフィルタリング

生成された多数の点すべてについて、目的関数の値（および制約違反）を計算します（関数評価）。
ここで、**「スコア関数（Score Function）」**を用いて、点を以下の2種類に選別します。

1. 有望な点（Promising Points）： 目的関数の値が低く、かつ制約を満たしている点。
2. 除外される点： 目的関数の値が悪い、または既存の解の近くにある点。

ステップ3：ステージ1 ローカルサーチ

まず、最も有望な1点を選び、そこからfmincon（局所探索）を実行します。これにより、最初の「局所解（Local Minima）」が見つかります。

ステップ4：吸引領域（Basin of Attraction）の推定

ここがGlobalSearchの賢いところです。
ある局所解が見つかると、アルゴリズムはその解へ収束するであろう範囲、すなわち**「吸引領域（Basin of Attraction）」**の半径を推定します。

• 判定ロジック：
  もし次のトライアルポイントが、すでに発見された局所解の「吸引領域」の中にあると判定された場合、そこからfminconを実行しても同じ解にたどり着くだけなので、計算をスキップします。

ステップ5：メインループ（反復探索）

残りのトライアルポイント候補の中から、以下の条件を満たすものを選んでfminconを実行します。

1. 品質が良い： 目的関数の値が十分に小さい。
2. 距離が遠い： すでに発見された局所解や、過去の探索点から十分離れている（未知の領域にある）。

これを繰り返し、新しい局所解が見つかるたびに吸引領域情報を更新し、無駄な探索を省きながら大域的最小値（Global Minimum）の候補リストを作成します。

---

3. イメージでの理解：山登り（下り）の例え

あなたが真っ暗な山脈の中で、一番低い谷底（大域的最小値）を探しているとします。

• fmincon単体： 今いる場所から傾斜に従って下るだけ。一番近い谷底には行けるが、隣のもっと深い谷には気づかない。
• MultiStart： 100人の登山家をヘリコプターでランダムに落とし、全員に「下れ」と命じる。確実だが、同じ谷に50人集まったりして無駄が多い。
• GlobalSearch：
  1. まずドローンで山脈全体を撮影し、1000箇所の標高を測る（トライアルポイント）。
  2. 「あそこは低そうだ」という場所をいくつかピックアップする。
  3. まず一番低そうな場所に登山家を一人送り込む。
  4. その登山家が降りた谷（吸引領域）の広さを記録する。
  5. 次の登山家を送る際、「さっきの谷に繋がりそうな場所」は無視し、「まだ誰も降りていない、かつ低そうな場所」を選んで送り込む。

4. 専門的なアドバイス

以下のような状況であればGlobalSearchは非常に有効です。

• fmincon 1回の計算コストが高い場合:
  GlobalSearchはfminconを呼ぶ回数を賢く減らすため、MultiStartよりも計算時間を短縮できる可能性が高いです。
• パラメータの初期値依存性が強い場合:
  非線形性が強く、局所解（Local Minima）が無数にある場合、単発のfminconでは真の解にたどり着けませんが、GlobalSearchならそのリスクを劇的に下げられます。

注意点：
並列計算（Parallel Computing）を行いたい場合は、GlobalSearchではなくMultiStartを使用してください。GlobalSearchのアルゴリズムは逐次的（前の結果を見て次の点を決める）であるため、並列化（parfor）に対応していません。

続きもよろしくお願いします。