#author("2018-11-05T23:08:46+09:00","default:admin","admin")
#author("2018-11-05T23:45:06+09:00","default:admin","admin")
#mathjax(text-align: center)
RIGHT:プログラミング:佐藤 尊樹
*はじめに [#h828cc51]
解が実数値で表現される最適化問題において,近年,注目される最適化法のひとつが差分進化(Differential Evolution, DE)
((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.))((田邊 遼司, 串田 淳一, 畠中 利治, 関数最適化における進化計算, 計測と制御, 54 巻, 8 号, pp. 567--572, 2015))です.ここでは簡単にDEを紹介します.
*差分進化 (Differential Evolution) [#q214a852]

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

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

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

#mathjax(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))
#mathjax(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))

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


#mathjax(\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}})
#mathjax(\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}})

上記を世代数&mathjax{t};を計数しながら繰り返します.これはDEのひとつの方法で,rand/1/binと表します.
*実験 [#m5e702b0]
関数最適化問題におけるDEの動作を紹介します.使用した方法は,前述のrand/1/binで,解集団サイズは50,世代数は250,スケーリング係数F=0.7,交叉率CR=0.9に設定しました.
**Sphere関数 [#a215c6ef]
***関数 [#oeda5e74]
#mathjax(\text{Minimize } f(\bm{x}) = \sum_{i=1}^n x_i^2)
 
#mathjax(-5.12 \leq x_i \leq 5.12)
#div(start)
***変数空間のみ [#g2a5ba85]
#ref(DE_Sphere_2d.gif,center,zoom,320x0)
#div(end)
***目的関数と変数空間 [#i9317a39]
#ref(DE_Sphere.gif,center,zoom,320x0)
#div(clear)

**Ackley関数 [#a215c6ef]
***関数 [#z05a866a]
#mathjax(\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))
 
#mathjax(-32 \leq x_i \leq 32)
#div(start)
***変数空間のみ [#g2a5ba85]
#ref(DE_Ackley_2d.gif,center,zoom,320x0)
#div(end)
***目的関数と変数空間 [#i9317a39]
#ref(DE_Ackley.gif,center,zoom,320x0)
#div(clear)

**Three-hump関数 [#a215c6ef]
***関数 [#idbccc86]
#mathjax(\text{Minimize } f(\bm{x}) = 2x_1^2-1.05x_1^4+\frac{x_1^6}{6}+x_1x_2+x_2^2)
 
#mathjax(-2.0 \leq x_i \leq 2.0)
#div(start)
***変数空間のみ [#g2a5ba85]
#ref(DE_Three-hump_2d.gif,center,zoom,320x0)
#div(end)
***目的関数と変数空間 [#i9317a39]
#ref(DE_Three-hump.gif,center,zoom,320x0)
#div(clear)

**Easom関数 [#a215c6ef]
***関数 [#w27f090c]
#mathjax(\text{Minimize } f(\bm{x}) = -\cos(x_1)\cos(x_2)\exp(-(x_1-\pi)^2-(x_2-\pi)^2))
 
#mathjax(-5.0 \leq x_i \leq 5.0)
#div(start)
***変数空間のみ [#g2a5ba85]
#ref(DE_Easom_2d.gif,center,zoom,320x0)
#div(end)
***目的関数と変数空間 [#i9317a39]
#ref(DE_Easom.gif,center,zoom,320x0)
#div(clear)

**Griewank関数 [#a215c6ef]
***関数 [#f78bd645]
#mathjax(\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}}))
 
#mathjax(-5.0 \leq x_i \leq 5.0)
#div(start)
***変数空間のみ [#g2a5ba85]
#ref(DE_Griewank_2d.gif,center,zoom,320x0)
#div(end)
***目的関数と変数空間 [#i9317a39]
#ref(DE_Griewank.gif,center,zoom,320x0)
#div(clear)


**Michalewicz関数 [#a215c6ef]
***関数 [#p79c3aa8]
#mathjax(\text{Minimize } f(\bm{x}) = -\sum_{i=1}^{n}\sin(x_i)\sin^{20}(\frac{ix_i^2}{\pi}))
 
#mathjax(\pi \leq x_i \leq \pi)
#div(start)
***変数空間のみ [#g2a5ba85]
#ref(DE_Michalewicz_2d.gif,center,zoom,320x0)
#div(end)
***目的関数と変数空間 [#i9317a39]
#ref(DE_Michalewicz.gif,center,zoom,320x0)
#div(clear)


**Rastrigin関数 [#a215c6ef]
***関数 [#u0ef2c06]
#mathjax(\text{Minimize } f(\bm{x}) = 10n + \sum_{i=1}^n (x_i^2 -10\cos(2\pi x_i)))
 
#mathjax(5.12 \leq x_i \leq 5.12)
#div(start)
***変数空間のみ [#g2a5ba85]
#ref(DE_Rastrigin_2d.gif,center,zoom,320x0)
#div(end)
***目的関数と変数空間 [#i9317a39]
#ref(DE_Rastrigin.gif,center,zoom,320x0)
#div(clear)


**Rosenbrock関数 [#a215c6ef]
***関数 [#o3b8f9f6]
#mathjax(\text{Minimize } f(\bm{x}) = \sum_{i=1}^{n-1} (100(x_i^2 - x_{i+1})^2 + (1-x_i)^2))
 
#mathjax(5.0 \leq x_i \leq 5.0)
#div(start)
***変数空間のみ [#g2a5ba85]
#ref(DE_Rosenbrock_2d.gif,center,zoom,320x0)
#div(end)
***目的関数と変数空間 [#i9317a39]
#ref(DE_Rosenbrock.gif,center,zoom,320x0)
#div(clear)
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS