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

信学技報
TECHNICAL REPORT OF IEICE.

複数の異なる働きを持つ集団からなる粒子群最適化手法
杉本雅樹†

松下春奈††

西尾芳文†† 徳島大学〒 770-8506 徳島県徳島市南常三島町 2-1† 徳島大学†† 法政大学
あらまし 粒子群最適化 (Particle Swarm Optimization : PSO）は，様々な最適化問題を解くのに用いられている最適化アルゴリズムである。本報告では，複数の異なる働きを持つ集団からなる粒子群最適化手法（Particle Swarm Optimization

containing Plural swarms whose particles have diﬀerent features : PPSO）を提案する。これは、PSO における粒子群を複数の集団に分け，各集団に個性を与えた PSO アルゴリズムである。PPSO の各集団は一定周期毎に、それまでの過程に従ってその構成を変化させる。シミュレーションによる性能比較の結果、提案手法である PPSO は問題がより複雑であるほど、従来の PSO より優れた性能を発揮することが明らかになった。
キーワード

最適化，群知能，粒子群最適化，目的関数

Particle Swarm Optimization Containing Plural Swarms whose Particles haveDiﬀerent Features
Masaki SUGIMOTO† , Haruna MATSUSHITA†† , and Yoshifumi NISHIO†† Dept. of E.E. Eng., Tokushima University, 2-1 Minami-Josanjima, Tokushima 770-8506, JAPAN† Tokushima Univ.
†† Hosei Univ.
Abstract This study proposes a new Particle Swarm Optimization (PSO) algorithm containing plural swarms whose particles
have diﬀerent features. Each particle of the proposed PSO belongs to one of plural swarms, which have diﬀerent characteristics, and the particle periodically changes the swarm that it belongs to. We confirm the eﬀectiveness of the proposed PSO for
both unimodal and multimodal functions with various dimensions.
Key words optimization, swarm, PSO, objective function

1. ま え が き
粒子群最適化 (Particle Swarm Optimization : PSO) は，鳥の動きをモデル化した進化アルゴリズムの一種である。概念が単純る。これに対して複数のグループを持たせた PSO では，各粒子の情報と全体の最も良かった位置の情報に加えて，それぞれの粒子が所属するグループごとの最も良かった位置に従って更新する。

であり実現が容易な上，収束が早いという特徴を持つことから，一方，実社会においては，企業のような大きな集団の構成員

近年，異なる様々な分野での応用に用いられている。しかしなには，内部に複数存在する部署や，役職が割り振られることにがら，パラメータに大きく依存することや，多数の局所解を持なる。この時，それらは人事担当等に従って，個人の能力や適つような複雑な問題を解く場合においての早過ぎる収束などが，性を考慮して決定される。さらにこの決定は，配属された後にPSO の問題点として挙げられている。この問題を解決する為の与えられる仕事の内容や重要性に大きく影響してくる。

試みの一つとして，複数のグループを持つ PSO が研究者たちによってにいくつか提案されている [2] [?]。

このように実社会では，集団は無作為に同じような複数のグループに分けられるのではなく，異なる役割を持つグループに，PSO は複数の解（粒子）群で構成され，各粒子は位置と速度個体の適性を考慮して分けられるということが言える。本研究の情報を持っている。通常の PSO は，各粒子の情報は各個体では，このような社会的な集団の構造を PSO に取り入れたアルが最も良かった位置と全体で最も良かった位置に従って更新すゴリズム，複数の異なる働きを持つ集団からなる PSO（PPSO）—1—

[PPSO6] もし tc = T c なら，[PPSO7] へと進む。そうでなけれを提案する。
また，提案手法の有効性を確認するために，単峰性と多峰性

ば，[PPSO10] へと進む。

それぞれ二つずつ計四つの評価関数に対してシミュレーション[PPSO7] 更新ごとの順位 r によって決定した各粒子 i の順位の和を行う。その結果を従来の PSO と比較することにより，PPSO

ri に従って ，各粒子に総合順位順位 Ri をつける（R = 1, · · · , N ）。

が探索能力を効果的に高めることを確認する。

1 位となるのは順位の和が最も少なかった粒子で，順位の和が2. PSO containing plural swarms whose particles have diﬀerent features (PPSO)PSO には粒子と呼ばれる複数の解が存在しており，各更新
では，固体の最良の位置 pbest と群全体での最良の位置 gbest

最も大きくなった粒子は N 位となる。

[PPSO8] （再構成）総合順位 Ri に従って，各粒子 i の再構成を行う。各群 k は NK 個ずつの粒子からなり，最良群 S 1 は総合順
位 Ri が１から NK の粒子によって構成される。つまり，各群 S k()に所属する粒子の総合順位 Ri は (k−1)N+ 1 から kNとなる。
KKに向かうように動く。各粒子は，位置 Xi = (xi1 , xi2 , . . . , xiD )[PPSO9] 全粒子の総合順位を初期化 （Ri = 0） し，再構成のタと速度 V i = (vi1 , vi2 , . . . , viD ) の情報を持っている。ここでは，イミングのカウントも初期化する （tc = 0）。

(d = 1, 2, . . . , D), (i = 1, 2, ..., N), xid ∈ [xmin , xmax ] とする。

[PPSO10] t = t + 1 と tc = tc + 1 を行い，t = T を満たすまではPPSO の重要な特徴は，各粒子は異なる特徴を持つ複数の群[PPSO2] へと戻って手順を繰り返す。に所属し，この所属は周期的に変化することである。それぞれの群 S k (k = 1, 2, . . . , K) には N/K 個ずつの粒子が属する。そし3. シミュレーション結果て各粒子 i の位置と速度が更新されると，各群と全粒子中の最PPSO の性能を評価するために，従来型 PSO との比較実験を良の位置も同時に更新される。

行った。用いたのは４つの目的関数で，Sphere 関数と Rosen-毎度の更新において，全粒子は評価値 f (Xi ) によって順位付

brock 関数は単峰性関数，Rastrigin 関数と Griewank 関数は多くけされる。また，T c 回の更新ごとに，それまでの総合順位 Riの局所解を持つ多峰性関数である。

によって全粒子は所属する群を変更する。

1. Sphere function:[PPSO1] (初期化) t = 0, tc = 0 （tc は群の再配置タイミング）

f1 (x) =とし，粒子 i の位置 Xi と速度 V i をランダムに初期化する。
各粒子 i に対し目的関数 f (Xi ) を計算し， 各粒子の最良解Pi = (pi1 , pi2 , ..., piD ) として初期化する。全粒子内での評価値
f (Xi ) を比較し，全体の最良解 Pg を初期化する。各粒子 i を各

位置 pbest Pi と，全粒子の最良解の位置 gbest Pg を，それまでxd2 ,(3)d=1

問 題 の 範 囲 は x ∈ [−2.048, 2.047]D で ，最 適 解 の 位 置 x∗ は[0, 0, . . . , 0] である。
2. Rosenbrock’s function:

群 S k にランダムに所属させる。

[PPSO2] 現在の評価値 f (Xi ) を計算する。各粒子 i の最良解のD∑

f2 (x) =D−1∑
(100(xd2 − xd+1 )2 + (1 − xd )2 ),(4)

d=1の最良解より良くなっていれば更新する。

問題の範囲は x ∈ [−2.048, 2.047]D で， 最適解の位置 x∗ は

[PPSO3] 各群 S k の最良解の位置 sbest Psk = (p sk 1 , p sk 2 , · · · , p sk D )[1, 1, . . . , 1] である。

を，それまでの最良解より良くなっていれば更新する。

3. Rastrigin’s function:

sk = arg min{ f (Xi )},ii ∈ S k.

(1)

[PPSO4] （順位付け）各粒子 i の順位 r = 1, · · · , N を評価値
f (Xi ) に従って計算する。最も少ない評価値 f (Xi ) を持つ粒子が一番高い順位である 1 位となり，最も大きい評価値を持つ粒子は一番低い順位である N 位となる。順位 ri は粒子 i ごとに，更新するたび加算していく。rinew = riold + ri .

[PPSO5] （速度と位置の更新）各粒子 i の速度 V i と位置 Xiを， pbest, sbest, gbest に従って更新する。

D∑(xd2 − 5 cos(2πxd ) + 5),

(5)

d=1

問 題 の 範 囲 は x ∈ [−5.12, 5.12]D で ，最 適 解 の 位 置 x∗ は[0, 0, . . . , 0] である。
4. Griewank’s function:
f4 (x) =DD∑∏
xd2
xdcos( √ ) + 1,+4000
dd=1
d=1

(6)

問 題 の 範 囲 は x ∈ [−600, 600]D で ，最 適 解 の 位 置 x∗ は[0, 0, . . . , 0] である。

vid (t + 1) =wk vid + c1 r1 (pid − xid (t))+ c2 r2 (p sk d − xid (t)) + c3 r3 (pgd − xid (t)),

f3 (x) =(2)xid (t + 1) =xid (t) + vid (t + 1),

この４つの目的関数の最適解の評価値は全て 0 である。また，関数の次元数 D は，30 と 100 の二種類に設定した。

PPSO の効果をより深く調べるため，PSO1，PSO2，PPSO-R，

ここで r1 , r2 , r3 は 0 から 1 の範囲のランダムな値であり， c1 ,PPSO の４つのアルゴリズムを実行，比較した。PSO1 は通常

c2 , c3 は正加速度係数である。wk は各群 S k の慣性重量で，群ごの PSO で，PSO2 は通常の PSO の慣性重量 w を更新が進むごとに異なる。これにより，各群ごとに所属する粒子は異なる特とに変化させていくアルゴリズムである。PSO2 の慣性重量の徴を持つことになる。

変化は，次式の通りである。

—2—

w(t) = wmax −wmax − wmin× t,
T(7)表 1 Comparison Results PSO1, PSO2, PPSO-R and PPSO on test func-

tions with D = 30.
目的関数

平均

最小最大

PSO1

9.04e-61

7.38e-66

1.45e-59

PSO2

2.19e-33

1.16e-46

4.42e-32

PPSO-R

8.24e-25

6.37e-39

2.24e-23

PPSO

1.13e-29

8.56e-35

6.19e-29

期化において所属した群に所属し続けて順位による再構成を行

PSO1

20.34

0.06

73.78

わない。

PSO2

30.16

2.1387.73

PPSO-R

29.00

15.08

76.94

PPSO-R と PPSO における群の数は 6，各群に所属する粒子数は

PPSO

21.57

0.06

76.51

10 に設定し，全粒子数は同じく 60 とした。PSO1 の慣性重量 w

PSO131.05

13.86

46.53

ここでの wmax と wmin は，慣性重量の最大値と最小値となる。

fPPSO のアルゴリズムにおける [PPSO6] から [PPSO9] の手順の効果を調べるために，この手順を省いたアルゴリズムが PPSO-R

f1である。つまり，PPSO-R の各粒子 i は PPSO とは異なり，初PSO1 と PSO2 における全粒子数 N は 60 に設定した。また，は 0.6 に設定し，PSO2 の慣性重量は最大値 wmax = 0.9 ，最小f2

f3

値 wmin = 0.4 と設定した。正加速度計数は PSO1，PSO2 ともにc1 = c2 = 1.8 に設定した。PPSO-R と PPSO における各群の慣性重量は w1 = 0.9, w2 = 0.8, w3 = 0.7, w4 = 0.6, w5 = 0.5, w6 = 0.4とし，正加速度係数は c1 = 1.8, c2 = 1.4, c3 = 0.4 と設定した。

f4

PPSO における再構成の更新周期 T c は，100 に設定した。

PSO2

22.44

15.84

30.69

PPSO-R

15.75

6.93

28.81

PPSO

14.95

5.94

22.77

PSO1

8.60e-03

05.62e-02

PSO2

1.14e-02

06.87e-02

PPSO-R

2.37e-03

02.16e-02

PPSO

1.31e-03

0

1.48e-02

3000 回の更新を一回のシミュレーションとし，30 回試行したときの gbest の平均値，最小値，最大値を，次元数 D が 30と 100 の場合に分け，表１と表２に示す。この表より，30 次元

表 2 Comparison Results PSO1, PSO2, PPSO-R and PPSO on test func-tions with D = 100.
目的関数平均最小最大の f1 (x) と f2 (x) ，つまり単峰性関数では，従来の PSO である

PSO1

1.08e-06

2.18e-11

3.00e-05

PSO1 が最も良い解に平均して辿りついていることがわかる。

PSO2

2.20e-01

4.76e-04

1.01

PPSO-R

3.48

2.08e-01

18.41

一方，それ以外の 30 次元の多峰性関数と，100 次元の全関数でff1

は，提案手法である PPSO が全アルゴリズム中で最も良い解にPPSO

9.92e-10

1.88e-15

1.28e-08平均して辿りついているという結果が得られた。

PSO1

17035.82

98.53

503344.7

また，更新数ごとの gbest の平均値の推移を表したグラフを，f2

図１と図２に示す。このグラフの共通点として，更新初期において PPSO と PPSO-R が素早く良い解に辿りついていることが読み取れる。しかし，更新が進むと提案手法である PPSO と比較して PPSO-R は gbest の更新が鈍いことも分かる。また，そf3

PSO2

747.08367.54

1958.46

PPSO-R

5478.69

514.8914010.7

PPSO

179.8377.57

311.71

PSO1

254.68197.00324.70

PSO2

307.93200.48401.12314.86

PPSO-R

208.83152.66の傾向は単峰性より多峰性，30 次元より 100 次元と，問題が複PPSO

138.4895.26

190.07雑になるほど強くなっている。このことから，PSO に役割の異PSO1

7.47e-03

6.92e-12

2.22e-02

なる複数のグループを持たせることは，少ない更新の段階から優れた gbest を見つけ出す効果があり，順位によるグループの再構成は局所解から抜け出す働きがあると推測できる。

f4

PSO2

5.29e-03

1.15e-04

2.76e-02

PPSO-R

5.78e-02

1.67e-02

1.81e-01

PPSO

2.71e-03

6.66e-16

2.22e-02

これらより，提案手法の PPSO は複雑な問題ほど従来の PSOと比較して高い性能を発揮することが確認できた。

4. お わ り に本研究では，複数の異なる働きを持つ集団からなる PSO（Par-ticle Swarm Optimization containing Plural swarms whose particles
have diﬀerent features : PPSO） を提案した。PPSO は複数の異なる働きを持つグループによって構成され，そのグループは一定周期毎にそれまでの各粒子の評価によってその構成を変化させる。
単峰性と多峰性を二つずつ計四つの目的関数に対して 30 次元と 100 次元の二種類の設定でシミュレーションを行なった。
それらの結果より，PPSO は多峰性、高次元の問題に対して高い有効性を持つ事を明らかにした。今後の課題として，各グな影響を及ぼすのかを調査していく。
文献[1] J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proc.
IEEE Int. Conf. on Neural Networks, vol. 4, pp. 1942–1948, 1995.
[2] J. Kennedy and R. Medes, “Population structure and particle swarm
performance,” Proc. IEEE Congress on Evolutionary Computation,
vol. 2, pp. 1671–1676, 2002.
[3] G. Yen and M. Daneshyari, “Diversity-based information exchange
among multiple swarm in particle swarm optimization,” Proc. IEEE
Congress on Evolutionary Computation, pp. 1686–1693, 2006.
[4] M. Iwamatsu, “Multi-species particle swarm optimizer for multimodal function optimization,” IEICE Trans. on Information and Systems, vol. E89-D, no. 3, pp. 1181–1187, 2006.
[5] M. Sugimoto, T. Haraguchi, H. Matsushita and Y. Nishio, “Particle swarm optimization containing plural swarms,” Proc. RISP Int.
Workshop on Nonlinear Circuits and Signal Processing, pp. 419–412, 2009.

ループに与える特徴を変えた場合，そのことが結果にどのよう—3—

101010101020100

Function Value log(f(x))

Function Value log(f(x))

10−20−40

PSO1
PSO2
PPSO−RPPSO−60−800500

1000 1500 2000
Number of Generaton t2500

101010101030006PSO1
PSO2
PPSO−R
PPSO

5432

10500(a)10102

103000(b)

PSO1
PSO2
PPSO−RPPSO
102500

13Function Value log(f(x))

Function Value log(f(x))

101000 1500 2000
Number of Generation t

PSO1
PSO2
PPSO−R
PPSO

010−1

10−2

10−3500

1000 1500 2000
Number of Generation t

2500

1030000500(c)1000 1500 2000
Number of Generation t

2500

3000(d)

図 1 Mean gbest value of every generation for 30-dimensional four functions. (a) Sphere function.

(b) Rosenbrock’s function. (c) Rastrigin’s function. (d) Griewank’s function.

105101010

Function Value log(f(x))

Function Value log(f(x))

100−5−100

PSO1
PSO2
PPSO−R
PPSO
500

1000 1500 2000
Number of Generation t

2500

1010103000

PSO1
PSO2
PPSO−R
PPSO

864

20500

(a)

3000(b)PSO1
PSO2
PPSO−R
PPSO
102500

4PSO1
PSO2
PPSO−RPPSO

2Function Value log(f(x))

Function Value log(f(x))

101000 1500 2000
Number of Generation t

310010−2101020500

1000 1500 2000
Number of Generation t(c)2500

30000500

1000 1500 2000
Number of Generation t

2500

3000(d)

図 2 Mean gbest value of every generation for 100-dimensional four functions. (a) Sphere function.

(b) Rosenbrock’s function. (c) Rastrigin’s function. (d) Griewank’s function.

—4—