線形変動パラメータによる指数型進化的プログラミング

岡山理科大学紀要第40号App91-lOO(2004）

線形変動パラメータによる指数型進化的プログラミング

成久洋之・谷口隆裕・津田倫彰＊・片山謙吾

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

＊岡山理科大学大学院工学研究科情報工学専攻

（2004年９月28日受付、2004年11月５日受理）

１はじめに

進化的計算（EvolutionaryComputation）［1]は自然の進化と適応の概念を導入した計算システムのこ とであり、従来の伝統計算手法では解けない大規模で複雑な問題を解くための強靭なしかも効率的計算法 と考えられ性目されている．これには進化的戦略（EvolutionaryStrategiesiES)、進化的プログラミング (EvolutionaJyProgramming;EP)、遺伝的アルゴリズム(GeneticAlgorithmsiGA)と遺伝的プログラミン グ(GeneticProgrammingiGP)などがある．

ＥＳは1965年に数値最適化手法としてRechenbergとSchwefelにより提案されたものであるＥＰはFogel

により1965年有限状態機械の人工知能的アプローチとして提案され、後に組み合わせや数値最適化手法に 応用されるに至った．ＧＡは１９７５年にHollandにより適応的探索アルゴリズムとして提案されたものであ る.ＧＰは１９８７年にＫｏｚａのＬＩＰＳプログラムとして提案されたものであるが、木構造染色体に対するＧＡ

の応用とみなすことができる．

これらの計算手法はすべて個体集団(population)を使用することと個体集団を構成する個体(individual）

の間の情報交換により、解を探索しようとするものである．

本論文は進化的計算の中のＥＰにつき記述するものである．進化的プログラミングは有限個の解集合か らなる個体集団に対し突然変異(mutation)と選択により、より質の高い解をもつ個体集団を発生させよう とする集団探索法である．これまでに提案されているＥＰは主としてGaussianMutationによるＣＥＰと CauchyMutationによるＦＥＰ手法がある．前者はGauss分布乱数を、後者はCauchy分布乱数をそれぞれ 使用し、関数最適化問題に対しては一般的にＦＥＰの方が有効であるとされている．［2]しかしながら、問題

によってはＣＥＰの方がよりすぐれた収束特性を示すこともあり、さらに収束の状況によって結果は異なる．

この観点から、Narihisaらは2002年に複合指数分布乱数を使用する指数型進化的プログラミング(EEP)を

提案した[3]これは指数分布のパラメータを制御することで分布の分散を変動させ収束の効率化を狙ったも のである.これまでの研究では種々のパラメータ値に対する収束特性を検討してきたが[4][5][617]、今回は パラメータ値を進化世代(evolutionarygeneration)に対応して線形に変動させたＥＥＰの収束特性につき検 討したものである．数値実験として、この分野でよく知られたベンチマーク問題に適応した結果、かなり良

好な収束特性が得られている．

２標準進化的プログラミング（ＣＥＰ）

ＢａｃｋとSchwefelによるＥＰのアルゴリズムは次の通り．

Stepl:似個の個体からなる初期個体集団の生成、Ａ＝ｌとする.各個体は実数ベクトルの対(⑰im),Vie

｛1,2,…,似}、ただし、鋤は変数ベクトル、ｎはガウス分布の標準偏差ベクトルとする．

Step2:個体集団の各個体("`,ワ｡),Vに｛1,2,…,似}に対して適合度を計算する．

成久洋之・谷口隆裕・津田倫彰・片山謙吾 9２

Step3:各個体(鋤側),j＝1,…,似は単一の子孫(蝿,ゲォ)を生成する.ノー1,2,…,”に対して

晩(j)＝ひi(小JDp{ﾃﾞﾉV(0,1)＋γ/Vj(0,1)｝（21）

コル(j)＝範i(j)＋◎i(j)jVj(0,1）（2.2）

ただし､鋤(i),錘`(j)町(j),｡`(j)はベクトル麺`,蝿,◎`’ぬのj-成分を表わすJv(0,1)は標準化された

1次元正規乱数で、その平均は０，標準偏差は’となっていることを示すJvj(0,1)は各ｊ毎に発生す る正規乱数を示し､デー(ｿﾞﾜﾏﾃﾃ)-1,γ＝(V面77)-1とする

Step4:各子孫(釣,晩),Vに{1,2,…,似)の適応度を計算する．

Step5:ｑトーナメント選択を実施し、（鈎側),(蝿心)の中から似個選択し,次世代の親とする．

Step6：停止条件を満たせば停止、そうでなければルール＋１としてStep3へ．

３Cauchy乱数を用いた進化的プログラミング（ＦＥＰ）

ＣＥＰではGauss分布に従う正規乱数Ｎ(0,1)を使用した突然変異を考えたのに対して、ＦＥＰではCauchy

分布に従う乱数を使用する．原点を平均とする１次元Cauchy分布の密度関数は

'低峠一声,‐｡｡≦露≦｡q'>ｏ

^（31）

ｔはスケールパラメータとする．これに対応するCauchy分布関数Ｆ(z,t)は次のようになる．

Ｆ(")=;+÷…(;）（皿）

したがって、［0,1]区間の一様乱数をｙとすると、

鰯=`伽{ﾍﾟﾘｰ;)｝

^(3.3）

となり、この乱数をＣ(０，t)で表わす．このスケールパラメータオー１とした乱数がＣ(0,1)であり、次の

ようになる．

ｃ(0止伽{術(｡-;)}p≦｡≦］

^（34）

ＦＥＰの処理アルゴリズムはＣＥＰのStep3における(22)式の代りに

趣！(ｊ)＝鋤(j)＋ｏｉ(j)ｑ(0,1）（35）

としたものである．

４複合指数乱数を用いた進化的プログラミング（ＥＥＰ）

ＥＥＰではDoubleExponential分布に従う乱数Ｅ(0,入)を用いた突然変異を考慮するものである．パラ メータ入の複合指数分布の１次元の確率密度関数ノ(Ｚ)は

巾)=;exp(-ハル｡｡≦錘≦oqA>０（4,）

として与えられる↓たがって、この分布における平均厄＝0,分散り＠㎡鯵)＝急となるこのことから、

この分布の分散は入が小さければ大きく、入が大きければ小さくなり、入により制御可能であることを示し

ている．ノ位)に対応した分布関数Ｆ(")は

「他ト{Ⅱ_鮒,雲：（4,）

線形変動パラメータによる指数型進化的ﾌﾟログラミング ^9３

として与えられる．したがって、［0,1]区間での一様乱数を〃とすると、

産{±紫伽,):三（4＄

で発生させる乱数ＺはＥ(0,入)で表わされるこのことから、Ｅ(0,入)＝；E(0,1)となりＥ(０，１)を発生さ せることによりＥ(0,入)を計算できる．ＥＥＰではＣＥＰのStep３における(22)式の代りに

Z!(j)＝鋤(ｊ)＋ひ｡(j)身(0,入）

(4.4）

としたものである．

５ＥＥＰにおける分布パラメータ入の収束特性に及ぼす効果

ＥＥＰではパラメータ入の複合指数乱数による突然変異により解を進化させるために、良好な収束特性を 得るための有効なしかも適正な入の値を何に決定するかが重要な研究課題である．定性的には進化の初期 段階では分散を大きくして解の多様性を高め、広域探索により解を進化させ、末期段階では局所探索とす

ることが望ましいわけである．

このような適正な入の値を決定するために、これまでに実施した実験は次の通り．

(1)入＝１とした場合のＥＥＰの収束検討[3］

世代数GEN＝1500、似＝１００，９＝１０、性能５０runsの平均 結果：Ｎ(0,1)、Ｃ(0,1)、Ｅ(0,1)mutationでＥ(0,1)が6est (2)入＝1,05,0.05とした場合のＥＥＰの収束検討[5］

ＧＥＮ＝2000、似＝１００，９＝１０、性能５０runsの平均

結果：入＝０．０５がbest

(3)入の初期値入,＝０．０５とした場合のl-timeswitchingEEPの検討[6］

（入,(9Ｗにおいては、入の初期値を９世代で切換えて入２とすることを示す）

入：0.05(500)１ 005(1000)１ 0.05(1500)１ 005(2000)１

似＝１００，９＝１０、ＧＥＮ＝1500、性能は100runsの平均

結果：問題によりswitching世代の早いもの、遅いものが望ましい場合があり、いずれもswitching効

果が認められた．

その他、

０１(2000)1,0.01(2000)1 01(2000)5,001(2000)５ ０１(2000)10,001(2000)１０

については２０００世代で入２＝１０とする方が良好な結果が得られた．なお、問題によって入＝

0.01,00005,0.00001と固定した方が良好な収束特性を示す場合もあった (4)４－timesswitchingEEPの検討[7］

multi-timesswitchingEEPとして、

EEPｌ；01(1000)05(2000)１０(3000)5.0(4000)lOO EEP2；０３(1000)１０(2000)5.0(3000)１００(4000)200 EEP３；05(１０００)１０(2000)5.0(3000)１００(4000)200

成久洋之・谷口隆裕・津田倫彰・片山謙吾 9４

EEP４；10(1000)3.0(2000)5.0(3000)10.0(4000)250

似＝１００，９＝１０、ＧＥＮ＝5000、性能はlOOrunsの平均．

結果：Uni-modqJ関数に対してはＥＥＰがＦＥＰより良好．

multi-modQJ関数に対しては２個だけＥＥＰが良い．

残り４個はＦＥＰの方が良い．

さらに、４timesswitchingでswitching効果がよく認められる関数に対して６－timesswitchingを施し たらなお精度の高い解が求められたさらに、multi-modal関数については初期値入を0.1より小さ い値(e鉱：0.05)にすると３～4個の問題に対して改善が認められ、multi-switchingEEPが有効であ

ることが認められた．

６数値実験

6.1今回の数値実験の目的

ＥＥＰではもっとも単純な手順としてＥ(0,1)乱数を使用した突然変異による進化法でも、これまで に提案された中で有効とされているＦＥＰに匹敵するかあるいはそれ以上の収束特性を示し得ること が明らかにされた．しかしながら、ＣＥＰやＦＥＰと根本的に異なる点は収束状況に応じて進化の探索 中を有効に制御することで収束の効率化を計らうとするものである．これがためには前回までの報告

で入の値を変動させるnmlti-switchingEEPの有効さも示してきた．しかしながら、multi-swiching

による入の値を決定する場合、switchingpointをどこにすべきか、あるいはその大きさはどの程度 にすべきか、さらに何回のswitchingを考慮すべきか等々の問題が生起してくる．勿論、これまでの 実験からはある範囲内のものであれば入のfixedvalueのみよりは効率的であることは判明している．

上記状況に鑑み、今回は初期値Ａ１と最終値入２を与えることで世代と共に線形に変動するＥＥＰにつ

き検討するものである．

6.2適用問題

ＥＥＰの収束特性を検討するために、今回の実験で対象とした問題はこの分野でよく知られている ベンチマーク問題で、表１に与えている関数最適化問題である．この中の九～んは単一の局所解を もつunj-modQl関数であり、’7～f11は複数の局所解をもつmultj-modal関数である．

6.3パラメータ設定

数値実験におけるパラメータは次のように設定した

(1)個体集団の大きさ；似＝100

(2)トーナメントサイズ；９＝１０

(3)計算世代数；GEN=5000 (4)入の初期値；入,＝００５，００００１ (5)入の最終値；A2＝10

(6)9世代で入;入＝且{蒜Ｌ９＋入，

(7)戦略パラメータの初期値；⑩(j)；[Ojl]区間の一様乱数

線形変動パラメータによる指数型進化的プログラミング ^9５

6.4実験実施要領

本実験は複合指数分布のパラメータ入を線形に変動させるＥＥＰの収束特性につき検討するもので あるが、同様に、ＣＥＰおよびＦＥＰについても5000世代までの特性につき記述する．これはＥＥＰと の性能比較という目的もさることながら、ＣＥＰやＦＥＰについての性能記述が多くの関連文献におい て１５００世代か２０００世代まで位のものであり、５０００世代までのものは殆んどないからである．例え ば、ＦＥＰの方がＣＥＰよりは一般によい特性を示すものとされているが、このことは1500世代ある いは２０００世代までの特性であり、それ以降のものについては殆んど言及されていない．しかし本実 験では２０００世代以降においてはＣＥＰの方が良好な結果を蘭すごとも明確になっている．これらの結 果は基本的にGauss分布とCauchy分布の特徴から類推しうるものである．

本実験での収束特性は各世代毎に各個体の関数値をlOOrunsの平均値として評価値とし、各世代毎に プロットして収束特性を表わすものとする．ここでは関数最適化問題を取り扱うので関数値が小さい 程望ましい状態といえる．進化の過程で、戦略パラメータヶ(j)は新しい解を決定する場合の変異巾と に関与するものであるが、｜ひ(ｊⅡ＝ｏは進化の停止を意味する．この状況を避けるために、｜ぴ(j)|の

下限をＥとし、|ぴ(j)|＜Ｅであれば強制的に|ひ(j)|＝化して進化を続行させる．標準的には＝10-2

とするが、状況によっては各問題に適した下限値についても検討する．

6.5実験結果

(1)入,＝0.0001,A2＝10,Ｅ＝10-2 図１～１１に各ＥＰの収束特性を示す．

f,に対して、１０００世代まではEEP、ＦＥＰ、ＣＥＰの順に良いが、１０００世代以降においてはＣＥＰが FEPに逆転している．九に対していずれも同じような収束傾向を示すがEEP、CEP、ＦＥＰの順に良 い．九に対して、全区間でEEP、CEP、ＦＥＰの順となっている．九に対して、ＥＥＰは最良である が、2000世代でCEP、ＦＥＰとが逆転している．九に対して、ＥＥＰは全区間で最良であり、1500世 代でＣＥＰとＦＥＰとが逆転している．九に対しても全区間でＥＥＰが最良で、EEP、CEP、ＦＥＰの

順になっている．ノ7に対して、全区間でＦＥＰが最良で、FEP、EEP、ＣＥＰの順になっている．たに

対して、1000世代まではＣＥＰが最良であるが、それ以降においてEEP、CEP、ＦＥＰの順となって いる．九に対して、当初ＦＥＰが最良であるが500世代以降においてEEP、FEP、ＣＥＰの順になっ ている．ｈｏに対して、当初ＦＥＰが最良であるが７００世代以降においてEEP、CEP、ＦＥＰの順に

なっている．九，に対して、EEP、FEP、ＣＥＰの順になっている．

/,～ｈ，の問題中、最終的に最良解となっているＥＰはＥＥＰ；10,ＦＥＰ；１，CEP；０

/,~たの川-ＭＱＪ関数に関して､EEP;；で全ての問題に対して最良解を得ることができたＣＥＰ とＦＥＰでは最終的にＣＥＰの方が良好な解となっているが、初期段階ではＦＥＰの方がいずれもよい 収束度を示している.方~んのmulti-modql関数に対してはEEPは：で最良解を得ているが､ＣＥＰ とFEPでは：でFEPの方が良好な収束を示している以上の事からE＝10-2とした場合について

は全面的にＥＥＰが有効なＥＰ手法であることが認められる．

(2)入,＝0001,A2＝10,Ｅ＝10-4 ５０００世代での最終関数値を表２に示す．

この表から､f,～たのuni-modal関数に対しては、６問中５０００世代で最良値を示したものはＥＥＰ；

4,FEP；２となり、ＥＥＰの方が良好な収束特性を示している．

/7～jF11はｎＭｉ－ｍｏｄｕｌ関数であるが、これについては５問中、５０００世代で最良値を示したものは

FEP；３，ＥＥＰ；1,ＣＥＰ；１となり、ＦＥＰが良好な収束特性を示す．また八や/9に対しては最終値

においてＥ＝１０－２とした場合に比し１０－４程解が改良されている．なお、ＦＥｐとＣＥｐについては

成久洋之・谷口隆裕・津田倫彰・片山謙吾 9６

u"ｊ－ｍｏｄＱｌ関数に対してＣＥＰが良いが、multi-modq【関数に対してＦＥＰが有効であることを示して

いる．ノi～/i，を全問題に対してはＥＥＰはunj-mocM関数については良いが、ｎＭｉ－ｍｏｄｕｌ関数に対

してはＦＥＰの方が良好な収束特性を示す．

(3)入,＝０００１，A2＝10,e＝最適下限

表３に５０００世代での関数値を示す．

この表から、ｈ～たの川-modql関数に対しては最良解はＥＥＰ；５，FEP；１となっており、ＥＥＰの良

好さが認められる．ノ7～/１１のmuJti-modaJ関数に対して最良解となった数はＥＥＰ；３，FEP；２となっ ている．これらの事から、力～た１の全問題を通して、最終的に良好な解を得たのはＥＥＰ；８，ＦＥＰ；

３となり、Ｅを問題に適合させれば、ＥＥＰ手法はＥＰとしてかなり有効なアルゴリズムと期待できる．

７結論

ＥＥＰでの複合指数分布のパラメータを入の値を世代と共に線形に変動させることで効率的なＥＰ を実現させることができた．さらに今回の実験では比較のために、CEP、ＦＥＰの性能特性についても 検討したが、実験結果によりuni-nzodql関数に対しては全てＣＥＰの方が、multi-modql関数に対し てはＦＥＰの方が優れた特性を示した．今回使用したＥＥＰのパラメータ設定としては戦略パラメータ ヶの下限Ｅを１０－２としているが、全般的にみて与えられた問題の８割以上において最良解を得ている

ことからＥＥＰが極めて有効なＥＰ手法であるといえよう．なお、Ｅとしては10-2～10-6程度入,,Ａ２

にしてもＡ１＝0.1～0.0001,入２＝１０～100程度の設定で割合有効なＥＥＰを実現できるものと考えら

れる．

参考文献

[1]TBackandH-PSchwefel,``Anoverviewofevolutionaryalgorithmsfbrparamenteroptimiza←

tion，',EvolutionaryComputation,1(1):1-23,1993．

[2]XYaoandYLiu,"hstEvolutionaryProgramming,''Proc・ofthe5thAnnualConferenceon EvolutionaryProgramming，ＭＩＴPress，pp451-460,1996．

[3]KKohmoto,HNarihisaandKKatayama,"Evolutionaryprogrammingusingeponentialmu‐

tation，，，ProcpfThe6thWOrldMulticonfbrenceonSystemics，Cyberneticsandlnfbrmat- ics(SCI2002),voLXI,ComputerScienceⅡ,pp､405-410,2002

[4]HNarihisa,KKohmoto,andKKatayama,``EvolutionaryProgrammingwithDoubleExponeL tialProbabilityDistribution'，，Proc,oftheSecondlASTEDInternationalConfbrenceonArti- ficiallntelligenceAndApplications,September9-12,Spain,358-363,2002．

[5]KKohmoto,HNarihisa,andKKatayama,"PerfbrmanceofEvolutionaryProgrammingUsing

ExponentialMutation，，，Proc､ｏｆｔｈｅ４ｔｈＡｓｉａ涙PasificConfbrenceonSimulatedEvolutionAnd Learnig,(SEAL'02)vol2,pp454-458,2002

[6]HNarihisa,KKohmoto,TKumon,andKKatayama,"PerfbrmanceofExponentialEvolution- aryProgramming'，，Proc・oflASTEDInternationalConfbrenceonArtificialIntelligenceand SoftComputing(ASC2003),ｐｐ243-248,2003．

[7]HNarihisa,KKohmoto,MTsuda，andKKatayama,``CONVERGENCECHARACTEmS- TICSOＦＥＸＰＯＮＥＮＴＩＡＬＥＶＯＬＵＴＩＯＮＡＲＹＰＲＯＧＲＡＭＭＩＮＧ，，，Procofthe8thIASTED InternationalConfbrenceonArtiHciallnte]ligenceandSoftComputing(ASC2004)，pp426‐

431,2004

線形変動パラメータによる指数型進化的ﾌﾟログラミング 9７

表１：ベンチマーク問題

Testfunction Ｓ f冗i”

力(z)＝Ｚ"；

たい)=書'露!'+Ⅱ'錘’

たい)＝Ｅ(Ezj)２

ｉ＝１ｊ＝１

九(z)＝mqzlzdl,1ニィニ３０

九(z)＝Ｅ[loo(ｚｚ+１－z:)2＋他－１)2］

た(z)＝工(Izi＋０５｣)２

川鍾)=一重(…m(何

九(釘)＝ｚ[毎?-10COS(2…)＋10］

帥)一汕叩(-.2,/;F三河‐岬'命､…;)+加十・

川)-赤篁遜;-iic.｡(諾)+ﾕ

ﾉ1,(鉱)＝：{lOsin2(７W`)＋Ｅ(gi-1)2[1＋l0sin2(汀ｙi+,)]＋(g"－１)2｝

＋Ｅｕ(z`,10,100,4),ツガ＝１＋ﾅ他＋1)，

－α≦ｚＥｑ

[-100,100]3Ｃ ^Ｏ

［-10,10]3Ｃ ^Ｏ [-100,100]3Ｃ ^Ｏ

［-1o0,1CO］ｏ [-100,100]3Ｃ ^Ｏ [-100,100]3０ ^０ [-500,500]３０ ^{－１２５６９．５} [-5.12,5.12]３０ ^０

［-32,32]３０ ^０ [-600,600]3０ ^０

[-50,50]3０ ⁰

1.0Ｅ+COG 1.0E+005 1.0Ｅ+００４ １．０Ｅ+003 1.0Ｅ+００２ １．０E+001 1.0Ｅ+COO １.OＥ－Ｏｍ ｌＯＥ－ＯＯ２ １.OE-OO3 １.OE-OO4

1.0Ｅ+025

1.0E+020

1.0E+015

⑭⑭①戸揮

：１０E+010闇

1.0Ｅ+005

1.0Ｅ+OOO

lOE-OO5 Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００

qeneralicn

図ｌ：ノ,の収束特性

Ｏ５００１０００１５ＣＯ２０００２５００３０００３５００４０００４５００５０００ qene｢臼ｌｉｏｎ

図２:./hの収束特性

1.0Ｅ+007 1.0Ｅ+006 1.0E+005 1.0Ｅ+004 1.0Ｅ+003 1.0Ｅ+ＣＯ２ １ＤＥ+001 1.0Ｅ+０００ １.OE-OO1 １.OE-OO2

1.0Ｅ+002

1.0Ｅ+001

1.0Ｅ+000

⑱⑩。（ぬ 吻飼①Ｆ回

1.OE-OO1

1.ＯＥ－ＯＯ２

1.OE-OO3 Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００

qeneralion

図３：/3の収束特性

Ｏ５００１０００１５００２０００２５００３０００３５ＯＯｄＩOOO45OO5OOO qeneralion

図４:/4の収束特性

Ｋ

CEP-- FEP-ヨーー

~ＥＥＰ…･侭…．

、１

８」■勺－０１

１^●■_■、 （!

｡温]

白^'箔JＬ^{廷 ■■■－－－陣｡Ｌ‐凸■-}

'け.、｡△

－－－句■．§白注～

■■、■^{■ﾄ引閂吟ト}

､声声■や卜、『詞司■幹」 P岸埒Xウ４｡ P■＄＋芹Ｈ■

､￣￣－－－

－二▲=

0句Oつい分い， 句､ぐひ●し仇

Ｌ■節｡⑪_Ｐ．

児■＿

￣■．0●_‐巴 白．１.◆凸■Ｚ■■■－－■向‐

'二つご砥：^{●￣－－￣－}１■･じじ●１_{番い■幻．}

>ＥＰ－－，

:ＥＰ－－トー！

:EＰ^●●●●_０^{紅･■･・}

峨些^{ｐ笘避■十一}_{悪盤尊:襲目聟＝ ■硅測都毎ｺ}

アーーー■'■･夕円，● |Ｃ母●⑤Ⅲ }＋砂路⑧･^{■￣■ｈＦ－－}

i}瓜

゛_■

P￣￣－－－■

､hR:！^詞_勺、

収o白_び１

町、

－－－￣￣｡

［▲ク

螺爾

訂?6耗拝 斗邑侶缶十 2２１．■：

ﾄ￥jq説調．

弐述司■い

“■･■■ｑ I井民汁憤ロ ー声二属

PＣＬ_■己．

－－－－'■■

毎痴司小hト ーーーーー

ゴート伶十

四壱重H１

》一

I角.ｎ℃_●．

lEP-÷

:ＥＰ－－時-－

iＥＰ^{Ⅱ■●Ⅱ■■}_、^{笹･･･｡￣}

「

.￣~~－F－－－．

「

……↓,`…“

'－－－トー--.

割→一ﾄｮｮｰﾄ_{ｒ－－－．}

￣~.－.~ｒ－－－￣

■ＣＱ唇読F尿ZＸ

船iｋ_ｌｋ

Ｐ－斗蛍

●

｡

●

｡

Ⅳ

、､八、

ｂｘ

必 Ｘ乳

●

■

■ 爲

瓜

霊

､兜蜂Ｈも 民

且-－－円●

■ｂ

Ｆ．

法

｡■ぬ＝二０

，－－■■■￣の

一』一、一』

』坐》

塾

｜蚤一号一勺一①

誼｡Ｒ調7Ｆ

弓■令十十

■■－－－－

＄分らぬＩ

CEP^一旬一 ＦＥＰ－→-－

ＥＥＰ…･■…・

-1-ﾄー

_’’

－－－－トーーーートー－－－．

…門蘂… -l－ｌ－

成久洋之・谷口隆裕・津田倫彰・片111謙吾 9８

1.0Ｅ+O11 1DE+010 1.0E+009 1.0Ｅ+008 1.0Ｅ+007 1.0Ｅ+006 1.0E+005 1.0E+004 1.0E+003 1.0E+002

陀肥四胆唖、加川００００００００日巳巳日己巳巳Ｅ００００００００１１１１１１１１

⑭切史■』』

昌關

Ｏ５００１０ＣＯ１５０Ｄ２０００２５００３０００３５ＯＯ４ＯOO45OO5OOO qene伯帥ion

図５:ノ5の収束特性

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ I1enemallon

図６：ノ６の収束特性

３０３３３３４４４００００００００００００００００００＋Ｅ巳ＥＥＥＥＥＥＥ＋＋＋＋＋＋＋

０００００００２４●●●●２０２４６８１１１Ｐ』』●

1.0Ｅ+003

鋤の： 削

呂l0BOO2

1.0Ｅ+001 Ｏ５００１０００１５００２０００２５００３０００３５００４ＯＯＯ４５ＯＯ５ＯＯＯ

リリeneraIlon

図７:/7の収束特性

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０CO neneralIon

図８:ノ8の収束特性

1.0Ｅ+CO2 1.0Ｅ+003

1.0Ｅ+002 1.0E+001

1.0Ｅ+001

g1DBOOo:I

屋

晩⑫①ＰＰ辱

1.0Ｅ+000

1.OE-OO1

1.OE-OO1

1.OE-OO2 1.OEOO2

Ｏ５００１０ＣＯ１５００２０００２５００３０００３５００４０００４５００５０００ U1eneralIon

図９:/9の収束特性

Ｏ５００１０００１５００２０００２５ＣO30003500400045005000 qenemaliｏｎ

図１０:ノ１０の収束特性

1.0E+010

1.0Ｅ+008

1.0Ｅ+006 ８１２１･OE､０Ｍ

1.0Ｅ+002

1.0E+COO

１.OE-CO2

Ｏ５００１０００１５００２０００２５００３０００３５００４０００４５００５０００ neneration

図11：ノ,，の収束特性

|、

１

ＣＥＰニーボFEP_一二

－－－－ＥＥＰ・…■････ ^￣

iいPii--●0

M^壜ｉ汀靭

i「

^{－－－－■}

｝

雨北机制沸

：路

！

，ｉ、^●■、

！

一

』Ｉ

~x，`,Ａ

２巫・五１戦

Ｉ私■■■

》一へ

》 ^{酌U詞詞◆＋ｒｒ－}トー外Ｘｐ罠誼｡ '＊６－-二 '●い■勺いめ ￣痔日孑炉

Ｉ

６ ＰＥＰ』』Ｐ』』一一Ｆ臣』〒ＩＩＩＩ０ＩＩ Ｐ

0

－￣

－－トー

ＥＥＰ・…侭…・

~~i－－｢￣

'１１（ I蕊

^{￣￣－－－■}

!（官

筑筑〆八 ^［､ＬＯＧ埣澤 ㈲0つd源①ひ,し岸DU輯“４

卜払忰忰×､ |講中b悩司炉 １９月額吾抵，Ｎ企H誼■？

ロ

■

Ⅸ_■＿

~、､`-ト_{引閂ﾄ＋←}～▲▲凸一

D戸ケマア一戸 ﾛ■■■￣■■■■■￣■

_ユ■■

￣句●千●I袈包Ｃ■｡

U■■￣Ⅱ■■￣q

'缶｡公乃ｑ

､￣￣￣￣

Ⅱ②●ら▲１

￣￣－－－

１つそ■ぬ｡月しＤＢ●ｑ 脾Ｃ公■←P■丹●缶｡

ｄＥＰ－＝

ＦＥＰ－→-－

－－－ＥＥＰ・…■･…－

ｴート ^－Ｈ－Ｈ

(…日G １

Ｕ Ｕ

火_浜 I済 妊涕エ【むけ▲._｡

誼引■←ｳト 門､試可印■弓 伊HｳⅢ弓q４Ｇｑ 卜悸肩口昨Ｈｑ牌岸Ｈ１Ｕ■４． 卜“■か⑪ﾄ笹。 ﾄ代心し何印可

豊

^{:痒嵐，`,`｛￣４円‐■} ,無粋j宇津 1つ0■労忰

何Ｎｂ枕骨幹‘ b悟印▲Ｈ弓､」 ,拭寸＋労咋

華ｌ咄 篝ｌＬ

》

■ Ｔ〒＋＋

し■．U、■．

－４－．．

■･の*で

)ｂＣ■⑤ﾛ_{トーら●｡.Ｉ缶巧巴守}

ﾄ●ご笛句巾 P■仏●÷

11r～^■▲q▲_

ＣＥＰ－－

ＦＥＰ－－■－－

ＥＥＰ・…打…．

|、

P－－

,Ｌ洋戸領｡

｡■．●．

良

■

｢缶缶何幹

－－－－－Ⅱ

■ 頂

Ⅱ■ 炉Ｈ弓n句O◆し

Ⅸ Ｗ･技Ｕｑ

b､し拭列可詞q

ＬＵ.＝

卜缶什似ﾄ円Ｐ }詞料やﾄ岸 閂､訶缶ウト 卜尚弓d詞qＨｑ Ｈ゛砕降Ｘ

■･●，

Ⅵ白 廷ｐｑ.■

■■の，}哲･● ■■･Ｉ b■゛｡■１_{ｌｐＣいい}

iii（

^Ｐ

Ｅ６

－口

一一↓ｌＩＩＩ

罫トー‐Ｉ

Di O ら

＃^b0UOq。

､ｏＸｌ Ｘ匂Ｌ_＄￣可、

日● ＣＯ

ｂ

９ ０日

､､､､、_､、偽～

、仏缶缶と

Ｑ

虹_▽

■由，卜ｐら也谷ﾄの⑤凸゛

｛ 一 一

6ＥＰ－ＦＥＰ－．－－，

ＥＥＰ…･何－．

－－i--十----

ＩＩｌｌＫ

^{Ｌ単a6分.已}Ｐ、、閨

■缶●｡

１軒升労いＬ,

ご■■■

Ｐｂ角◆少 ギャザ

)■●＋●,ｂＧＧ６1つ■Pらあ,}■･■剤ｅ缶， ^司司＝片

線形変動パラメータによる指数型進化的プログラミング 9９

表２:最終世代での適応度に＝10-2）

ノＣＥＰ ^{ＦＥＰ ＥＥＰ}

ノ12.11366e-’

た1.71999 九2.30155ｅ 九a83286e-2 九l49840e2 九1.42460 f7-762757e3 几6.96276ｅ 九1.08810ｅ /lo410545e-2 /l1189849e-1

2.57091e-4 691784e-2 214424e-2 389591e－３ 126704e2 610000e-1 -88608e3 3.33348e L19992e-2 181654e-2 933051e-2 2.80764

5.59973 l58996e2 5.76661e－１ 7.78664e２ 1.31743e -L25424e4 LO9076e2 253202 8.89725e－１ l06290e-1

表3:最終世代での適応度(E＝10-4）

ノＣＥＰ ^ＦＥＰ EＥＰ

九l40355e-4 九4.39687e－２ 九6.16582 九2.82547 九l01883e2 九5.76040eｌ ノア-7.63698ｅ３ た1250948ｅ 九203914 力o223479e-1 h1195496e-’

l15573e-1 9.58763e－１ 7.66093e l69291e-1 1.65745e２ 9.71800e-1 -12561e4 276834ｅ 3.51060e－’

8.25179e-2 486307e-3

3.01536e－８ 7.35000e－４ a91940e-1 3.95447e－１ 8.27275e L23500e -884030e 230830e l23992e-4 180516e-1 872115e-2

表4:最終世代での適応度(‐最適値）

/ＣＥＰ FＥＰ ＥＥＰ Ｅ

九l83253e-6 九l19587e-3 だ2.30155ｅ 九3.83286e－２ 九l04217e2 九5.76040ｅｌ 方-7.53590ｅ３ た3.34505ｅ 九203914 f10410545e-2 h1189849e-1

6.35955e-4 540637e-3 1.58996e2 5.76661e-1 L2490e2 971800e-1 -12532e4 2D8208e-1 3.51060e-1 889725e-1 106290e-1

700000e－１４ 1.13089e-７ 214424e－２ 3.89591e－３ 8.21130e l23500e -871936e3 1.83968e l23992e-4 L81654e-2 9.33051e－２

８８２２６４８８４２２－一一一一一一一一一一０〈Ｕ０００００００００勺１勺１勺１己１勺１１１勺１勺１１１１

成久洋之・谷口隆裕・津田倫彰・片山謙吾 100

Perfbrmanceo丘ExponentialEvolutionaryProgramming withLinearVaryingParameter

HiroyukiNarihisa,TakahiroTaniguchi，MichiakiTsuda＊andKengoKatayama

Depqrtmerztqﾉﾉ､L/Ormcltio〃ＱｎｄＣｏｍｐｕｔｅｒＥ，Ｗｊ〃eermg，

ＦｈＭｔｙｑ/Engjneermg，

＊ＧｒＱｄＭｅＳｃｈｏｏｌｑ/Ｅ叩meermg・

ＯＡａｙａｍＧＵＭ）ers伽qfScience LIRjdcuj-cho，Ｏｋａｙａｍａ，700-0005,Ｊ叩α〃

(ReceivedSeptember28,2004;acceptedNovember5,2004）

Thetermevolutionarycomputingrefbrstothestudyofthefbundationandapplicationsofcertain heuristictechniguesandbasedontheprinciplesofnaturalevolutionithustheaimofdesigningevolutionary alｇｏｒｉｔｈｍｓｉｓｔｏｍｉｍｉｅｓｏｍｅｏｆｔｈｅｐｒｏｃessestakingplaceinnaturalevolutionThesealgorithmsare classifiedintothreemaincategories,dependingmoreonhistoricaldevelopmentthanonmajorfUnctional techniques・Infact,theirbiologicalbasisisessentiallythesame

ThesealgorithmscontajnevolutionaryprogranⅡning(iEP),evolutionarystratefies(;ES),geneticalgo- rithms(;GA)andgeneticprogramming(iGP）

Anevolutionaryalgorithm(iEA)isaniterativeandstochssticprocessthatoperatesonasetofin- dividuals(calledpopulation)．Eachindividualrepresentsapotentialsolutiontotheproblembeing solved・Initially,thepopulationisrandomlygeneratedEveryindovidualinthepopulationisassigned,by meansofafitnessfimction，amesuresofitsgoodnesswithrespecttotheproblemunderconsideratiｏｎ，

whichguidesthesearch

EPwasoriginallyproposedbyFbgelasanapproachtoartificialintelligenceinl966Sincelatel98０，s，

EPwasalsoappliedtoviriouscombinationalandnumericalaplimirationproblems、StandardEPuses GaussianmutationwhichisbasedonGaussianrandomnumber,ａｎｄｒｅｆｂｒｅｄｔｏＣＥＰ・Ｉｎｏｒｄｅｒｔｏｉmprove EPconvergence,variousmutationshaﾊﾉebeenproposed、Ａｍｏｎｇｔｈｅｍ，FEPalgorithmwhichwasbased onCauchymutationwasconsideredtobethemostefYicientalgorithm・

Ｉｎ２００２,weproposedaneweHicientEPwithdoubleexponentialmutationasrefbrｅｄｔｏＥＥＰ・

Inthispaper,ｗｅｐｒｅｓｅｎｔａｎｅｗＥＥＰｗｉｔhlinearvaryingparameterofdoubleexponentialdistribution・

TheexperimentalresultsshowthaｔＥＥＰｉｓｓｕｐｅｒｉｏｒｔｏＣＥＰａｎｄＦＥＰｏnapplyingtohmctionoptimization problems．