林孝志郎・片山謙吾＊・南原英生＊・成久洋之＊

岡山理科大学紀要第43号Ａｐｐ６７－７６(2007）

ParticleSwarmOptimizationの多様化に関する検討

林孝志郎・片山謙吾＊・南原英生＊・成久洋之＊

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

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

（2007年１０月１日受付、2007年11月２日受理）

ついて調査し，それらの多様性について検討を行う．

2．関数最適化問題 1゜はじめに

ParticleSwarmOptimization(以下，ＰＳO)')2)3)は単 純化された社会モデルのシミュレーションを通じて，

1995年にパデュー大学のREberhartらによって開発さ れたメタヒューリスティクスの一つであり，非線形最 適化問題を解くための，有力な手法の一つとして知ら れている．これまでの数多くの研究から，連続型多峰 関数の大域的最適解を実用的な計算時間内に高い最適 性を満足しつつ，探索を遂行できる手法であると考え られている．ＰＳＯは，関数の勾配を利用しないため，

微分不可能な問題にも適用でき，多点探索を行うため，

単点探索に比べ，初期値依存性が少なく，大域的な探 索が可能である．更に，評価値情報のみを利用するた め，数式モデルを必要とせず，直接シミュレータや実 システムのデータを用いることが出来るため，実問題 に適用しやすいという利点を持つ．このような観点よ り，工学分野への適用を考える場合，最適性，汎用性 の観点から，ＰＳＯは，非常に有効な手法である5)．

PSOの更新式が，探索するベクトルの可変が可能な局 所探索と類似した方法であると考えられることから，局 所探索について非常に強力なアプローチと考えられる．

そのため，解空間全体より大域的最適解を発見するに は，ＰＳＯの探索を多様化させることが，有望な方法で あると考えられる．ＰＳＯの多様化を促進させるために 過去に行われたＰＳＯの研究では，LinearlyDecreasing lnertiaWeightApproach(以下，LDIWA)8)，)などのパラ メータによる多様化の促進について提案されてきた．

しかし，これだけでは十分な探索性能を発揮できてい ないと考えられる．そこで，この他の多様化を促進す る方法として，分割法12)や階層型法13)など様々な方法 が考えられる．

本論文では，ＰＳＯで過去に非常に有効なパラメータ であるといわれるＬＤＩＷＡと経験的に得た有効なパラ メータについて検討を行い，更に分割法(以下，D-PSO）

と，D-PSOに階層化を加えた方法(以下，DH-PSO)に

最適化問題は一般的に次のように表される．

ｍiｎ／1(x）（１）

Ｘ

ｓｕｂｊｅｃｔｔｏｊｒＥＦ （２）

ＦＥＸ （３）

/(x)は目的関数(objectivefimction)と呼ばれ，解兀 の良さを表す尺度で実数値をとろものとし，集合Ｆは 可能領域(fbasibleregion)を表す．ｘは通常ベクトル量 で，問題の`性質から定まる基本空間Ｘの要素となる が，実際にはその部分集合であるＦの要素しかとるこ とを許さないこの関係を規定した式(2)を制約条件

(constraint)と呼ぶ．

3．ParticleSwarmOptimization(PSOｿ)2)3）

本章では，ＰＳＯの背景・基本的な概念，及びアルゴ リズムの詳細をまとめる．

3.1ＰＳＯの概念

「ParticleSwarm」は，位置や速度の概念を持つ探索 点を表現した「Particle(微小粒子)」と，人工生命の研 究におけるSwarmlntelligenceの概念より「Swarm(群 れ)」が選定されて作られた言葉である．このことから も分かるようにＰＳＯの最大の特徴は複数の探索点か ら構成された群れによる探索であるといえる．それら が，お互いに情報を共有し，それに基づき解空間を探 索でき，非常にシンプルなアルゴリズムによって構成 される．基本的な算術演算のみを用い，連続型の非線 形な解空間を持つ最適化問題に対して比較的，高速に 探索することが可能であると考えられている．

ＰＳＯによる工学的応用を考えれば，得られる解の最 適性や計算効率の一層の向上などが挙げられる．その ため，研究においてＰＳＯ自体の精度向上が非常に重要 な位置を占めている．

林孝志郎・片山謙吾・南原英生・成久洋之

6８

やEberhartらによってパラメータｗを付加した更新 式が提案された．慣性パラメータｗの導入は，それ以 前の更新式をその特別な場合として含んでいることか ら，`慣性パラメータｗを含む式が最も広く知られてい る．そのため，本稿で採用した更新式もｗを含む更新 式を使用する．更に，ＰＳＯの更新式には，いくつかの バリエーションが存在するが，本稿で用いる更新式は，

Eberhartらにより，１９９５年～1996年に提案された更 新式

，！+'＝，ｆ＋Ｃｌ･'α"`,()･(pMrj-x『）

＋ｃ２．”"ぬ()･(gbeルェｂ（７）

と，1998年にEberhartとShiによって修正された慣性 重み付きの更新釘）

’'ｉ+'＝Ｗド＋Ｃｌ･'α"diO(Ｐｂ剛,－x'）

＋伽.α"｡b()･(9Ｍ’一xb｝（８）

ｘは，‘慣性重みを示す．

を包含している更新式である式(5)を用いる．

3.2活性度(Activityｿ)の定義

探索の状況を把握するためにはＰＳＯの探索における 多様化・集中化がどの程度実現されているかを定量的 に評価できる指標を定義する必要がある．そこで，本 論文では多くの文瀞)で利用され，評価指針の一つで ある活性度(Activity)を用いる．ＰＳＯにおける探索は，

個々のParticle(粒子)が探索空間を動き回ることによっ て実現されており，これは熱・統計力学における気体 分子の運動に例えることができる．そこで，ＰＳＯの探 索における多様化･集中化の指標として，各Particleの 速度の二乗平均値として群の活性度ＡＣ/が式(4)によ り定義されている．ＰＳＯにおいては，後述する式(5)

におけるヅヴが，Particleの速度に相当する．以下に活 性度(ActMty)の計算式を記す．ここで，〃を個体数，

〃を次元数，ｖを式(5)で計算した移動ベクトルとする．

志喜喜mii

』α＝

活性度(Activity)を用いることにより，発散・収束 を判断することが可能となる．』αが大きいときは発 散，小さいときは収束とする．

3.3ＰＳＯのアルゴリズム

ＰＳＯの概念は群状の探索点(個体)が情報を共有する 最良の情報(Ｐｂ剛）と群れで共有する情報(9ＭＪ)を 利用して解を探索する手法である．ここでは，1995年 にＲ・Eberhartらにより提唱された基本的なＰＳＯのア ルゴリズムについて示す．以下が基本的なＰＳＯの探索 点の更新式である．

Particle数２≦胸ERParticleのパラメータO＜ｗＥ Ｒ，０＜ＣｌＥＲ，０＜ＣｌＥＲとする．

砺'＝ｗｍｆ＋Ｃｌ･'α"`ﾉi()･(pb剛j-琴）

＋ｃＭＪ"dhO(gDeルェ③（５）

Fig.２ＰＳＯの近傍 Fig.１探索点(個体の移動）

3.4ＰＳＯの近傍

式(5)と式(6)より，個体jのk＋1回目の位置x'十’

は

鞭!=x『十Ｗ#Ｍ(p一考）（９）

と変形することができる．ここで式(9)中の‘とｐは

それぞれ

‘＝Ｃｌｒ１＋C2n （10）

Ｍｍａｌ()Pb"罐＋c川刎･gbcs〆（,,）

ｐ＝

である．これは,Fig2に示すように現在の位置埒か らｗ澪だけ平行移動した位置の近傍内に新たに点を生 成することを意味する．式(9)は，探索方向ベクトル

p-x！にステップ幅‘を乗じた形となっているまた，

式('0)より‘は二つの一様乱数を足し合わせたもので

あり，その最小値は０，最大値c1＋c２，平均(Ｃｌ＋c2)/２ の分布に従う．そのため，ＰＳＯは確率的なステップ幅 を持った局所探索法などの降下法と類似した構造を持っ ていると考えられる．

鞭'＝xｸ＋鏥ｌ

ｊ＝1,2,…〃とおく．

(6)

ここで,xｻﾞは個体jのA回目の探索点,'α"d'(ＭＪ"ぬＯ

はＯから１までの一様乱数，ｗ，ｃ,，ｃ２はそれぞれの 項に対する非負の重み係数である．ｊ番目の個体は現

在の探索方法罐と，現在の探索点ｘｆからその個体自 身の最良探索点ｐＭ４へ向かう方向及び，群れの最良 探索点gbes8へ向かう方向を用いて次の探索方向”’

を決定し，現在の探索点茸から次の探索点ｘｒ+'へ移 動する．Fig.１は，個体の移動の様子を示している．

ＰＳＯが開発された当初は，慣性パラメータであるｗ を含まない更新式が提案されていたが，1998年，Ｓｈｉ

ParticleSwarmOptimizationの多様化に関する検討 6９

3.5分割ＰＳO(D-PSO)のアルゴリズム

これまでに紹介したＰＳＯは，１９９５年から１９９８年 までに提案された基本的なＰＳＯの枠組みである．こ れらの更新式の提案は画期的なものであったが，ＰＳＯ の性質上，局所探索には非常に強く，探索終盤におけ る多様`性の維持の困難さがさまざまな論文6)7)より指 摘されている．そのため，探索終盤における多様性の 維持が重要になるが，基本的なＰＳＯでは，探索終盤 でのParticleの移動速度が落ちてしまい，局所解から の脱出が困難となる．そこで我々は，これまでに多様 性を維持する改良案を検討してきた．その一つが分割 PSO(以下，D-PSO)である．

９５９０９２９３５Ｊ５

◆ ● ロロロ』０ ３ ２ １ ０ Ｈ２５２９ 。■ 乃刀１

】ｎ超

０．５

"４０6０００1００2ＺＯ260zＯＣ ０

ＬｃＣｍＣＬｍ コロ△ﾛ“■0100｡。0100100

Lt0rDrO毎

Fig.４D-PSOの評価値と活性度の推移(Raslriginfimction）

邇岫！

^ｆ③⑨９

３鈍感

”５０ 藷｡⑥ Zp5o iLB“

2⑥６１０ ５錦

‘

nevation=１

Fig.５問題点

が一つの箇所に集まり，収束していることがわかる．

Fig.４，Ｆｉｇ５より，D-PSOは，このような複雑な景観 を有した問題においては，活性度の値が比較的早い段 階で低くなり，個々のParticleが活性していないため，

探索の比較的早い段階で局所解から抜け出せなくなる と考えられる．この弱点を補うには，常に広域な探索 ができる方法を考える必要がある．そこで，これらの 弱点を補った手法が，次に示すDH-PSOである．

3.6分割階層型ＰＳO(DH-PSO）

DH-PSOは，基本的なＰＳＯとD-PSOの欠点を補っ たＰＳＯである．イメージとしては，低い位置の空を 飛び，細かな調査をする飛行機部隊と高い位置の空を 飛び，広域的な調査が出来る飛行機部隊の２種類があ り，広域で見つけた比較的よい地点を細かな調査をす る飛行機部隊にその地点を教え，その部隊が細かく調 査をするといったイメージである．

Fig.６は，階層数２，分割数４のときのDH-PSOの 情報伝達の様子を示している．ＤＨＰＳＯでの更新式は 式(5)を用いており，ＰＳＯの局所探索性能を損なわな い手法となっている．また，通常のＰＳＯＤ－ＰＳＯで問 題になっている複雑な景観を持つ問題例においても，

階層型にすることで，通常のＰＳＯやD-PSOの性能を 損なわず広域探索を可能にしているハイブリッド型の PSOである．この階層は，任意に指定でき，階層が低 いほど詳細な探索が可能となっている．また，分割数 もD-PSO同様，任意に指定できる．以下に，DH-PSO の一般的な処理手順を示す．

-2,5－２－１．５－１⑳５００．５１１．５２ J9

Rosenbrock,sfUnctiOn

Fig.３分割型ＰＳＯ(探索点の分割の様子）

D-PSOは，Fig.３に示すように，Particle(粒子)，

ｐ６伽，gbeslを複数のグループに分害Ｉし，グループご とで探索する手法である．基本的なＰＳＯのアルゴリズ ムでは，探索終盤における多様性維持が困難なため，以 下に示す操作をすることにより多様性を維持している．

グループ数を任意の数ｍ，現在指し示しているグループ

をｇとしたとき，任意の一定周期で９Ｍを+,＝g6es`ｇ

とする操作をg6esl,,,＝gbes鼎，となるまでくり返し 行う．Fig.３では，gbesjを☆で示し，Particleを丸で示 している．矢印は，移住の方向を表しており，リング状 に移住していく．この操作は，Particleがgbesrに引っ

張られやすいという性質を利用し，渡り鳥の移住(mi‐

gration)の様子を再現しようとしたものである．Fig.４，

Fig.５では，関数最適化問題における２次元のRastrigin

fimctionをD-PSOを用いて探索した結果を表してい る．Fig.４は評価値と活性度(以下，Act)の繰り返し回

数(以下，iteration)に応じた推移を示しており，Fig.５

Fig.４よりActが小さくなり，Ｆｉｇ５のように大域的 最適解(☆印)でない局所的最適解を探索し，Particle

林孝志郎・片山謙吾・南原英生・成久洋之

7０

男三ｌｍＩｏＯＯ纈もoooooc

_0．ユ

^{HＡ Ｈ８ ＭＯロルｌ－－ ＭｃＢ２｡。…･…。}

｡､Ｏｌ Ｃ･ＯＯ１ ＣｐＯＯｎ Ｌｅ･Ｏ３ ｌ●－０６

熟＜G"ｕｌ関）懲＜Ｇ１｡`"'4趣

vpuO91鰯

^H‘

A猫ＩＤ

｡ｃｏｏＧｏｏｏ]CD］”Ⅱ００l6c句2⑰６，０９０，１００110０４０１６ｏ ｉｆ●r●ＵｑｃｎｌＺ“■ＬＡ印

潔鰯

(篝iLilｾﾞﾘｾﾞﾂ{={iil111iうてM受IiI壷､､'i11`きＩ篝|t〕

ｍＨｒＢ３ｃ◆￣－｡『ＤｕＤ四

■■■９

第１醗掴

○露Pa鯛⑧鰯雲§剛

階層分割型ＰＳＣ(情報伝達の様子）

Fig.６

個体数をＰ…，腕を階層数，〃,,,を碗階層におけ る分割数としたときFig.６では，、＝２で〃，＝４，

"2＝１でのＤＨＰＳＯの構成を示す．各集団の個体数は，

PS姪/〃/",,,個として分割し，各集団をＰＳ"6,～Ｐｓｕ６５と して記する．各集団は独立に探索し，その更新式は式 (5)，式(6)を用いる．よって集団ごとにｐＭｒとgbesl が存在する．Fig.６では，第１階層目の４集団におけ る各ｇＭｒは,ｇｌＥＰｓｕ６１，ｇＺｅＰｓｕ６２,ｇ３ＥＰｓｕ６３，

ｇ４ｅＰｓ卿糾として配置され，それらは任意の周期で移 住する．しかし，移住のみの処理では，探索終盤になる と探索の多様性を維持しにくいということが，D-PSO のFig.4,Fig.５の結果より明らかなので，第２階層目 のＰ３卿６５の集団によって広域的な探索を平行して実施 する(Fig.6)．この広域的な探索によって，解空間全体 を見渡すことができ，第２階層目の有益な解情報を第 １階層目へ伝達することで，より有望となり得る探索 空間を提供すると共に，第１階層の探索の多様性を更 に向上させることができる．DH-PSOでは，第１階層 目の９１，９２，９３，９４の解の中で最も悪い評価値を持 つものと第２階層目のPsu65の最良解９５を任意の周期 で比較する．例えばFig.６に示すように第１階層の最 悪解が９４とするとき，旗の方が良好な評価値であれ ば９４を９５に書き換える．また，第２階層目の個体集

団に対しては，多様性の維持のために任意の周期でリ スタート処理を施す．DH-PSOは，これら一連の処理 を終了条件を満たすまで繰り返す．

Fig.７，Fig.８では，２次元のRastriginfimctionをＤＨ－

ＰＳＯを用いて探索した結果を示している．Fig.７は評 価値と活性度(Act)のiterationに応じた推移を示して おり，Actの実線は第１階層の活性度，破線は第２階 層の活性度を表している．また，Fig.８はParticleの探 索の推移を示す．Fig.８の☆印は，大域的最適解，○は １階層目のParticle，□は２階層目のParticleを示す．

順個tion=150 ite『aUon=１

Fig.８改良案

Fig.７の評価値の推移より，前述したD-PSOの結果 と比較すると，DH-PSOで探索を行うと階段状に最適 解に近づいていることがわかる．これは，Ｆｉｇ７の活性 度の推移より，第２階層の活性度が衰えていないこと から，第１階層が局所解に陥った後，第２階層より情 報を得て，更なる大域的最適解の探索の継続を可能に すると同時に探索の停滞を抑制する効果を有している と考えられる．このことからDH-PSOの特徴でもある 階層化は有効であると考えられる．

4．数値実験の概要

本論文では，DH-PSOにおいて有効なパラメータ設 定の検討を行うために，代表的なベンチマーク問題例 を用いて数値実験を行った．数値実験に使用したベンチ マーク問題例は，単峰性関数２例題(Sphere，Ridge)及 び多峰性関数４例題(Rosenbrock，RastriginAckley，

Griewank)の計６例題とする(付録Ａ参照).本実験では，

式(5)で用いる慣性項ｗについて，固定型とＬＤＩＷＡ ８)9)を用いた場合で比較する．なお，ＬＤＩＷＡは，’償`性 項Ｗが次式によって線形に変化することで，多様化と 集中化の自動調整を可能にした手法である．

Ｗ＝Ｗ"ｉｍＦ－

Ａ､“

ここでｗ…とwmi"はそれぞれ慣性項の最大値と最小 値を表し，Ａ),､xは最大探索回数である．

実験で用いるパラメータは，固定型では，これまでの 実験で我々が経験的に得た良好であると考えられる値 のｗ＝Ｃｌ＝ｃ２＝0.8を用い，ＬＤＩＷＡについては，他の

ParticleSwarmOptimizationの多様化に関する検討

7１

ＰＳＯの研究で最もよく使用されるｗ＝0.9→0.4,Ｃｌ＝

ｃ２＝2.0を用いる．実験環境は，ＣＰＵ:AthlonXP2500＋

1.82GHz，ＲＡＭ:1ＯＢ，ＯＳ:FedoraCore6，使用言語は Ｃ言語を用い，０３オプションを適用している．

集団全体の個体数(Psize)を１０次元のとき１００，２０ 次元のとき１００，３０次元のとき１００とし，DH-PSOの リスタートは，２０iteration毎として，分割数を変化さ せた．分割数(Division)には１，２，５，１０を用いた．集 団全体の個体数を固定させているため，群れのグルー プごとの個体数は

グループごとの個体数＝集団全体の個体数（13）_分割数

としている．また，移住間隔は，Z0iterationとした．

なお，ＤＨＰＳＯは，全２階層とし，第１階層と第２階 層の個体の割り当ては，（全個体数/2)個とし，第１階

層のみ分割を行う．

終了条件として，繰り返し回数がl0000iterationと なったとき，または，計算中に評価値が1.0×10-7以 下の値を得たとき，最適解を得たとし計算を打ち切る．

それぞれ20試行ずつ実験を行った．Tablel～THble6の iterationは，最適解を得るまでの繰り返し回数を示し，

successは,２０試行中に最適解を得た回数を示している．

エ００ １，

]、Ｏ ＩＯ

可．エ

AI

O･ｍ ＯＤＤ０Ｌ Ｌ０－ＯＯ 功一0５

｡｡】

ｌｉ Ｃ･ＯＬ Ｃ･CO2 ２０－００

１●-０５ ６ｺ０００．００ＣＺＯＯＤＯＯＣＯＱＯＯＯ６００９７ＯＯＯＤＯ９Ｏ９ＣＯ０２００００

““■ｇｄ印８ ０Ⅱ０００３０００DOOgOODC＄①０，600Ｕ ^{ＤＢ己r■９２印Ｂ}

ＤＰＣＴＱ２２２＝

Fig.９Sphcrcfi】nction Fig」ORidgcfimction Figll活性度の推移の比較

ＬＯＯ 」、⑤、ロ

ユ0０

１４０００２ ００００１１ □一⑤。●●６●●■●■ １２１１１

盤ｕ■

０．９ユ

凹

且 _{１●－０４} 些一ｇｄ ＬＯ－ＤＢ ユのﾏｺﾛ DLOOD。ＯＯＯＺＣＯＯ４Ｑ００５００００ｇＯｇ７０９００ｇＯＯウO”BOOC

Atヰエゼ生ご？ ｡」ｇＯＯ３０００ｊ”０４９５０５０００ＵＯＯｇ７０００００００ＤｐＯＯ８００００ ｆＣ二二21曇

Fig.1２AckleyfimctionFig､1３Griewankfimction Fig,1４活性度の推移の比較

保たせた探索が効率的であると考えられる．Fig.１４は，

Table､５，Thble6に示されている２０次元のAckley関数 と２０次元のGriewank関数の探索時の活性度を示した グラフである．実験結果よりＬＤＩＷＡは，探索終盤にお いて，固定パラメータより多様性を保っている．Table､５ の結果より２０次元のAckley関数は，２０回試行中，２０ 回探索に成功している．これは，Fig.１４に示すように，

活性度が効率的に調整されているものと考えられる．

しかし，Tnble､６の結果よりGIiwankfimctionに対して LDIWAを適用したとき，探索成功回数が少ないこと からロバスト性に欠けている．これは，ＬＤＩＷＡでは，

線形に多様的な探索から局所的な探索に移行するため，

探索初期で大域的最適解の近傍を発見できなかった場 合，探索終盤において局所解に陥り，大域的最適解を 発見できないと考えられる．これらの結果より，凹凸 の景観を有した問題例において，探索終盤でも，より 強い多様性が必要になると推測できる．

5.2分割数におけるＰＳＯの性能の検討

次にＰＳＯの多様化を目的としたD-PSODH-PSO での分割数における性能比較を行う．ここでは，パラ メータの性能を明確にするためD-PSOでの結果より 検討を行う．

THblel～Table6のiterationよりRosenbrock関数以外 の問題例については，分割数が増えることで全体的に iterationが増えている傾向がある．これは，分割数を 増やすことにより，多様`性を保たせるため，局所的な 探索を遅らせているためだと思われる．successの数を 合わせて見ると，分割数の増加に伴い，successの回数 が比較的多くなる傾向にある．これは，分割数を増や すことで，多様的に探索ができ，時期早々に局所解に 5．実験結果と考察

5.1ＬＤＩＷＡにおけるＰＳＯの性能の検討

基本的なＰＳＯで固定パラメータを用いたときと LDIWAを用いたときの比較を行う．TnbleLnUble2の 結果表より単峰性関数の問題例において，固定パラメー タとＬＤＩＷＡでは，固定パラメータの方が，iterationが 少ないことから効率的に最適解を求められていると考 えられる．これについてFig.１１を用いて検討する．

Fig.１１は，単峰性関数の問題例である３０次元の Sphere関数と３０次元のRidge関数について固定パラ メータとＬＤＩＷＡを用いたとき，式(5)のＰＳＯが探索 に行ったときの活性度を示している．Fig.１１の実験結 果よりLDIWdLを用いると活性度が緩やかに減衰して おり，スピードの衰えが遅いことがわかる．これによ り，探索序盤では非常に多様性化しており，探索終盤 では，探索が局所的になっていると考えられる．そのた め，探索終盤においての局所的な探索が固定パラメー タと比べてＬＤＩＷＡは比較的遅<に始まる．このため，

最適解を発見するためにiterationを多く必要とすると 考えられる．

THble､５，THble,６の問題例は，小さな凹凸の存在する 問題例である．このような問題例の場合，探索終盤に おいて，完全な局所探索を行うのではなく，多様性を

LＤ２ ･残

林孝志郎・片山謙吾・南原英生・成久洋之

7２

THblc4IRastrigm

Tnblcl

ＤＭ５ｎＤ ＮＵｍ肚壺

=二I簔簔i享

^{、i画口ｎｍ ＭｍＵ比守 ＤＭＢｕｍ Ｎｕｍ比守 ＤＭｑｕｍ ＭＴｍ牌■ 00385２０} ■■■■■■￣■■■Ｉ・ ^{ＤＭＢ１Ｄｎ ＮＵＴｍ比＝ ＤＩｖｉ５Ｉｍ ＮＨＪｍ比丘 ＤｗＩ巴Ⅱ亜 ＮＵｍ陸〃}

■■■■■■￣■■■

■■■■■■上,￣＝

ＤＭ５Ｂｍ ＮＵＪｍ椎ｒ

印■薯田悪霊岳＝ニーー■巴四ヱ

ーー云己＝￣■■■■■I■■■■■■■■■ﾛ■■

＝■■■■I■■■■￣￣￣＝已狸＝己

－－１■■■■￣壁■￣￣■型＝￣

￣￣￣￣し■丁一－二些延ヨー

印■覇ﾛ呈呈笘鵠二塁鎧悪呈三二芒三 一＝雨五一＝■■■■■￣■■■■■■

￣■■■■■■￣□且声一■■と⑫と已已

￣■---＝軸■￣＝■些四已已

￣■■，1匹■￣￣￣批酉一

ＤＭＢｍｍ ＭＪＴＴｎ肚可

Ｌ、】ＷＡ－ＰＳＯＬＤＩＷＡ－Ｄ－ＰＳＯＬＤｍ川Ａ‐

ロ『⑭ｍＲＵｎｎ国ZEE迄回ｐＤＥｍｍｎｎ曰ＴＦ毎回n匹ｍＤｕｎｎ DuviBIm

NUm比啄 ＤＭＢｉｍ ■、【

ＭＪｍ罹守

二：:１１卍

￣non￣

T1able5Ackley nble2Ridge

DHUi亜皿 Mwn牲守 ＤＭ５ｍｍ

ＮＵｍ比莊

川

DUvi且Ｉｍ ＭＪｍ帷Ｔ ＤＭ邸亜

FI1vTn出了

、I咀皿四 ＭJ、帷丘 Dlvim面

ＮＦｕｍ絶守

D1viｮＩｍ ＭＪｍ惟庁 Divjm面

FIUvm比壺

】Ⅱ

￣￣■■■■■■■■■■■

■､日田■照ニニニニ黒雲＝■ニニエニ笘笘＝

ﾛ■■■■■＝死一一■■■■■■■■■■■■■■■■■■■■

￣■■■■■■■■■■■＝-”－－＝理＝￣

￣■■■■■■■■■■■￣巫虹＝￣￣■■≦江￣￣

￣￣■■■■■■■■■■■■■碑ユカ■■￣＝■■ＬｈＨ－－

■：臼田=辱票自豐ニニー鼻号豐笘蔦ﾆﾆﾆ鼎呈鵲

■■■■■■￣△￣＝￣■■■■■■■■■■■■■■■■■■■■

￣■■■■■■■■■■■■型ユー■－回型匹＝■■■

￣■■■■■■■■■■■－－■竺一■■■

■■■■■■■■■■■￣－－＝皿一■■■

ＤＭ巴ｕｍ ＮｕＹｍ雄ｒ

、耐前面 Ｎｗｎ肚守

四Luuu

■Ｆ了戸〒面可万三五■Ｔ宗呑口

■■■■■■■■F可ロー■■■■■■■■■■■■ﾛ■■■■

￣■■■■■■■■■■■旦堅一一＝■堅エ ー■■■■■■■■■■■ユー￣＝■些匹四

■■■■■■|■■■■■￣-埠四￣￣－１】“■■ _Dlvislon NIJm牌仔

R､毎F■rmn国?便臣■■uにmTRnn亜ＦＰ■団BにmTunnBUC[

DivinR面 ＮＵｍ陸Ｐ

】n面 】、

nｃｍ ＝旬

■■■■■ｎｏｎｌ■■■■■■■non

■■■■■ｎｏｎロ■■ロー■ｎｏｎ

■■■■■non＝￣■ロoｎ

mble6Griewank Tnblc3Roscnbrock

回■鰯5■黒聖=■二一房一一一一房一一＝

_{－－－－￣－－－}

－￣－－Ｆ￣￣■些型＝－

－￣￣四－－■Ｌ一一

＝－－－＝、－－￣-z－－

回■H田5■二黒当舍苦ﾆﾆﾆ号些呈器ﾆﾆﾆ砦些呈砦ニ

_{ーーーー￣￣￣－}

－－－－＝￣ご鋤■f＝－

－￣ローーー■型一一 一一一一一＝￣■－１反--＝￣

因■HWB■黒黒ニニニ黒晉=ﾆﾆﾆ勇二笘呂二

_－---＝

DlViSlDn NIJm槌牙 DlviHI■n

ＭJ、比守

ｎＭ口､■ｎ ＩｑｎＰｍ比＝

、Ｍ１亜 ＮＤｕｍ化可 DiviBim

NUmM宙

DmBIm

ＮＬＹｍ陀可ロ『但画Rn、亜FFP｡■０にｍｈｎｎロ｢厘田Tｕｎｎ釦回 旧Ｂ

ＤｍＢｕ亜 NPY、比可 ＤＭ■im

FInmu比＝

ＤＭ■Ｍｒｎ ＭＹｍ陸Ｐ ＤＭＢｉｍ

ＮＵＪｍｆ凶＝

■■■■■■■214ｺ１４66075

■■■■■■■IL DHvn皿亟

ＭＪｍ吋可u『侯mDDnnﾛ『■mrnnn巴Ⅱ0･ＥＰ空ﾛに西?0,,皿GＩ ＤＭ■ｌｍ

ＮｕＴｍ比汀 DIvipnm

IUum睦守

…,＝＝fr-■■

ParticleSwarmOptimizationの多様化に関する検討

7３

場合，分割数を増やすことで性能が落ちる場合がある．

これは，第１階層と第２階層との個体数の比率が関係 していると推測している．現在，全100個体で探索を 行っているが，第１階層に５０個，第２階層に５０個割 り当てている．よって，例えば分割数が１０の場合，第 １階層の１グループ辺りの個体数は５個となる．この ことから，１グループ辺りの個体数が減少することで，

局所的な探索性能が衰えていると考えられる．

5.3Migrationにおける探索`性能の検討

D-PSQDH-PSOでは，Migrationという操作があ る．この操作の間隔による探索性能の検討を行う．

LｐＣＯＯ

ＬＯＯ

■ロムＵ｜ロゴ、』『■■邑勺凸守・

凹的ご正「

ＤｎＶＺＤ１ｏｎ｡Ｚ－

Ｄ１ＶｌＱｑｍ⑰日.｡-……

ｐｌｖＺＢ１ｏｎ■no……･･･

Ｃｌ▼２，．⑥－２－

ＤＬｖｌｏｑ－－Ｆ－･…｡

､1▼i■ＩＣ､ロユ０．.……

刀..■

２４６０ ００００

０●ｃ 漣ⅡＩ

&割些馳jh::苫隆…か，

５０IOC190200290]ＯＧO9OlCO250ZOO２５０ｊＯＯ ｌ［ｏｚｑ上１．，１上P亟璽型！

Fig.1５評価値と活性度の推移(Ridgefimction）

陥ることを抑制しているためであると推察できる．

Fig.１５は，１０次元Ridge関数のD-PSOを適用したと きの分割数毎の評価値と活性度の比較である．グラフ より周期的に活性度が高まっていることがわかる．こ れは，ちょうど移住が起きた状態を示している．この とき，分割数が大きいほど活性度が大きくなっている．

このことから，分割数が大きいほど全体的により多く 移動していると考えられ，このことから広範囲を探索 できていると考えられる．そのため，少ない分割数で 探索を行うよりも比較的安定した探索が行えると考え られる．しかし，活性度を大きくすることで逆に局所 的な探索能力が衰える可能性がある．Fig.１５の評価値 より分割数が大きいと収束に時間がかかってしまう．

これは，単峰性関数の問題においては，分割数を少な くし，局所的な探索能力を向上させることで短時間で の最適解の探索を可能にしていると考えられる．

ＵＣ⑤□⑤

ユ００

ｎＯＯＯ ｍＯ ｌ０

０．１ ０，Ｏｌ ｄ。ＯＯｎ １Ｑ。OＯ Ｌｅ－Ｄ１ｊ ＬＱＣＯＧ ＬＯ－Ｏプ

､塒Z■巳』、ロコー ロ｣ｇｍＬ１ｏｎ■9.-…･

■j師Ｄｔ２ｏｎＣ２Ｏ・…叩.

:鑑::l鵲:;:.二

ＯｐＯＵ

”･００

１■－００

１●。Ｏ、 、、

5０100LSOzOO２ＤＣ

」tcmtL唖 ClOOO200C］O0000COQDOOOOOOO7OOOOOOO90qO1OOOO i上●r－１ｍ

Fig.1７Ridgefimction Fig」８Rosenbrockfimction Figl9Migration間隔における解比較

Fig.17,Fig.１８では，単峰性関数の中で探索が比較的 困難である１０次元のRidge関数と多峰性関数の中で比 較的困難である１０次元のRosenbmck関数のMigration 間隔における比較を行っている．結果より単峰性関数 の探索では，Migrationの間隔が短いほど探索が速く 行われていることから，Migration間隔を短くするこ とで局所的な探索を効率よく行われていると見受けら れる．つまり，Migration間隔が短いほど局所探索性能 が向上すると推測できる．これに対し，Rosenbmck関 数では，Migration間隔が短いと探索に失敗している．

これは，局所探索性能が向上し，多様性を保つ性能が 減衰しているため，局所解に陥り，大域的最適解の発 見が出来なくなっていると考えられる．

5.4リスタートにおける性能の検討

ＤＨＰＳＯはある一定のiterationにおいてリスタート を行う．リスタートは，上位階層の探索で多様化が保た れなくなり，広域的な探索が抑制され，局所的な探索に

陥ることを抑制しているFig22は，１０次元Ridge関

数,Rosenbrock関数における３，５，１０，２０，３０itelation 毎でリスタートを行った場合の活性度である．実験結 果では，リスタートの間隔が短いほど，活性度が高い．

これは，間隔が短いと広域な探索域を探索する可能性 があると考えられる．

Fig25は，１０次元Ridge関数，Rosenbrock関数にお ける３，５，１０，２０，３０iteration毎でリスタートを行つ

０００３日、“的妬賄硯００２ ０Ｌ ｃ。。◆。ご●０⑨功、狛炬Ⅱ

『Ｈ』■

Ｈｏ･ユ

０．０１

ＤＵＯＯＤｚＯＯＯ〕ＯＯＯＯＯＯＯ曰OOO60007DOOOOCODOOO300上

』上⑧亟皿⑤fＴ ＯﾕOOO2OCO］ODOOOOO900C6DOO7000DOOCpCOＯ２ＯＯＤＯ iEcPznEmn

Fig.1６評価値と活性度の推移(Rosenbrockfimction）

Fig.１６は，１０次元のRosenbmckfilnctionの評価値と 活性度の推移を示している．活,性度の推移より，個体 を２分割(Division=2）したときでは，時期早々に活性 度が落ち込み，その後変化していない．これは，時期 早々に局所解に陥り抜け出すことが出来ない状態であ ると見受けられる．また，個体を１０分割(Division=10）

したときでは，探索後半において階段状に活性度が低 くなっていることから，探索後半において，更なる良 好な探索域を発見していることが，評価値の計測結果 からも確認できる．このことから分割数を増やすこと で，時期早々に局所解に陥ることを防ぎ，migrationに よって新たな探索域の探索が行われていると推察でき る．しかし，Rosenbrock関数でＤＨＰＳＯを適用した

漣^{＝￣くわ□■．}

^Ｉ

赤igrct1m■Ｄ－

ｍｌ９ｍＬＩｏｎ･９－－－

■１９ｍ上人“■１０．．.…

＆

DW1●10ｎｎＺ－－－－

Ｄ４ｖＩ二.亜Q-z…･面･･･

D1v1の1句③■l０．…･…．

！。

』

『０４」 。

■ Ｆ 一

、

、

林孝志郎・片山謙吾・南原英生・成久洋之

7４

Ｚら

２０

ｺB

8

1q

参考文献

１）Ｊ､KennedyandR・CEbelhart,“ParticleSwannOptimization,'，

Proc､oflFFFthelntemationalConferenceonNeuralNetworks，

ｐｐ､1942-1948,1995.

2）Ｒ､CEberhartandJKcnnedyl`§ANewOptimizerUsingPalticle SwarmTheory,ｌｌＰｒｏｃ､oftheSixthlntemationalSymposiumon MicromachineandHumanScicnce,pp39L43,１９９５．

３）Ｒ､Ｃ・Eberhart,Simpson,ＲＫ.,andDobbins,Ｒ､Ｗ,"Computa‐

tionallntelligencePCtools11，１stc｡､edBoston,ＭＡ:Academic pressprofessional,1996.

4）ＹＳｈｉ,Ｒ・CEbcrhart,andlKcnnedyl"Paramctersclectioninparと ticlcswarmoptimization1，,EvolutionaryParogrammingVII,Proc・

ＥＰ９８,ｐｐ､591-600,Springe炉Verlag,ＮｅｗＹｏｒｋ,１９９８．

５）武居麻里，安田恵一郎，“ParticleSwarmOptimizationにおける 制約条件の取り扱い，１，平成１９年度電気学会電子・情報・

システム部門大会講演論文集，ｐｐ,805-810,2007.

6）安田恵一郎，“進化論的計算手法とメタヒユーリステイクズ,，

電学論Ｃ，VbL122-C,Ｎｏ３，ｐｐ､320-323,2002.

7）平岡創土，岡本卓，相吉英太郎，“繰り返し型探索指針とそれ に基づくParticleSwarmOptimizationの改良手法の提案，１，平 成１９年度電気学会電子・'情報・システム部門大会講演論文 集，pp83作843,2007.

8）ＲＣ,EberhartandYShi,“Comparingincrtiaweightsandcon‐

ｓ位ictionsfactorsinparticleswarmoptimization,ｉ１Ｐｒｏｃ・ofthe CongressonEvolutionaryComputation(CEC2000)，ｐp84-88,

2000.

9）Ｊ・KennedyandR・CEberhart,“Swarmlntelligence,'，Molgan

KaufillannPUblishers,2001.

10）山口晃歓，岩崎信弘，安田恵一郎，“最良解情報を用いた適 応型ParticleSwamlOptimization,１，電学論Ｃ，Vbll26，No.２，

ｐｐ,270-276,2006.

11）Ｊ・JLiang,Ａ､Ｋ,Qin,PonnuthruraiNagaratnam,ａｎｄＳ､Baskar，

‘`ComprchensivcLcarningParticleSwarmOptimizcrfbrG1obal OptimizationofMultimodalFunctions,WIEEETiFansofEvolution- aryComp.Ｖb1.10,No.3,2006.

12）Ｇ､ＧＹｅｎ,andMoaycdDaneshyari,"Diversity-basedInfbrmation ExchangeamongMultipleSwarmsinParticleSwarmOptimiza- tion,''１EEECongrCssonEvolutionaryComputation(CEC2006）

ShcratonVancoUberWaUCentrchotＣｌ,VancoubeBBC,Canada，

ｐｐ､6150-6157,2006.

13）SJansonandＭ・Middendorf;`§AHierarchicalParticleSwarmOp‐

timizerandltsAdaptiveVariant,I01EEETYansactiononSystcm，

Man,andCybemetics-PalB:Cybemetics,Ｖ01.35,No.6,ｐｐ､1272-

1282,2005.

８６０３１日００２

℃●■。■０■□２１Ｊ。。ｎｏ００

Ｈ芝

禰璽留鰹幾N

5０3９０１９０２００２９０３００］ＳＣＯヨＣ１００２９◎３００２９０］ＯＯ

ｉＥごｍＥ１ｍＤ Ｉｔｏｍｔｌｍ

Fig2ORidgefimction Fig21Rosenbmckfilnction Fig22リスタート間隔における活性度の比較

100 10

函顛１ｍ叫峠“００■●

０８●

Ｒ●■curと。。~

■●■上■rEp９．－．－

m図U楡WiliiIJ

Ｖ

８１Ⅱ４５０７ ．００００００ ０００。ロー● ００●●。●ＯＬ１２３

二円》】

5０1001５０２００２９ｺ］ＣＯ Ａ上０ｍ上8ｍ

Sc1００，５０2Ｃ○250DOO３９［

」ての‐…ｑ…

Fig.2３RidgefimctionFig､2４Rosenbrockfimction Fig25リスタート間隔における評価値の比較 た場合の評価値の推移を比較した結果である．どちら の問題例においても，３iterationまたはSiterationが少 ないiterationで大域的最適解を発見している寸活性度，

評価値の双方の結果より，リスタートのタイミングが 比較的短いほど，広域的な探索が効率よく行われてい ることが観測できる．

6．むすび

本論文では，ＰＳＯの研究で過去に非常に有効なパラ メータであると知られているＬＤＩＷＡと経験的に得た 有効なパラメータについて検討を行い，更に分割法の‐

PSO)と，これに階層化を加えたＤＨＰＳＯについて調 査し，その多様性について検討を行った．実験結果よ りＬＤＩＷＡは，１集団で行われるＰＳＯに対しては，多 様的な探索から局所的な探索に切り替えた探索が行わ れるため，固定パラメータの探索より多様的な探索に ついての有効性が確認できる．D-PSOは，群を分割す るため探索終盤においても，多様化が行われているが，

比較的初期段階での大域的最適解の発見が必要になる と推測できる．これに対し，DH-PSOは，探索終盤で も上位の階層が多様性を保ちつつ下位の階層では詳細 な探索が行われていることから，広域的な探索と局所 的な探索のバランスが取れていると考えられる．また，

２０試行中の探索の成功回数も多いことから，ＰＳＯや D-PSOと比較して，ロバスト性に優れた手法であると 考えられる．

ParticleSwarmOptimizationの多様化に関する検討

7５

4．Rastriginfimction

Ａ付録

_〃

F)?.…(J『)=10"+Ｚ(毒-10･Cs(2派jr,)）_ノー１ ^(17）

A1TbstFunction

本論文で使用する代表的なベンチマーク問題例を示 す．なお，ｎは次元数を示す．

LSpherefilnction

_〃

舟,胸籔.(j【)=Ｚｘ？（'4）_ｉ＝１

（-5.12≦xi≦5.12）

〃"(FRas"igW))＝Ｆ(0,0,…,O)＝0

⑭

暉鈴恋鰯淨鹸玲雰冴

il1llIl1111il1； lil

矼年⑨斗乃尻守ムグＧＦ乃鈩■■＆？●』Ｊ・△ｐ■⑪

（-100≦ｘｊ≦100）

〃"(Fbph"・(x))＝Ｆ(0,0,…，O)＝0

｡Ｕ

汀悪２

；きｅ

弓勿

Ｃ

､５．』

・ＷＦＲＳ

§ 》》辮牌好サブ－

８９８

lil

5．Ackleyfilnction

:○沙 醗斡§

…-肌叩｛０ｺ凧

一抑Ｉ増…ﾙⅢ川

Fig.2７等高線 Fig.2６ランドスケープ

zRidgefilnction

=|剤

Fh岬(x)＝ (15）

（-32.768≦xi≦32.768）

〃"(EdcA匂(x))＝Ｆ(0,0,…,O)＝0

（-64≦ｘ'三６４）

〃"(Fh噸(x))＝Ｆ(0,0,…,O)＝０

４つ

＊Ｓ

３Ｇ Ｂｓ

Ｐ８句 1,Ｊ０ ３２ つ４侭

へり殉》で謎比布Ｑ〉色冴べこへザ勺》勺４勺⑪○＄②０℃◆丹やら

又お みｃ

Ｉ

公８■ずロ

忽搾》穴．〉「の角 。。品ｒザ。》、》》群秤、》癖タケｒ■ワヴ口。◆、グ『堆準評昧一殿一》》》一》一『》》》》》》》》》》一一一印一‐。咄一Ｍ》、⑤負■、△『わタマ、乱ケムⅡ△Ｂ

Ｇ

甲,》

僻・”難２悪9３６識９００９

、,や'３｡“,率◇率神１９６＄⑭

Fig.3５等高線 Fig.3４ランドスケープ

Fig.2８ランドスケープ ３．Rosenbrockfimction

_〃－１

A…"ルニ(,00(毒

Fig.2９等高線

6．Griewankfimction

-卿)2+(Ｍ)`）

（16） ^Fb,jeMmk＝

喜論-口｡．.(蓋） ^＋１

（-600≦jrj≦600）

〃"(凡,.…,,A(x))＝Ｆ(0,0,…，O)＝０

（-2.048≦xj≦2.048）

〃"(FR｡…mcAc))＝Ｆ(1,1,…，1)＝0

みつⅡ ４＄凶 苫沙８１

⑱

６９引

２．２

や」Ｆ●妙心》ぷ時が。勺■且ｂ０

》矛；蘂…：Ｌｉ腸１１穂 》‐■小、‐に・勺．‐‐・声‐悪‐函‐評岼‐糾西》冬少も」Ｐど■‐．」枅川》雌》》一》》》》》『一》一一》》》》》一》』一一》一一一一

鈴ゼウ３ ５，Ｐ ＯＳ ＸＡ

汐千四」屯汀⑥内々毛）

。（乱．、ト．△聖●④●。‐・‐」ら路ご● 巴寺

ふさ

蛍轌｡,＆可､？･尻辣鯵か苧ＣＯ“色守り ８＄K:と

６`、"Ｚ.Ｏご＄秒峰ｂも6ム､勝之ヨル３

Fig.3６ランドスケープ Fig.3７等高線

Fig.3０ランドスケープ Fig.3１等高線

76

On Diversity of Particle Swarm Optimization Methods

Koushirou HAYASHI, Kengo KATAYAMA*, Hideo MINAMIHARA*

and Hiroyuki NARIHISA*

Graduate School of Engineering,

^Department of Information and Computer Engineering, Faculty of Engineering,

Okayama University of Science, 1-1 Ridai-cho, Okayama 700-0005, Japan (Received October 1, 2007; accepted November 2, 2007)

Particle Swarm Optimization (PSO) is one of the most powerful metaheuristic algorithms for solving global optimiza tion problems such as function optimization problem. PSO has demonstrated a great performance, however, it often leads to premature convergence in local optima. To enhance standard PSO algorithms, we consider the diversification of the search. Particularly, we focus on a distributed version and a hierarchical version to maintain the diversity. We investigate several parameters of the PSOs and LDIWA (Linearly Decreasing Inertia Weight Approach). Computational results on the benchmark functions demonstrate that these PSOs outperform the standard PSO, and the performance of the distributed and hierarchical PSO is highly effective in terms of the diversity and reaching the global optimal solution for hard functions.

Keywords: particle swarm optimization; linearly decreasing inertia weight approach; diversty.