プログラミング：佐藤 尊樹
はじめに † 
解が実数値で表現される最適化問題において，近年，注目される最適化法のひとつが差分進化(Differential Evolution, DE) *1*2です．ここでは簡単にDEを紹介します．
差分進化 (Differential Evolution) †
解は実数値ベクトル\( \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と表します．
実験 †
関数最適化問題におけるDEの動作を紹介します．使用した方法は，前述のrand/1/binで，解集団サイズは50，世代数は250，スケーリング係数F＝0.7，交叉率CR＝0.9に設定しました．
Sphere関数 †
関数 †
\[ \text{Minimize } f(\bm{x}) = \sum_{i=1}^n x_i^2 \]
\[ -5.12 \leq x_i \leq 5.12 \]
変数空間のみ †
目的関数と変数空間 †
Ackley関数 †
関数 †
\[ \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 \]
変数空間のみ †
目的関数と変数空間 †
Three-hump関数 †
関数 †
\[ \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 \]
変数空間のみ †
目的関数と変数空間 †
Easom関数 †
関数 †
\[ \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 \]
変数空間のみ †
目的関数と変数空間 †
Griewank関数 †
関数 †
\[ \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 \]
変数空間のみ †
目的関数と変数空間 †
Michalewicz関数 †
関数 †
\[ \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 \]
変数空間のみ †
目的関数と変数空間 †
Rastrigin関数 †
関数 †
\[ \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 \]
変数空間のみ †
目的関数と変数空間 †
Rosenbrock関数 †
関数 †
\[ \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 \]
変数空間のみ †
目的関数と変数空間 †
*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
添付ファイル: 
DE_Three-hump_2d.gif 107件
[詳細]
DE_Three-hump.gif 128件
[詳細]
DE_Sphere_2d.gif 153件
[詳細]
DE_Sphere.gif 191件
[詳細]
DE_Rosenbrock_2d.gif 81件
[詳細]
DE_Rosenbrock.gif 96件
[詳細]
DE_Rastrigin_2d.gif 106件
[詳細]
DE_Rastrigin.gif 108件
[詳細]
DE_Michalewicz_2d.gif 83件
[詳細]
DE_Michalewicz.gif 97件
[詳細]
DE_Griewank_2d.gif 100件
[詳細]
DE_Griewank.gif 95件
[詳細]
DE_Easom_2d.gif 98件
[詳細]
DE_Easom.gif 121件
[詳細]
DE_Ackley_2d.gif 112件
[詳細]
DE_Ackley.gif 213件
[詳細]
DE_Three-hump_2d.gif 107件
[詳細]
DE_Three-hump.gif 128件
[詳細]
DE_Sphere_2d.gif 153件
[詳細]
DE_Sphere.gif 191件
[詳細]
DE_Rosenbrock_2d.gif 81件
[詳細]
DE_Rosenbrock.gif 96件
[詳細]
DE_Rastrigin_2d.gif 106件
[詳細]
DE_Rastrigin.gif 108件
[詳細]
DE_Michalewicz_2d.gif 83件
[詳細]
DE_Michalewicz.gif 97件
[詳細]
DE_Griewank_2d.gif 100件
[詳細]
DE_Griewank.gif 95件
[詳細]
DE_Easom_2d.gif 98件
[詳細]
DE_Easom.gif 121件
[詳細]
DE_Ackley_2d.gif 112件
[詳細]
DE_Ackley.gif 213件
[詳細]
Last-modified: 2018-11-05 (月) 23:45:06 (346d)