最悪ケースの多数目的最適化問題に対する差分進化の適用

全文

(1)Vol.2015-MPS-102 No.19 2015/3/4. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ࠷ѱέʔεͷଟ਺໨త࠷దԽ໰୊ʹର͢Δ ࠩ෼ਐԽͷద༻ ‫ ాݪ‬ᠳҰ1. ా઒ ੟࣏2. ֓ཁɿ‫࣮ݱ‬తͳ࠷దԽ໰୊Λߟ͑Δͱɼଟ͘ͷ৔߹ʹ໨తؔ਺͕ෳ਺ଘࡏ͠ɼ໨తؔ਺஋͸ϊΠζΛ‫ؚ‬Μ Ͱ͍Δɽ͜ͷ༷ͳ໰୊Ͱ͸ಉҰͷղΛ‫܁‬Γฦ͠ධՁ͢Δ͜ͱͰɼͦͷղͷྑ͠ѱ͠Λ൑அ͢Δඞཁ͕͋Δɽ ͦ͜Ͱɼ্‫ه‬ͷଟ਺໨త࠷దԽ໰୊Λର৅ͱͨࠩ͠෼ਐԽʢDEɿDifferential Evolutionʣʹ‫ͮ͘ج‬Ξϧΰ ϦζϜΛఏҊ͢ΔɽఏҊ͢ΔΞϧΰϦζϜͰ͸༧ଌ۠ؒͷ্‫ݶ‬஋ʹΑΔ U ΧοτͱɼΧοτΦϑ఺ʹΑΔ. C ΧοτʹΑΓɼྑ͘ͳ͍ղΛ൑ఆͯ͠αϯϓϦϯάΛதࢭ͢Δ͜ͱͰແବͳॲཧΛ࡟‫͍ͯ͠ݮ‬Δɽ. 1. ͸͡Ίʹ ‫࣮ݱ‬ͷੈքͰ͸༷ʑͳଟ਺໨త࠷దԽ໰୊͕ଘࡏ͠ɼͦ ͷଟ͕͘໨తؔ਺஋ʹϊΠζΛ‫ؚ‬ΜͰ͍Δɽ͜ͷͨΊɼಉ. n fm (x) = fm (x) + κ1 fm (x) ε1 + κ2 ε2. (1). n ࣜ (1) ΑΓɼfm (x) ͸ਖ਼‫ن‬෼෍ʹै͏ɽ n fm (x). ∼ N (μm (x), σm (x)2 ) = N (fm (x), κ21 fm (x)2 + κ22 ). ͡ղͰ͋ͬͯ΋ධՁ͢ΔͨͼʹҟͳΔ݁Ռ͕ಘΒΕΔɽ. (2). ຊߘͰ͸ɼϊΠζΛ‫ؚ‬Μͩෳ਺ͷ໨తؔ਺ʹ͍ͭͯɼͦ. ࣜ (1) ͷਖ਼‫ن‬෼෍ͷฏ‫ ۉ‬μm (x) ͱ෼ࢄ σm (x)2 ͸෼͔. ΕΒͷ࠷ѱͷ৔߹ͷ஋Λվળ͢Δ໰୊Λߟ͑Δɽ͢ͳΘ. Βͳ͍ɽͦ͜Ͱɼղ x Λ N ճධՁͯ͠ಘΒΕͨඪຊΛ. ͪɼղΛ‫܁‬Γฦ͠ධՁ͢Δ͜ͱͰ໨తؔ਺஋ͷ༧ଌ۠ؒΛ. 1 n N {fm (x), · · · , fm (x), · · · , fm (x)} ͱ͠ɼඪຊฏ‫ ۉ‬f m (x). ౷‫ֶܭ‬తʹ‫ٻ‬Ίɼͦͷ্‫ݶ‬஋Λ࠷খԽ͢Δɽ͜͜Ͱɼඇྼ. ͱෆภ෼ࢄ vm (x)2 Ͱ μm (x) ͱ σm (x)2 Λਪఆ͢Δɽ. ղͰ͋ͬͯ΋‫͔ͭز‬ͷ໨తؔ਺஋͕ඇৗʹѱ͍Α͏ͳ‫୺ۃ‬ ͳղ͸ෆཁͰ͋Δɽͦ͜Ͱɼ‫ͳ୺ۃ‬ղΛআͨ͘Ίɼଟ਺໨. f m (x) =. త࠷దԽ໰୊Ͱ͸໨తؔ਺஋ʹ੍໿৚݅Λઃఆ͢Δɽ ࣍ʹɼ্‫ه‬ͷଟ਺໨త࠷దԽ໰୊Λղͨ͘ΊʹਐԽ‫ࢉܭ‬. vm (x)2 =. ͷҰछͰ͋Δࠩ෼ਐԽʢDEɿDifferential EvolutionʣΛ༻ ͍ͨΞϧΰϦζϜΛఏҊ͢Δɽ֤໨తؔ਺ͷ༧ଌ۠ؒΛ‫ٻ‬. N 1 n f (x) N n=1 m. (3). N 1 n (f (x) − fm (x))2 N − 1 n=1 m. (4). ࣍ʹɼ͢Ͱʹ N ‫ݸ‬ͷ໨తؔ਺஋ͷඪຊ͕ಘΒΕ͍ͯΔ. ΊΔʹ͸ಉҰͷղΛԿ౓΋ධՁ͢Δඞཁ͕͋Δɽͦ͜Ͱɼ. N +1 ঢ়ଶͰɼ༗ҙਫ४ α ͱ͢ΔͱɼN + 1 ‫ݸ‬໨ͷඪຊ fm (x). ఏҊ͢ΔΞϧΰϦζϜͰ͸ɼ༧ଌ۠ؒͷ্‫ݶ‬஋ʹ‫ ͮ͘ج‬U. ͷ஋͸ɼ֬཰ (1 − α) ͰҎԼͷൣғʹ͋Δͱ༧ଌ͞ΕΔɽ. ΧοτͱɼΧοτΦϑ఺ʹΑΔ C ΧοτΛ༻͍ͯɼྑ͘ͳ ͍ղͰ͋Δͱ൑அͰ͖ͨ࣌఺ͰɼͦͷղͷධՁΛࢭΊΔɽ ͜ΕʹΑΓɼෆྑͳղͷධՁճ਺Λ࡟‫͍ͯ͠ݮ‬Δɽ. 2. ϊΠζΛ‫ؚ‬Μͩଟ਺໨త࠷దԽ໰୊ 2.1 ϊΠζΛ‫ؚ‬Μͩ໨తؔ਺. −∞. N +1 < fm (x) ≤ fm (x)+ . t(N − 1, α) vm (x). 1+. 1 U = fm (x) N. (5). 2.2 ໰୊ͷఆࣜԽ ܾఆม਺ x = (x1 , · · · , xj , · · · , xD ) Λ D ࣍‫ݩ‬ͷϕΫτ U (x) ͸ M ‫͢ͱݸ‬Δɽ·ͨɼ‫ͳ୺ۃ‬ղ ϧͱ͠ɼ໨తؔ਺ fm. n (x) Λࣜ (1) Ͱఆٛ ϊΠζΛ‫ؚ‬Μͩ໨తؔ਺ͷධՁ஋ fm. Λআͨ͘ΊʹɼΧοτΦϑ఺ γ = (γ1 , · · · , γM ) Λઃఆ͠. ͢Δɽfm (x) ͸໨తؔ਺஋ɼκ1 ͱ κ2 ͸ఆ਺ɼε1 ͱ ε2 ͸. ͯɼΧοτΦϑ఺Λ༏ӽ͢Δղ͸࣮ߦՄೳɼͦΕҎ֎ͷղ. ඪ४ਖ਼‫ن‬෼෍ʹै͏‫ʹ͍ޓ‬ಠཱͳ֬཰ม਺Ͱ͋Δɽ. Λ࣮ߦෆՄೳͱ͢Δɽ͜͜ͰɼຊߘͰର৅ͱ͢ΔϊΠζΛ. 1. 2. ۙ‫ـ‬େֶ૯߹ཧ޻ֶ‫ڀݚ‬Պ Graduate School of Science and Engineering Research, Kinki University ۙ‫ـ‬େֶཧ޻ֶ෦ School of Science and Engineering, Kinki University. c 2015 Information Processing Society of Japan . ‫ؚ‬Ήଟ਺໨త࠷దԽ໰୊Λࣜ (6) ͷΑ͏ʹఆࣜԽ͢Δɽ ⎡ U (x)) minimize f U (x) = (f1U (x), · · · , fM ⎣ (6) U subject to (x ∈ X) ∧ (∀m : fM (x) ≤ γ). 1.

(2) Vol.2015-MPS-102 No.19 2015/3/4. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ද 2 Convergence Measure. 3. DERʢDE with Resamplingʣ. DER. DER ͸ NP ‫ݸ‬ͷ‫ݸ‬ମ xiʢi = 1, · · · , NP ʣΛอ࣋͠ɼࣜ (6) ͷ࠷దԽ໰୊ͷղީิͱ͢Δɽ·ͨɼશͯͷ‫ݸ‬ମ xi Λ N ճධՁͯ͠ f U (x) Λ‫ٻ‬ΊΔɽ‫ੈݱ‬୅ͷूஂ͔Β࣍ੈ୅. DEUCR. M. 4. 6. 8. 4. 6. 8. DTLZ1. 0.64. 0.17. 0.15. 0.54. 1.38. 1.08. DTLZ2. 0.29. 0.39. 0.43. 0.29. 0.39. 0.42. DTLZ3. 0.30. 0.16. —. 0.33. 0.45. 0.12. ͷूஂΛબ୒͢Δࡍ͸ɼ࣮ߦՄೳͳ‫ݸ‬ମΛ༏ઌతʹબͼɼ. DTLZ4. 0.29. 0.39. 0.43. 0.29. 0.40. 0.42. ࢒ͬͨ‫ݸ‬ମ͸ NSGA-III[2] ͱಉ༷ʹ༏ӽؔ܎ʹ‫ͮ͘ج‬ϥϯ. DTLZ5. 0.30. 0.36. 0.37. 0.30. 0.35. 0.37. Ϋͱɼࢀর఺͔Βͷ‫ʹ཭ڑ‬Αͬͯબ୒͢Δɽ͞Βʹɼղͷ. DTLZ6. —. —. —. 0.48. —. —. ਫ਼౓Λ্͛ΔͨΊɼ֤ੈ୅Ͱ࣮ߦՄೳͳ‫ݸ‬ମͷΈ໨తؔ਺. ද 3 Maximum Spread. ஋ͷඪຊΛ 1 ͭͣͭ௥Ճͯ͠༧ଌ۠ؒΛ࠶‫͢ࢉܭ‬Δɽ. DER. 4. DEUCRʢDER with U-cut & C-cutʣ. DEUCR. M. 4. 6. 8. 4. 6. 8. DTLZ1. 1.48. 0.13. 0.01. 1.49. 2.01. 1.26. ఏҊ͢ΔΞϧΰϦζϜͰ͸ɼ༧ଌ۠ؒͷ্‫ ͮ͘جʹݶ‬U. DTLZ2. 1.69. 2.18. 2.58. 1.69. 2.18. 2.58. ΧοτͱɼΧοτΦϑ఺ʹ‫ ͮ͘ج‬C ΧοτΛ༻͍ͯɼྑ͘. DTLZ3. 1.10. 0.31. —. 1.69. 1.38. 0.43. ͳ͍‫ݸ‬ମʢղʣΛ൑ผ͠ɼͦͷධՁͷ‫܁‬Γฦ͠ΛࢭΊΔɽ. DTLZ4. 1.67. 2.14. 2.54. 1.66. 2.18. 2.54. ·ͨɼྑ͘ͳ͍‫ݸ‬ମͷ্‫ݶ‬஋͸ɼͦͷ࣌఺ͰಘΒΕ͍ͯΔ. DTLZ5. 1.35. 1.56. 1.69. 1.35. 1.56. 1.67. DTLZ6. —. —. —. 1.12. —. —. ඪຊ͔Β‫ٻ‬ΊΔɽ͜ΕʹΑΓɼྑ͘ͳ͍‫ݸ‬ମͷແବͳධՁ ΛলུͰ͖Δɽ·ͨɼDER ͱಉ༷ɼ֤ੈ୅Ͱ࣮ߦՄೳͳ. ද 4 Hypervolume. ‫ݸ‬ମͷΈඪຊΛ 1 ͭ௥Ճͯ͠༧ଌ۠ؒΛ࠶‫͢ࢉܭ‬Δɽ. M. 4. 6. 8. 5. ਺஋࣮‫ݧ‬. DTLZ1. . . . DTLZ2. —. —. —. DTLZ3. . . . DTLZ4. —. —. —. DTLZ5. —. —. —. DTLZ6. . —. —. DER ͱ DEUCR Λ༻͍ͯϊΠζΛ‫ ͨͤ·ؚ‬DTLZ1ʙ6 [3] Λղ͍ͨɽूஂͷ‫ݸ‬ମ਺ NP ͸ 120ɼΧοτΦϑ఺͸ γm = 1.0, ऴྃ৚݅͸‫ݸ‬ମͷධՁճ਺Λ 100 ສճͱͨ͠ɽ ໨తؔ਺ͷ਺ M ͸ 4ɼ6ɼ8 Λઃఆ͠ɼͦΕͧΕ 30 ճ࣮ ߦͯ͠ಘΒΕͨσʔλͷฏ‫ۉ‬Λൺֱ͢ΔɽධՁࢦ਺ʹ͸࣮ ߦՄೳղͷ਺ɼConvergence MeasureʢCMʣɼMaximum. SpreadʢMSʣɼHypervolumeʢHvʣ [4] Λ༻͍ͨɽ ද 1 ʹ࣮ߦՄೳղͷ਺ɼද 2 ʹ CM ͷ஋ɼද 3 ʹ MS ͷ஋ɼ. 6. ͓ΘΓʹ DER ͱఏҊͨ͠ DEUCR Λ 6 छྨͷςετ໰୊Ͱൺֱ Λߦ͍ɼDEUCR ͕༏Ε͍ͯΔ͜ͱΛ֬ೝͨ͠ɽ. ද 4 ʹ Hv ͷ݁ՌΛͦΕͧΕࣔ͢ɽද 1 ͔Β DEUCR ͷํ. ࠓ‫ޙ‬ͷ՝୊͸ɼΧοτΦϑ఺ͷऔΓํΛ޻෉ͯ͠ଟ༷ੑ. ͕ଟ͘ͷ࣮ߦՄೳղΛ‫ٻ‬ΊΒΕ͍ͯΔ͜ͱ͕෼͔ΔɽCM. ΛࣦΘͣʹΑΓྑ͍ղΛಘΒΕΔΑ͏ʹ͢Δ͜ͱͰ͋Δɽ. ͸‫ݸ‬ମͷྑ͞Λද͢ධՁࢦ਺Ͱ͋Δɽද 2 ͔Β DTLZ1ɼ. 3ɼ6 Ͱྑ͍݁Ռ͕ಘΒΕ͍ͯΔ͜ͱ͕෼͔ΔɽMS ͸ूஂ ͷଟ༷ੑͷධՁࢦ਺Ͱ͋Γɼද 3 ͔Β DTLZ1ɼ3 Ͱྑ͍݁ Ռ͕ಘΒΕ͍ͯΔ͜ͱ͕෼͔ΔɽHv ͸‫ݸ‬ମͷྑ͞ͱଟ༷. ࢀߟจ‫ݙ‬ [1]. ੑͷ྆ํΛධՁ͢Δ஋ͱͳ͓ͬͯΓɼද 4 ͸༗ҙਫ४ 0.05. tinuous spaces, Journal of Global Optimization, vol. 4,. ͰԾઆ‫ݕ‬ఆΛߦͬͨ݁ՌΛ͍ࣔͯ͠ΔɽDEUCR ͕ྑ͍݁ Ռ͕Ͱͨͱ͜Ζʹ Λ‫͍ͯ͠ه‬Δɽ. no. 11, pp. 341–359 (1997) [2]. K. Deb and H. JainɿAn evolutionary many-objective optimization algorithm using reference-point-based nondom-. ද 1 ࣮ߦՄೳղͷ਺. DER. R. Storn and K. PriceɿDifferential evolution - a simple and efficient heuristic for global optimization over con-. inated sorting approach, part 1: solving problems with. DEUCR. box constraints, IEEE transactions on evolutionary com-. M. 4. 6. 8. 4. 6. 8. DTLZ1. 110. 8.00. 0.07. 118. 115. 59.7. DTLZ2. 116. 119. 119. 117. 119. 119. DTLZ3. 70. 15.7. 0.00. 116. 75.1. 19.7. objective optimization, TIK-Technical Report, no. 112,. DTLZ4. 115. 119. 119. 115. 118. 119. pp. 1–27 (1981). DTLZ5. 104. 112. 116. 105. 110. 116. DTLZ6. 0.00. 0.00. 0.00. 91.2. 0.00. 0.00. putation, vol. 18, no. 4, pp577–601ʢ2014ʣ [3]. [4]. K. DebɿScalable test problems for evolutionary multi-. E. Zitzler:Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications, PhD thesis, Swiss Federal Institute of Technology, Zurich(1999). c 2015 Information Processing Society of Japan . 2.

(3)