第22回 回路とシステム
軽井沢ワークショップ
The 22nd Workshop on Circuits and Systems
in Karuizawa, April 20-21, 2009

近傍関係を考慮するネットワーク構造型粒子群最適化法

Network-Structured Particle Swarm Optimizer
松下春奈 †西尾芳文 †† 徳島大学 工学部 電気電子工学科

Haruna MATSUSHITA†
Yoshifumi NISHIO††Department of Electrical and Electronic Engineering, Tokushima University
1

はじめには 2 次元ネットワーク上での近傍に従い結合されており，直接結合された粒子間，つまりネットワーク粒子群最適化 (Particle Swarm Optimization:上の近傍粒子間で，それらが最も良かった位置を情PSO) は，鳥の群れの動きをモデル化した進化アルゴ報交換する．また，ステップ毎にその時最も良い位リズムの一種である．概念が単純であり実現が容易置を持つ粒子を勝者とし，ネットワーク上の勝者とな上，収束が早いという特徴を持つことから，近年，の近傍距離に従い各粒子は更新される．
異なる分野の様々な応用に用いられている．しかし提案手法の有効性を確認するために，単峰性と多ながら，パラメータに大きく依存することや，多数の局所解を持つような複雑な問題を解く場合におい 峰性それぞれ 4 つの評価関数に対してシミュレーショての早すぎる収束などが，PSO の問題点として挙げ ンを行う．従来の PSO と比較することにより，正確性，ロバスト性，パラメータ依存性の観点から評価られている．
PSO は複数の解 (粒子) 群で構成され，各粒子は し，NS-PSO が探索能力を効果的に高めることを確
位置と速度の情報を持っている，通常 PSO は，これ 認する．
らの情報を群内で交換しながら良好な位置を探すが，粒子間に特別な繋がりはない．つまり，各粒子の情報は固体が最も良かった位置と群全体で最も良かった位置に従って更新するが，どちらを重要視するかの割合は毎更新ごとにランダムで決められる．一方，実社会においては，上下関係，信頼関係，親子関係などの様々な人間関係が存在している．

2

Particle Swarm Optimization (PSO)

PSO には粒子と呼ばれる複数の解が存在しており，各更新では，固体の最良の位置と群全体での最良の位置に向かうように動く．各粒子は，位置 X i = (xi1 , · · · , xid , · · · , xiD ) と速度 V i =PSO における様々なトポロジー近傍については， (vi1 , · · · , vid , · · · , viD ) の情報を持っている．ここで，以前から議論されてきており [2]–[6]，リング型近傍， (d = 1, 2, · · · , D)，(i = 1, 2, · · · , M )，xid ∈ノイマン近傍，ランダム近傍などのあらゆるトポロ [xmin , xmax ] とする．
ジー近傍が適用されてきた．しかしながら，粒子情報(PSO1) (初期化) t = 0 とし，粒子 i の位置 X iを更新する際の近傍を考慮するための新しい項，及をランダムに，速度 V i を 0 に初期化する．P i =びそれに伴うパラメータの増加などが懸念されてい(pi1 , pi2 , · · · , piD ) を現在位置 X i に初期化する．各る．また，“近傍” の概念についてはいくつかの考え
粒子 i に対し目的関数 f (X i ) を計算し，P g を群全体方があり，複数の研究においては，似た評価値を持で最も良い評価値を持つ粒子の位置に初期化する．
つ粒子や空間で近くに位置する粒子が近傍粒子として定義されてきた．しかし，粒子間に結合関係がな (PSO2) 適応度 f (X i ) を計算する．各粒子に対して，い場合，更新の度に近傍粒子を見つけ出す必要があ f (X i ) < f (P i ) であれば，自己最高の位置 (pbest) を置き換える (P i = X i )．P g を群全体において今までり，計算量が増大するといった問題がある．
本研究では，近傍関係を考慮するネットワーク構 で最良の位置 (gbest) とし，必要があれば更新する．
造型 PSO(NS-PSO) を提案する．NS-PSO の全粒子(PSO3) pbest と gbest に応じて，粒子 i の V i と X i− 295 −を更新する．

vid (t + 1) = wvid (t) + c1 rand(·) (pid − xid (t))+ c2 Rand(·) (pg − xid (t)) (1)12345Neighborhood 6A

78910 Neighborhood

111213141516171819202122232425

xid (t + 1) = xid (t) + vid (t + 1)
ここで，w は慣性重みであり，以前の速度をどれだけ保持するかを決める．c1 ，c2 は正の加速度係数であり，通常 c1 = c2 とする. rand(·)，Rand(·) は U (0, 1)における一様ランダム値である．

(PSO4) t = t + 1 とし，(PSO2) に戻る．
3

近傍関係を考慮するネットワーク構造型 PSO(NS-PSO)

NS-PSO は通常の PSO と同様にシンプルなアルゴリズムで成り立っている．NS-PSO の最も重要な特徴は，全粒子が図 1 のように二次元グリッド上で編成されており，粒子は隣接した粒子と結合されていることから，近傍関係を持っていることである．また，粒子は直接結合された近傍粒子間で，ローカルな最良の位置を交換する．ここで，本研究における“近傍” の定義について記述する．複数の研究においては，似た評価値を持つ粒子や空間で近くに位置する粒子が，近傍粒子として定義されてきた．しかし本研究では，たとえ評価値や位置が離れていたとしても，ネットワーク上で直接結合されている粒子を“近傍” とする．

B

図 1: ネットワーク構造と近傍関係．粒子 12 の近傍は粒子 7, 11, 12, 13, 17 を含む Neighborhood A である．
粒子 14 の近傍は粒子 9, 13, 14, 15, 19 を含む Neighborhood B である．もし f (P 13 ) が Neighborhood A
内で最小の値なら，粒子 12 の lbest は L12 = P 13 となる．もし f (P 14 ) が Neighborhood B 内で最小の値，粒子 14 の lbest は L14 = P 14 となる．

(NS-PSO4) 各粒子 i の V i と X i を，lbest，勝者の位置 X c 及び勝者 c とのネットワーク上の近傍距離に従い更新する．
vid (t + 1) = wvid (t) + c1 rand(·) (lid − xid (t))+ c2 hc,i (xcd − xid (t))(3)

xid (t + 1) = xid (t) + vid (t + 1)
ここで，hc,i は近傍関数と呼ばれるガウス関数である．

r i − r c 2
hc,i = exp −2σ 2(4)(NS-PSO1) (初期化) ステップを t = 0 とし，(PSO1) に従い粒子情報を初期化する．gbest の粒子
g を勝者粒子 c とする．Li = (li1 , li2 , · · · , liD ) を，直 r i − r c  は勝者 c と粒子 i のネットワーク上の距離，接結合された粒子間，つまり近傍粒子間で，最良評 σ は近傍関数の幅に対応する固定パラメータである．
σ が大きいと粒子群が空間全体に広がる力を強め，価値を持つ粒子の位置に初期化する．
(NS-PSO2) 適応度 f (X i ) を計算し，現ステップ t が小さいと粒子群が勝者に近づく収束力を強める．
(NS-PSO5) t = t + 1 とし，(NS-PSO2) に戻る．
において最良の評価値を持つ粒子を勝者 c とする．
c = arg min{f (X i (t))}i(2)

各粒子 i に対して，f (X i ) < f (P i ) であれば pbestを置き換える (P i = X i ).
もし f (X c ) < f (P g ) であれば，gbest を置き換える (P g = X c )．ここで，X c = (xc1 , xc2 , · · · , xcD )は勝者 c の位置である．

(NS-PSO3) Li を，粒子 i とネットワーク上で直接結合された近傍粒子内の今までで最良の位置 (lbest)とし，必要であれば更新する (図 1 参照)．

4

シミュレーション結果

NS-PSO の性能を評価するために，従来型 PSOとの比較実験を行った．用いたのは表 1 に示される8 つのベンチマーク最適化問題で，f1 ，f2 ，f3 及びf4 は単峰性関数 (図 2(a)–(d) 参照)，f5 ，f6 ，f7 及びf8 は多くの局所解を持つ多峰性関数 (図 2(e)–(h) 参照) である．図 2(h) において，Griewank 関数は単峰性関数である Sphere 関数 (図 2(a)) と類似しているように見えるが，中心付近を拡大すると多くの小さな山と谷が存在する．Rosenbrock 関数 f2 の最適− 296 −表 1: 8 つの最適化関数．
関数名Sphere;
Rosenbrock;

関数式

f1 (x) =f2 (x) =初期空間
D−1x ∈ [−2.048, 2.047]Dx2i ,d=1D−122100 x2d − xd+1 + (1 − xd ) ,x ∈ [−2.048, 2.047]D

d=1

3rd De Jong;
4th De Jong;

f3 (x) =f4 (x) =

D

d=1
D


|xd |,x ∈ [−2.048, 2.047]D

dx4d ,x ∈ [−1.28, 1.27]D

d=1

Rastrigin;
Ackley;f5 (x) =f6 (x) =D
x2d − 10 cos (2πxd ) + 10 ,d=1D−1

20 + e − 20e−0.2

d=1D−1√x ∈ [−5.12, 5.12]D0.5(x2d +x2d+1 )−e0.5(cos(2πxd )+cos(2πxd+1 )) ,x ∈ [−30, 30]D
(x2d + x2d+1 )0.25 1 + sin2 (50(x2d + x2d+1 )0.1 ) ,x ∈ [−10, 10]DStretched V sine wave;

f7 (x) =Griewank;DD
x2dxd−f8 (x) =cos √+ 1,4000
dd=1

d=1

d=1

解 x∗ は [1, 1, . . . , 1] で，それ以外の関数の x∗ は全て[0, 0, . . . , 0] である．全関数において最適評価値 f (x∗ )は 0 である．全関数は D 個の変数を持っており，本研究では D = 50 に設定する．

PSO の全粒子数 M は 36 に，MS-PSO のネット
ワークサイズは 6 × 6 に設定した．PSO および MSPSO においてパラメータは w = 0.7，c1 = c2 = 1.6とし，MS-PSO の近傍幅 σ は 1.5 とする．
3000 generations を一回のシミュレーションとし，30 回試行したときの gbest の最小値，平均値及び標準偏差を表 2 に示す．これを見ると，全ベンチマーク関数において MS-PSO が良い値を得られていることがわかる．特に f1 ，f3 ，f4 及び f8 に関しては，MS-PSO は PSO の結果を大きく改善しており，さらに，7 つの関数においてより良い最小値に到達できている．
5x ∈ [−600, 600]D

パラメータ依存性

ff1f2
f3f4
f5f6
f7f8

さらに，慣性重み w の性能評価への効果と，そのパラメータ鋭敏性について考察する．
図 4 は異なる w を用い，それぞれ 30 回試行したgbest の平均を示している．固定パラメータ c1 = c2− 297 −

表 2: PSO と MS-PSO の比較結果．
MethodMean
Minimum
Std

PSO
MS-PSO
PSO
MS-PSO
PSO
MS-PSO
PSO
MS-PSO
PSO
MS-PSO
PSO
MS-PSO
PSO
MS-PSO
PSO
MS-PSO

2.31e-18
8.34e-26
55.88
41.60
1.70e-06
1.59e-07
9.83e-36
3.27e-42
149.7187.69
235.98180.7969.88
37.08
9.10e-02
2.61e-02

1.25e-25
2.16e-30
16.33
37.22
1.15e-09
3.16e-12
1.34e-41
9.94e-48
99.50
54.72
123.85
10.32
49.71
17.72
00

1.26e-17
2.74e-25
27.55
9.63
6.81e-06
7.46e-07
4.15e-35
1.13e-41
34.84
21.91
59.03
239.379.517.910.2788
4.11e-02x 101281065846344252210220050000−500−2(a)01250000−202−500−2(b)(c)

258200206150

410050151020

5205001050−5−5(e)201020000−20−200−10 −10(f)

(g)

−1(d)

60

00−1−28040

1000500
50000−500−500(h)図 2: 8 つのベンチマーク最適化関数．1 番目と 2 番目の変数値をそれぞれ X 軸，Y 軸とし，Z 軸は対応する関数値を示している．(a) Sphere. (b) Rosenbrock. (c) 3rd De Jong. (d) 4th De Jong. (e) Rastrigin.
(f) Ackley. (g) Stretched V sine wave. (h) Griewank.

及び σ は，4 章で用いたものと同じとした．この図から，たとえ慣性重み w を変化させたとしても，MSPSO は PSO よりも良い性能を示していることがわ
かる．さらに，たとえ w の値を 0.1 増減させただけだとしても，PSO の性能は大きく悪くなってしまっており，特に図 4(a)–(d), (g) 及び (h) においてその様子が顕著に見られる．一方，MS-PSO は慣性重みw が小さな値 (w ∈ [0.1, 0.6]) だとしても PSO よりも良い値を得られており [7]，特に図 4(e)–(h) の様な多峰性関数において安定した結果を示している．これらの結果から，MS-PSO はより高性能であり，そのパラメータ依存性は従来の PSO の比べてそれほど強くないことがわかる．

6

おわりに

本研究では，トポロジー近傍を持った新しい粒子群最適化法 (Particle Swarm Optimization: PSO) である，近傍関係を考慮するネットワーク構造型 PSO(NS-PSO) を提案した．NS-PSO の全粒子は，2 次元格子ネットワークにおける近傍関係に従って隣接する粒子と結合されており，直接結合されている粒子間で各自の最良の位置を情報交換する．また，ステップ毎にその時最も良い位置を持つ粒子を勝者粒子とし，各粒子は勝者とのネットワーク上の近傍距離に従い更新される．

単峰性と多峰性それぞれ 4 つの評価関数に対してシミュレーションを行った．それらの結果より，PSO とNS-PSO の正確性，ロバスト性及びパラメータ依存性の観点から比較し，NS-PSO の総合的性能が PSOよりも有効でロバストであることを明らかにした．
今後の課題として，様々なネットワークトポロジーを持った NS-PSO の振る舞いを調査するとともに，ネットワーク構造と性能の関係性をさらに詳しく調査する必要がある．
参考文献[1] J. Kennedy and R. C. Eberhart, “Particleswarm optimization,” in Proc. IEEE. Int.
Conf. Neural Netw., pp. 1942–1948, 1995.
[2] J. Kennedy, “Small worlds and mega-minds:
eﬀects of neighborhood topology on particle
swarm performance,” in Proc. of Cong. onEvolut. Comput., pp. 1931–1938, 1999.
[3] J. Kennedy and R. Mendes, “Population structure and particle swarm performance,” in Proc.
of Cong. on Evolut. Comput., pp. 1671–1676,2002.
[4] R. Mendes, J. Kennedy and J. Neves, “TheFully Informed Particle Swarm: Simpler,− 298 −

10510PSO
NS−SOM010−1010−2010Function Value log(f(x))

Function Value log(f(x))

10−30100PSONS−PSO

4103102101500

1000
1500
2000
Number of Generation t

2500

1030000500(a)2500

3000(b)20510PSO
NS−SOM010−510Function Value log(f(x))

10Function Value log(f(x))

1000
1500
2000
Number of Generation t−10100PSO
NS−PSO010−2010−4010−60500

1000
1500
2000
Number of Generation t

2500

1030000500(c)

1000
1500
2000
Number of Generation t

2500

3000(d)3PSO
NS−SOM

210

Function Value log(f(x))

Function Value log(f(x))

10010101011010500

1000
1500
2000
Number of Generation t

2500

2.9PSONS−SOM

2.72.52.3

30000500(e)42101

Function Value log(f(x))

Function Value log(f(x))

3000

10PSO
MS−PSO02500(f)310101000
1500
2000
Number of Generation t

PSO
NS−SOM
210010−2500

1000
1500
2000
Number of Generation t

2500

3000

10(g)

0500

1000
1500
2000
Number of Generation t

2500

3000(h)

図 3: 毎 generation の gbest の平均値．D = 50. (a) Sphere. (b) Rosenbrock. (c) 3rd De Jong. (d) 4th De
Jong. (e) Rastrigin. (f) Ackley. (g) Stretched V sine wave. (h) Griewank.

Maybe Better,” in IEEE Trans. Evolut. Comput., vol. 8, no.3, pp. 204–210, June 2004.
[5] J. Lane, A. Engelbrecht and J. Gain, “Particle
Swarm Optimization with Spatially Meaningful Neighbours” in Proc. of IEEE Swarm Intelligence Symposium, 2008.

mization with Dynamic Neighborhood Topology: Three Neighborhood Strategies and Preliminary Results” in Proc. of IEEE Swarm Intelligence Symposium, 2008.
[7] X. Xie, W. Zang and Z. Yang, “A dissipativeswarm optimization” in Proc. of Cong. on Evolut. Comput., pp. 1456–1461, 2002.

[6] S. B. Akat and V. Gazi, “Particle Swarm Opti-− 299 −1041010PSO
NS−PSO

0PSO
NS−PSO
3log(f(x))

log(f(x))

10−10

10

−20

102

1010−30

100.1

1

0.2

0.3

0.4

0.5

0.6

0.7

100.8

0.1

0.2

0.3

0.4w

(a)
10PSO
NS−PSO

10log(f(x))

log(f(x))

010−5101010−100.1

0.2

0.3

0.6

0.7

0.8(b)

5

10100.5w

0.4

0.5

0.6

0.7

100.820PSO
NS−PSO

0−20−40−60

0.1

0.2

0.3

0.4

w

0.5

0.6

0.7

0.8

0.5

0.6

0.7

0.8w(c)(d)

33

1010log(f(x))

log(f(x))

PSO
NS−PSO

2

101

10

0.1

2

10

1

0.2

0.3

0.4

0.5

0.6

0.7

10

0.8

0.1

PSO
NS−PSO
0.2

0.3

0.4

ww

(e)

(f)

3

10

104

2

10

1

100.1

PSO
NS−PSOlog(f(x))

log(f(x))

PSO
NS−PSO

0.2

0.3

0.4

0.5

0.6

0.7

0.8

1010102

0−2

0.1

0.2

0.3

0.4

w

0.5

0.60.70.8w(g)(h)

図 4: 異なる w の値に対する gbest の平均値．D = 50. 固定パラメータは c1 = c2 = 1.6 及び σ = 1.5 とする．
(a) Sphere. (b) Rosenbrock. (c) 3rd De Jong. (d) 4th De Jong. (e) Rastrigin. (f) Ackley. (g) Stretched
V sine wave. (h) Griewank.

− 300 −