成久洋之・太田真由美・谷口隆裕＊・片山謙吾

(1)

岡山理科大学紀要第41号Ａｐｐ５９－６８(2005）

戦略パラメータを使用しない効率的ＥＰについて

成久洋之・太田真由美・谷口隆裕＊・片山謙吾

岡山理科大学工学部情報工学科

*岡山理科大学大学院工学研究科情報工学専攻 (2005年９月30日受付、2005年11月７日受理）

要約

進化的計算法[1]の一つであるＥＰ(EvolutionaryProgramming)は関数最適化問題に対して有効な手法であると考えられている。このＥＰは解の探索幅と探索方向を規定するために戦略パラメータを使用している。本論文は戦略パラメータを使用しない指数型ＥＰ(nsEEP)を提案し、その有効性を検討したものである。数値実験の結果、この新手法はかなり効率的なものであることが判明した。

１はじめに

進化的プログラミング(Evolutiona正yProgramming;EP)[4]は遺伝的アルゴリズム(GeneticAlgorithm;GA）

などと同様に生物の進化の過程と自然の選択を模倣した最適化手法で、複雑で大規模な問題に対する解法としては極めて有効なものと考えられている。ＧＡもＥＰも個体集団(population)を形成し、集団で精度の良い最適近似解を求めようとする集団最適化手法であるが、ＧＡの主要演算(オペレータ)が交叉(crossover）

であるのに対し、ＥＰのそれは突然変異(mutation)のみ使用するものである。したがって、実数を主体とした乱数を使用した突然変異となるので機械的に処理しやすい利点が指摘されている。

ＥＰはＬＪ・Fbgelが人工知能に対するアプローチとして提案したもので、後にDBFogelによって最適化手法として開発されたものである。このＥＰはGaussMutation(Gauss分布に従う乱数を使用した突然変異により解を進化させるもの)を主体にしたものであり、これをＣＥＰと呼んでいる。[2][5]1965年に、Yao etaLはCauchyMutation(Cauchy分布に従う乱数を使用した突然変異により解を進化させるもの)を主

としたものを提案し、これをＦＥＰと呼んでいる。これらＣＥＰとＦＥＰとでは全般的にＦＥＰの方が有効なＥＰであるとみなされている。

2002年に、NanhisaetaLはExponentialMutation(複合指数分布に従う乱数を使用した突然変異により解を進化させるもの)を主体としたものを提案し、これをＥＥＰ(ExponentialEvolutionaryProgramming）

と呼んでいる。［7Ⅱ８１[９１[10]これは指数分布のパラメータを進化の状態に対応させて、初期段階では広域探索に、最適解の近傍に近づけば局所探索向けに制御しようとすることで進化の効率化を狙ったＥＰ手法である。これまでの研究では分布パラメータのとり方として、固定値をとるＦｉｘＥＥＰと分布パラメータを多段階に変動させるMulti-SwitchingEEPを提案し、ＣＥＰやＦＥＰに比較して有効なＥＰであることを示した。

さらに、分布パラメータを連続的に変動させるlinEEP(パラメータを線形に変動させる)やexpEEP(パラメータを指数関数的に変動させる）を提案し、それらの有効性を示してきた。

本論文は、従来のＥＰ手法で重視されている戦略パラメータを使用しないexpEEP(これをnsEEPと呼ぶ)を新規に提案し、その有効性につき検討したものである。

２指数型進化的プログラミング(EEP）

ＥＥＰは分布パラメータ入に従う複合指数乱数Ｅ(0,入)を使用した突然変異(exponentialmutation)によ

り解を進化させるアルゴリズムであり、その概要は次のとおり。

Stepl（初期個体集団の生成)：似個のｎ次元実数ベクトル対(⑳jβ`),ｉ＝1,2,…,似を生成する．

Step２（各個体の適応度評価)：ノ(Ｚ｡),ｉ＝1,2,…,似を計算する．

(2)

成久洋之・太田真由美・谷口隆裕・片山謙吾

6０ Step３（子孫の生成)：各個体(qEjm)から単一の子孫(z'@β'`）を次のように生成する．

グィ(j)＝o,(氷zp[γ'１V(0,1)＋γＭ(0,1)]，（１）

ｚｌ(j)＝z`(j)＋◎;(j)Ej(0,入)，（２）

ｉ＝1,2,…,似，ｊ＝１，２，…,、

ただし、ｚ`(j),⑰!(ルヮ`(j),ひ!(j）はそれぞれ、ベクトル⑰`,⑰'@,ヶ,,ヮ'`のｊ番目の成分を示す．

Ⅳ(0,1)は正規乱数(平均=0,標準偏差=1)を表しｊＶ)(0,1)は各ｊ毎に新たに乱数を発生させるものである.γ＝(,/ﾖﾜﾃﾃ)-1,γ'＝(何)-1とするＥ(0,入)はパラメータ入の複合指数乱数(平均=0,分散＝急)を示し､Ｅｊ(0,入)はｊ毎に新規に乱数を発生させることを意味する．

Step４（子孫の適応度評価)：子孫(⑳'`β'｡)における/(､'`),ｊ＝1,2,…,似を計算する．

Step５（各個体のトーナメント評価)：２似個の親と子孫｛(､ｉｎ),(z'@,ヶ'`)｝,ｉ＝1,2,…,似の中から任意の９個をランダムに選ぶ．これらの９個の、ベクトルをｓ1,82,…,ｓ９とする.ノ(鰯)ニノ(SIC)であれば個体(⑪､,仇)は勝ち点１点を取得する.すべてのj(i＝1,2,…,2似)について、１６＝1,2,…,９の比較

を行う．

Step６（次世代の親の選択)：Step5での勝ち点の多い方から似個選択し次世代の親とする．

Step７(停止・続行判定)：終了条件を満たせば処理停止,そうでなければStep2へ戻る．

３ＥＥＰにおける入の決定法

ＥＥＰは複合指数乱数による突然変異を使用するので、指数分布におけるパラメータ入の値がその収束特性に多大の影響を与える。これまでの研究では次のようなものを検討してきた。

（１）固定値：入の値を全進化世代で一定値に固定する。（FixEEP）

（２）多段階変動値：全進化世代で入を複数回変動させ、世代が進むにつれ入の値を増大させる。（Multi‐

SwitchingEEP）

（３）増加関数値：入の値を世代９の増加関数として与えるもので、これには線形関数入Ｌと指数関数入Ｅ

とがある。

入L=入』+A2=入'９ ^（３）

ハ画一MpI(加美)≦’い）

ただし、入，は入の初期値、Ａ２は入の最終値、Ｇは全進化世代をそれぞれ示すものとする。入として入Ｌを使用するものをlinEEP、ＡＥを使用するものをexpEEPと呼んでいる。入の値として増加関数を考えることで入Ｌおよび入Ｅを使用した場合、入のパラメータ値として入１と入２のみを設定すればよく、ＥＥＰにおけるパラメータ数を減少させ得る利点がある。このことは、最適化アルゴリズムという観点から極めて望ましいことである。

４expEEPにおける入の役割

ＥＥＰアルゴリズムにおけるStep3での(1)、(2)から

ｚ;(j)＝z`(j)＋⑩(j)Ej(0,入)ezp[T'Ⅳ(0,1)＋ＴＪＶｊ(0,1)］

として子孫ｚ;(j)が生成される。ここでＥｊ(0,入）として、(4)の入Ｅを使用するとｚｌ(j)＝z`(j)＋⑱(j)Ej(0,1)s，

＆-÷｡”[(－m(芸))≦+ｱw(0,,)+了,v川

(5)

(6)

(3)

戦略パラメータを使用しない効率的ＥＰについて ^6１

として表せる。本来(5)における

び`(j)Ｅｊ(0,入)ezp[ＴＷ(0,1)＋γＭ(0,1)］

は自己適応機能(selfLadaptivity)と呼ばれているもので､進化の状況に応じて減少しているものである。した

がって､(6)のＳにおける(-m(蓋))急が７Ｗ(0,1)+γＭ(0,1)の値に連動したものでなければＥＰにおけ

る自己適応機能を弱めることになる。このことから、ＥＰにおけるこれらの機能を補強するような入1,入２でなければ､ＥＥＰの効率化は期待できないことになる。戦略パラメータとしての。‘(j)は進化が進むにつれて小さくなる特性を持ち、これは指数的減少傾向を示している。実際の数値計算では局所解に陥ることを避ける

ため､その下限Eを設定し､。〈〔であれば。＝〔として計算させている｡一方､士＝☆e叩[(-hm(砦))き］

も指数関数的に減少し、ｃにおいては士となる｡そこで､(6)式における自己適応機能を満足させるよう

な、入,内を決定することは実験的に求めるにしてもかなり労力を必要とすることから、囚(j)を抜きにした入,,入２の適当値を探す方が労力は少なくて済むのではないかとも考えられる。

５戦略パラメータなしのexpEEP(nsEEP）

前節における考え方に基づき、分布パラメータ入として、入＝入Ｅとした戦略パラメータを使用しない expEEPをnsEEPと呼び、次のようなnsEEPアルゴリズムを提案する。

Stepl似個の初期個体集団(鋤),ｊ＝1,2,…,似,ｇｃｊｅＲｎを生成する．

Step2ノ(鋤),ｊ＝1,2,…,似を計算する．

Step３各個体、Zから単一の子孫Ｚ'@を次のように生成する．

z;(j)＝鰯(j)＋Ｅｊ(0,入）

Ｅ,(oルナiE,(0,,）

形入川[(､'芸))≦］ ⁽⁷⁾

i＝1,2,…,似，ｊ＝１，２，…,、

Step4ノ(q，'@),ｊ＝1,2,…,似を計算する．

Step５９トーナメント選択により、｛Uac`}Ｕ{Uz'`｝から似個の個体を選び次世代の親とする．

Step６終了条件を満たせば処理停止,そうでなければStep2へ戻る．

(4)

成久洋之・太田真由美・谷口隆裕・片山謙吾 6２

６数値実験 6.1対象問題

本研究での対象問題は、この分野の最適化問題としてよく知られているベンチマーク問題とし、表１で与えた１２問題とする。

表１適用問題

Ｅｕ几ｎＵ

凡Ｏ０００ｎＵ００冊０００

呵竺１人

［-600600]3ｏ

6.2実験要領

（１）個体集団数：似＝100

（２）トーナメントサイズ：９＝１０

（３）進化世代数：Ｇ＝5000

（４）適応度：100runsの平均

（５）分布パラメータ入：入,＝5.0×10-2ルー5.0×１０１０ (6)性能比較のために使用するCEP、ＦＥＰのパラメータ

Ｅ＝ヮの下限＝ｍ－４

なお、びの上限は１．０とする．

(7)実験環境

ＩｎｔｅｌＰｅｎｔｉｕｍ４ＣＰＵ２５３ＧＨｚＲＡＭ２５６ＭＢ

Ｔｂｓｔ]Rmction Ｓん

^Ｚね

/,(z）

^￣^￣

Ｚ ^３０ ^`＝１ z； -100,100 ^3０ ^０

九(z）

^￣^￣

Ｚ ^3０ j＝１Ｚ。＋ ^３０Ｚ＝１Ｚｉ－１０，１０ ^3０ ⁰ 九(z）

^￣^￣

E淫,(Ｚ ^０ ^j＝１ ^Zｊ ^） ^２ [-100,100］ ^3０ ⁰

八(z） ^{＝ｎＺｑＺ} ｛ ^Ｚ‘ ’１≦'三30｝ [-10o,100］ ^０

九(z）

^－^－

Ｚ ^2９ ^i＝１ 1100（ ^、 ^ｚ＋１ ^－ｍ ;)2＋(zｉ ^1） ^２－３０，３０ ^3０ ⁰

九(z）

^￣^{■■■■■■■}

Ｚ ^３０ ^`＝１ (Izi＋０５｣） ^２－１CO,10o］ ^3０ ⁰

乃(z）

^{■■■■■■■}^￣

工 ^３０． j＝１ ^ZＺ４

Ｚ

＋ｒａｎｄｏｍ U’1）－１．２８，１２８ ^3０ ^０九(z）

^－－^￣

Ｚ｡＝１ ^3０ (z`smMF7 )） -500,500 ^3０ ^-12569.5 /b(麺）

^￣^￣

Ｚ ^3０ ^j＝１ ^⑳ ^２

^Ｚ

10ＣＯＳ(2汀z`)＋1０ -5.12,5.12 ^3０ ⁰ /,o(z)＝-20eｚｐ ^－２０ ,／ ^3０ ^１ ^Ｚ ^`＝1 ^3０ ^Ｚ ^２ ^０１－ezp[売乙聖,cos2川]＋20＋ｅ ^[-32,32］ ^3０ ⁰

/,,(z）

^￣^￣

4000 ^１Ｚ ^３０｡＝１ ^Ｚ２

Ｚ Ⅱ ^３０｡＝１ ^ＣＯＳ三▲

､/５ )＋１ -600,600 ^3０ ⁰

/'2(Z)＝：{1Osin2(剛)＋Ｚ ^〃-１ ^｡＝１ ^(y。 1)2[1＋l0Sjn2(剛十,)]＋(Zﾉ施

+Ｚ廷,u(z'’'0,100,4)，ｚ/`＝’＋i(z`＋'） ^1)2｝ ^[-50,501

3００

(5)

_タを使用しない効率的ＥＰについて

戦略パラメ ^6３

７実験結果とその考察本論文で提案した戦略バラを表２に示す。

メータを使用しないＥＥＰとしてのnsEEPを関数最小化問題に適応した結果表２最終世代での関数値

宝－１２４３７．６８９８９ ^0087222395 ^{１５３２９７４３１８} １１．３０４３８６２３

表２は、nsEEPの収束解を示すが、参考のために従来のＥＰ手法としてのＣＥＰおよびＦＥＰを適用した場合の収束解をも表示した。この結果、１２問中10間においてnsEEPが最良解を得ており、ＣＥＰとＦＥＰがそれぞれ１個の最良解となっている。特に、nsEEPはノ,からんでの単峰性関数においてはすべての問題に対して最良解を得ている。しかも、/１，ノ2,九,ノｌｏおよびノ１２に対してはＣＥＰやＦＥＰに比較にならないくらいの精度の良い解となっていることがわかる。

表３は、5000世代までの処理時間を示す。ただし、単位は秒とする。

表３処理時間の比較

nsEEPは個体として戦略パラメータを含まないので各世代の進化において、そのための進化処理が不必要となる。このことから、少なくとも台以上の処理時間の短縮は期待しうるものであったが、表３に示す

ようにCEPやFEPに比較して；から；の処理時間となっている。

以上の実験結果より、nsEEPは分布パラメータ（入1,A2）について、入,＝5.0×１０~2ルー５．０×１０１０とセットするだけで、従来のＣＥＰやＦＥＰに比較して極めて効率的なＥＰアルゴリズムであるといえる。

ＣＥＰＦＥＰ nｓｎｎＰ

/， 0.000127883 0.117415256 ４．７６１３８Ｅ-２０

九 0.037526577 0.982577878 ９．５２６４７Ｅ-１０九 2.698873419 15.32974318 ０．０６２１４０４９ /４ 15.82811054 0.087222395 ９．３５５６４Ｅ-１１九 86.37205982 96.95708171 4２．０８８６４９１４

九 ^170.5788 ^0.3533 ^０

/７ 0.060257634 0.122782395 ０．０１６９５０５５７九 -7326263085 -１２４３７．６８９８９ -8908.172791 九 1１．３０４３８６２３ 27.20929974 48.29853828 /,ｏ 1.361045781 0.364342106 1.59959Ｅ-１０ A1 0.177531732 0.018376979 ０．００５４６８７９１

A２ ^1.28601905 ^0.0008712 3.14684Ｅ-２２

ＣＥＰＦＥＰ nRF】、Ｐ

/， ¹⁰⁹¹ ^1０１５ ¹⁹⁵

九 ¹¹⁰⁸ ¹⁰³³ 207

九 ¹³⁷⁰ ¹²⁹⁶ 417

九 ^1１１８ ¹⁰³³ 206

九 ¹¹⁰³ ¹⁰³⁰ 208

九 ^1２１６ ^1１４１ ²⁸¹

/７ ¹⁰⁹² ¹⁰²⁴ 196

ん ¹³⁴⁰ ¹²⁷³ ³⁶⁷

九 ¹²⁸² ¹¹⁹³ ³³⁴

八ｏ ¹²⁹⁸ ¹²⁰⁶ ³⁴³

八， ¹³²³ ¹²⁷⁵ ³⁶⁶

ｈ２ ¹³⁷⁰ ¹²⁸⁶ ⁴¹⁶

(6)

成久洋之・太田真由美・谷口隆裕・片山謙吾 6４

なお、図１から図１２において各関数の収束特性を示す６図１はノ，に対する収束特`性を示すものである。nsEEPはほとんど全世代を通じてほぼ同じ収束率を示している。800世代まではＦＥＰの方が良いが、

最終的にはＦＥＰは最悪となっている。これは如実にＣＥＰとＦＥＰの収束特性を表しているものといえる。

すなわち、CauchyMutationはGaussianMutationに対して探索率が大きいがために進化の初期段階では威力を発揮するが、終期の段階では、親と子孫との距離が親と最適解との距離を超過している結果といえる。図４はたの収束特性を示すが、nsEEP,FEP,ＣＥＰの順によい収束特性となっている。図５はたの収束特性を示すが、1000世代以降においてnsEEPが他を凌駕している。図６はたの収束特性を示すが、

1038世代で最適解に収束している。図７はノ７の収束特性を示すが、nsEEPにおいて200～1000世代で stagnationが見られるものの、それ以降は良好な収束を実施している。図８、図９はそれぞれ/8,九の収束特性を示すが、図８ではＦＥＰがbestで、図９ではＣＥＰがbestな収束を表している。図１０、図１２においては、nsEEPは全世代を通じて一貫した収束状況を示している。図１１では、nsEEPの収束は1500世代以降において飽和状況を示しているが、最終解はnsEEPが良い結果を表している。九に対しては2000世代、九に対しては1500世代、方に関しては2500世代、たに対しては500世代、ノｂに対しては1500世代以降において、nsEEPの収束は飽和状況を示しており、分布パラメータ入の値が大きすぎていることを示している。すなわち、それらの各世代で局所解に陥っているものと考えられる。

参考文献

[1]TBackandH-PSchwefel,'，AnoverviewofevolutionaryalgorithmsfOrparameteroptimization''，

Evolution虹yComputation,１(1):ppl-23,1993．

[2]XYao,YLiu,，，脇tEvolutionaryProgramming，，,Proc､ofthe5thAnnualConferenceonEvolutioL aryProgramming,ＭＩＴPress,pp451-460,1996．

[3]Ｋ､-HLiang,XYao,YLiu,ONewtonandDHofIinan,''AnExperimentallnvestigationofSelfadaD tationinEvolutionaryProgramming，，，Procofthe7thAnnualConferenceonEvolutionampyPro‐

gramming,Springer-Verla,pp291-300,1998．

[4]KChellapilla,，'CombiningMutationOperatorsinEvolutionmyProgramming，',IEEETYansactions onEvolutionaJFyComputation,２(3),ｐp91-96,1998

[5]XYao,YLiu,ＧＬｉｎ,，'EvolutionaJ｢yProgrammingMaderhster，，,IEEEIransactionsonEvolution‐

aryComputation,３(2),ｐp82-102,1999．

[6]O-YLeeandYsong,，，EvolutionaryProgrammingusingtheLevyprobabilityDistribution，，,Proc、

ofGeneticandEvolutionaryComputationConference(GECC0,99),MorganDaufman,pp886-893,

19998

[7]KKohmoto,HNaJFihisa,KKatayama,'，EvolutionaryProgrammingUsingExponentialMutation''，

Proc､ofthe6thWOrldMulticonferenceonSystematics,Cyberneticsandlnfbrmatics,vol11,Com- puterScience2,Julyl4P18，ＵＳＡ,pp405-410,2002.

[8]HNarihisa,KKohmotoandKKatayama,，'EvolutionaryProgrammingwithDoubleExponential ProbabilityDistribution，，，Proc・oftheSecondlnternationalAssociationofScienceandTbchnol- ogyfbrDevelopment(IASTED)InternationalConferenceonArtificiallntelligenceandApplications

（AIA2002),ｐp358-363,2002

[９１KKohmoto,HNaJFihisaandKKatayama,'，PERFORMANCEOFEVOLUTIONARYPROGRAM‐

ＭＩＮＧＵＳＩＮＧＥＸＰＯＮＥＮＴＩＡＬＭＵＴｙｌＴＩＯＮ，，，Proc,ｏｆＴｈｅ４ｔｈＡｓｉａ戸PacificConferenceonSimuP

latedEvolutionAndLearning(SEAL2002),vol2,ｐp454-458,2002.

(7)

戦略パラメータを使用しない効率的ＥＰについて 6５

[10]HNarihisa,KKohmoto,TKumonandKKatayama,，，PerfOrmanceofExponentialEvolutionary Programming'，，Proc，ofthe7thIASTEDInternationalCon化renceonArtificiallntelligenceand SoftComputing(ASC2003),ｐp243-248,2003.

[11]HNarihisa,KKohmoto,MTsuda,KKatayama,''CONVERGENCECHARACTEmSTICSOF EXＰＯＮＥＮＴＩＡＬＥＶＯＬＵＴＩＯＮＡＲＹＰＲＯＧＲＡＭＭＩＮＧ，，，Proc、ofthe8thlASTEDInternational ConferenceonArtificiallntelligenceandSoftComputing(ASC2004),ｐp426-431,2004

[12]HNarihisa,Ｔ､TbLniguchi,MThudaandKKat印ama,，'EfliciencyofPaJ『allelExponentialEvolution‐

aryProgramming，，，Proc・ofthe20051ntemationalconferenceonParallelProcessingWOrkshops，

pp585-595,2005.

[13]HNarihisa,Ｔ､Ianiguchi,MDhtaandKKatayama,'，EVOLUTIONARYPROGRAMMINGWITH

EXPＯＮＥＮＴＩＡＬＭＵＴＡＴＩＯＮ，，，Proc・oftheNinthlASTEDInternationalConferenceonARTIFI-

CIALINTELLIGENCEANDSOFTCOMPUTING(ASC2005),ｐｐ55-60,2005.

(8)

成久洋之・太田真由美・谷口隆裕・片山謙吾 6６

1.0Ｅ+0０５ 1.0Ｅ+０２５

１．０E+Ｏ２０

１０Ｅ+０１５ＣＥＰ－－

ＦＥＰ－←

nｓＥＥＰ－

ＣＥＰ－－

ＦＥＰ－←

nｓＥＥＰ－

ＣＥＰ－－

ＦＥＰ－←

nｓＥＥＰ－

1.0Ｅ+０００

１０E-OO5

ｕｎｌＯＥ+Ｏ１０

ｎｑＤ

ＥＬ１．０Ｅ+００５

飼い①巨猩」

１０E-O10

1.0Ｅ+０００

１.OE-005

iOE-O10 1.ＯＥ－Ｏ１５

1.0E-O20

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ GenemIion

図１/,の収束特'性

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ Gene埴tion

図２ノ２の収束特`性

1.0Ｅ+OO7 10E+００６

１．０Ｅ+ＯＯ５

１０Ｅ+OO4

10E+００３

１．０E+OO2

10E+００１

１．０E+０００

１．０E-OO1

１.OE-OO2

1.0Ｅ+002

1.0E+０００

1.0E-OO2

１.OE-004

l0E-OO6

１.OE-OO8

１０E-O10

１.OE-O12

､鳶三

ＣＥＰ－－

ＦＥＰ－←

nｓＥＥＰ－

ＣＥＰ－－

ＦＥＰ－←

nｓＥＥＰ－

⑪⑬①巨轌」

凹吻⑩巨窪」

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ Genemtion

図３/３の収束特`性

Ｏ５００１０００１５００２０００２５００３０００３５００４ＯOO45OO5OOO Generation

図４/4の収束特‘性

噸唾”噸噸幽噸唖呵

＋＋＋

ＥＥＥＢＥＳＥＥＥ

＋＋＋＋

０００００００００１１１１１１１１１

⑬⑪①Ｅ」

噸・魎幽皿皿呵魎呵唖

十十十十十十十

に叱肥に吃肥肥肥に

１１１１１１１１１

⑪⑱①眉匡

ＣＥＰ－－

ＦＥＰ一一一 nｓＥＥＰ－

ＣＥＰ－ＦＥＰ→－

nｓＥＥＰ－

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ Genemtion

図５．Ajの収束特性

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ Gene冠Iion

図６/６の収束特`性

(9)

戦略パラメータを使用しない効率的ＥＰについて 6７

００

００血唖皿血血皿皿

２

２卦６８０２４

１１１

1.0Ｅ+003

ｎｓＥＥＰ－時＝Ｅ

ＣＥＰ－－

ＦＥＰ－－

ｎｓＥＥＰ－

1.0Ｅ+００２

1.0E+００１

_{、的①Ｅ』」}

山切⑩Ｅ一一」

1.0Ｅ+０００

1.OE-OO1

1.ＯＥ－ＯＯ２

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ Genemtion

図８/８の収束特性

Ｏ５００１０００１５００２０００２５００３０００３５ＯＯ４ＯOO45OO5OOO Genemtion

図７ノ7の収束特`性

１０Ｅ+002 1.0Ｅ+００３

ＣＥＰ－－

ＦＥＰ－－

ｎｓＥＥＰ－

１０Ｅ+０００

1.OE-OO2 ＣＥＰ－－

ＦＥＰ－－

ｎｓＥＥＰ－

ＣＥＰ－－

ＦＥＰ－－

ｎｓＥＥＰ－

ｎｍの匡起」

、（〃

：１０E+OO2

LL

1.ＯＥ－ＯＯ４

1.OE-OO6

1.OE-OO8

1.OE-O10 1.0Ｅ+001

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ Gene旧tion

図９ノ９の収束特`性

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５OOO Genemtion

図１０ノ,ｏの収束特'性

1.0Ｅ+０１０

１．０E+００５

１．０E+OOO

iOE-OO5

１０E-O10

１０E-O15

１.OE-O20

１.OE-O25 1.0Ｅ+００３

ＣＥＰ－

ＦＥＰ－－

ｎｓＥＥＰ－

1.0E+００２

1.0Ｅ＋0０１

、⑪①巨毒」

飼切の巨君」

1.0Ｅ＋０００

1.OE-OO1

1.OE-OO2

1.OEPOO3

５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ Gene厄tion

図１１ノ,，の収束特`性

００５００１０００１５００２０００２５００３０００３５００４００O45OO5OOO

Gene埴tion

図１２ノ１２の収束特性

(10)

成久洋之・太田真由美・谷口隆裕・片山謙吾

6８ ＡｎＥ田cientEvolutionaryProgramming VVithoutUsingStrategyParameter

HiroyukiNarihisa,MayumiOhta，

HirotakaTaniguchi＊andKengoKatayama

Depqm7Dentq/１，/b7wDatjonqndCDmPuterEn9meerz､９，

FhcultZ/ｑｆＥ"gmeemn9，

掌G7MuqteSchooJq/En9inee7wB9，

ＯＡＤｑｙｑｍｑ【ﾉｹDITﾉeMt1/ｑ/Science，

Ｌ１ＲＭｑｊ－ｃﾉto，Okq9qmq，700-0005,Ｊ〃ａｎ (ReceivedSeptember30,2005;acceptedNovember7,2005）

EvolutionaryProgrammingwhichusesonlymutationoperatorisconsideredtobean eflicientapproachtosolvefilnctionoptimizationproblems・Conventionally,Evolutionary ProgrammingusesstrategyparameterfbrselfLadaptationoffimctionoptimization、

Inthispaper,wepresentaneHicientnewEPalgorithmwithoutusingstrategyparame- terbyadoptmgexponentialdistributionparameterofEEPEssentially,EEP(Exponential EP)usesexponentialmutationEEPneedstodetermineappropriatedistributionpamme- tervalueOurnewlyproposedEP(nsEEP)providesasimilarroleasconventionalstrategy parameterbyusingappropriaLeexponentialdistributionparametervalue・Ｔｈｅｒｅsultsof numericalexperimentsshowthatnsEEPoutperfbrmsconventioｎａｌＥＰａｌｇｏｒｉｔｈｍｓｕｃｈａｓ

ＣＥＰａｎｄＦＥＰ．

成久洋之・太田真由美・谷口隆裕＊・片山謙吾

岡山理科大学紀要第41号Ａｐｐ５９－６８(2005）

戦略パラメータを使用しない効率的ＥＰについて

成久洋之・太田真由美・谷口隆裕＊・片山謙吾

岡山理科大学工学部情報工学科

*岡山理科大学大学院工学研究科情報工学専攻 (2005年９月30日受付、2005年11月７日受理）

要約

１はじめに

進化的プログラミング(Evolutiona正yProgramming;EP)[4]は遺伝的アルゴリズム(GeneticAlgorithm;GA）

であるのに対し、ＥＰのそれは突然変異(mutation)のみ使用するものである。したがって、実数を主体と した乱数を使用した突然変異となるので機械的に処理しやすい利点が指摘されている。

としたものを提案し、これをＦＥＰと呼んでいる。これらＣＥＰとＦＥＰとでは全般的にＦＥＰの方が有効な ＥＰであるとみなされている。

2002年に、NanhisaetaLはExponentialMutation(複合指数分布に従う乱数を使用した突然変異によ り解を進化させるもの)を主体としたものを提案し、これをＥＥＰ(ExponentialEvolutionaryProgramming）

さらに、分布パラメータを連続的に変動させるlinEEP(パラメータを線形に変動させる)やexpEEP(パラ メータを指数関数的に変動させる）を提案し、それらの有効性を示してきた。

本論文は、従来のＥＰ手法で重視されている戦略パラメータを使用しないexpEEP(これをnsEEPと呼 ぶ)を新規に提案し、その有効性につき検討したものである。

２指数型進化的プログラミング(EEP）

ＥＥＰは分布パラメータ入に従う複合指数乱数Ｅ(0,入)を使用した突然変異(exponentialmutation)によ

り解を進化させるアルゴリズムであり、その概要は次のとおり。

Stepl（初期個体集団の生成)：似個のｎ次元実数ベクトル対(⑳jβ`),ｉ＝1,2,…,似を生成する．

Step２（各個体の適応度評価)：ノ(Ｚ｡),ｉ＝1,2,…,似を計算する．

成久洋之・太田真由美・谷口隆裕・片山謙吾

6０

Step３（子孫の生成)：各個体(qEjm)から単一の子孫(z'@β'`）を次のように生成する．

グィ(j)＝o,(氷zp[γ'１V(0,1)＋γＭ(0,1)]，（１）

ｚｌ(j)＝z`(j)＋◎;(j)Ej(0,入)，（２）

ｉ＝1,2,…,似，ｊ＝１，２，…,、

ただし、ｚ`(j),⑰!(ルヮ`(j),ひ!(j）はそれぞれ、ベクトル⑰`,⑰'@,ヶ,,ヮ'`のｊ番目の成分を示す．

Step４（子孫の適応度評価)：子孫(⑳'`β'｡)における/(､'`),ｊ＝1,2,…,似を計算する．

を行う．

Step６（次世代の親の選択)：Step5での勝ち点の多い方から似個選択し次世代の親とする．

Step７(停止・続行判定)：終了条件を満たせば処理停止,そうでなければStep2へ戻る．

３ＥＥＰにおける入の決定法

ＥＥＰは複合指数乱数による突然変異を使用するので、指数分布におけるパラメータ入の値がその収束特 性に多大の影響を与える。これまでの研究では次のようなものを検討してきた。

（１）固定値：入の値を全進化世代で一定値に固定する。（FixEEP）

（２）多段階変動値：全進化世代で入を複数回変動させ、世代が進むにつれ入の値を増大させる。（Multi‐

SwitchingEEP）

（３）増加関数値：入の値を世代９の増加関数として与えるもので、これには線形関数入Ｌと指数関数入Ｅ

とがある。

入L=入』+A2=入'９ （３）

ハ画一MpI(加美)≦’い）

４expEEPにおける入の役割

ＥＥＰアルゴリズムにおけるStep3での(1)、(2)から

ｚ;(j)＝z`(j)＋⑩(j)Ej(0,入)ezp[T'Ⅳ(0,1)＋ＴＪＶｊ(0,1)］

として子孫ｚ;(j)が生成される。ここでＥｊ(0,入）として、(4)の入Ｅを使用すると ｚｌ(j)＝z`(j)＋⑱(j)Ej(0,1)s，

＆-÷｡”[(－m(芸))≦+ｱw(0,,)+了,v川

(5)

(6)

戦略パラメータを使用しない効率的ＥＰについて 6１

として表せる。本来(5)における

び`(j)Ｅｊ(0,入)ezp[ＴＷ(0,1)＋γＭ(0,1)］

は自己適応機能(selfLadaptivity)と呼ばれているもので､進化の状況に応じて減少しているものである。した

がって､(6)のＳにおける(-m(蓋))急が７Ｗ(0,1)+γＭ(0,1)の値に連動したものでなければＥＰにおけ

ため､その下限Eを設定し､。〈〔であれば。＝〔として計算させている｡一方､士＝☆e叩[(-hm(砦))き］

も指数関数的に減少し、ｃにおいては士となる｡そこで､(6)式における自己適応機能を満足させるよう

な、入,内を決定することは実験的に求めるにしてもかなり労力を必要とすることから、囚(j)を抜きにし た入,,入２の適当値を探す方が労力は少なくて済むのではないかとも考えられる。

５戦略パラメータなしのexpEEP(nsEEP）

前節における考え方に基づき、分布パラメータ入として、入＝入Ｅとした戦略パラメータを使用しない expEEPをnsEEPと呼び、次のようなnsEEPアルゴリズムを提案する。

Stepl似個の初期個体集団(鋤),ｊ＝1,2,…,似,ｇｃｊｅＲｎを生成する．

Step2ノ(鋤),ｊ＝1,2,…,似を計算する．

Step３各個体、Zから単一の子孫Ｚ'@を次のように生成する．

z;(j)＝鰯(j)＋Ｅｊ(0,入）

Ｅ,(oルナiE,(0,,）

形入川[(､'芸))≦］ (7)

i＝1,2,…,似，ｊ＝１，２，…,、

Step4ノ(q，'@),ｊ＝1,2,…,似を計算する．

Step５９トーナメント選択により、｛Uac`}Ｕ{Uz'`｝から似個の個体を選び次世代の親とする．

Step６終了条件を満たせば処理停止,そうでなければStep2へ戻る．

成久洋之・太田真由美・谷口隆裕・片山謙吾 6２

６数値実験 6.1対象問題

本研究での対象問題は、この分野の最適化問題としてよく知られているベンチマーク問題とし、表１で与 えた１２問題とする。

表１適用問題

凡Ｏ０００ｎＵ００冊０００

［-600600]3ｏ

6.2実験要領

（１）個体集団数：似＝100

（２）トーナメントサイズ：９＝１０

（３）進化世代数：Ｇ＝5000

（４）適応度：100runsの平均

（５）分布パラメータ入：入,＝5.0×10-2ルー5.0×１０１０ (6)性能比較のために使用するCEP、ＦＥＰのパラメータ

Ｅ＝ヮの下限＝ｍ－４

なお、びの上限は１．０とする．

であるのに対し、ＥＰのそれは突然変異(mutation)のみ使用するものである。したがって、実数を主体とした乱数を使用した突然変異となるので機械的に処理しやすい利点が指摘されている。

としたものを提案し、これをＦＥＰと呼んでいる。これらＣＥＰとＦＥＰとでは全般的にＦＥＰの方が有効なＥＰであるとみなされている。

2002年に、NanhisaetaLはExponentialMutation(複合指数分布に従う乱数を使用した突然変異により解を進化させるもの)を主体としたものを提案し、これをＥＥＰ(ExponentialEvolutionaryProgramming）

さらに、分布パラメータを連続的に変動させるlinEEP(パラメータを線形に変動させる)やexpEEP(パラメータを指数関数的に変動させる）を提案し、それらの有効性を示してきた。

本論文は、従来のＥＰ手法で重視されている戦略パラメータを使用しないexpEEP(これをnsEEPと呼ぶ)を新規に提案し、その有効性につき検討したものである。

ＥＥＰは複合指数乱数による突然変異を使用するので、指数分布におけるパラメータ入の値がその収束特性に多大の影響を与える。これまでの研究では次のようなものを検討してきた。

入L=入』+A2=入'９ ^（３）

として子孫ｚ;(j)が生成される。ここでＥｊ(0,入）として、(4)の入Ｅを使用するとｚｌ(j)＝z`(j)＋⑱(j)Ej(0,1)s，

戦略パラメータを使用しない効率的ＥＰについて ^6１

な、入,内を決定することは実験的に求めるにしてもかなり労力を必要とすることから、囚(j)を抜きにした入,,入２の適当値を探す方が労力は少なくて済むのではないかとも考えられる。

形入川[(､'芸))≦］ ⁽⁷⁾

本研究での対象問題は、この分野の最適化問題としてよく知られているベンチマーク問題とし、表１で与えた１２問題とする。

Ｔｂｓｔ]Rmction Ｓん

Ｚ ^３０ ^`＝１ z； -100,100 ^3０ ^０

Ｚ ^3０ j＝１Ｚ。＋ ^３０Ｚ＝１Ｚｉ－１０，１０ ^3０ ⁰ 九(z）

E淫,(Ｚ ^０ ^j＝１ ^Zｊ ^） ^２ [-100,100］ ^3０ ⁰

八(z） ^{＝ｎＺｑＺ} ｛ ^Ｚ‘ ’１≦'三30｝ [-10o,100］ ^０

Ｚ ^2９ ^i＝１ 1100（ ^、 ^ｚ＋１ ^－ｍ ;)2＋(zｉ ^1） ^２－３０，３０ ^3０ ⁰

Ｚ ^３０ ^`＝１ (Izi＋０５｣） ^２－１CO,10o］ ^3０ ⁰

工 ^３０． j＝１ ^ZＺ４

＋ｒａｎｄｏｍ U’1）－１．２８，１２８ ^3０ ^０九(z）

Ｚ｡＝１ ^3０ (z`smMF7 )） -500,500 ^3０ ^-12569.5 /b(麺）

Ｚ ^3０ ^j＝１ ^⑳ ^２

10ＣＯＳ(2汀z`)＋1０ -5.12,5.12 ^3０ ⁰ /,o(z)＝-20eｚｐ ^－２０ ,／ ^3０ ^１ ^Ｚ ^`＝1 ^3０ ^Ｚ ^２ ^０１－ezp[売乙聖,cos2川]＋20＋ｅ ^[-32,32］ ^3０ ⁰

4000 ^１Ｚ ^３０｡＝１ ^Ｚ２

Ｚ Ⅱ ^３０｡＝１ ^ＣＯＳ三▲

､/５ )＋１ -600,600 ^3０ ⁰

/'2(Z)＝：{1Osin2(剛)＋Ｚ ^〃-１ ^｡＝１ ^(y。 1)2[1＋l0Sjn2(剛十,)]＋(Zﾉ施

+Ｚ廷,u(z'’'0,100,4)，ｚ/`＝’＋i(z`＋'） ^1)2｝ ^[-50,501

3００

戦略パラメ ^6３

７実験結果とその考察本論文で提案した戦略バラを表２に示す。

メータを使用しないＥＥＰとしてのnsEEPを関数最小化問題に適応した結果表２最終世代での関数値

宝－１２４３７．６８９８９ ^0087222395 ^{１５３２９７４３１８} １１．３０４３８６２３

nsEEPは個体として戦略パラメータを含まないので各世代の進化において、そのための進化処理が不必要となる。このことから、少なくとも台以上の処理時間の短縮は期待しうるものであったが、表３に示す

以上の実験結果より、nsEEPは分布パラメータ（入1,A2）について、入,＝5.0×１０~2ルー５．０×１０１０とセットするだけで、従来のＣＥＰやＦＥＰに比較して極めて効率的なＥＰアルゴリズムであるといえる。

ＣＥＰＦＥＰ nｓｎｎＰ

九 0.037526577 0.982577878 ９．５２６４７Ｅ-１０九 2.698873419 15.32974318 ０．０６２１４０４９ /４ 15.82811054 0.087222395 ９．３５５６４Ｅ-１１九 86.37205982 96.95708171 4２．０８８６４９１４

九 ^170.5788 ^0.3533 ^０

/７ 0.060257634 0.122782395 ０．０１６９５０５５７九 -7326263085 -１２４３７．６８９８９ -8908.172791 九 1１．３０４３８６２３ 27.20929974 48.29853828 /,ｏ 1.361045781 0.364342106 1.59959Ｅ-１０ A1 0.177531732 0.018376979 ０．００５４６８７９１

A２ ^1.28601905 ^0.0008712 3.14684Ｅ-２２

ＣＥＰＦＥＰ nRF】、Ｐ

/， ¹⁰⁹¹ ^1０１５ ¹⁹⁵

九 ¹¹⁰⁸ ¹⁰³³ 207

九 ¹³⁷⁰ ¹²⁹⁶ 417

九 ^1１１８ ¹⁰³³ 206

九 ¹¹⁰³ ¹⁰³⁰ 208

九 ^1２１６ ^1１４１ ²⁸¹

/７ ¹⁰⁹² ¹⁰²⁴ 196

ん ¹³⁴⁰ ¹²⁷³ ³⁶⁷

九 ¹²⁸² ¹¹⁹³ ³³⁴

八ｏ ¹²⁹⁸ ¹²⁰⁶ ³⁴³

八， ¹³²³ ¹²⁷⁵ ³⁶⁶

ｈ２ ¹³⁷⁰ ¹²⁸⁶ ⁴¹⁶

なお、図１から図１２において各関数の収束特性を示す６図１はノ，に対する収束特`性を示すものである。nsEEPはほとんど全世代を通じてほぼ同じ収束率を示している。800世代まではＦＥＰの方が良いが、