プログラミング:佐藤 尊樹

はじめに Edit

解が実数値で表現される最適化問題において,近年,注目される最適化法のひとつが差分進化(Differential Evolution, DE) *1*2です.ここでは簡単にDEを紹介します.

差分進化 (Differential Evolution) Edit

解は実数値ベクトル\( \bm{x}=\{x_1,x_2,\cdots,x_n\} \)で表します. 世代数\( t \)に対し,解集団\( \mathcal{P}_t=\{\bm{x}_{1,t},\bm{x}_{2,t},\cdots,\bm{x}_{N,t}\} \)をランダムに生成します. 各\( \bm{x}_{i,t} \)に対して,次式で変異ベクトルを算出します.

\[ \bm{v}_{i,t}=\bm{x}_{r_1,t}+F\cdot(\bm{x}_{r_2,t}-\bm{x}_{r_3,t}) \]

ここで,\( F \)はスケーリング係数,\( \bm{x}_{r_1,t} \)\( \bm{x}_{r_2,t} \)\( \bm{x}_{r_3,t} \)は,解集団からランダムに取り出した解です. 次に\( \bm{x}_{i,t} \)と変異ベクトル\( \bm{v}_{i,t} \)を次式のように交叉させることで,新しい解\( \bm{u}_{i,t} \)を生成します.これを各\( \bm{x}_{i,t} \)について繰り返します.

\[ u_{j,i,t+1}=\Biggl\{\array{v_{j,i,t} & \text{rand}[0,1) \le CR\text{ or } j=j_{rand}\\ x_{j,i,t} & \text{otherwise}}\text{ }(j=1,2,\cdots,n) \]

次に,解集団を更新します.各解\( \bm{x}_{i,t} \)と新しい解\( \bm{u}_{i,t} \)を比較し,目的関数値が良好な方を次世代の解集団に残します.

\[ \bm{x}_{i,t+1}=\Biggl\{\array{\bm{u}_{i,t} & \text{if } f(\bm{u}_{i,t})\le f(\bm{x}_{i,t})\\\bm{x}_{i,t} & \text{otherwise}} \]

上記を世代数\( t \)を計数しながら繰り返します.これはDEのひとつの方法で,rand/1/binと表します.

実験 Edit

関数最適化問題におけるDEの動作を紹介します.使用した方法は,前述のrand/1/binで,解集団サイズは50,世代数は250,スケーリング係数F=0.7,交叉率CR=0.9に設定しました.

Sphere関数 Edit

関数 Edit

\[ \text{Minimize } f(\bm{x}) = \sum_{i=1}^n x_i^2 \]
\[ -5.12 \leq x_i \leq 5.12 \]

変数空間のみ Edit

DE_Sphere_2d.gif

目的関数と変数空間 Edit

DE_Sphere.gif

Ackley関数 Edit

関数 Edit

\[ \text{Minimize } f(\bm{x}) = -20 \exp(-0.2 \sqrt{\frac{1}{n} \sum_{i=1}^n x_i^2}) - \exp(\frac{1}{n} \sum_{i=1}^n \cos(2\pi x_i)) + 20 + \exp(1) \]
\[ -32 \leq x_i \leq 32 \]

変数空間のみ Edit

DE_Ackley_2d.gif

目的関数と変数空間 Edit

DE_Ackley.gif

Three-hump関数 Edit

関数 Edit

\[ \text{Minimize } f(\bm{x}) = 2x_1^2-1.05x_1^4+\frac{x_1^6}{6}+x_1x_2+x_2^2 \]
\[ -2.0 \leq x_i \leq 2.0 \]

変数空間のみ Edit

DE_Three-hump_2d.gif

目的関数と変数空間 Edit

DE_Three-hump.gif

Easom関数 Edit

関数 Edit

\[ \text{Minimize } f(\bm{x}) = -\cos(x_1)\cos(x_2)\exp(-(x_1-\pi)^2-(x_2-\pi)^2) \]
\[ -5.0 \leq x_i \leq 5.0 \]

変数空間のみ Edit

DE_Easom_2d.gif

目的関数と変数空間 Edit

DE_Easom.gif

Griewank関数 Edit

関数 Edit

\[ \text{Minimize } f(\bm{x}) = 1 + \frac{1}{4000} \sum_{i=1}^n x^2_i - \prod_{i=1}^n \cos(\frac{x_i}{\sqrt{i}}) \]
\[ -5.0 \leq x_i \leq 5.0 \]

変数空間のみ Edit

DE_Griewank_2d.gif

目的関数と変数空間 Edit

DE_Griewank.gif

Michalewicz関数 Edit

関数 Edit

\[ \text{Minimize } f(\bm{x}) = -\sum_{i=1}^{n}\sin(x_i)\sin^{20}(\frac{ix_i^2}{\pi}) \]
\[ \pi \leq x_i \leq \pi \]

変数空間のみ Edit

DE_Michalewicz_2d.gif

目的関数と変数空間 Edit

DE_Michalewicz.gif

Rastrigin関数 Edit

関数 Edit

\[ \text{Minimize } f(\bm{x}) = 10n + \sum_{i=1}^n (x_i^2 -10\cos(2\pi x_i)) \]
\[ 5.12 \leq x_i \leq 5.12 \]

変数空間のみ Edit

DE_Rastrigin_2d.gif

目的関数と変数空間 Edit

DE_Rastrigin.gif

Rosenbrock関数 Edit

関数 Edit

\[ \text{Minimize } f(\bm{x}) = \sum_{i=1}^{n-1} (100(x_i^2 - x_{i+1})^2 + (1-x_i)^2) \]
\[ 5.0 \leq x_i \leq 5.0 \]

変数空間のみ Edit

DE_Rosenbrock_2d.gif

目的関数と変数空間 Edit

DE_Rosenbrock.gif

*1 R. Storn, K. Price, "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces," Journal of Global Optimization, Vol. 11, pp.341-–359, 1997.
*2 田邊 遼司, 串田 淳一, 畠中 利治, 関数最適化における進化計算, 計測と制御, 54 巻, 8 号, pp. 567--572, 2015
トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2018-11-05 (月) 23:45:06 (346d)