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

信学技報
TECHNICAL REPORT OF IEICE.

役割分担を行うミツバチコロニー最適化
白崎雄大†

下村将†

上手洋子†

西尾芳文†

† 徳島大学工学部 〒 770–8506 徳島県徳島市南常三島町 2-1
E-mail: †{shirasaki, s-sho, uwate, nishio}@ee.tokushima-u.ac.jp
あらまし

本研究で我々は新しいミツバチコロニー最適化 (Honeybee Colony Optimization: HCO) として，役割分担を行うミツバチコロニー最適化 (Honeybee Colony Optimization with Role and Responsibility: HCOR&R) を提案する．HCOR&R は，グローバルサーチを行う探索バチとローカルサーチを行う派遣バチという様に現実のミツバチと同様に役割分担を行う．HCOR&R を巡回セールスマン問題 (Traveling Salesman Problem: TSP) に適応し，従来の HCO より効果的な結果を得ることを確認する．
キーワード

最適化，巡回セールスマン問題，ミツバチ，ローカルサーチ

Honeybee Colony Optimization with Role and Responsibility
Yudai SHIRASAKI† , Sho SHIMOMURA† , Yoko UWATE† , and Yoshifumi NISHIO†† Department of Electrical and Electronic Engineering, Tokushima University
2-1 Minami-Josanjima, Tokushimashi, Tokushima, 770-8506, Japan
E-mail: †{shirasaki, s-sho, uwate, nishio}@ee.tokushima-u.ac.jp
Abstract In this study, we proposes a new Honeybee Colony Optimization (HCO) method; Honeybee Colony
Optimization with Role and Responsibility (HCOR&R). In HCOR&R, Role and Responsibility is performed like an
actual honeybee like the search-bee who performs a global search, and recruit-bee who performs a local search. We
apply HCOR&R to Traveling Salesman Problems (TSPs) and conﬁrm that HCOR&R obtains more eﬀective results
than the standard HCO.
Key words Optimization, Traveling Salesman Problem, Honeybee, Local Search

1. ま え が きが決定していて一生を与えられた役割通りに行動する．そしてこの特徴は採餌行動の際にもみられる．次に，採餌行動の手順

巡回セールスマン問題 (Traveling Salesman Problem: TSP)を説明する (図 1 参照)．ミツバチには女王バチや働きバチ，雄は都市の集合と各 2 都市間の移動コストが与えられたとき、全バチなどが存在するが採餌行動を行うのは働きバチのみであり，ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のコスト

その働きバチの中でも探索バチと派遣バチの 2 種類に分らけれ

すなわち総移動距離が最小のものを求める組合せ最適化問題でる．まず，探索バチはランダムに周囲を探索することで芳醇なあり，都市数が増えるに従って計算量が爆発的に増加すること食料源を探す．そして芳醇な食料源を発見すると，探索バチはから非常に困難な問題とされている．TSP の解法として，ア巣に戻ってその食糧源に適切な数の派遣バチを派遣するためにントコロニー最適化 (Ant Colony Optimization: ACO) [1], [2]尻振りダンス (Waggle Dance) [7] を行なう．この尻振りダンス

や粒子群最適化 (Particle Swarm Optimization: PSO) [3] など

は，派遣行動とナビゲート行動を組み合わせたものであり，派の最適化手法が用いられる．これらは現実の昆虫や鳥などの生遣行動は巣で待機している派遣バチに探索結果を伝えることで物学的なメガニズムを応用した最適化アルゴリズムであり総じ食料源に適切な数の派遣バチを派遣する役割，ナビゲート行動て群知能と呼ばれている．

は巣で待機している派遣バチと誘導したい場所の位置情報 (方本研究では，ミツバチの採餌行動をモデル化した群知能の向と距離) を共有する役割をそれぞれ持つ．このように 2 種類一種であるミツバチコロニー最適化 (Honeybee Colony Opti-のミツバチが分担して探索することによって個々で各々に探索

mization: HCO) [4]- [6] を用いた TSP の解法として新しいアするのではなく，集団で広域に渡って緻密な探索を行うことがルゴリズムの提案を行う．現実世界のミツバチの特徴として，できる．これら役割分担や集団行動は昆虫では珍しいものとさ役割分担を行う昆虫であり，生まれた瞬間から既に自分の役割れ，それゆえ，社会的な昆虫とも言われている．

—1—

Poor

Poor

Poor

Mellow

Poor

Poor

Mellow

Poor

Mellow

PoorPoorPoor

In Bee Hive

Neighborhood searchwith recruit bees
BeeHive

BeeHive

BeeHive

STEP:2

STEP:1

Waggle Dance

STEP:3

図 1 Food foraging behavior of honeybee

HCO では，” ハチ” と呼ばれる並列的に行動する複数の解

R は，Mg と Ml の比率を決定する制御パラメータである．

が存在し，ハチごとにそれぞれ最適な巡経路リスト: Personal

ローカルサーチは，まず全都市の位置情報の平均を取りそのtour List(P L) を持ちより良い経路を発見した際は自身の P L中で最も中心近くの数都市の中からランダムで選ばれた都市の更新を行う．それとは別に，全体で P L の情報を共有，更新を共通都市と定める．共通都市は分割した時にどちらにも含した巡経路リスト: Global tour List(GL) を持つ．この 2 つをまれるものとする．ローカルサーチを行う派遣バチ Ml は，最使い分けることで HCO は局所解に陥るリスクを下げている．

適候補解の巡経路を記憶した GL を用い，それを境目に巡経

しかし，都市数が増えるに従って，計算量が膨大になり部分的路を 2 つに分割する．そして，その情報をグローバルサーチに局所解に陥ってしまう問題点がある．

を行う探索バチ mg に還元している．情報の還元は，Ml のそこで我々は，現実のハチが行っている役割分担 (探索バGL をカウントしていくことで行う．例えば都市数 N = 6 でチと派遣バチ) の概念を追加した役割分担するミツバチコロ

GL = {4, 2, 3, 1, 5, 6, } の時，まず 6 × 6 の行列を作成する．そニー最適化 (Honeybee Colony Optimization with Role andして，{4 と 2}, {2 と 3}, {3 と 1}, ..., {6 と 4} の様に GL の隣

Responsibility: HCOR&R) を提案する．従来の HCO では，在っている都市をカウントしていく．4 と 7 の場合，4 行 7 列全ての解は全都市の巡経路を求めるためにグローバルサーチをと 7 行 4 列にカウントする．ただしこの時，共通都市に隣在っ行っているが HCOR&R ではそれに加えてローカルサーチも行ている都市ではカウントしないものとする．これは，ローカルう．ローカルサーチとは，グローバルサーチと比べて探索都市サーチにおける共通都市周辺では局所解に陥っている場合が多数を少なくしたものであり，グローバルサーチより細部まで探いためである．

索できる特徴を持つ．これより，探索バチ部分的な最適解の情また一定期間経過やローカルサーチが局所解に陥って改善が報を複数得ることができ，それらを組み合わせることで最適解見込めない場合，ローカルサーチの初期化を行う．そして再度への到達が容易となる．

都市の分割を行うがこのときに，分割する共通都市を変更させHCOR& R の原理については 2 章で説明する．3 章では，ることで分割した時に含まれる都市を変化させ，局所解に陥る

HCOR&R を 2 つの TSP に応用し，従来の HCO と比較する可能性を抑えている．共通都市の変更方法は，初期の共通都市

ことにより HCOR&R の性能を確認する．とに比較的近い都市がランダムで選ばれる．TSP の N 個の都
市集合 S は次式で表される．

2. HCOR&R
通常の HCO と比較した場合，HCOR&R の重要な特徴は，

S ≡ P1 , P2 , ..., PN , Pi ≡ (xi , yi )(2)グローバルサーチ行う探索バチとローカルサーチを行う派遣バ

都市の座標は 0 から 1 に正規化し，Pi は i 番目の都市の場所をチの２種類のハチが存在していることである (図 2 参照).

表している (i = 1, 2, ..., N )．

探索の初期段階において，すべてのハチ M 匹の中で探索バ
チ Mg (g = 1, 2, ..., mg ) のみがグローバルサーチを行う．そして，評価の高かった巡経路を GL 及び P L に記憶，更新を行っていく．ある期間経過した後 (t < tlimit )，GL を利用しながら派遣バチ Ml はローカルサーチを行う．

1Mg = M × R, Ml = M (1 − R) ×2

[Step. 1] (初期化) t = 0, tR = 0 (tR はローカルサーチの初期化カウント) とする．

[Step. 2] (巡回路の生成)M (= Mg + Ml ) 匹の巡経路を生成する．ローカルサーチは t > tlocal 以降から開始．

(1)
—2—

[Step. 3] (グローバルサーチ) 巡経路の評価を行う．そして，Waggle Dance に従う確率を求める．
1, Lg = tour length
Lg

(6)

Mg
1 ∑P fg
P fg GL(t) =Nbee g=1
P fcolony(7)

P fg =P fcolony =P fg はハチ g の評価値であり，これは総距離 Lg の逆数である．
P fcolony は Mg 匹のハチの評価値の平均．GL(t) は (t + 1) の時の P L に選ばれる確率であり，高評価値の巡経路ほど選ばれやすくなっている．ここで，(a) グローバルサーチ

P fgbest < P fg (t) の時，P fgbest と P Lg (t) を更新．
以下の表は，すべてのハチ M が (t + 1) の時，GL(t) かP Lg (t) のどちらを用いるかの決定を行う確率を示す．
表 1 Waggle Dance に従う確率

Proﬁtability Scores(b) ローカルサーチ

Pf ollow

P fg < 0.95P fcolony
0.95P fcolony <= P fg < 0.975P fcolony

0.80

0.975P fcolony <= P fg < 0.99P fcolony<0.99P fcolony = P fg <= P fg

0.02

0.20
0

[Step. 4] (ローカルサーチ)t > tlocal 以降，以下の処理を実行する．[Step. 3] と同様の処理を Ml についても行う．ローカルサーチの GL(t) を用いて巡経路をカウントする．
もし GL(t + 1) = GL(t) の時，tR (t + 1) = tR (t) + 1 する．
そして tR (t) > tlimit または一定周期経過した時，ローカルサーチを初期化，tR (t) = 0 とする．

[Step. 5] t = t + 1 を行う．t = tmax に達していなければ，[Step. 2] に戻る．tlocal はローカルサーチの開始ポイント．

(c) ローカルサーチ+グローバルサーチ
図 2 HCOR&R の探索方法

Pij,n (t) = ∑[ρij,n ]α · [ d1ij ]β · [Cij ]γj∈Ag,i,n [ρij,n ](t > tlocal ) Pl,ij,n (t) = ∑α · [ 1 ]β · [C ]γij
dij

[ρij,n ]α · [ d1ij ]βj∈Al,i,n [ρij,n ]α · [ 1 ]βdij

3. シミュレーション
本報告では，PBHCO の性能を att48(都市数 N = 48) と(3)kroA100(都市数 N = 100) の 2 種類の TSP を用いて標準HCO を比較することで評価を行う．更新数: tmax = 2000 回，(4)シミュレーション回数: 10 回とする．ハチの数 M はそれぞれの都市数と等しいものとし，標準 HCO と HCOR&R のパラ

ρg,ij,n は n 回目の移動で都市 i から都市 j へツアーリスト(GL(t) or P Li (t)) を用いて移動する確率であり，dij は都市i から都市 j の距離の逆数である．Ag,i,n , Al,i,n は，g, l が n

メータは以下のように設定する．

λ = 0.95, α = 1, β = 10, γ = 15, R = 0.65, tlimit = 30

回目の移動でまだ訪れていない都市集合である．そして，Cijtlimit はローカルサーチの初期化カウント．得られた解と最適はローカルサーチから得られる局所的な最適解の情報であり，解を比較するために次のような誤差率を用いる．

Pij,n (t) でも P L を使用している場合 γ = 0 とする，α, β ，γは各々の制御パラメータである．

ρij,n は，
λ, j ∈ Fi,n , |Ai,n | > 1 
1−λ|Ai,n ∩Fi,n |ρij,n =,j∈
/F,|A|>
1i,ni,n|Ai,n −Fi,n |
1, |A | = 1 i,nで表される．(0 <= 1)=λ<

誤差率 [%] =(得られた解) − (最適解)
× 100
(最適解)

(8)

この式は巡経路の長さが最適解と比べた場合，どれくらい長いかを示したものであり，誤差率が 0 に近いほど最適解に近い．

(5)

また，HCOR&R が HCO と比べてどれくらい改善されたか評価するために以下の式を用いる.
)−(HCOR&R の誤差率)
改善率 [%] = (HCO の誤差率
× 100
(HCO の最適解)(9)—3—3. 1 att48
まず初めに，att48(都市数 N ＝ 48) の TSP について得られた解を表 2 に示す．
表 2 att48 における結果

HCO HCOR ＆ R
誤差率平均 [％]

2.43

1.73

最小値 [％]

1.58

0.08

標準偏差 [％]

0.620.53-28.81

改善率 [％]

HCOR&R は標準 HCO より平均値，最小値において良い解を得ることができた．また，標準偏差も HCOR&R のほうが良かったことからローカル探索は有効であると考えられる．

3. 2 kroA100
次に，kroA100(都市数 N ＝ 100) の TSP について得られた解を表 3 に示す．
表 3 kroA100 における結果

HCO HCOR ＆ R
誤差率

平均 [％]

11.2

9.27

最小値 [％]

9.57

6.8

標準偏差 [％]

11.5-

17.23

改善率 [％][3] J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proc. IEEE Int. Conf. on Neural Networks, vol. 4,pp. 1942–1948, 1995.
[4] D.T. Pham, A. Ghanbarzaden, E. Koc, S. Otri, S. Rahimand M. Zaidi, “The Bees Algorithm - A Novel Tool for Complex Optimization Problems,” Intelligent Production Machines and Systems, pp. 454-459, Cardiﬀ University, UK,2006.
[5] L. Wong, M.Y.H. Low, C.S. Chong, “Bee Colony Optimization with Local Search for Traveling Salesman Problem,” inProc. of 6th IEEE International Conference on Industrial
Informatics (INDIN2008), pp. 1019-1025, Nanyang TechnolUniversity, 2008.
[6] L. Wong, M.Y.H. Low, C.S. Chong, “An Eﬃcient Bee
Colony Optimization Algorithm for Traveling Salesman
Problem using Frequency-based Pruning,” 7th IEEE International Conference on Industrial Informatics (INDIN2009),
pp. 775-782, Nanyang Technol University, 2009.
[7] C.Gruter and W.M. Farina, “The honeybee waggle dance:
can we follow the steps?,” Trends in Ecology and Evolution
vol. 24, pp. 242-247, 2008.

平均値及び最小値において HCOR&R は HCO より良い結果を得，標準偏差でも標準 HCO より大きく改善された．ただ，改善率は 17[%] と 48 都市の 28[%] と減少した．これは 100 都
市において 2 つに分割した場合でも，都市数は 48 都市を上回る数となりローカルサーチにおいても細部まで探索できないといった結果になってると考えられる．この問題を改善するために，分割数を増やして 1 か所のローカルサーチが探索する都市数を減らし，より細部まで探索できるようにすることが必要であると考えられる．

4. ま と め
本報告で，私たちは役割分担するミツバチコロニー最適化(Honeybee Colony Optimization with Role and Responsibility: HCOR&R) を提案した．HCOR&R を 2 種類の TSP に適用することで性能の調査を行った．その結果，att48(都市数N ＝ 48) ではローカルサーチにおける改善が大きく見られたが，kroA100(都市数 N ＝ 100) では att48 と比較して改善率が減少した．これは都市数に対して，分割数の不足が原因ではないかと考えれる．今後の課題として，共通都市の決定方法の工夫及び複数の共通都市で複数個分割によるローカルサーチなどがある．
文献[1] M. Dorigo and T. Stutzle, “Ant Colony Optimization,”
Bradford Books, 2004.
[2] H. Koshmizu, T. Saito, “Parallel Ant Colony Optimizers
with Local and Global Ants,” Proceedings of International
Joint Conference on Neural Networks, 2009.

—4—