微分不要最適化とメタヒューリスティクス

概要

微分不要最適化 (Derivative-Free Optimization, DFO) は勾配情報を使わずに関数値だけで $\min f(x)$ を解く手法群。 勾配が存在しない・解析できない・評価が高コスト・ノイジーといった場面で必要となる。 本記事では決定論的な直接探索 (Nelder-Mead, パターン探索, DIRECT, BOBYQA) と 確率的なメタヒューリスティクス (SA, GA, PSO, DE, CMA-ES) を統一的に扱う。

sangi は optimization_nd.hpp でこれらを提供しており、 境界制約 $\mathbf{x} \in [l, u]$ を持つメタヒューリスティクスはバウンド付きシグネチャで呼び出す。

Nelder-Mead シンプレックス

Nelder and Mead (1965) によるシンプレックス変形法。 $n + 1$ 頂点のシンプレックス $\{x_0, x_1, \dots, x_n\}$ を 4 種類の幾何変形で反復更新する。

頂点を関数値で昇順ソート ($f(x_0) \leq \cdots \leq f(x_n)$) し、最悪点 $x_n$ を改善することを目指す。 重心 $\bar{x} = \frac{1}{n} \sum_{i=0}^{n-1} x_i$ を中心に以下の操作を行う:

操作定義条件
反射$x_r = \bar{x} + \alpha (\bar{x} - x_n)$$\alpha = 1$
拡大$x_e = \bar{x} + \gamma (x_r - \bar{x})$$\gamma = 2$, $x_r$ が最良なら
外側収縮$x_c = \bar{x} + \rho (x_r - \bar{x})$$\rho = 0.5$, $x_r$ が中位なら
内側収縮$x_c = \bar{x} - \rho (x_r - \bar{x})$$\rho = 0.5$, $x_r$ が最悪なら
全体縮小$x_i \leftarrow x_0 + \sigma (x_i - x_0)$$\sigma = 0.5$, 上記すべて失敗

収束判定

典型的な停止条件は関数値スプレッド $\max_i f(x_i) - f(x_0) < \varepsilon_f$ かつ シンプレックス直径 $\max_i \|x_i - x_0\| < \varepsilon_x$ の二重判定。 どちらか一方では「停滞」を検出できないため、両方を要求する。

制約と注意点

  • $n \leq 10$ では実用的に強力。$n > 20$ では関数評価あたりの情報量が落ち、停滞しやすい。
  • 悪条件問題で全体縮小に陥ると進まなくなる現象が知られ、リスタート (シンプレックスを再初期化) が推奨される。
  • 収束保証は厳密には存在しない (Nelder-Mead は反例が知られている: McKinnon 1998)。

sangi の nelderMeadMinimize はこの実装で、 NelderMeadOptions で $\alpha, \gamma, \rho, \sigma$ をカスタマイズできる。

関連記事: Nelder-Mead 法

DIRECT と BOBYQA

DIRECT (DIvide a RECTangle)

Jones, Perttunen, Stuckle (1993) の決定論的大域最適化。 探索領域を超直方体に分割し、各超直方体の中心で関数値を計算する。 Lipschitz 定数を事前に与えず、「潜在的に最適な」超直方体を再帰的に分割していく。

有限の関数評価回数で大域最適に近づく稀な決定論的アルゴリズムだが、次元の呪いで $n > 10$ 程度から効率が急速に落ちる。 低次元の高コスト・ブラックボックス問題に向く。

BOBYQA (Bound Optimization BY Quadratic Approximation)

Powell (2009) による微分不要の局所最適化。$\binom{n+1}{2} + n + 1$ 点の二次補間モデルを構築し、 信頼領域法でモデルを最小化する。境界制約に対応し、関数評価がボトルネックの工学設計でよく使われる。

同系統に COBYLA (線形補間, 制約付き)、NEWUOA (BOBYQA の無制約版)、UOBYQA (二次補間, 旧版) がある。 sangi 現バージョンでは BOBYQA / COBYLA は未提供 (ロードマップ項目)。

Powell 系のいま

Bayesian Optimization (Gaussian Process surrogate + acquisition function) が黒箱最適化の主流となった現在も、 Powell 系の二次補間アルゴリズムは「高コスト関数評価で勾配なし、$n \leq 30$」という条件で実用的に強い。

焼きなまし (SA)

Kirkpatrick, Gelatt, Vecchi (1983) による確率的大域最適化。 固体の焼きなまし過程に着想を得て、悪化提案を温度 $T_k$ に応じた確率で受理する Metropolis 判定を行う。

$$P(\text{accept}) = \begin{cases} 1 & f(x') \leq f(x) \\ \exp\!\bigl(-(f(x') - f(x))/T_k\bigr) & f(x') > f(x) \end{cases}$$

冷却スケジュール

  • 指数冷却: $T_{k+1} = r \cdot T_k$, $r \in [0.9, 0.999]$. 実用的に多用。
  • 対数冷却: $T_k = T_0 / \log(k + 2)$. 理論的に大域最適収束を保証するが極端に遅い。
  • 適応的冷却: 受理率に応じて $r$ を動的に変える。

sangi の simulatedAnnealingMinimize は指数冷却 (デフォルト $r = 0.995$) と 範囲比 $\sigma_\text{near}$ のガウス近傍を採用する。neighbor_scale = 0.1 は探索範囲の 10% を標準偏差とする。

関連記事: 焼きなまし法

遺伝的アルゴリズム (GA)

Holland (1975) の進化計算枠組み。個体集団 (population) を選択・交叉・突然変異・エリート保存で世代更新する。

  • 選択: トーナメント選択 (集団からランダム $k$ 個取り最良を選ぶ) が標準。
  • 交叉: 連続変数では BLX-$\alpha$ (Blend Crossover) や SBX (Simulated Binary Crossover) を使う。 BLX-$\alpha$: 親 $p_1, p_2$ ($p_1 \leq p_2$) から $[p_1 - \alpha d, p_2 + \alpha d]$ ($d = p_2 - p_1$) で一様サンプル。
  • 突然変異: ガウス変異 $x' = x + \mathcal{N}(0, \sigma^2)$ または多項式変異。
  • エリート保存: 最良 $k$ 個体を次世代に直接コピーし、進化の後退を防ぐ。

sangi の geneticAlgorithmMinimize はトーナメント選択 + BLX-$0.5$ 交叉 + ガウス変異 + エリート保存 (デフォルト 2 個体) の標準的構成。 汎用性は高いが、CMA-ES や DE と比べ離散・組合せ最適化以外では性能でやや劣る。

関連記事: 遺伝的アルゴリズム

粒子群最適化 (PSO)

Kennedy and Eberhart (1995) による群知能アルゴリズム。各粒子 $i$ が位置 $x_i$ と速度 $v_i$ を持ち、 自己最良 $p_i$ と群全体最良 $g$ に向かって速度を更新する。

$$v_i \leftarrow w \, v_i + c_1 r_1 (p_i - x_i) + c_2 r_2 (g - x_i), \qquad x_i \leftarrow x_i + v_i$$

$w$ は慣性 (典型 0.7)、$c_1, c_2$ は加速係数 (典型 1.5–2.0)、$r_1, r_2 \in [0, 1]$ は乱数。 実装が極めて単純で並列化しやすい。局所最適への陥りやすさはハイブリッド化で軽減する。

sangi 現バージョンには PSO 単体は未提供 (DE / CMA-ES / jSO で代替可能)。

関連記事: 群知能 (PSO 含む)

差分進化 (DE, jSO)

DE (Storn-Price 1997)

DE/rand/1/bin は次の単純な差分変異で新候補を生成する:

$$v_i = x_{r_0} + F (x_{r_1} - x_{r_2}), \quad r_0, r_1, r_2 \text{ 互いに異なる}$$

続いて二項交叉で $u_i$ を作り、$f(u_i) < f(x_i)$ なら $x_i \leftarrow u_i$ で世代を進める。 典型パラメータ $F = 0.8$, $CR = 0.9$。 計算オーバーヘッドが小さく、連続変数の大域最適化で強力。

sangi の differentialEvolutionMinimize はこの DE/rand/1/bin。

L-SHADE と jSO

SHADE (Tanabe-Fukunaga 2013) は成功した $(F, CR)$ の履歴を保持し、適応的にサンプルする。 L-SHADE は線形人口サイズ縮小を加え、CEC 2014 ベンチマーク優勝。 jSO (Brest et al. 2017) は L-SHADE に jSO 固有の $F/CR$ 初期化改良と current-to-pbest/1 変異を加え、CEC 2017 ベンチマークで上位入賞。

sangi の jsoMinimize は jSO の実装。 メタヒューリスティクスで最も信頼性が高い手法の一つで、CMA-ES と並んでデフォルト候補となる。

CMA-ES

Hansen and Ostermeier (2001) の共分散行列適応進化戦略。 多変量正規分布 $\mathcal{N}(\mu, \sigma^2 C)$ から $\lambda$ 個サンプリングし、上位 $\mu_w$ 個から $\mu, \sigma, C$ を更新する。

更新式の概略

  1. $\lambda$ 個サンプル: $x_i \sim \mathcal{N}(m_k, \sigma_k^2 C_k)$
  2. 関数値で昇順ソートし、上位 $\mu_w$ 個で重み付き平均: $m_{k+1} = \sum_{i=1}^{\mu_w} w_i x_{i:\lambda}$
  3. 進化経路 $p_\sigma, p_c$ で過去の進化方向を累積
  4. 共分散行列 $C_{k+1}$ を rank-1 + rank-$\mu_w$ 更新
  5. ステップサイズ $\sigma_{k+1}$ を $p_\sigma$ のノルムから cumulative step-size adaptation (CSA) で更新

共分散 $C$ が目的関数の局所 Hessian の逆行列に近づく性質を持つため、CMA-ES は微分不要でありながら準ニュートン的に振る舞う。 ill-conditioned, non-separable な目的関数に強い。 典型 $\lambda = 4 + \lfloor 3 \ln n \rfloor$、中規模 ($n \leq 数百$) で実用的。

sangi の cmaesMinimize は標準 (μ/μ_w, λ)-CMA-ES。condition_limit = 10^{14} で $C$ の発散を防ぐ。

関連記事: 進化戦略 (CMA-ES 含む)

ノイズと非滑らかな目的関数

関数評価がノイジーな場面 (Monte Carlo シミュレーション、実機計測、確率的シミュレータ) では追加の対策が要る。

  • 再評価: 同じ $x$ で複数回評価し平均を取る。サンプル数を世代とともに増やす方式が一般的。
  • ノイズ耐性ある手法: CMA-ES は集団ベースで暗黙のノイズ平均化が効く。Nelder-Mead はノイズに弱い。
  • 反復回数の引き伸ばし: 収束判定の許容誤差をノイズレベル以上に設定する。

非滑らか (区分線形、不連続、$\max/\min$ を含む) な目的関数では:

  • MADS / GPS は理論的収束保証あり (Clarke 停留点)。
  • Nelder-Mead は実用上動くが収束は保証されない。
  • メタヒューリスティクス (SA, GA, DE, CMA-ES) は連続性を仮定せず動作するが、保証は確率的。

勾配不連続が既知の場合、滑らかな近似 ($\max(0, x) \to \log(1 + e^x)$ 等) で勾配法を使う方が速いことも多い。

用途別ガイド

状況推奨手法 (sangi)
$n \leq 10$、滑らか、関数評価安いnelderMeadMinimize
$n \leq 30$、関数評価安いhookeJeevesMinimize
$n \leq 数百$、悪条件、関数評価中程度cmaesMinimize
$n \leq 数百$、ベンチマーク勝負jsoMinimize
連続変数の大域探索、汎用differentialEvolutionMinimize
離散・組合せ要素ありgeneticAlgorithmMinimize
局所最適脱出が必要simulatedAnnealingMinimize
関数評価が非常に高コスト ($> $ 数秒/回)Bayesian Optimization (外部) または BOBYQA (将来追加予定)

参考文献

  • Conn, A. R., Scheinberg, K., and Vicente, L. N. (2009). Introduction to Derivative-Free Optimization. SIAM.
  • Nelder, J. A. and Mead, R. (1965). "A Simplex Method for Function Minimization". Computer Journal, 7, 308–313.
  • Hansen, N. and Ostermeier, A. (2001). "Completely Derandomized Self-Adaptation in Evolution Strategies". Evolutionary Computation, 9, 159–195.
  • Storn, R. and Price, K. (1997). "Differential Evolution — A Simple and Efficient Heuristic for global Optimization over Continuous Spaces". J. Global Optimization, 11, 341–359.
  • Brest, J., Maučec, M. S., and Bošković, B. (2017). "Single objective real-parameter optimization: Algorithm jSO". CEC 2017.
  • Audet, C. and Dennis, J. E. (2006). "Mesh Adaptive Direct Search Algorithms for Constrained Optimization". SIAM J. Optim., 17, 188–217.