信学技報
TECHNICAL REPORT OF IEICE.

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

雌のパラメータを変化させたときのホタルアルゴリズム
武内将希†

松下春奈††

上手 洋子†

西尾芳文†† 徳島大学 〒 770–8506 徳島県南常三島 2–1†† 香川大学 〒 761–0396 香川県高松市林町 2217–20
E-mail: †{masaki,uwate,nishio}@ee.tokushima-u.ac.jp, ††haruna@eng.kagawa-u.ac.jp
あらまし

私達は，ホタルの性別を区別した雌雄区別型ホタルアルゴリズム (FADMF) を提案した. 従来のホタルア

ルゴリズム (FA) において，すべてのホタルの性別は区別しない. しかし，現実において多様性を持つことは非常に重要な意味を持つ. 最適化問題を解く上でも，多様な個体が存在することで多様な解を生み出し，ホタルが局所解に陥ることを防ぐ効果があると考えられる. そこで私達は，性別を区別することで従来の FA に多様性を持たせた. 本報告では，8 個の最適化ベンチマーク関数に適用し，従来の FA と比較することで，提案手法の有用性を確認する. 特に，群全体に対する雌の比率と雌の 2 つのパラメータに注目する.
キーワード

ホタルアルゴリズム，最適化問題，多様性，群知能

Firefly Algorithm Changing Parameters of Females
Masaki TAKEUCHI† , Haruna MATSUSHITA†† , Yoko UWATE† ,and Yoshifumi NISHIO†† Dept. of Electrical and Electronic Engineering, Tokushima University
2-1 Minami-Josanjima, Tokushima 770–8506, Japan†† Dept. of Electronics and Information Engineering, Kagawa University
2217-20 Hayashi-cho, Takamatsu, Kagawa, 761-0396, JapanE-mail: †{masaki,uwate,nishio}@ee.tokushima-u.ac.jp, ††haruna@eng.kagawa-u.ac.jp
Abstract We have proposed Firefly Algorithm Distinguishing between Males and Females. It is important to havea diversity in various fields. This proposed algorithm exists together with male and female fireflies. The movementsof males and females are diﬀerent each other. These diﬀerence is inspired from the physical diﬀerences. In thisstudy, we compare our proposed algorithm to the conventional Firefly Algorithm by using 8 composition functionsof Congress on Evolutionary Computation 2013.
Key words Firefly Algorithm, optimization, diversity, swarm intelligence

1. ま え が き
近年，最適化問題を解くことが非常に重要になってきている.

粒子群最適化 (PSO) [1]，蜂コロニー最適化 (BCO)，ホタルア
ルゴリズム (FA) [2]〜[4]，カッコウ探索 (CS) [5] などが代表例として挙げられる.

確率的アルゴリズムは，最適化問題を解く上で非常に有用なア

従来の FA においてホタルの性別は区別されない. しかし，ルゴリズムと考えられており，決定論的要素とランダム要素で現実において多様性を持つことは生存する上で非常に重要で構成される. 決定論的要素しか持たないアルゴリズムは，ほとある. 生物は多様性を持つことにより多様な環境に対応するこんどの場合，局所探索アルゴリズムであり局所解に陥る可能性とができ，予想外の事態が起きても生存することができる. こがある. しかし，確率論的アルゴリズムは，ランダム要素を持れは，様々な個体がいることにより，環境に適応できる個体がつためにそのような局所解から抜け出すことができる.

いる可能性が高いからである. そこで私達は，従来のホタルに確率的アルゴリズムの代表的なものとして群知能アルゴリズ

多様性を持たせるために性別を区別したホタルアルゴリズム

ムが挙げられる．群知能アルゴリズムは，動物や昆虫の特徴的なである，雌雄区別型ホタルアルゴリズム (FADMF) を提案し行動から考えられたアルゴリズムで，蟻コロニー最適化 (ACO)，た [7], [8]. このアルゴリズムにおいて，雄と雌のホタルはそれ—1—

Algorithm 1 ホタルアルゴリズムの擬似コード

Algorithm 2 雌雄区別型ホタルアルゴリズムの擬似コード

Objective function f (x), x = (x1 , ..., xd )T

Objective function f (x), x = (x1 , ..., xd )T

Initialize a population of fireflies xi (i = 1, 2, ..., n)

Initialize a population of male fireflies xi (i = 1, 2, ..., n)

Define light absorption coeﬃcient γ

Initialize a population of female fireflies yi (i = 1, 2, ..., m)while t < M axGeneration do

Define light absorption coeﬃcient γ

for i = 1 to n, all n fireflies dowhile t < M axGeneration dofor j = 1 to n, all n fireflies dofor i = 1 to n, all n male fireflies doLight intensity Ii at xi is determined by f (xi )for j = 1 to n, all n male fireflies do

if Ii > Ij thenLight intensity Ixi at xi is determined by f (xi )Move firefly i towards j in all d dimensions

if Ixi > Ixj thenend ifMove male firefly i towards j in all d dimensions

Attractiveness varies with distance r via exp[−γr]end if

Evaluate new solutions and update light intensity

end forj

end forj

for k = 1 to m, all m female fireflies do

end fori

Light intensity Iyk at yk is determined by f (yk )Rank the fireflies and find the current best

if Ixi > Iyk thenend whileMove male firefly i towards k in all d dimensions

Postprocess results and visualization

else
Move female firefly k towards i in all d dimensions
end if

ぞれ異なる動き方をする. この動き方の違いは自然界の雄と雌

end forkのホタルの特徴の違いから考えている. 本報告では，FADMF

Attractiveness varies with distance r via exp[−γr]を Congress on Evolutionary Computation (CEC) 2013 で提Evaluate new solutions and update light intensity

案された 8 個の合成関数 [6] に適用し, 従来の FA と比較する.
シミュレーション結果より，提案する FADMF が従来の FA よりも合成関数に対して有用であることを確認する. 特に，群全end fori
Rank the fireflies and find the current best
end while
Postprocess results and visualization体に対する雌の比率と雌の 2 つのパラメータに注目する.
本報告は，2. で従来のホタルアルゴリズムを説明した後，3.
で提案する雌雄区別型ホタルアルゴリズムについて説明する.

タル i と j 間の距離，β0 は rij = 0 の時の魅力の強さ，βmin はその後，4. でシミュレーション結果を示し，最後に 5. で結論をβ の最小値を表している. 距離 rij は次式で計算する.

述べる.

2. ホタルアルゴリズム (FA)vu Du∑
rij =t(xid − xjd )2(2)d=1

ホタルアルゴリズム (FA) は，2007 年に Yang により提案された, ホタルの点滅の様子から考えられたアルゴリズムである.

次式に従って，ホタル i はより光っているホタル j に引き寄せられる。

ホタルは, 以下の 3 つの規則に従って他のホタルに引き寄せられ大域的な解を探索する.

•

性別の区別をしない. つまり, すべてのホタルは他のすべてのホタルに引き寄せられる.

•魅力の強さは光の強さに比例する. つまり，より光っていないホタルは，より光っているホタルに引き寄せられる. 魅力の強さと光の強さは距離によって減少する. もっとも光っているのホタルはランダムに動く.

•xi = xi + ∆x

(3)∆x = β(xj − xi ) + αϵi(4)ここで，ϵi はランダムベクトル，α は次式で定義される.

(α(t) = α(0)10−40.9)t/tmax(5)

α は，反復回数 t が大きくなるにつれて小さくなっていく. 最ホタルの光の強さは目的関数によって決まる. つまり，小化問題を解くときの FA の擬似コードを Algorithm1 に示す.

最小化問題をとく場合，より低い場所にいるホタルの方がより強い光を放つ.

3. 雌雄区別型ホタルアルゴリズム (FADMF)

魅力の強さは光の強さによって決まるが，光っているホタルと従来の FA においてホタルの性別は区別しない. しかし，現の距離が遠ければ遠いほど光は強さは弱くなる. そのため，ホ実において多様性を持つことは生存する上で非常に重要であタルの魅力の強さは次式で定義される.

る. 生物は多様性を持つことにより多様な環境に対応すること

2

β = (β0 − βmin )e−γrij + βmin

(1)ができ，予想外の事態が起きても生存することができる. これは様々な個体がいることにより，環境に適応できる個体がいる

ここで，γ は吸引係数，rij は位置ベクトル xi と xj を持つホ可能性が高いからである. 最適化問題を解く上でも多様な個体—2—が存在することで多様な解を生み出し，局所解に陥ることを防ぐ効果があると考えた. そこで私達は，ホタルの性別を区別し表1

パラメータ V と W を 1 から 4 まで変化させたときの結果(群全体に対する雌の比率は 60 パーセント).

Wたホタルアルゴリズムである，雌雄区別型ホタルアルゴリズ

123415354266433433342111ム (FADMF) を提案した. 提案した FADMF には雄と雌の２種類のホタルが共存しており，それぞれ異なる動き方をする.
この動き方の違いは自然界のホタルの特徴の違いから考えていVる. 自然界において，雌のホタルの方が身体が大きく，雄のホタルの方が目が大きい. また, 雄は他の雄の光と同期しながら雌のホタルを探して飛び回ること，雌は雄の光しか見ないことがわかっている. そこで提案手法において，雌の移動距離を減らし，雌が遠くのホタルに引き寄せられにくくする. また，雄はすべてのホタルに引き寄せられるが，雌は雄にしか引き寄せられない. 加えて，雌のパラメータ α も変化させる. 変化させた雌に関する式は次のように定義する.

(α(t) = α(0)1040.9)t/2tmax

2

平均が少なくなる関数が急激に減少していく. これは雌の移動する距離が短くなりすぎることにより局所解を抜け出すことができなくなるためだと考えられる．パラメータ W に注目すると，V = 1 のときを除いて W が大きくなるにつれて結果が悪くなっていく．V = 1 のときは特に規則性を見つけることがで(6)きない．したがって，パラメータ W はパラメータ V の値を考慮して設定する必要がある.

β = β0 e−γrij /W(7)

4. 2 シミュレーション 2x = x + ∆x/V

(8)

シミュレーション 1 より，パラメータの値を (V ，W ) = (2パラメータ V が増加すると雌の移動距離が減少し，パラメータW が増加すると雌が遠くのホタルに引き寄せられにくくなる.
最小化問題を解くときの FADMF の擬似コードを Algorithm2に示す.

4. シミュレーション
私達は，提案した FADMF を 2013 年に Congress on Evo-lutionary Computation (CEC) で提案された 8 個の合成関数 (f21 〜f28 ) に適用し, その誤差の平均値を従来の FA と比較する. 各関数の最適解は 0 からそれぞれ異なる値でシフトされており，最適解の関数値も 0 ではない. 各関数は，3〜5 個の関数をシフトするなどし形を変え，組み合わせた関数である. 探索範囲は [−100, 100]D であり，各関数の次元 D は 30 に設定する. ホタルの総数も 30 と設定した. 反復回数は 1500 回とし，各シミュレーションは 50 回行い，各シミュレーションの初期値はランダムに与える. 本報告では，パラメータ V と W ，群全体に対する雌の比率に注目し結果を考察する. まず，群全体に対する雌の比率を 60 パーセントに固定し，パラメータ V とW を 1 から 4 まで変化させ結果を比較する. その後，パラメー
タ V と W を最適な値に固定し，群全体に対する雌の比率を 10から 90 パーセントまで変化させ結果を比較する.

4. 1 シミュレーション 1
表 1 に群全体に対する雌の比率を 60 パーセントに固定した
ときの，パラメータ V と W を 1 から 4 まで変化させた結果を示す. 表 1 に示されている値は FADMF が従来の FA よりも誤差の平均が小さくなった関数の個数である.
表 1 より，(V ，W ) = (2，1)，(2，2) のときに，FADMF が従来の FA より誤差の平均が少なくなる関数がもっとも多い
ことがわかる．パラメータ V に注目すると，パラメータ V は

V = 2 のときに誤差の平均が少なくなる関数がもっとも多いこ，1)，(2，2) に設定し，群全体に対する雌の比率を 10 から 90まで変化せた結果と，従来の FA よりも良い結果を得た回数を
表 2，表 3 に示す. 表 2 がパラメータの値を (V ，W ) = (2，1)に設定した結果，表 3 がパラメータの値を (V ，W ) = (2，2) に設定した結果である. 表 2，表 3 に示している値は，誤差の平均値である. また，太字で示している値はもっとも誤差の平均が小さかった値である.
表 2，表 3 より，FADMF は f22 と f23 の 2 つの関数において特に良い結果を得ている. また，(V ，W ) = (2，1) に設定したときは群全体に対する雌の比率は 50 パーセント，(V ，W ) = (2，2) に設定したときは群全体に対する雌の比率が 60 パーセン
トであるときがもっとも良い結果を得ている. 表 2，表 3 ともに最初は雌の比率が増えるに従って従来の FA よりも良い結果を得る関数の数は増えていくが，雌の比率が 60 パーセントを超えると急激に良い結果を得れる関数の数が減少する. これは，雌は雄にしか引き寄せられないため，1 回の反復で移動するホタルの数が減少していくからだと考えられる. 従来の FA ではすべてのホタルがより光っているホタルに引き寄せられる. したがって，複数のホタルが同じ局所解に陥ってしまうとなかなか抜け出すことができない. しかし，雌のホタルが存在することで，自分よりも光っているホタルに引き寄せられないホタルが存在することになり，局所解に捕まりにくくなる. 表 2 と表3 を比較すると，良い結果を得た数を平均すると表 3 の方が多い. しかし，表 2 の方がより良い結果を得ることができている.
したがって，(V ，W ) = (2，1) の方が有用であると言える.
シミュレーション 1，2 より，雌の移動距離は雄の半分に設定することがもっともよいことがわかる. そのとき，雌は雄と同じだけ遠くのホタルに引き寄せられる方がよく，ほとんどの場合，群全体に対する雌の比率は 50 か 60 パーセントに設定するとよい.とがわかる. パラメータ V が V = 2 より大きくなると誤差の—3—

表 2 群全体に対する雌の比率を 10 から 90 まで変化させたときの結果 ((V ，W ) = (2，1)).
関数名FAFADMF

雌の比率

10304050f21

3.30 × 102 3.30 × 102 3.28 × 102

3.35 × 102

3.39 × 102

3.45 × 102

f22

3.31 × 103 3.47 × 103 2.90 × 103

2.85 × 103

2.67 × 103 2.49 × 103

f23

3.84 × 103 3.59 × 103 3.45 × 103 2.83 × 103 2.89 × 103

f24

2.17 × 102 2.27 × 102 2.22 × 102

2.17 × 102

f2520607080

90

3.25 × 102 3.33 × 102 3.29 × 102 3.35 × 102
2.61 × 103

3.14 × 103 3.15 × 103 3.93 × 103

2.98 × 103

3.01 × 103

3.19 × 103 3.95 × 103 4.93 × 103

2.15 × 102

2.15 × 102 2.23 × 102 2.26 × 102 2.36 × 102

2.34 × 102 2.30 × 102 2.31 × 102 2.29 × 102 2.32 × 102

2.30 × 102

2.33 × 102

2.35 × 102 2.41 × 102 2.51 × 102

f26

2.89 × 102

2.92 × 102

3.01 × 102

3.00 × 102

2.95 × 102

2.85 × 102

3.03 × 102

3.11 × 102 3.08 × 102 3.06 × 102

f27

4.56 × 102

5.46 × 102

4.69 × 102

4.69 × 102

4.58 × 102

4.50 × 102

4.59 × 102

4.64 × 102 5.39 × 102 6.62 × 102

f28

3.06 × 102 3.05 × 102 3.32 × 102

2.98 × 102

3.06 × 102

3.09 × 102

2.77 × 102 3.50 × 102 3.57 × 102 3.20 × 102456

FA より良かった数

342.22 × 102

62208090

表 3 群全体に対する雌の比率を 10 から 90 まで変化させたときの結果 ((V ，W ) = (2，2)).
関数名FA

FADMF

雌の比率

5060

f21

3.30 × 102

3.05 × 102

3.36 × 102

3.31 × 102

3.25 × 102

3.25 × 102

3.24 × 102

3.41 × 101 3.29 × 102 3.14 × 102

f223.31 × 103

3.55 × 103

3.11 × 103

2.75 × 103 2.63 × 103

2.65 × 103

2.67 × 103

2.71 × 103 3.31 × 103 4.36 × 103

f23

3.84 × 103

3.79 × 103

3.14 × 103

2.91 × 103

2.85 × 103

3.12 × 103

3.11 × 103

3.13 × 103 3.56 × 103 4.63 × 103

f24

2.17 × 102

2.25 × 102

2.23 × 102

2.20 × 102

2.20 × 102

2.20 × 102

2.15 × 102

2.22 × 102 2.28 × 102 2.41 × 102

f25

2.34 × 102

2.30 × 102

2.29 × 102 2.31 × 102

2.31 × 102

2.32 × 102

2.32 × 102

2.36 × 102 2.39 × 102 2.51 × 102

f26

2.89 × 102

2.93 × 102

2.79 × 102 2.99 × 102

2.99 × 102

2.96 × 102

2.97 × 102

3.02 × 102 3.00 × 102 2.97 × 102

f27

4.56 × 102

5.29 × 102

4.59 × 102

4.70 × 102

4.87 × 102

4.90 × 102

4.69 × 102

4.85 × 102 5.61 × 102 6.43 × 102

f28

3.06 × 102

2.93 × 102

3.22 × 102

2.89 × 102

3.64 × 102

2.85 × 102

2.89 × 102

2.98 × 102 3.39 × 102 3.01 × 102

444456

FA より良かった数

5. 結

10203040論

私達は，ホタルの性別を区別したホタルアルゴリズムである，雌雄区別型ホタルアルゴリズム (FADMF) を提案した. 従来のホタルアルゴリズム (FA) ではホタルの性別を区別しない. しかし，FADMF には雄と雌のホタルが共存しており，それぞれ異なる動き方をする. また，雄は雄と雌の両方に引き寄せられるが，雌は雄にしか引き寄せられない. 本報告では，2013 年にCongress on Evolutionary Computation (CEC) で提案された8 個の合成関数に FADMF と従来の FA を適用し，それぞれの誤差の平均値を比較した. その結果，適切なパラメータ設定を行うことにより，FADMF が従来の FA よりも有用であることを確認した. したがって，雌と雄が存在することで従来の FAよりも多様な解を生み出し，ホタルが局所解に陥りにくくなる効果があると言える.
今後の研究は，雄と雌のホタルの動き方を改良することによる性能の更なる向上と，他の有用なアルゴリズムとの比較が考えられる. また，実社会最適化問題への適用も挙げられる.
文

献[1] J. Kennedy, and R. Eberhart, “Particle Swarm Optimization", Proceedings of the IEEE international conference onneural networks, pp. 1942âĂŞ1948, 1995.
[2] X.S. Yang, “Nature-Inspired Metaheuristic Algorithms Sec-70322ond Edition", Luniver Press, 2010.
[3] H. Matsushita, “Firefly Algorithm with Dynamically
Changing Connections", Proceedings of International Symposium on Nonlinear Theory and its Application, pp.906909, 2014.
[4] S. Lukasik, and S. Zak, “Firefly Algorithm for Continuous
Constrained Optimization Tasks", Computational Collective Intelligence. Semantic Web, Social Networks and Multiagent Systems, Vol. 5796 of the series Lecture Notes in
Computer Science, pp.97-106, 2009.
[5] X.S. Yang, and S. Deb, “Cuckoo search via Levy flights",
Proceedings of World Congress on Nature & Biologically
Inspired Computing (NaBIC 2009, India), pp.210âĂŞ214,2009.
[6] J.J. Liang, B.Y. Qu, P.N. Suganthan, and A.G. HernandezDiaz, “Problem Definitions and Evaluation Criteria for theCEC 2013 Special Session on Real-Parameter Optimization", Technical Report 201212, Computational Intelligence
Laboratory, Zhengzhou University,Zhengzhou China andTechnical Report, Nanyang Technological University, Singapore, January 2013.
[7] M. Takeuchi, H. Matsushita, Y. Uwate, and Y. Nishio,“Investigation of Firefly Algorithm Distinguishing between
Males and Females for Minimum Optimization Problems",
RISP International Workshop on Nonlinear Circuits, Communications and Signal Processing (NCSP), 2016.
[8] M. Takeuchi, H. Matsushita, Y. Uwate, and Y. Nishio,“Firefly Algorithm Distinguishing between Males and Females for Minimum Optimization Problems", being submitted to elsewhere.

—4—