不確実性を含む最適化問題に対する差分進化の適用

全文

(1)Vol.2014-MPS-97 No.5 2014/3/3. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ෆ࣮֬ੑΛ‫ؚ‬Ή࠷దԽ໰୊ʹର͢Δ ࠩ෼ਐԽͷద༻ ຤Ӭ େथ1. ా઒ ੟࣏2. ֓ཁɿຊߘͰ͸ɼෆ࣮֬ੑΛ‫ؚ‬Ή࠷దԽ໰୊Ͱ͋Δ໨తؔ਺ʹϊΠζΛ‫ؚ‬ΉϊΠζ໰୊Λର৅ͱͯ͠ਐԽ ‫ࢉܭ‬ͷҰछͰ͋Δࠩ෼ਐԽʢDE:Differential EvolutionʣΛ֦ுͨ͠৽ͨͳ DE ΛఏҊ͢ΔɽఏҊ͢Δ DE Ͱ ͸ɼ༧ଌ۠ؒʹΑΔ౷‫ܭ‬త‫ݕ‬ఆͱΧοτΦϑ఺Λ༻͍ͯɼ໨తؔ਺஋Λ̍ճαϯϓϦϯά͢Δ͜ͱʹΑͬ ͯ‫ݸ‬ମͷ࠷దੑΛධՁ͠ɼ༗๬Ͱͳ͍‫ݸ‬ମʹରͯ͠͸ɼҎ߱ͷαϯϓϦϯάͷ‫܁‬Γฦ͠Λলུ͢Δɽ. 1. ͸͡Ίʹ. ੜଘબ୒ʹண໨͠ɼτϥΠΞϧϕΫτϧʹର͢Δ໨తؔ਺ ஋Λ༧ଌ۠ؒͱΧοτΦϑ఺ʹΑΓධՁ͠ɼτϥΠΞϧϕ. ਐԽ‫ࢉܭ‬ʢEAɿEvolutionary Algorithmʣ͸ɼෆ࣮֬ੑ. Ϋτϧ͕ෆྑղͱ༧૝͞ΕΔ৔߹͸ɼͦͷαϯϓϦϯάͷ. Λ‫ؚ‬Ή࠷దԽ໰୊ʹదԠͰ͖Δ͜ͱ͕ใࠂ͞Ε͍ͯ. ‫܁‬ฦ͠Λলུ͢Δɽ·ͨɼ໨తؔ਺஋ʹ෇Ճ͞ΕΔϊΠζ. Δ [1][2][3][4][5]ɽ͜ͷΑ͏ͳෆ࣮֬ੑΛ‫ؚ‬Ή࠷దԽ໰୊ʹ. ͱͯ͠͸ɼଟ͘ͷ‫࣮ݱ‬తͳ໰୊ͰΈΒΕΔਖ਼‫ن‬෼෍ʹै͏. ରͯ͠ैདྷͷਐԽ‫ࢉܭ‬Λద༻͢Δࡍɼ֤‫ݸ‬ମͷ໨తؔ਺஋. ϊΠζΛߟ͑Δɽ. Λෳ਺ճͷαϯϓϦϯάʹΑΓධՁ͢Δɽͭ·Γɼαϯϓ. ࠷‫ʹޙ‬ɼैདྷͷ DE ͷΞϧΰϦζϜɼDE ʹ༧ଌ۠ؒΛ. Ϧϯάճ਺ʹΑͬͯಘΒΕΔղͷਫ਼౓͸ࠨӈ͞ΕΔɽ͔͠. ಋೖͨ͠ΞϧΰϦζϜɼDE ʹΧοτΦϑ఺Λಋೖͨ͠Ξ. ͠ɼαϯϓϦϯάʹΑΔղͷධՁ͸‫ࢉܭ‬ίετ͕൐͏ɽͦ. ϧΰϦζϜɼఏҊ๏Ͱ͋Δ DE ʹ༧ଌ۠ؒͱΧοτΦϑ఺. ͷͨΊɼෆ࣮֬ੑΛ‫ؚ‬Ή࠷దԽ໰୊ʹର͢ΔղΛޮ཰తʹ. ͷ྆ํΛಋೖͨ͠ΞϧΰϦζϜΛൺֱ͠ɼαϯϓϦϯάճ. ୳ࡧ͢ΔਐԽ‫Ͱࢉܭ‬͸ɼղͷਫ਼౓ΛଛͳΘͣαϯϓϦϯά. ਺͕ಉ͡৔߹ɼଟ͘ͷςετ໰୊ʹ͓͍ͯఏҊ๏ʹΑΓ࠷. ճ਺Λ‫ݮ‬Β͢޻෉͕ॏཁͱͳΔɽ. ྑͷղ͕ಘΒΕΔ͜ͱΛ֬ೝ͢Δɽ. ࠩ෼ਐԽʢDEɿDifferential Evolutionʣ[6] ͸ܾఆม਺͕ ࣮਺஋ΛऔΔؔ਺࠷దԽ໰୊ʹର͢ΔਐԽ‫ࢉܭ‬ͷҰछͰ͋ ΔɽDE ͸ΞϧΰϦζϜ͕୯७Ͱ͋ΔͨΊ࣮૷͕༰қͰ͋ Δɽ·ͨɼ୅දతͳςετؔ਺Λର৅ͱͨ͠਺஋࣮‫ʹݧ‬Α Ε͹ɼయ‫ܕ‬తͳҨ఻తΞϧΰϦζϜ΍ਐԽઓུͱൺֱ͠ɼ. DE ͸ղͷऩଋʹ༏ΕɼಘΒΕΔղ΋‫͋Ͱ݈ؤ‬ΔɽDE ͷ Ҩ఻ࢠతԋࢉࢠͰ͋ΔઓུͰ͸ɼλʔήοτϕΫτϧͱ‫ݺ‬ ͹ΕΔ̍ͭͷ਌‫ݸ‬ମʹରͯ͠τϥΠΞϧϕΫτϧͱ‫ݺ‬͹Ε Δ̍ͭͷࢠ‫ݸ‬ମ͕ੜ੒͞ΕΔɽ࣍ʹɼDE ͷੜଘબ୒Ͱ͸ɼ. 2. ϊΠζ໰୊ͷఆࣜԽ ϊΠζΛ‫ؚ‬Μͩ໨తؔ਺ F ( x) ͸ɼฏ‫ ۉ‬μ (x) Ͱ෼ࢄ σ(x)2 ͷࣜ (1) ͷΑ͏ͳਖ਼‫ن‬෼෍ʹै͏ɽ. F (x) ∼ N (μ(x), σ(x)2 ). ͋Δղ x ∈ D ʹରͯ͠໨తؔ਺஋Λ N ճධՁͯ͠ಘ ΒΕͨඪຊΛ {F1 , · · · , Fn , · · · , FN } ͱ͢ΔͱɼͦΕΒͷ ඪຊฏ‫ۉ‬͸ࣜ (2)ɼඪຊෆม෼ࢄ͸ࣜ (3) ͱͳΔɽ. λʔήοτϕΫτϧͱτϥΠΞϧϕΫτϧΛൺֱ͢Δ͜ͱ. N 1 F (x, N ) = Fn N. Ͱɼ਌ࢠؒͰͷτʔφϝϯτબ୒Λߦ͏ɽ ຊߘͰ͸ɼෆ࣮֬ੑΛ‫ؚ‬Ή࠷దԽ໰୊ͷҰछͰ͋Δɼଌ. (2). n=1. ఆ‫Ͳͳࠩޡ‬໨తؔ਺ʹϊΠζΛ‫ؚ‬Ή໰୊Λର৅ͱͯ͠ɼ৽ ͨͳ DE ͷΞϧΰϦζϜΛఏҊ͢ΔɽఏҊ๏Ͱ͸ɼDE ͷ. (1). s(x, N )2 =. 1 (Fn − F (x, N ))2 N −1 N. (3). n=1. 1. 2. ۙ‫ـ‬େֶ૯߹ཧ޻ֶ‫ڀݚ‬Պ Graduate School of Science and Engineering Research, Kinki University ۙ‫ـ‬େֶཧ޻ֶ෦ School of Science and Engineering, Kinki University. c 2014 Information Processing Society of Japan . ࣍ʹɼ͋Δղ x ʹରͯ͠ N ‫ݸ‬ͷ໨తؔ਺஋ Fn ͕ඪຊ. x ʹର͢Δ໨తؔ਺஋ͷ ͱͯ͠ಘΒΕ͍ͯΔͱ͖ɼͦͷղ N + 1 ൪໨ͷඪຊͷ஋ Fn+1 ͸ɼ༗ҙਫ४Λ α ͱͯࣜ͠ (4) ͷൣғʹ͋Δͱ༧ଌ͞ΕΔɽ. 1.

(2) Vol.2014-MPS-97 No.5 2014/3/3. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. L(x, N ) ≤ FN +1 ≤ U (x, N ). . L(x, N ) = F (x, N ) − β s(x, N ) U (x, N ) = F (x, N ) + β s(x, N ) 1 β = t(N − 1, α/2), 1 + N. (4). for (i = 1; i ≤ NP ; i + +) { Randomly generate xi ∈ P;. (5). Evaluate U ( xi , N ); } i = 1;. (6). Generate the trial vector u;. ͜͜Ͱɼt(N − 1, α/2) ͸༗ҙਫ४Λ α ͱ͢Δ t ෼෍ͷ. Evaluate F ( u, 1);. ্ଆ֬཰Ͱ͋Δɽ·ͨɼຊߘͰ͸ α = 0.05 ͱ͢Δɽ. if (F ( u, 1) ≤ U ( xi , N )) { Evaluate U ( u, N );. x, N ) Λ໨తؔ ຊߘͰ͸, ࣜ (4) ͷ༧ଌ۠ؒͷ্‫ݶ‬஋ U (. if (U ( u, N ) ≤ U ( xi , N )) {. ਺ͱ͢ΔҎԼͷϊΠζ໰୊Λର৅ͱ͢Δɽ. . /* index of the target vector */. while (termination condition == false) {. xi = u;. minimize. U (x, N ). subject to. xj ≤ xj ≤ xj , j = 1, · · · , D. U ( xi , N ) = U ( u, N );. (7). } }. ্‫ه‬ͷϊΠζ໰୊͸ɼ༧ଌ۠ؒͷ্‫ݶ‬஋ U ( x, N ) Λ࠷খ ͱ͢Δ໰୊Ͱ͋Γɼܾఆม਺͸ D ‫ݸ‬ͷ࣮਺஋ xj ∈ Ͱ͋ Γɼͦͷ্Լ‫ݶ‬஋ xj ͱ xj ͕༩͑ΒΕ͍ͯΔɽ. 3. DE ͷ֦ு๏. i = (i mod NP ) + 1; } Output xb ∈ P with the minimun U ( xb , N ); ਤ1. DE-P ͷٖࣅίʔυ. for (i = 1; i ≤ NP ; i + +) { Randomly generate xi ∈ P;. ϊΠζ໰୊ʹ DE Λద༻͠ղͷਫ਼౓ΛߴΊΔʹ͸ɼࣜ (2). Evaluate F ( xi , 1);. ͱࣜ (3) ͷαϯϓϦϯάճ਺ N Λଟ͘͢Δඞཁ͕͋Δɽ͠. if (F ( xi , 1) ≤ γ) {. ͔͠ɼैདྷͷ DE Ͱ͸ɼ֤‫ݸ‬ମͷධՁʹ͓͍ͯ, ࣜ (1) ͷؔ. Evaluate U ( xi , N );. ਺஋Λ N ճ‫͢ࢉܭ‬Δඞཁ͕͋ΓɼαϯϓϦϯάճ਺ N Λ. } else {. ૿΍͢ͱ DE ͷ࣮ߦ͕࣌ؒ๲େͱͳΔɽ. U ( xi , N ) = ∞; }. 3.1 ༧ଌ۠ؒΛ༻͍ͨ DEʢDE-Pʣ DE-P ͷٖࣅίʔυΛਤ 1 ʹࣔ͢ɽ·ͣɼैདྷͷ DE ͱಉ ༷ɼॳ‫ஂूظ‬ͷ‫ݸ‬ମΛੜ੒͠ɼ֤‫ݸ‬ମͷ໨తؔ਺஋ U (xi , N ). } i = 1;. /* index of the target vector */. while (termination condition == false) { Generate the trial vector u;. Λ‫͢ࢉܭ‬Δɽ࣍ʹτϥΠΞϧϕΫτϧ u Λੜ੒͠ɼࣜ (2) Ͱ. Evaluate F ( u, 1);. N = 1 ͱͯ͠ɼ1 ճͷαϯϓϧͰ࡞ΒΕͨ໨తؔ਺஋Ͱ͋Δ. if (F ( u, 1) ≤ γ) { Evaluate U ( u, N );. F (u, 1) Λ‫ޙࢉܭ‬ɼF (u, 1) ͱλʔήοτϕΫτϧ xi ͷ໨త. if (U ( u, N ) ≤ U ( xi , N ) ). u, 1) ΑΓ U (xi , N ) ͕ྼ ؔ਺஋ U (xi , N ) Λൺֱ͢ΔɽF (. xi = u;. u, N ) ͷ‫ࢉܭ‬Λলུ͠ɼF (u, 1) ͕উΕ͹ U (u, N ) Ε͹ U (. F ( xi , 1) = F ( u, 1);. Λ‫ ͼ࠶ͯ͠ࢉܭ‬U (xi , N ) ͱൺֱ͢Δɽ࠷‫ʹޙ‬ɼࣄલʹఆ. U ( xi , N ) = U ( u, N );. ΊΒΕͨऴྃ৚͕݅ຬͨ͞ΕΔͱɼूஂ಺Ͱ໨తؔ਺஋. }. U (xb , N ) ͕࠷খͷ‫ݸ‬ମ xb ∈ P Λग़ྗͯ͠ऴྃ͢Δɽ. } else {. /* F ( u, 1) > γ */. if (F ( u, 1) ≤ F ( xi , 1)) xi = u;. 3.2 ΧοτΦϑ఺Λ༻͍ͨ DEʢDE-Cʣ. F ( xi , 1) = F ( u, 1);. DE-C ͷٖࣅίʔυΛਤ 2 ʹࣔ͢ɽΧοτΦϑ఺͸೚ҙ. }. u, 1) ͱ γ Λൺֱ͢ΔɽF (u, 1) ͷ஋ γ (γ > 0) Ͱ͋ΓɼF (. }. ͕ΧοτΦϑ఺ γ ΑΓେ͖͚Ε͹ɼ‫࣮ݱ‬తʹղͱͯ͠ෆྑ. i = (i mod NP ) + 1;. u, N ) ͷ‫ܭ‬ Ͱ͋ΔΑ͏ͳ໨తؔ਺஋͕ಘΒΕͨͱͯ͠ɼU (. }. ࢉΛলུ͢ΔɽࣄલʹఆΊΒΕͨऴྃ৚͕݅ຬͨ͞ΕΔͱɼ. Output xb ∈ P with the minimum U ( xb , N );. ूஂ಺Ͱ໨తؔ਺஋͕࠷খͷ‫ݸ‬ମΛग़ྗͯ͠ऴྃ͢Δɽ. ਤ2. DE-C ͷٖࣅίʔυ. Έ N ճαϯϓϦϯά͢Δɽ͞ΒʹɼτϥΠΞϧϕΫτϧ u. 3.3 ༧ଌ۠ؒͱΧοτΦϑ఺Λ༻͍ͨ DEʢDE-PCʣ ఏҊ͢Δ DE-PC ͸ DE-P ͱ DE-C Λ૊Έ߹Θͤͨ΋ͷ Ͱ͋ΔɽDE-PC Ͱ͸ DE-C ͱಉ༷ɼશͯͷ‫ݸ‬ମΛ̍ճͷΈ. ʹ͍ͭͯ͸ɼ̍ճͷαϯϓϦϯά஋͕ΧοτΦϑ఺ͱλʔ ήοτϕΫτϧ xi ͷ໨తؔ਺஋ U (xi , N ) ΑΓ΋খ͍͞৔. u Λ N ճαϯϓϦϯάͯ͠ U (u, N ) Λ‫ٻ‬ΊΔɽ ߹ͷΈɼ. αϯϓϦϯά͠ɼͦΕ͕ΧοτΦϑ఺ΑΓ΋খ͍͞৔߹ͷ. c 2014 Information Processing Society of Japan . 2.

(3) Vol.2014-MPS-97 No.5 2014/3/3. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. fp. DE. ද 1 ࠷ྑղͷ໨తؔ਺஋ U DE-P DE-C. DE-PC. f1. 371.718. 3.709. 3.198. f2. 54.291. 3.281. 2.994. 2.780 2.661. f3. 75.996. 19.289. 18.971. 18.273. f4. 3500.078. 4.203. 6.556. 3.221. f5. 7.404. 3.847. 3.986. 3.815. 4. ਺஋࣮‫ݧ‬ Sphere function: f1. DEɼDE-PɼDE-C ͱ DE-PC ͷϓϩάϥϜΛ Java ‫Ͱޠݴ‬ x, N ) ʹ͓͍ͯ ࣮૷ͨ͠ɽ·ͨɼϊΠζ໰୊ͷ໨తؔ਺ U ( F (x) Λఆٛ͢ΔͨΊɼ5 छྨͷςετؔ਺ fp Λ༻ҙͨ͠ɽ ͢΂ͯͷ DE ʹ͓͍ͯूஂͷ‫ݸ‬ମ਺ Np = 100ɼऴྃ৚݅ Λαϯϓϧͷ૯਺ 3 × 105 ɼΧοτΦϑ఺ γ = 50 ͱͯ͠ɼ. 5 छྨͷϊΠζ໰୊ʹରͯ͠ɼ30 ճͣͭద༻ͨ͠ɽ ֤ DE ͰಘΒΕͨ໨తؔ਺஋Λද 1 ʹࣔ͢ɽද 1 Ͱ͸֤ ςετؔ਺͝ͱʹ࠷ྑ஋ΛଠࣈͰ͍ࣔͯ͠Δɽද 1 ͔Βఏ Ҋ๏Ͱ͋Δ DE-PC ͷ༗ޮੑ͕֬ೝͰ͖Δɽ ਤ 3 ʹ DEɼDE-PɼDE-C ͱ DE-PC ʹΑΔࣜ (7) ͷ࠷ద Խ໰୊ͷ໨తؔ਺஋ͷαϯϓϧ਺ʹର͢ΔมԽΛࣔ͢ɽਤ. Hyper-Ellipsoid function: f2. 3 ͔Β༧ଌ۠ؒͱΧοτΦϑ఺͸ DE ͷऩଋੑΛߴΊΔ͜ ͱ͕Θ͔Δɽ·ͨɼΧοτΦϑ఺͸୳ࡧͷॳ‫ظ‬ஈ֊Ͱ‫ۃ‬Ί ͯ༗ޮͰ͋Δɽ. 5. ͓ΘΓʹ ຊߘͰ͸ɼϊΠζ໰୊ʹద༻͢Δ DE ͷαϯϓϦϯάճ ਺Λ୹ॖ͢ΔͨΊɼ৽ͨʹ DE Λ֦ுͨ͠ DE-PC ΛఏҊ͠ ͨɽ਺஋࣮‫ݧ‬ͷ݁ՌΑΓɼఏҊͨ͠ DE-PC ͸ಉ͡αϯϓ ϧ਺Ͱैདྷ๏ΑΓྑ͍ղ͕ಘΒΕΔ͜ͱΛ֬ೝͨ͠ɽ ࠓ‫ޙ‬ͷ՝୊͸ɼΧοτΦϑ఺ γ ͷௐ੔๏ͷఏҊͰ͋Δɽ. Rosenbrock function: f3. ࢀߟจ‫ݙ‬ [1]. [2]. [3]. [4]. [5]. [6]. Y. Jin and J. Branke: Evolutionary optimization in uncertain environments – a survey, IEEE Trans. on Evolutionary Computation, Vol. 9, No. 3, 2005, pp. 303–317. J. Branke and C. Schmidt: Sequential sampling in noisy environments: Proc. of PPSN VIII, LNCS 3242, Springer, 2004, pp. 202–211. S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama: Opposition-based differential evolution for optimization of noisy problems, Proc. of IEEE Congress of Evolutionary Computation, 2006, pp. 6756–6763. B. Liu, X. Zhang, and H. Ma: Hybrid differential evolution for noisy optimization, Proc. of IEEE Congress of Evolutionary Computation, 2008, pp. 587–592. ຤Ӭେथ, ా઒੟࣏: ϩόετ࠷దԽ໰୊ʹର͢Δࠩ෼ਐ Խͷద༻, ৘ใॲཧֶձؔ੢ࢧ෦ ࢧ෦େձ ߨԋ࿦จू, 2013, B-101. R. Storn and K. Price: Differential evolution - a simple and efficient heuristic for global optimization over continuous space, Journal of Global Optimization, Vol. 4, No. 11, 1997, pp. 341–359.. Schwefel’s Ridge function: f4. Griewank function: f5 ໨తؔ਺஋ U ͷมԽ. ਤ3 c 2014 Information Processing Society of Japan . 3.

(4)