Title
領域適応型Differential Evolutionの提案
Author(s)
小貫, 涼介; 北山, 哲士; 山崎, 光悦; 荒川, 雅生
Citation
日本機械学会論文集. C編 = Transactions of the Japan society of
mechanical engineers. C, 79(798): 429-441
Issue Date
2013
Type
Journal Article
Text version
author
URL
http://hdl.handle.net/2297/34641
Right
©2013 The Japan Society of Mechanical Engineers.
*KURAに登録されているコンテンツの著作権は,執筆者,出版社(学協会)などが有します。
*KURAに登録されているコンテンツの利用については,著作権法に規定されている私的使用や引用などの範囲内で行ってください。
*著作権法に規定されている私的使用や引用などの範囲を超える利用を行う場合には,著作権者の許諾を得てください。ただし,著作権者
から著作権等管理事業者(学術著作権協会,日本著作出版権管理システムなど)に権利委託されているコンテンツの利用手続については
,各著作権等管理事業者に確認してください。
http://dspace.lib.kanazawa-u.ac.jp/dspace/
領域適応型 Differential Evolution の提案 *
小貫涼介 *1,北山哲士 *2,山崎光悦 *3,荒川雅生 *4
Proposal of Adaptive Range Differential Evolution
Ryosuke ONUKI*1, Satoshi KITAYAMA, Koetsu YAMAZAKI and Masao ARAKAWA
*1
Graduate School of Natural & Science Technology, Kanazawa University,
Kakuma-machi, Kanazawa, 920-1192 Japan
This paper proposes a new method called Adaptive Range Differential Evolution (ARDE). The basic idea can be
obtained from the Adaptive Range Particle Swarm Optimization (ARPSO). In the ARDE, the active search domain
range consists of the mean and the standard deviation of each design variable. Also the best position is included in this
search range. Therefore, the active search domain range is newly defined by utilizing the mean and the standard
deviation of each design variable, and the best position. The detailed procedure of the new active search domain range
is described in this paper. To keep the best position for the new active search domain range will lead to the wide search
range. Of course, the newly active search domain range will shrink through the search iteration. As the result, a highly
accurate global minimum can be found. The effectiveness and validity of the ARDE are examined through typical
benchmark problems. It could be found through benchmark problems that the ARDE can find a global minimum with
the small number of function evaluations in comparison with basic Differential Evolution.
Key Words : Global Optimization, Adaptive Range Differential Evolution, Optimal Design, System Engineering,
Engineering Optimization
1. 緒
言
Differential Evolution (DE)は連続型多峰性関数の大域的最適解を見つけるために,1995 年に Storn と Price によっ
て提案された関数の感度(勾配)を利用せず大域的最適解を求める多点同時探索法である (1,2).同年に Particle
Swarm Optimization (PSO)も提案されており (3),
遺伝的アルゴリズム(GA)や Ant Colony Optimization (ACO)と同様,
進化計算と称される最適化手法に分類される.PSO は p-best と g-best の線形結合で新しい探索点を生成するのに
対し,DE は 2 章で述べるようにランダムに 3 つの探索点を選び,突然変異や交叉といった操作を通じて,新し
い探索点を生成する.PSO は勾配法との類似構造を持っていたり,
次の探索点を生成する近傍が明確であること (4),
また力学系と見なすことで,速度の更新式のパラメータ設定範囲を絞り込むなどの研究が盛んに行われている (5).
一方で DE は,アルゴリズム内に用いられるパラメータが探索性能に与える影響についての研究が行われている
が (6,7),最適化手法としての位置づけが必ずしも明確になっておらず,PSO ほど活発に研究がされているとは言
い難い.筆者らは DE の探索性能の高さに注目し,最適化手法としての位置づけ,特に勾配法や PSO などとの類
似性について研究を行ったり (8),離散変数問題へ適用するなどの研究を行っている (9).また,スケジューリング
問題へ適用する研究や (10,11),安定性解析を行うことで収束性を論じる研究もある (12).
一般に進化計算と称される多点同時探索型最適化手法では,はじめに探索領域を固定して大域的最適解の探索
*
原稿受付
学生員,金沢大学大学院自然科学研究科(〒920-1192 石川県金沢市角間町)
.
*2
正員,金沢大学理工研究域.
*3
正員,フェロー,金沢大学理工研究域.
*4
正員,香川大学工学部(〒761-0396 高松市林町 2217-20)
.
E-mail: [email protected]
*1
を行うため,初期探索領域の設定は極めて重要である.筆者らは探索点のばらつき状況に応じて探索領域を更新
する領域適応型 PSO(Adaptive Range PSO: ARPSO)を提案し,数値計算を通じ,その有効性を検討した (13).ARPSO
では,探索点がもつ各設計変数の平均値と標準偏差,g-best を利用し,正規分布を基調とした有効探索領域と称
される探索領域を生成する.探索点がばらついていれば有効探索領域は拡大し,一方で探索点の集中化が起きれ
ば有効探索領域は縮小する.これらを繰り返すことで,最終的に精度の高い大域的最適解を得る方法であった.
この手法の中では,最良値の保存という操作を行うことで常に g-best を有効探索領域内に残す操作を行う.そ
のため,正規分布の形を強制的に変化させながら探索を続けるため,どこか不自然さを含むものであった.最良
点(g-best)が重要な意味を持つのであれば,強制的に正規分布の形を変形するのではなく,有効探索領域に用い
る正規分布の形を保持したまま有効探索領域を生成するほうが望ましい.また,PSO では探索点が常に g-best へ
向かうという性質があり,探索点が g-best へ向かう過程で目的関数値を改善する点が g-best に置き換わるため,
内挿領域を集中探索している方法と捉えることができる.一方,DE では,3 つの探索点をランダムに選択するが,
2 つの探索点が探索方向ベクトルを生成するため (8),PSO のように常に内挿領域に探索方向ベクトルが向くので
はなく,場合によっては外挿領域へ向かうこともあり,その結果,未知探索領域の探索を行うことになるので大
域的最適解も見つけることが期待できる.このようなことを考えれば,ARPSO のように,ある意味で強引に正規
分布の形を崩すのではなく,正規分布の形を維持するような有効探索領域の設定を行うことが自然であろう.そ
のためには,最良点の各設計変数を中心とした有効探索領域と,探索点の各設計変数の平均値を中心とした有効
探索領域をそれぞれ設定し,それらを合成した領域を有効探索領域とすればよい.また ARPSO で提案された探
索領域では,領域を強制的に縮小させるパラメータが導入されている.一般に最適化問題の大域的最適解は未知
であるため,有効探索領域を強制的に縮小すると,場合によっては初期収束により局所的最適解の発見に留まる
ことも考えられる.
上述のような ARPSO の不自然さやパラメータ設定の問題を踏まえ,本論文では,探索領域を探索状況に応じ
て適応的に変化させる領域適応型 Differential Evolution (Adaptive Range Differential Evolution: ARDE)を提案する.
ARDE で導入する有効探索領域は,3 章で述べるように,各設計変数の平均と標準偏差,そして最良点を利用し
て決定される.これにより,ARPSO で導入していた最良点の保存といった不自然さが解消される.単に領域の取
り方を変更しただけであり,他は ARPSO と同じではないかと思われるかもしれないが,PSO の基本的思想は,
既に述べたように力学系に基づく内挿領域の集中探索であり,一方で DE では,ランダム性を基調とした外挿領
域の探索も可能な多点同時探索法である.これら両者を結びつけ,さらに ARPSO で不自然と考えられている正
規分布の強制変化をなくし,またパラメータによる強制的な有効探索領域の縮小をなくし,外挿領域への探索を
期待した方法が ARDE である.代表的な計算例を通じて,ARDE の有効性を検討する.
2. Differential Evolution
DE では様々なモデルが提唱されているが,本論文では最も基本的な DE/1/rand/bin を対象とする.DE では,
DE/X/Y/Z と表記し,X は基底ベクトルの数,Y は親となる探索点の選択方法,Z は交叉方法をそれぞれ意味して
いる.本論文で対象とする DE/1/rand/bin とは,基底ベクトルの数が 1 で,親となる探索点をランダムに選択し,
交叉方法は一様(Binomial)交叉を用いるということを意味している.
2・1 基本アルゴリズム
k 回目の探索における d 番目の探索点を xdk と表記し,n を設計変数の数とする.
(STEP1) 探索点数 dmaxと最大探索回数 kmax を設定.初期探索集団をランダムに生成.突然変異確率 F ,
交叉確率 Cr を設定.探索回数を k = 1 とする.
(STEP2) 全探索点に対し,以下の操作を繰り返す.
(STEP2-1) d 番目の探索点 x dk が,ランダムに 3 つの探索点 x r1k , x rk2 , x rk3 を選ぶ.ただし d ≠ r1 ≠ r 2 ≠ r 3 .
(STEP2-2)突然変異によって,新たな探索点 v dk を以下の式により生成する.
v dk = x rk1 + F ( x rk2 − x rk3 )
(1)
(STEP2-3)探索点 x dk と v dk が交叉確率 Cr によって交叉し,新たな点 u dk を生成する.
(STEP2-4)目的関数 f (x)を評価し,探索点の位置を更新.
f (u dk ) ≤ f ( x dk ) → x dk = u dk
(2)
f (udk ) > f ( x dk ) → x dk = x dk
(3)
(STEP3)探索回数を更新( k = k +1)
.
(STEP4)終了条件を満足していれば,終了.そうでなければ(STEP2)へ戻る.
2・2 交叉
DE の交叉について,図 1 を用いて説明する.ここで x dk , v dk それぞれの成分を x dk ,i , v dk ,i ( i = 1, 2,…, n )と
表記する.交叉による u dk の生成を図 1 に示す.図 1 中の交叉点(Crossover point)は,ランダムに選ばれる.ま
た r は設計変数ごとに発生させる[0,1) の乱数である.はじめに交叉点の設計変数の成分が v dk から引き継がれ,
新たな点 u dk の成分となる.
次に u dk の他の成分を決定するため,
交叉点以外の設計変数に対して成分毎に乱数 r を
k
k
発生させ, x d , v d から引き継いで残りの成分を決定していく.
Cross over point
v dk vdk ,1 vdk , 2 vdk ,3 vdk , 4 vdk ,5
udk
xdk ,1
xdk , 2
vdk ,3
xdk , 4
r ∈ [0,1) ≤ Cr
vdk ,5
x dk xdk ,1 xdk , 2 xdk ,3 xdk , 4 xdk ,5
r ∈ [0,1) > Cr
Fig.1 Crossover in DE
3. 領域適応型 Differential Evolution
本論文で提案する ARDE の探索領域は,ARPSO を参考にして設定する.はじめに ARPSO で提案された探索
領域の基本的な考え方を示し,次に ARDE の探索領域の設定指針や特徴について述べる.
3・1 領域設定の基本方針
ARPSO の探索領域の設定方法を示す.PSO は,各探索点が位置と速度を持ち,それらを更新して最適解を求
める方法である.k 回目の探索における d 番目の探索点の位置を x dk ,速度を v dk とすると,k + 1 回目の探索にお
ける位置 x dk +1 と速度 v dk +1 はそれぞれ以下の式によって表される.
x dk +1 = x dk + v dk +1
(4)
v dk +1 = wv dk + c1 r1 ( p dk − x dk ) + c 2 r2 ( p gk − x dk )
(5)
式(5)において,w は慣性項と呼ばれる係数,c1,c2 は定数であり, r1 と r2 は[0,1)の乱数, p dk は探索点 d
の k 回目までの最良点(p-best)
, pgk は k 回目の探索における探索点全体の最良点(g-best)を表す.
ARPSO における有効探索領域は,式(6)で示される正規分布を基調とし,式(7)によって与えられる.ここで i
番目の設計変数を xi とし,i 番目の設計変数における各探索点の位置に対する標準偏差を σ i ,平均を µ i とする.
N ( x i ) = exp(−
( xi − µ i ) 2
2σ i2
)
(6)
µ i − − 2σ i log ai ≤ xi ≤ µ i + − 2σ i log ai
(7)
図 2 に ARPSO の有効探索領域を示す.ARDE でも式(7)を基調とした有効探索領域を考えるが,式(7)は
有効探索領域を設定する際の基本的な考え方を示すものであり,ARDE で探索に用いる領域については次節以降
で述べる.
N ( xi )
N ( xi )
N ( xi ) = exp(−
( xi − µi ) 2
)
2σ i2
σ iL
ai
xi
ai
N ( xi ) = exp(−
σ i,Rnew
µi
µi
µi − − 2σ i log ai
µi + − 2σ i log ai
µi − − 2σ i log ai
Fig.2 The active search domain of i-th design variable
New range
( xi − µi ) 2
)
2σ i2
xi
xibest
µi + − 2σ i log ai
Fig.3 New range of ARPSO by changing the standard deviation
3・2 ARDE における有効探索領域
ARPSO では,さらに最良値の保存という操作を行い,過去の探索において最良値をとった探索点 p g の座標が
探索領域内に必ず含まれるようにしていた.そのため強制的に正規分布の形状を変更することで有効探索領域を
更新して探索を行うため,統計的要素を含むとは言え,どこか不自然さが残っていた.図 3 に ARPSO で最良点
座標が式(7)の右側に位置した時に,最良値の保存を行った場合の有効探索領域を示す.ここで x ibest は p g の i
番目の成分であり,σ i,Rnew は式(6)の xi を x ibest に,N ( xi ) を a i に置き換えて σ i について解くと得られる値で,σ iL
は σ i である.ARDE における有効探索領域は,以下のようにして生成する.
全探索点の中で目的関数を最良にした探索点 xbestの i 番目の成分を x ibest とし,最良点を中心とした領域を作成
する.
xibest − − 2s i log ai ≤ xi ≤ xibest + − 2s i log ai
(8)
そして式(7)と式(8)それぞれの上下限を用いて有効探索領域を決定する.ARDE で最終的に探索に用いる
領域は式(11)である.
{
}
(9)
{
}
(10)
xiRight = max m i + − 2s i log ai , xibest + − 2s i log ai
xiLeft = min m i − − 2s i log a i , xibest − − 2s i log a i
x iLeft ≤ x i ≤ x iRight
(11)
3・3 有効探索領域の性質と ARPSO との相違
式(11)で与えられる有効探索領域の一例を図 4 に示す.破線の曲線が各設計変数の平均値,最良点を中心と
した正規分布を,実線の曲線がそれら 2 つの曲線を重ね合せたものを表している.図 4(a)の場合,実線部は大き
な正規分布のような形状となり,巨大な正規分布から有効探索領域を決定していると見なすことができる.本来
正規分布は平均を中心に左右対称であり,基準となる値を中心としたばらつきを表すものである.このようなこ
とを踏まえれば不自然にこの形状を変更する ARPSO より,本来の正規分布に基づく左右対称な一つの巨大な正
規分布から有効探索領域を決定している ARDE の有効探索領域の方が考え方が自然である.ただし図 4(b)にある
ように,実線部の曲線は必ずしも正規分布の形状をとらないことに注意されたい.平均値と最良点の位置が大き
く離れている場合,重ね合せた曲線は正規分布の形状とはならずに中央がくぼんだ形状となる.その場合,有効
探索領域が巨大な正規分布から決定されるという意味は薄れ,広い有効探索領域を用いて探索の多様性が高まる
という意味合いが強くなる.
また図 4 には ARPSO で最良値の保存を行った場合の有効探索領域も示されている.
図 4 から明らかなように,
ARPSO の有効探索領域より ARDE の有効探索領域の方が有効探索領域を広くとることができる.有効探索領域
が広い場合,探索点の移動範囲が増加するため有効探索領域は探索の多様性が高くなる.多様性の高い有効探索
領域は局所的最適解に捕らわれにくい幅広い探索を可能とし,大域的最適解の発見が期待できる.探索初期は探
索点の位置がばらつき,正規分布のすそ野が広く,最良点と平均値が離れていることが予想される.探索初期で
探索の多様性が求められる場合に有効探索領域は図 4(a)のようになることが予想され,ARDE の方が ARPSO よ
りも,大域的最適解を発見しやすい有効探索領域になることが期待される.また最良点が局所的最適解から離れ
た位置に発見された場合,有効探索領域は図 4(b)のようになることが予想される.この場合局所的最適解付近を
集中的に探索するよりも,新たに発見された最良点付近の探索も考慮して有効探索領域を広げたほうが大域的最
適解の発見が期待できる.このような状況でも ARDE は ARPSO より多様性のある効果的な有効探索領域を設定
することができる.このように ARDE では最良点を有効探索領域に残すという ARPSO の最良値の保存の設定指
針を常に含んだまま,探索の多様性が特に求められる状況で有効探索領域を ARPSO より多様性のあるものにす
ることが期待できる.
N ( xi ) + N ′( xi )
N ( xi ) = exp(−
( xi − µi ) 2
)
2σ i2
N ( xi ) N ′( xi )
N ′( xi ) = exp(−
( xi − xibest ) 2
)
2σ i2
N ( xi ) + N ′( xi )
N ′( xi )
N ( xi )
ARPSO
ARPSO
ai
ai
xi
µi
µ i − − 2σ i log ai
xibest − − 2σ i log ai
xiLeft
New range
µi
xibest + − 2σ i log ai
xibest
xiRight
µ i + − 2σ i log ai
xi
xiLeft
(a) Superposed distribution curve
xibest
New range
xiRight
(b) Expanded range
Fig.4 Active search domain range of ARDE
3・4 有効探索領域の確保
探索終盤に探索点が集中して探索領域が極端に小さくなるのを防ぐために,
各設計変数の標準偏差の最小値を,
側面制約条件を利用して式(12)のように決定する.
σ i , min = ε i ( xiU − xiL )
(12)
ここで ε i は [ 0 , 1 ] の値である.また xiU , xiL は側面制約条件の上限値,下限値である.
3・5 有効探索領域の多様性と集中化
式(11)では常に最良点と探索点の平均値を含むため,探索初期では図 5(a)に示すような広い探索領域となる.
探索が進むにつれ,探索点の集中化が進めば探索点の平均値と最良点は近づくことが期待され,図 5(b)のように
徐々に有効探索領域は小さくなる.最終的には図 5(c)のように探索点の平均値と最良点はほぼ一致して,有効探
索領域は十分小さくなる.ARDE は,DE がランダム性を強く意識した方法であるということを踏まえて, 正規
分布の形状を維持しながら探索を行う方法であり,図 5 に示したように有効探索領域は幅広くとることができる.
探索が進んでも,探索点がばらついていれば,有効探索領域は広いまま探索を続けることになるため,大域的最
適解の発見確率が高く,さらに最終的に得られる最適解の精度も十分高いことが期待できる.
N ( xi ) + N ′( xi )
N ′( xi )
N ( xi )
xi
x
best
i
Right
xiLeft Range of this study xi
(a) Initial search stage
N ′( xi )
N ( xi )
ai
µi
N ( xi ) + N ′( xi )
N ( xi ) + N ′( xi )
ai
µi
xi
xiLeft
µ i xibest
xiRight
(b) Convergence stage
ai
xiLeft
xibest
xi
xiRight
(c) Search termination
Fig.5 Shrinkage of active search domain
4. アルゴリズム
提案する手法のアルゴリズムを示す.ARDE では 2 章で述べた DE の基本的なアルゴリズムにおける(STEP1)
~(STEP2-4)および(STEP3),(STEP4)が同じであるため,変更を加える(STEP2-4)以降について示す.ただし(STEP1)
においては 2 章の設定パラメータに加えて,新たに a i と ε i を設定する.そして以下に示す(STEP2-6)が終了した
ら 2 章の(STEP3)へ移動する.
(STEP2-5)各設計変数の標準偏差 σ i と平均 µ i を計算し, xibest を求める. σ i が σ i , min を下回っているのなら置
換する.
σ i < σ i , min ⇒ σ i = σ i , min
(13)
(STEP2-6)設計変数毎に,式(7)
,
(8)から平均を中心とした領域,最良点を中心とした領域の上下限値を
求め,それら 4 つの値から有効探索領域の幅が最大となるように式(9)
,
(10)を用いて有効探索
領域の上限値・下限値を決定し,式(11)のように有効探索領域を設定する.
5. 数値計算
代表的な数値計算例を通じて本論文で提案する手法の有効性を検討する.本論文では有効探索領域の変更が基
本的な DE にもたらす有効性を確認するため,ARDE と有効探索領域の変更を行わない通常の DE で数値計算を
行った.また本論文では参考とした ARPSO の数値計算結果との比較は極力行わなかった.これははじめに述べ
たように,PSO が力学系に基づく内挿領域の集中探索であり,一方で DE はランダム性を基調とした外挿領域の
探索も可能な多点同時探索法であるため,ARPSO と ARDE では基本的な探索の性質が異なるためである.
すべての数値計算例で,突然変異率 F = 0.7,交叉率 Cr = 0.5 とし,探索領域の作成で必要となるパラメータは,
ε i = 0.01 (側面制約の 1%)として,乱数の種を変え 10 回試行した.なお以下では標準偏差(Standard Deviation)
を SD と略記する.
5・1 有効探索領域の変化
有効探索領域の変化を可視化するため,式(14),(15)で与えられる Schwefel 関数を用いる.関数の様子と等高
線を図 6 に示す.
∑ {− x sin
n
f ( x ) = 418.9829n +
i
}
xi → min
(14)
i =1
−500 ≤ x ≤ 500
(15)
大域的最適解は xi,G = 420.9687( i = 1,2,  , n )であり,そのときの目的関数値は 0 である.多くの局所的最適
解が含まれており,ARDE のように初期設定領域にとらわれずに外挿領域の探索をも意識した方法であれば,局
所的最適解にとらわれず大域的最適解の発見が期待できる.有効探索領域の可視化のため,設計変数の数は 2 と
し,探索点数を 20,最大探索回数を 100 とした時,目的関数の履歴を図 7 に,有効探索領域の変化の一例を図 8
に示す.また数値計算の結果を表 1 に示す.
x2
f ( x)
Global minimum
Local minimum
x2
x1
x1
Objective
Fig.6 The behavior and contour of objective function
300
250
200
150
100
50
0
Table 1 Result of Schwefel function
DE
ARDE
0
10
20
30
Iteration
40
Fig.7 Convergence of objective function
50
Best objective
Worst objective
Mean value of objective
SD of objective
Average of function call
ARDE
2.55E-05
2.55E-05
2.55E-05
6.74E-09
1528
DE
2.55E-05
2.55E-05
2.55E-05
8.33E-09
1588
Best position
Mean of particles
2nd iteration
Active search domain range
17th iteration
7th iteration
12th iteration
22nd iteration
24th iteration
Fig.8 Change of search domain through search process
図 7 から,ARDE は探索が進むと早い段階で DE よりも良い最良値を求めることができている.図 8 では,探
索が進むにつれて最良点が移動しながら大域的最適解を発見する様子が見て取れる.有効探索領域は初期の探索
回では広いままであったが,その後大域的最適解を発見してから,探索点の座標平均値と最良点座標が近付いて
縮小していく様子がわかる.
5・2 無制約最適化問題
無制約最適化問題の代表的なベンチマーク問題を考える.
(用いたベンチマーク問題は付録に記載)
.探索点数
を 30 点,最大探索回数 k max = 500 とした.探索性能を比較するため,有効探索領域を操作しない通常の DE で試
行した結果と合わせて数値計算の結果を表 2~5 に示す.
これらの結果から,本論文で提案する手法は通常の DE よりも少ないファンクションコール(目的関数値の計
算回数)で大域的最適解を求めることができており,探索効率が向上していることがわかる.また目的関数値の
平均,標準偏差も小さな値となっているため,安定的に大域的最適解の探索が行われていることがわかる.本節
で用いたベンチマーク問題は多峰性が激しかったり,大域的最適解と局所的最適解の位置が離れていたり,各設
計変数で大域的最適解が異なる値をとったりするなどの特徴を有するものである.このような問題でも大域的最
適解が見つかったのは有効探索領域が探索状況に合わせて適切に行われて,探索の多様性を維持したまま探索が
行われているためと考えられる.
Table 2 Result of 2n minima function
Best objective
Worst objective
Mean value of objective
SD of objective
Average of function call
ARDE
-391.661657
-391.661654
-391.661656
5.42E-07
8250
DE
-391.661657
-391.661654
-391.661655
6.75E-06
10611
Table 3 Result of Griewank function
Best objective
Worst objective
Mean value of objective
SD of objective
Average of function call
ARDE
3.95E-09
1.93E-08
1.05E-08
3.54E-09
8091
DE
4.23E-09
2.16E-08
1.19E-08
4.03E-09
10242
Table 4 Result of Ackley function
Best objective
Worst objective
Mean value of objective
SD of objective
Average of function call
ARDE
1.71E-07
2.54E-06
1.29E-06
5.69E-07
12633
Table 5 Result of Michalewics function
DE
2.97E-07
2.66E-06
1.46E-06
5.82E-07
14082
Best objective
Worst objective
Mean value of objective
SD of objective
Average of function call
ARDE
-4.68766
-4.68765
-4.68766
1.86E-06
4029
DE
-4.68766
-4.68765
-4.68766
1.90E-06
4311
5・3 コイルばねの重量最小化設計
文献(14)で取り上げられているコイルばねの重量最小化設計問題を考える.この問題は,探索効率や最適解
の精度を検討するために多点同時探索型最適化手法でしばしば用いられる問題である (13,15,16).設計変数はワイヤ
の直径 d (= x1 ) ,コイルの平均直径 D(= x 2 ) ,コイルの巻数 N (= x 3 ) であり,すべて連続変数である.最適設計問
題は以下の式(16)~(23)のように定式化される.探索点数を 20 とし,最大探索回数を 500 として計算したと
きの結果を,他の研究報告と併せ,表 6 に示す.なお,制約条件はペナルティ関数として扱い,文献(13)の方
法を採用した.
f ( x ) = (2 + x 3 ) x12 x 2 → min
(16)
g 1 ( x ) = 1 − x 23 x 3 /(71785 x14 ) ≤ 0
(17)
g 2 ( x) =
4 x 22 − x1 x 2
12566( x 2 x13 − x14 )
g 3 ( x) = 1 −
140.45 x1
x 22 x 3
+
1
−1≤ 0
5108 x12
(18)
≤0
(19)
x1 + x 2
−1≤ 0
1.5
0.05 ≤ x1 ≤ 2.00
g 4 ( x) =
(20)
(21)
0.25 ≤ x2 ≤ 1.30
2.00 ≤ x3 ≤ 15.0
(22)
(23)
Table 6 Comparison of results of minimum weight design of tension/compression spring
Best solutions found
Design Variables
(14)
x 1 (d )
x 2 (D )
x 3 (N )
g 1 (x )
g 2 (x )
g 3 (x )
g 4 (x )
f (x )
Average of f (x )
Worst of f (x )
SD of f (x )
Function call
Arora
Coello (15)
0.053396
0.05148
0.039918
0.351661
9.1854 11.632201
0.000019
-0.00208
-0.000018
-0.00011
-4.123832 -4.026318
-0.698283 -0.731239
0.01273
0.012705
N/A
0.012769
N/A
0.012822
N/A
3.94E-05
N/A
900000
DE
This study
Ray (16)
ARPSO(13)
0.050417
0.051679 0.051668
0.051638
0.321532
0.356477 0.35620
0.35549
13.979915 11.299395
11.320
11.362
-0.001926
-0.000037 -1.01E-02
-1.06E-06
-0.012944
-0.000008 -5.29E-06
-6.53E-06
-3.89943
-4.054976
-4.0527
-4.0513
-0.752034
-0.727895 -0.72809
-0.72858
0.01306
0.012661 0.012665
0.012665
0.013436
0.012675 0.012666
0.012666
0.01358
0.012696 0.012668
0.012667
N/A
1.17E-05 4.75E-07
4.00E-07
1291
5804
6880
5900
表 6 より ARDE では少ないファンクションコールで効率的に大域的最適解を求めることができている.標準偏
差と平均値も小さいため,ARDE はロバスト性が高いアルゴリズムであると考えられる.
5・4 溶接梁のコスト最小化問題
文献(17)にある溶接梁のコスト最小化問題を考える.図 9 に対象とする溶接梁を示す.目的関数は式(24)
にあるように溶接梁の重量に単位重量当たりのコスト係数 c1,c2 をかけたものである.設計変数は溶接部の寸法
,
h (= x1 ) ,溶接する長さ l (= x 2 ) ,はりの断面寸法 t (= x 3 ) , b (= x 4 ) の 4 つである.また側面制約条件は式(25)
(26)である.制約条件は,はりのせん断応力や曲げ応力,たわみ,座屈等である.それらを式(27)~(41)
に示す. ここで c1 = 67413.5[$ /m3],c2 = 2935.85[$ /m3],L = 357[mm], τ max = 93.769[MPa], σ max = 206.84[MPa],
δ max = 6.35[mm],P = 26.689[kN],E = 206.84[GPa],G = 82.737[GPa]である.探索点数を 20,最大探索回数を 500
として DE と ARDE で計算した結果を,他の文献に記された結果 (18-20)と併せて表 7 に示す.
表 7 より ARDE はファンクションコールが少なく,探索が効率的であることが分かる.前節のコイルばねの重
量最小化問題の結果と合わせて考えると,ARDE は有制約最適化問題に対しても有効であると考えられる.
f ( x ) = c1 x12 x 2 + c 2 x3 x 4 ( L + x 2 )
(24)
2.54 ≤ x i ≤ 50.8
(25)
(26)
2.54 ≤ xi ≤ 254
(i = 1 ,4)
(i = 2 , 3)
g 1 ( x ) = τ ( x ) − τ max ≤ 0
g 2 ( x ) = σ ( x ) − σ max ≤ 0
g 3 ( x ) = x1 − x 4 ≤ 0
(27)
(28)
g 4 ( x ) = 3.175 − x1 ≤ 0
(30)
(31)
(32)
(29)
g 5 ( x ) = δ ( x ) − δ max ≤ 0
g 6 ( x ) = P − Pc ( x ) ≤ 0
x2
+ (τ ′′) 2
2R
τ ( x ) = (τ ′) 2 + 2τ ′τ ′′
(33)
τ ′ = P / ( 2 x1 x 2 )
(34)
τ ′′ = MR / J
M = P( L + ( x 2 / 2))
(35)
(36)
R=
x 22  x1 + x3 
+

4  2 
 x x
J = 2 1 2
 2
2
(37)
 x 2  x + x  2  
3
 
 2 + 1
 12  2   
(38)
σ ( x ) = 6 PL /( x 4 x32 )
(39)
δ ( x ) = 4 PL3 /( Ex33 x4 )
(40)
Pc ( x ) =
4.013 EG ( x32 x 46 / 36) 
1 − x 3
2
 2L
L

E
4G




(41)
P
h
h
t
l
L
b
Fig.9 Design problem of welded beam
Table 7 Comparison of results of welded beam design
Best solutions found
Design Variables
(18)
x 1 (h ) [mm]
x 2 (l ) [mm]
x 3 (t ) [mm]
x 4 (b ) [mm]
g 1 (x ) [Pa]
g 2 (x ) [Pa]
g 3 (x ) [mm]
g 4 (x ) [mm]
g 5 (x ) [mm]
g 6 (x ) [ N ]
f (x ) [$]
Function call
Average of f (x )
Worst of f (x )
Standard Deviaton of f (x )
(19)
DE
ARDE
Ray and Liew
He et al
Wang and Yin (20)
6.2087
6.2070
6.2070
6.2067
6.2068
158.44
157.92
157.92
157.91
157.93
210.53
210.60
210.60
210.63
210.61
6.2120
6.2070
6.2070
6.2069
6.2069
-22346E+01
-1.9262
-1.6981
-354.96
-2215.6
-22376
-3.5293
-4.0282
-47426
-19434
-3.2488E-03 0.0000E+00
0.0000E+00 -1.4073E-04 -1.0780E-04
-3.0337
-3.0320
-3.0320
-3.0317
-3.0318
-5.9496
-5.9497
-5.9497
-5.9499
-5.9498
-58.180 -1.3745E-03
-1.3968E-03
-1.1409
-0.47144
2.3854
2.3810
2.3810
2.3810
2.3810
40000
30000
30000
8100
7560
3.2551
2.3819
2.3810
2.3813
2.3811
6.3997
N/A
2.3810
2.3815
2.3813
0.959
5.24E-03
1.14E-05
1.28E-04
5.92E-05
5・5 数値計算のまとめ
提案する手法は通常の DE に比べ,少ない計算回数で効率的に精度良く大域的最適解を求めることができてい
る.DE では探索方向のランダム性により,探索は時として外挿領域にも及び幅広い探索が行われるが,提案手
法では有効探索領域内に常に最良点を含みつつ平均まで考慮するため,有効探索領域を広く取ることができ,外
挿領域への探索を妨げない.また仮に探索の途中で見つけた局所的最適解に最良点が移動した場合でも,平均値
と局所的最適解の位置がずれていたり,あるいは探索点のばらつきが大きかったりする場合,簡単に有効探索領
域は縮小しない.そして平均値と最良点が近付き,全体のばらつきが少なくなってきたときに,はじめて探索点
の集中化がおき有効探索領域は縮小する.このため局所的最適解の発見に留まることなく,大域的最適解を求め
ることができると言える.また,5.2 節で扱った問題に関して,Michalewics 関数を除くベンチマーク問題に対し
て,最大探索回数を固定(k max=1000)し,探索点数を 20,設計変数の数を 20 とした場合,ARDE において大域
的最適解が発見できない結果も見受けられた.5.2 節で扱った問題に関しては,本手法の有効範囲は設計変数の数
が 10 程度の問題までと考えられる.なお,文献(21)では,探索の初めに設定する突然変異確率 F と交叉確率 Cr
を,探索状況に応じて自動的に制御する研究が行われており,数多くのベンチマーク問題が示されているが,フ
ァンクションコール(探索点数と最大探索回数の積)は本論文で提案した方法に比べ非常に多いため,一概に比
較することは困難であるが,最適解を求めるまでの効率(ファンクションコール)を考慮すれば,本論文で提案
した方法の有効性の一端は確認できるものと考えられる.
6. 結
語
本論文では,先行研究である領域適応型 Particle Swarm Optimization(ARPSO)を参考に,領域適応型 Differential
Evolution(ARDE)を提案した.提案する手法は DE に各設計変数の平均と標準偏差,そして最良点から構成さ
れる有効探索領域を適用して探索を行う.この有効探索領域は ARPSO の強制的な正規分布の変更をなくし,本
来の正規分布を利用して構成され,探索状況をより反映したものとなっている.提案手法は各設計変数の最良点
と平均それぞれを中心とした領域を重ね合わせるため有効探索領域を広く取ることができ,DE の持つ外挿領域
をも探索に含む探索の多様性を維持したまま探索を行うことが可能である.数値計算例を通じ,計算コスト(フ
ァンクションコール)を下げつつ局所的最適解の発見に留まらずに精度良く大域的最適解を発見できることが確
認できた.
付
録
本論文で扱った無制約最適化問題を以下に示す.なお以下では設計変数の数を n とする.
(P1)2n minima 関数
大域的最適解は n = 10 で x G = (−2.90354,3,−2.90354) T ,そのときの目的関数値は f ( x G ) = −391.661 で
ある.本論文の表 2 は n = 10 の場合の計算結果である.
f ( x) =
1
2
n
∑ (x
− 16 xi2 + 5 xi ) → min
4
i
(A1)
i =1
−5 ≤ x ≤ 5
(A2)
(P2)Griewank 関数
大域的最適解は n = 10 で x G = (0, 0,, 0) T ,そのときの目的関数値は f ( x G ) = 0 である.本論文の表 3
は n = 10 の場合の計算結果である.
f ( x) = 1 +
1
400
n
n
∑
i =1
xi2 −
∏ cos(
i =1
xi
) → min
(A3)
i
−10 ≤ x ≤ 10
(A4)
(P3)Ackley 関数
大域的最適解は n = 10 で x G = (0, 0,, 0) T ,そのときの目的関数値は f ( x G ) = 0 である.本論文の表 4
は n = 10 の場合の計算結果である.
f ( x ) = 22.71828 − 20 exp[−0.2
1
n
n
∑
xi2 ] − exp[
i =1
1
n
n
∑ cos(2p x )] → min
i
(A5)
i =1
−30 ≤ x ≤ 30
(A6)
(P4)Michalewics 関数
本論文では n = 5 として計算し,大域的最適解は x G = (2.202906,1.570796,1.284992,1.923059,1.720470) T
であり,そのときの目的関数値は f ( x G ) = −4.687658 である.
n
f ( x) = −
∑
i =1
0≤ x ≤π

ix 2 
sin( xi ) × sin( i )
π 

20
→ min
(A7)
(A8)
文
献
(1) Storn, R., and Price, K.V., “Differential Evolution – a simple and efficient adaptive scheme for global optimization over
continuous space”, Technical Report TR-95-012, (1995), ICSI.
(2) Storn, R., and Price, K.V., “Differential Evolution –a simple and efficient heuristic for global optimization over continuous
spaces”, Journal of Global Optimization, Vol.11, (1997), pp. 341-359.
(3) Kennedy, J., and Eberhart, R., “Particle Swarm Optimization”, IEEE International Conference on Neural Networks, (1995),
pp.1942-1948.
(4) Kitayama, S., Arakawa, M., and Yamazaki, K., “Penalty Function Approach for the Mixed Discrete Non-Linear Problems by
Particle Swarm Optimization”, Structural and Multidisciplinary Optimization, Vol.32, No.3, (2006), pp.191-202.
(5) 安田恵一郎,石亀篤司,
“非線形計画アルゴリズム―実用的視点から―”
,システム/制御/情報,Vol.50, No.9, (2006),
pp.1-7.
(6) Zaharie, D., “Influence of Crossover on the Behavior of Differential Evolution Algorithms”, Applied Soft Computing, Vol. 9,
(2009), pp. 1126-1138.
(7) Tvrdik, J., “Adaptation in Differential Evolution: A Numerical Comparison”, Applied Soft Computing, Vol.9, (2009), pp.
1149-1155.
(8) 北山哲士,酒井忍,荒川雅生,山崎光悦,
“大域的最適化手法としての Differential Evolution と数値計算”
,日本機
械学会論文集 C 編,Vol. 76, No. 771, (2010), pp. 73-82.
(9) 北山哲士,荒川雅生,山崎光悦,
“Discrete Differential Evolution の提案”
,日本機械学会論文集 C 編,Vol. 76, No. 772,
(2010), pp. 3828-3836.
(10) Pan, Q.K., Tasgetiren, M.F., and Liang, Y.C., “A Discrete Differential Evolution Algorithm for the Permutation Flowshop
Scheduling Problem”, Computers and Industrial Engineering, Vol.55, (2008), pp.795-816.
(11) Qian, B., Wang, L., Hu, R., Huang, D.X., and Wang, X., “A DE-based Approach to No-Wait Flow-Shop Scheduling”,
Computers and Industrial Engineering, Vol.57, (2009), pp.787-805.
(12) Dasgupta, S., Das, S., Biswas, A, and Abraham. A., “On Stability and Convergence of the population-dynamics in Differential
Evolution”, AI Communications, Vol.22, (2009), pp.1-20.
(13) 北山哲士,荒川雅生,山崎光悦,
“領域適応型 Particle Swarm Optimization の提案”
,日本機械学会論文集 C 編,Vol.
73, No. 725, (2007), pp. 280-287.
(14) Arora, J.S., Introduction to Optimum Design (1989), McGraw-Hill, New York.
(15) Coello Coello C.A., “Use of a Self-Adaptive Penalty Approach for Engineering Optimization Problems”, Computers in
Industry, Vol.41, (2000), pp.113-127.
(16) Ray, T., and Saini, P., “Engineering Design Optimization Using Swarm with an Intelligent Information Sharing among
Individuals”, Engineering Optimization, Vol.33, (2001), pp.735-748.
(17) Rao, S.S., Engineering Optimization, Theory and Practice, Third Edition (1996), Wiley Interscience.
(18) Ray, T., and Liew, KM., “Society and civilization: An optimization algorithm based on the simulation of social behavior”,
IEEE Transactions on Evolutionary Computation, Vol.7, (2003), pp.386-396.
(19) He, S., Prempain, E., and Wu, Q.H., “An improved particle swarm optimizer for mechanical design optimization problems”,
Engineering Optimization, Vol.36, (2004), pp.585-605.
(20) Wang, J., and Yin, Z., “A ranking selection-based particle swarm optimizer for engineering design optimization problems”,
Structural and Multidisciplinary Optimization, Vol.37, (2008), pp.131-147.
(21) J. Brest., S. Greiner., B. Boskovic., M. Mernik, and V. Zumer., “Self-Adapting Control Parameters in Differential Evolution: A
Comparative study on Numerical Benchmark Problems”, IEEE Transactions on Evolutionary Computation, Vol.10, (2006), pp.
646-657.
ダウンロード

Title 領域適応型Differential Evolutionの提案 Author(s