Differential Evolution — 全域確率的最適化手法
- 提唱者
- Rainer Storn & Kenneth Price
- 年
- 1997
- 種類
- Population-based stochastic metaheuristic
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
Differential Evolution (DE) は、1997年にRainer StornとKenneth Priceによって導入された、連続パラメータ空間向けに設計された集団ベースの確率的最適化アルゴリズムである。既存の集団メンバー間のベクトル差を組み合わせて候補解を生成するため、探索ランドスケープが非凸、多峰性、または勾配ベースの手法に適さない場合に、遺伝的アルゴリズムや粒子群最適化に対する強力でパラメータ効率の良い代替手段となる。
手法の背後にある直感
未知の風景に散らばった探検家たちが最も低い谷を探している状況を想像してほしい。各ステップで、各探検家はランダムに選ばれた3人の同僚を観察し、2人の間の差にステップサイズ係数を掛けたものによって示される方向に移動し、新しい位置と元の位置のどちらがより良い地形であるかを決定する。多くのラウンドを経て、グループ全体は協力して見つけた最も深い谷の周りに徐々に集まっていく。Differential Evolutionはまさにこの方法で動作する。「差」は2つのベクトル間の差であり、探索方向として機能し、スケール係数Fが各ステップの大きさを制御する。
歴史学
Differential Evolutionは、1997年のJournal of Global Optimization誌におけるRainer StornとKenneth Priceによる画期的な論文で導入された。このアルゴリズムは、Priceによる以前の遺伝的焼きなましに関する研究と、Stornによる浮動小数点交叉の実験から発展した。現在DE/best/1/binと呼ばれる元のバリアントは、標準ベンチマークにおいて、当時の進化戦略や遺伝的アルゴリズムと同等かそれ以上の性能を示した。Das、Mullick、Suganthan(2016)による包括的なレビューでは、20年以上にわたるバリアント、適応スキーム、および応用がカタログ化され、DEはメタヒューリスティクスの文献における基礎的な手法の1つとしての地位を確立した。
使うべき場面
Differential Evolutionは、目的関数が連続的で、微分不可能または多峰性である可能性があり、すべてのパラメータの探索範囲が事前にわかっている場合に適切である。勾配情報や正規性の仮定を必要としないため、工学設計、ハイパーパラメータチューニング、シミュレーションモデルのキャリブレーション、およびあらゆるブラックボックス最適化タスクに適している。パラメータ数の約10倍の集団サイズが一般的な出発点である。DEは純粋に離散的または組み合わせ的な問題には適用すべきではなく、信頼性の高い収束には少なくとも1,000回の反復が必要である。もし関数評価の予算が非常にタイトな場合、ベイズ最適化がよりサンプル効率の良い代替手段となる。
限界と注意点
- 十分な反復回数がない場合、収束が遅くなる可能性がある。1,000世代未満では、しばしば最適でない結果が得られる。
- 性能はFとCRの選択に敏感である。パラメータ設定が不適切だと、早期収束や進行の遅延につながる可能性がある。
- 純粋に離散的または組み合わせ的な探索空間には設計されていない。離散的な拡張は存在するが、一般的ではない。
- 各反復で目的関数をNP回評価する必要があり、各評価が計算コストが高い場合にはコストがかかる。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 勾配情報を必要としない — 微分不可能でノイズの多いものを含む、あらゆるブラックボックス目的関数で機能する。
- 探索能力と比較して制御パラメータ(F、CR、NP)が非常に少なく、設定が比較的容易である。
- 勾配ベースの最適化手法が局所最適解に収束する多峰性ランドスケープを自然に処理できる。
- 集団評価は独立しており、容易に並列化できるため、マルチコアシステムでの実時間を短縮できる。
- 多くのベンチマークで遺伝的アルゴリズムや粒子群最適化と同等以上の性能を発揮し、より単純な更新ルールを使用する。
応用
- 目的関数が非解析的なシミュレーションモデルやエージェントベースモデルのキャリブレーション。
- 探索空間が連続的で有界な場合の、機械学習パイプラインのハイパーパラメータ最適化。
- アンテナ設計、構造最適化、コントローラチューニングなどの工学設計問題。
- 工学および自然科学におけるニューラルネットワークのトレーニングや非線形モデルのフィッティング。
- 金融時系列モデルにおけるポートフォリオウェイト最適化およびパラメータ推定。
使い方
使い方
NP個の候補解ベクトルからなる集団は、各パラメータについて定義済みの探索範囲内で一様にランダムに抽出される。探索範囲は、アルゴリズムが開始する前にユーザーが指定する必要がある。DEは問題から範囲を推測することはできない。良い初期集団は、アルゴリズムが出発時に有望な領域を見逃さないように、実現可能な空間全体をカバーする。
集団内の各ターゲットベクトルについて、3つの異なるベクトルがランダムに選択される。変異ベクトルは、3番目のベクトルに、2つのベクトルの差にスケール係数を掛けたものを加えることによって形成される: v = x_r1 + F*(x_r2 - x_r3)。ここでFはスケール係数(通常0.4–1.0)である。この差ベースのステップが、DEを他の進化計算アルゴリズムと区別し、勾配計算を必要とせずに自己適応的な方向情報を提供する。
トライアルベクトルは、変異ベクトルと元のターゲットベクトルを要素ごとに混合することによって構築される。各要素は、確率CR(交叉率、通常0.5–1.0)で変異ベクトルから取得され、それ以外の場合はターゲットベクトルから取得される。少なくとも1つの要素は常に変異ベクトルから取得される。このステップは、探索と活用のバランスを制御する。高いCRは変異ベクトルを優先し、低いCRは現在の解のより多くの部分を保持する。
トライアルベクトルは目的関数で評価され、ターゲットベクトルと比較される。トライアルが同等またはそれ以上の目的値に達した場合、次の世代でターゲットを置き換える。そうでなければ、ターゲットは変更されずに保持される。この貪欲な1対1選択は、集団の劣化を防ぎ、見つかった最良解の単調な改善を保証する。
突然変異、交叉、選択は、十分な世代数(一般に1,000以上)繰り返されるか、収束基準が満たされるまで行われる。例えば、最良目的値の変化が許容誤差を下回るか、最大反復回数に達した場合である。最終集団の最良ベクトルがアルゴリズムの解となる。
よくある落とし穴
- DEを反復回数が少ない(約1,000回未満)状態で実行することは最も一般的な間違いである。アルゴリズムは収束するのに十分な世代を経過しておらず、結果は予備的なものとして扱うべきである。評価予算がタイトな場合は、ベイズ最適化に切り替える。
- スケール係数Fを低く設定しすぎると多様性が早期に失われ、高く設定しすぎると収束が妨げられる。Fは[0.4, 1.0]の範囲で開始し、経験的に調整する。
- 探索範囲の省略または誤った指定は重大なエラーである。DEは集団の初期化に範囲を使用し、範囲が狭すぎるか存在しない場合、無意味な結果を生じる。
- 多峰性ランドスケープでは、DEを一発勝負で実行するのは危険である。異なるランダムシードから複数の独立した試行を実行し、実行全体で見つかった最良の解を報告する。
よくある質問
スケール係数Fと交叉率CRをどのように選択しますか?
最も広く引用されているデフォルト値は、DE/best/1/bin戦略の場合、F = 0.8およびCR = 0.9である。実際には、Fはステップサイズを制御し(通常0.4–1.0の値)、CRは変異がターゲットをどれだけ置き換えるかを制御する。集団が速すぎる収束する場合、Fを上げるかCRを下げる。適応型DEバリアント(jDE、JADE)は、実行中にこれらのパラメータを自動的に調整するため、手動チューニングが実用的でない場合には合理的な選択肢となる。
いくつの世代が必要ですか?
経験則として、少なくとも1,000世代が推奨される。高次元の問題(多くのパラメータ)や複雑なランドスケープでは、より多くの反復が必要になる場合がある。最良解の目的値が世代ごとにどのように変化するかを監視する。もし数百回の反復で変化がなければ、DEは収束したか、あるいは停滞した可能性が高い。停滞した場合は、新しいランダムシードで再実行することが推奨される。
DEは遺伝的アルゴリズムや粒子群最適化と比較してどうですか?
いずれも連続最適化のための集団ベースのメタヒューリスティクスである。DEは通常、GAよりも制御パラメータが少なく、PSOと比較してより単純で決定論的な更新ルールを持つ。多くの標準ベンチマークでは、DEは両者と同等かそれ以上の性能を発揮するが、性能は問題に依存する。選択は、普遍的なランキングというよりも、慣れや利用可能な実装に依存することが多い。
DEは整数またはカテゴリカルパラメータを扱えますか?
DEは連続空間向けに設計されている。整数パラメータは、各更新後に連続解を最も近い整数に丸めることで対応できるが、これは近似である。スケジューリングやルーティングのような純粋にカテゴリカルまたは組み合わせ的な問題には、蟻コロニー最適化やタブーサーチのような離散空間向けに設計された手法の方が適している。
関連する手法
参考文献
Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.
DOI 文献を開くコピーしました。Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.
DOI 文献を開くコピーしました。