信学技報
TECHNICAL REPORT OF IEICE.

社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

様々なトポロジーを持つネットワーク構造型粒子群最適化法とその振る舞い
松下 春奈†

西尾 芳文†† 徳島大学 工学部 電気電子工学科 〒 770–8506 徳島県徳島市南常三島 2–1
E-mail: †{haruna,nishio}@ee.tokushima-u.ac.jp
あらまし

本報告では，様々なトポロジーを持つネットワーク構造型粒子群最適化法（Network-Structured Particle

Swarm Optimizer: NS-PSO）を提案する．提案 PSO に長方形，六角形，円筒，トロイダルの 4 種のトポロジーをもたせ，8 つのベンチマーク最適化問題へ適用する．シミュレーションによりこれらの振る舞いを調査し，どのようなトポロジーがどのような最適化問題に適しているかを評価する．
キーワード

粒子群最適化（PSO），ネットワーク構造，自己組織化マップ（SOM）

Network-Structured Particle Swarm Optimizer with Various Topology
Haruna MATSUSHITA† and Yoshifumi NISHIO†† Department of Electrical and Electronic Engineering, Tokushima University
2–1 Minami-Josanjima, Tokushima 770-8506, Japan
E-mail: †{haruna,nishio}@ee.tokushima-u.ac.jp
Abstract This study proposes Network-Structured Particle Swarm Optimizer (NS-PSO) with various neighborhood topology. The proposed PSO has the various network topology as rectangular, hexagonal, cylinder and toroidal.
We apply NS-PSO with various topology to optimization problems. We investigate their behaviors and evaluate
what kind of topology would be the most appropriate for each function.
Key words Particle Swarm Optimization (PSO), network structure, Self-Organizing Map (SOM)

1. は じ め につに，自己組織化マップ（Self-Organizing Map: SOM） [2] がある．SOM は教師なしニューラルネットワークのひとつで，2粒子群最適化 (Particle Swarm Optimization: PSO) は，鳥もしくは 3 次元の低次元トポロジーに従い配置されたニューロの群れの動きをモデル化した群知能の一種である．概念が単純ンで構成されている．SOM は，マップ構造の近傍関係に従いであり実現が容易な上，収束が早いという特徴を持つことから，学習することで，入力の特徴を反映したマップを得ることが出

近年，異なる分野の様々な応用に用いられている．しかしなが来る．

ら，パラメータに大きく依存することや，多数の局所解を持つ

PSO における様々なトポロジー近傍については，以前からような複雑な問題を解く場合においての早すぎる収束などが，議論されてきており [3]– [7]，リング型近傍，ノイマン近傍，ラPSO の問題点として挙げられている．

ンダム近傍などのあらゆるトポロジー近傍が適用されてきた．

PSO は複数の解 (粒子) 群で構成され，各粒子は位置と速度

各粒子は，ネットワークの近傍間で最良の位置を共有しながらの情報を持っている．PSO は，これらの情報を群内で交換しな最適値に向かう．しかしながら，粒子情報の更新時に，ネットがら良好な位置を探すが，粒子間に特別な繋がりはない．つまワークの近傍距離は無関係であった．

り，各粒子の情報は固体が最も良かった位置と群全体で最も良先行研究として，近傍関係を考慮するネットワーク構造型

かった位置に従って更新するが，どちらを重要視するかの重みPSO (Network-Structured Particle Swarm Optimizer: NS-は毎更新ごとにランダムで決められる．しかしながら，実社会PSO) を提案している [8]．NS-PSO は，PSO と SOM の両方においては，上下関係，信頼関係，親子関係などの様々なネッの特徴を兼ね備えた最適化手法である．NS-PSO の全粒子は 2トワークが存在している．

次元ネットワーク上での近傍に従い結合されており，直接結合ネットワークを利用したアルゴリズムで代表的なもののひとされた粒子間，つまりネットワーク上の近傍粒子間で，それら—1—

ここで，本研究における “近傍” の意味について触れておかなければならない．多くの研究では，近い評価値を持つ粒子や，それぞれの位置が近い場所にある粒子のことを，近傍粒子と定義している．しかしながら，本研究では，それぞれの位置や評
(a)

(b)

(c)

(d)

図 1 Different map shapes with 10×10 particles. (a) Rectangular-topology. (b) Hexagonal-topology. (c) Cylinder-topology.
(d) Toroidal-topology.

価値にはかかわらず，ネットワーク上で直接結合された粒子を“近傍” と呼ぶ．
(Step1) t = 0 において，各粒子の位置 X i をランダムに，速度 V i を 0 に，pbest P i = (pi1 , pi2 , · · · , piD ) を X i に初期化が最も良かった位置を情報交換する．また，毎ステップ時に最する．各粒子 i の評価値 f (X i ) を計算し，群全体での最良の位良の位置を持つ粒子を勝者粒子とし，勝者とのネットワーク上置 gbest P g を決定，その粒子 g を勝者 c(0) とする．各粒子のでの近傍距離に従い各粒子は更新される．しかしながら，最適近傍間での最良の位置 lbest Li = (li1 , li2 , · · · , liD ) を決定する．

化の有効性と NS-PSO のネットワークトポロジーの関連性に(Step2) 評価値 f (X i ) を計算し，時間 t において群全体で最ついては，詳しく解明されていなかった．

良の位置を持つ粒子を勝者 c(t) に決定する．

そこで本研究では，様々な近傍トポロジーを持ったネットワー
ク構造型 PSO を提案する．これは，NS-PSO を，四角形，六角c(t) = arg min{f (X i (t))}.

(1)i形，円筒，トロイダルの 4 種のトポロジーに適用したものであ

各粒子 i において，f (X i ) < f (P i ) ならば pbest を P i = X iる．本提案手法は，単峰性，多峰性を含む 8 つのベンチマークとす る ．群 全 体で 今 ま で で 最 良 の位 置 P g (gbest) に対 し，関数に対してシミュレーションを行い，どのようなトポロジー

もし f (X c ) < f (P g ) ならば，P g = X c とする．ここで，がどのような関数に適しているかを調査する．シミュレーショ

X c = (xc1 , xc2 , · · · , xcD ) は勝者 c(t) の位置ベクトルである．

ン結果より，環状トポロジーは，各粒子の最良位置の情報が群(Step3) 粒子 i と直接結合されている近傍粒子間での今までの全体に伝わりやすいことから，単峰性関数に適していることを最良の位置 lbest Li を決定する．

確認する．また，六角形トポロジーには振る舞いの異なる様々(Step4) lbest，勝者の位置 X c (t)，i と c(t) の近傍距離に従い，な粒子が共存しており，早すぎる収束を防ぐことから，複雑な各粒子 i の V i と X i を更新する．

多峰性関数に効果的であることを確かめる．

2. ネットワーク構造を持つ粒子群最適化法（NSPSO）

V i (t + 1) = wV i (t) + c1 rand (Li − X i (t))+ c2 hc(t),i (X c − X i (t)) ,(2)X i (t + 1) = X i (t) + V i (t + 1),
通常，PSO には粒子と呼ばれる複数の解が存在しており，各更新では，固体の最良の位置 (pbest) と群全体での最良

ここで，w は慣性重みであり，以前の速度をどれだけ保持するの位置 (gbest) に向かうように動く．各粒子は，位置 X i =かを決める．c1 ，c2 は正の加速度係数であり，通常 c1 = c2 と(xi1 , · · · , xid , · · · , xiD ) と速度 V i = (vi1 , · · · , vid , · · · , viD )する. rand は U (0, 1) における D 次元一様ランダムベクトルの 情 報 を 持って い る ．こ こ で ，(d = 1, 2, · · · , D)，(i =である．また，hc,i は近傍関数と呼ばれるガウス関数である．

1, 2, · · · , M )，xid ∈ [xmin , xmax ] とする．
ネットワーク構造を持つ粒子群最適化法（NS-PSO）は，PSOと SOM の両方の特徴を持つ．NS-PSO の 3 つの重要な特徴は以下のとおりである．

1. 各粒子は，ネットワーク・トポロジーによって決定された近傍関係に従って結合されている．本研究では，図 1 に示される様々なネットワーク・トポロジーを NS-PSO に適用し，それらの振る舞いを調査する．図 1(a)–(b) の長方形トポロジーと六角形トポロジーはシート型トポロジー，図 1(c)–(d) の円筒トポロジーとトロイダルトポロジーは環状トポロジーと呼ばれる．

2. 各粒子は，直接結合された近傍粒子間でローカルな最良の位置 (lbest) を共有する．

3. SOM の学習と同様に，毎更新時において，全粒子の中で最良の評価値を持つ粒子を勝者に決定する．
これらの特徴から，NS-PSO の各粒子は，lbest，勝者粒子の位置，そして勝者とのネットワーク上での近傍距離に従い更新される．

„«
kr i − r c(t) k2hc(t),i = exp −,2σ 2(3)kr i − r c(t) k は勝者 c(t) と粒子 i のネットワーク上の近傍距離，σ は近傍関数の幅に対応する固定パラメータである．σ が大き
いと粒子群が空間全体に広がる力を強め，小さいと粒子群が勝者に近づく収束力を強める．

(Step5) t = t + 1 とし，(Step2) に戻る．

3. コンピュータ・シミュレーション
様々なトポロジーを持った NS-PSO の性能を評価するために，従来型 PSO との比較実験を行った．用いたのは表 1 に示される 8 つのベンチマーク最適化問題で，f1 ，f2 ，f3 及び f4
は単峰性関数，f5 ，f6 ，f7 及び f8 は多くの局所解を持つ多峰性関数である．Rosenbrock 関数 f2 の最適解 x∗ は [1, 1, . . . , 1]
で，それ以外の関数の x∗ は全て [0, 0, . . . , 0] である．全関数において最適評価値 f (x∗ ) は 0 である．また，全関数は D 次元の変数を持っており，本研究では D = 50 に設定する．

—2—

表 1 Eight Test Functions.

Function nameSphere function;

Test function
D−1X
f1 (x) =x2d ,Initialization spacex ∈ [−5.12, 5.12]D

d=1

Rosenbrock’s function;

f2 (x) =D−1X“”´2`
100 x2d − xd+1 + (1 − xd )2 ,x ∈ [−2.048, 2.048]D

d=1

3rd De Jong’s function;

f3 (x) =D
X|xd |,x ∈ [−2.048, 2.048]D

dx4d ,x ∈ [−1.28, 1.28]D

d=1

4th De Jong’s function;

f4 (x) =DX
d=1

Rastrigin’s function;

f5 (x) =DX` 2´
xd − 10 cos (2πxd ) + 10 ,x ∈ [−5.12, 5.12]D

d=1

Ackley’s function;

f6 (x) =D−1X„

20 + e − 20e”
−e0.5(cos(2πxd )+cos(2πxd+1 )) ,d=1

Stretched V sine wave func.; f7 (x) =q−0.2 0.5(x2+x2)
dd+1x ∈ [−30, 30]DD−1X`´(x2d + x2d+1 )0.25 1 + sin2 (50(x2d + x2d+1 )0.1 ) , x ∈ [−10, 10]Dd=1

Griewank’s function;

f8 (x) =DX
x2dd=14000−DY„cosd=1

PSO の全粒子数 M は 36 に，NS-PSO のネットワークサイxd√d«+ 1,x ∈ [−600, 600]D定した良い値を獲得している．

ズは 6 × 6 に設定した．PSO および NS-PSO においてパラメー

これらの結果から，トロイダルトポロジーのような環状 NS-タは w = 0.7，c1 = c2 = 1.6 とし，NS-PSO の近傍幅 σ は

PSO は単峰性関数に適しており，六角形トポロジーのような1.5 とする．シミュレーションは各関数に対し最大ステップ数

シート状 NS-PSO は多峰性関数に有効であるといえる．特に，を 3000 回とし，30 回探索を行う．

トロイダルトポロジーは多峰性関数のような複雑な問題には適3. 1 シミュレーション結果
30 回の探索における最小値と平均値を表 3 に示す．全アルゴしていないことを確認した．

3. 1. 1 結果と各トポロジーの関連性についての考察

リズムにおいて最も良い結果を太字で，最も悪い結果を下線でネットワーク・トポロジーとその振る舞いについて，平均頂表記している．全関数において，様々なトポロジーを持つ全て点間距離 L と平均近傍粒子数 Nl の観点から考察する．平均頂の NS-PSO は従来型 PSO の結果を大きく改善している．それ

点間距離 L は，平均最短距離としても知られており，2 点間でどころか，従来型 PSO は NS-PSO よりも良い結果を一度も得通らなければならない結合の数の平均であり，平均近傍粒子数られていない．これらの結果から，何らかのネットワーク構造

Nl は，自分自身を含めた lbest を共有する近傍粒子数の平均でを持ち，その近傍関係を利用した PSO の方が，何の近傍関係ある．

も持たない従来の PSO よりも有効な結果を得られるといえる．

本シミュレーションで使用した 6 × 6 のトポロジーでは，長次に，最も良い結果と各結果との差をまとめたものを，表 3方形，六角形，円筒，トロイダルの 4 つのトポロジーの平均頂に示す．長方形トポロジー，六角形トポロジー，円筒トポロ

点間距離 L は，それぞれ，6.6，5.34，5.8，5.0 である．また，ジー，トロイダルトポロジーを持つ 4 つの NS-PSO における最自分自身を含む平均近傍粒子数 Nl は，同様に，それぞれ，4.6，良値獲得回数は，それぞれ，0，3，2，3 回である．また，f1 〜6.18，4.8，5.0 となっている．まず，環状トポロジーを考える．

f4 の単峰性関数に対して注目すると，トロイダルトポロジーを円筒とトロイダルは環状トポロジーなので，これらの各粒子の持つ NS-PSO が最も多く最良値を得ており，円筒トポロジーの個性はほぼ同じである．つまり，トロイダルトポロジーにおい結果も最良値からの誤差が少ないことがわかる．しかしながら，ては，全粒子の結合状態が同じであるため，L と Nl が完全にf5 〜f8 の多峰性関数に対して注目すると，単峰性関数に対して同じ値をとる．これは，各粒子の役割に差がないことを意味し最適なトポロジーだったトロイダルトポロジーの結果が，他のている．さらに，トロイダルトポロジーの L は 4 つのトポロ

3 つの NS-PSO と比較して，最良値からの差が最も大きいこと

ジーにおいて最小であるが，これは，群全体の粒子が短い距離がわかる．一方，六角形トポロジーは f6 と f7 に対して最良ので繋がっていることを示している．これらの効果から，lbest の結果を得ており，他の 2 つの多峰性関数に対しても，最良値か情報が群全体に伝わりやすく，結果，環状トポロジーがシンプらの誤差が少ない安定した結果を出していることがわかる．まルな単峰性関数に適していたのだと考えられる．しかしながら，た，長方形トポロジーを持つ NS-PSO は一度も最良の結果を早い情報伝達は早すぎる収束を引き起こすことから，トロイダ出せてはいないものの，単峰性，多峰性の両関数において，安ルトポロジーは多峰性関数では局所解におちいりやすい特徴を—3—

表 2 Comparison results of PSO and NS-PSO on 8 test functions with D = 50.

fPSO

Hexagon

CylinderToroidal

2.29e-20

8.22e-25

1.50e-23

1.62e-25

1.58e-25

Minimum 4.09e-27

1.51e-29

1.29e-22

9.59e-32

1.78e-31

Mean

f1
f2
f3

Mean

55.24

43.61

42.56

38.80

40.82

Minimum

36.74

38.48

35.56

31.04

30.33

Mean

7.49e-06

1.23e-07

7.37e-09

3.93e-08

4.50e-08

Minimum 9.41e-11

3.15e-12

5.81e-13

1.85e-12

3.19e-11

1.58e-35

1.51e-41

1.32e-41

2.90e-42

3.53e-44

Minimum 9.86e-42

7.96e-47

2.84e-46

3.90e-49

1.32e-50

92.80

104.4488.32

115.45

Mean

f4

Mean

f5
f6
f7
f8

NS-PSO
Rectangular148.31Minimum

94.52

52.73

60.69

45.77

29.85

Mean

249.67

159.62

157.28193.50205.75

Minimum

97.84

67.60

41.13

64.90

66.46

Mean

65.62

41.35

33.46

41.06

43.04

Minimum

39.36

21.95

17.68

18.90

21.78

Mean

0.24400.08530.04480.09240.0350

Minimum00

1.11e-16

1.11e-16

0

表 3 Difference from the best result.

Best

Difference from the best mean result

fMean

f1

1.58e-25 2.29e-20

f2

38.80

f3

ResultPSO

NS-PSO
Rectangular Hexagon Cylinder Toroidal
6.64e-25

1.49e-23

4.72e-27

0

4.82

3.77

0

2.02

7.37e-09 7.48e-06

1.15e-070

3.19e-08

3.76e-08f4

3.53e-44 1.58e-35

1.50e-41

1.32e-41

1.32e-41

0f5

88.319

60.00

4.48

16.12

0

27.13

f6

157.28

92.39

2.34

0

36.22

48.47

f7

33.4615

32.16

7.89

0

7.60

9.58

f80.0350

0.20900.05030.00980.0574016.44持つ．一方，六角形トポロジーを持つ NS-PSO では，L は短く，Nl は大きい値ではあるが，異なる頂点間距離，異なる近傍粒子数を持つ様々な種類の粒子が共存している．この様々な個性の粒子の共存は，粒子の多様性を生み，早すぎる収束を防ぐ．
このことから，六角形トポロジーを持つ NS-PSO は局所解から抜け出しやすいと予想できる．

4. お わ り に本研究では，自己組織化マップ (SOM) と粒子群最適化 (PSO)の両方の特徴を兼ね備える，様々な近傍トポロジーを持つネットワーク構造型 PSO を提案した．NS-PSO の全粒子は 2 次元ネットワーク上での近傍に従い結合されており，各粒子情報はその近傍関係に従い更新される．本提案手法を，単峰性，多峰性を含む 8 つのベンチマーク関数に適用した結果，何のネットワーク構造も持たない PSO よりも，何らかのネットワーク構造を持った PSO のほうが有効性が高いことを確認した．さらに，トロイダルトポロジー，及び，六角形トポロジーを持つ

NS-PSO は，それぞれ，単峰性のようなシンプルな関数，多峰性のような複雑な関数に適していることを発見した．

文

献[1] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proc. IEEE. Int. Conf. Neural Netw., pp. 1942–1948, 1995.
[2] T. Kohonen, Self-organizing Maps, Berlin, Springer, 1995.
[3] J. Kennedy, “Small worlds and mega-minds: effects ofneighborhood topology on particle swarm performance,” inProc. of Cong. on Evolut. Comput., pp. 1931–1938, 1999.
[4] J. Kennedy and R. Mendes, “Population structure and particle swarm performance,” in Proc. of Cong. on Evolut.
Comput., pp. 1671–1676, 2002.
[5] R. Mendes, J. Kennedy and J. Neves, “The Fully Informed
Particle Swarm: Simpler, Maybe Better,” in IEEE Trans.
Evolut. Comput., vol. 8, no.3, pp. 204–210, June 2004.
[6] J. Lane, A. Engelbrecht and J. Gain, “Particle Swarm Optimization with Spatially Meaningful Neighbours” in Proc.
of IEEE Swarm Intelligence Symposium, 2008.
[7] S. B. Akat and V. Gazi, “Particle Swarm Optimizationwith Dynamic Neighborhood Topology: Three Neighborhood Strategies and Preliminary Results” in Proc. of IEEE
Swarm Intelligence Symposium, 2008.
[8] H. Matsushita and Y. Nishio, “Network-Structured Particle Swarm Optimizer Considering Neighborhood Relationships,” in Proc. of IEEE. Int. Jont Conf. on Neural Netw.,
pp. 2038–2044, 2009.

—4—