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

信学技報
TECHNICAL REPORT OF IEICE.

２種類の探索法を用いるミツバチコロニー最適化
白崎雄大†

上手洋子†

西尾芳文†

† 徳島大学工学部 〒 770–8506 徳島県徳島市南常三島町 2-1
E-mail: †{shirasaki, uwate, nishio}@ee.tokushima-u.ac.jp
あらまし これまでの研究で，我々は群知能の一種であるミツバチの採餌行動をモデル化した新しいミツバチコロニー最適化 (Bee Colony Optimization: BCO) として，役割分担を行うミツバチコロニー最適化 (Bee Colony Optimization

with Role and Responsibility: BCORR) を提案した．BCORR は，グローバルサーチを行う探索バチとローカルサー
チを行う派遣バチという様に現実のミツバチと同様に役割分担を行う．本研究では，我々はローカルサーチとグローバルサーチを並列に行う新しい BCORR を提案する．また，新しい BCORR ではグローバルサーチ時の巨大近傍使用，ローカルサーチを行う位置の決定法をそれぞれ提案し，その振る舞いの調査を行う．そして BCORR を巡回セー
ルスマン問題 (Traveling Salesman Problem: TSP) に適応し，従来の BCO より効果的な結果を得ることを確認する．
キーワード

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

Bee Colony Optimization with Role and Responsibility
Yudai SHIRASAKI† , 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, uwate, nishio}@ee.tokushima-u.ac.jp
Abstract In previous study, we proposed Bee Colony Optimization with Role and Responsibility(BCORR) asnew Bee Colony Optimization(BCO) for a kind of swarm intelligence. BCORR does Role and Responsibility that isperformed like an actual honeybee like the search-bee who performs a global search, and recruit-bee who performs alocal search. In this study, we proposes a new BCORR for Parallel Searching with Local Search and Global Search.
And, it is added new two functions in BCORR, one is very large-scale heighborhood for global search, another isthe determine method of local search position for local search. We apply HCORR to Traveling Salesman Problems(TSPs) and conﬁrm that HCORR obtains more eﬀective results than the standard HCO.
Key words Optimization, Traveling Salesman Problem, Honeybee, Local Search

1. ま え が き
日常生活の中には，カーナビゲーションの最短経路の発見や工場の最適な配置設計など様々な問題が存在している．これら

Swarm Optimization: PSO) [4] などの最適化手法が用いられる．これらは現実の昆虫や鳥などの生物学的なメガニズムを応用した最適化アルゴリズムであり総じて群知能 [5] [6] と呼ばれている．の問題は組み合わせ最適化問題の一種として知られており，そ本研究では，同じく群知能の一種であるミツバチの採餌行

れぞれ巡回セールスマン問題 (Traveling Salesman Problem:

動をモデル化したミツバチコロニー最適化 (Bee Colony Opti-TSP)，二次割り当て問題 (Quadratic Assignment Problem:mization: BCO) [7]- [9] を用いて TSP の解決を行う．現実世QAP) [1] と呼ばれている．TSP は都市の集合と各 2 都市間の界のミツバチの特徴は，役割分担を行う昆虫であり，生まれた移動コストが与えられたとき，全ての都市をちょうど一度ずつ瞬間から既に自分の役割が決定していて一生を与えられた役割巡り出発地に戻る巡回路のコストすなわち総移動距離が最小の通りに行動する．そしてこの特徴は採餌行動の際にもみられる．

ものを求める組合せ最適化問題であり，都市数が増えるに従っミツバチには女王バチや働きバチ，雄バチなどが存在するが採て計算量が爆発的に増加することからしだいに解決が困難に

餌行動を行うのは働きバチ (これ以降，働きバチを 2 種類に分なっていく．TSP の解法として，アントコロニー最適化 (Ant類し，それぞれ探索バチ，派遣バチと呼称する) のみである．しColony Optimization: ACO) [2] [3] や粒子群最適化 (Particle

かし，全ての働きバチが一斉に探索を行うのでなく，まず初め—1—

に一定の数の働きバチ (探索バチ) が芳醇な食料源を探すために探索を行う．そして芳醇な食料源を発見すると，探索バチは巣に戻り，待機している働きバチ (派遣バチ) に食料源の位置情報 (方向と距離) をダンスを用いて伝える．このダンスは尻振りダンス (Waggle Dance) [10] と呼ばれており，食料源の位置情報を伝えるだけでなく，その食料源の評価値を仲間に伝える役割も兼ねており，それによって食糧源に適切な数の派遣バチを派遣することができる．つまりこの尻振りダンスは，派遣行動とナビゲート行動を組み合わせたものであり，派遣行動は巣で待機している派遣バチに探索結果を伝えることで食料源に適切な数の派遣バチを派遣する役割，ナビゲート行動は巣で待機している派遣バチに誘導したい場所の位置情報を伝える役割を(a) Global search

それぞれ持つ．これがミツバチの採餌メカニズムであり，このような探索戦略を用いることで個々で探索するよりも，広域に渡って緻密な探索を行えるので探索効率が非常に高くなる．このような役割分担や集団行動は昆虫では珍しいものとされ，それゆえ，社会的な昆虫や群知能とも言われている．
前回までの研究で，我々は一般的な BCO アルゴリズムに上記の探索戦略を追加した新しい BCO アルゴリズム，役割分担を行うミツバチコロニー最適化 (Bee Colony Optimization(b) Local searchwith Role and Responsibility: BCORR) を提案した．この手法では，現実のミツバチにおける初期探索の部分をグローバルサーチとし，巣に戻ってから他の働きバチに情報を伝えた後に行う探索をローカルサーチとした．グローバルサーチでは TSPの全都市の探索を行い，ローカルサーチではグローバルサーチで探索して得られた結果を元にして少数の都市内で探索を行う．
つまり，グローバルサーチを構築法，ローカルサーチは改善法として位置付けられる．BCORR では，試行回数の前半部をグ(c) Exportation of global search from local search

ローバルサーチ，後半部をローカルサーチとして探索を行って図 1 Search method of BCORRいた．そのため，前半部のグローバルサーチで局所解に捕まってしまった場合，少数都市内でしか探索を行えないローカルサーチでは局所解から抜け出せないという欠点があった．

更新を行っていく．ここで，P L は各ハチ Mg の現在までの試行回数の中で最も評価の高かった巡経路の記憶であり，GL

今回の研究で，我々のこの欠点を克服するためグローバルは全ての P L の中で最も評価の高かった巡経路から順に確サーチとローカルサーチを並列に行う新しい BCO を提案す率的に選択される．グローバルサーチを終えた後，派遣バチる．(以下，新しい BCO を BCO と呼称する) この新しい BCO

Ml (l = 1, 2, ..., ml ) は P L を利用してローカルサーチを行う．

では，同試行回数中にグローバルサーチとローカルサーチに最も評価の高い P L(P Lbest に記憶された巡経路の並びからラよる探索を行っているためにもしも局所解に捕まった際にもンダムに都市の並び (Nl = N ∗ LSrange ) を取り出し，その取グローバルサーチによって局所解から抜け出せる可能性があり出した都市をローカルサーチによって改善していく．もしる．更に我々は，グローバルサーチに巨大近傍 (very large-scale

ローカルサーチで巡経路が改善された場合，その巡経路は新たneighborhood)，ローカルサーチを行う位置決定法を提案する．

な P Lbest をして更新されグローバルサーチに情報還元される．

ローカルサーチの範囲の調整に加えて，これらを使用した場合

そしてグローバルサーチに情報還元された場合，現在のローカの振る舞いの調査を行う．

ルサーチは初期化され，次試行回数時に新たな P Lbest を利用

2. BCORRHCORR の特徴は，グローバルサーチに加えてローカルサーチを行うことである (図 1 参照). 探索の初期段階において，すべてのハチ M 匹の中で探索バチ Mg (g = 1, 2, ..., mg ) のみがグローバルサーチを行い，残りの派遣バチ Ml (l = 1, 2, ..., ml )してローカルサーチを行う．逆に一定期間の試行回数改善されなかった場合，その地点でのローカルサーチは改善の余地がな
いとみなされ，初期化を行い新たな地点でローサルサーチを行う．TSP の N 個の都市集合 S は次式で表される．

S ≡ P1 , P2 , ..., PN , Pi ≡ (xi , yi )(1)は 巣 で 待 機 し て お く．そ し て ，評 価 の 高 かった 巡 経 路 を

都市の座標は 0 から 1 に正規化し，Pi は i 番目の都市の場所

P ersonaltourLists : P L 及び GlobaltourList : GL に記憶，を表している (i = 1, 2, ..., N )．次に，フローチャートを用いて—2—

START
t=0Mg bees are set to city at random
Waggle danceEach bee visiting N cityNo

Choose the next cities j from choice probability pij,nBee g visited all cities

NoMl bees are set to city at random
Each bee visiting N city
Choose the next cities j from choice probability pij,nAll bees visited all cities

NoYes

Decision of local search position

Yes
t=t+1

t Limit>tlocal

No

Yes

Bee g visited all cities

Update PL and GL

t Limit=t Limit+1

Yes

No

All bees visited all cities

Local search

Yes
Update PL and GL

Not>tmaxYesEND(a) Flowchart of BCORR(b) Constitution of local search

図 2 Flowchart of HCORR algorithm.

時の P L に選ばれる確率であり，高評価値の巡経路ほど選ばれBCORR アルゴリズムの説明を行う (図 2 参照)．

やすくなっている．ここで，[Step. 1] (初期化) t = 0, tR = 0 (tR はローカルサーチの初P fgbest < P fg (t) の時，P fgbest と P Lg (t) を更新する．

期化カウント) とする．

以下の表は，すべてのハチ M が (t + 1) の時，GL(t) か P Lg (t)[Step. 2] (巡回路の生成)Mg 匹の巡経路を生成する．のどちらを用いるかの決定を行う確率を示す．

Pij,n (t) = ∑[ρij,n ]α · [ d1ij ]β(2)1 βαj∈Al,i,n [ρij,n ] · [ dij ]ρij,n は n 回目の移動で都市 i から都市 j へツアーリスト (GL(t)or P Lg (t)) を用いて移動する確率であり，dij は都市 i から都市 j の距離の逆数である．Ai,n は，g が n 回目の移動でまだ訪れていない都市集合である．そして，α, β は各々の制御パラメータである．

ρij,n は，
λ,j∈Fi,n , |Ai,n | > 1 
1−λ|Ai,n ∩Fi,n |ρij,n =,j∈
/F,|A|>
1i,ni,n|A−F|i,ni,n
1, |A | = 1 

表 1 Waggle Dance に従う確率

Proﬁtability Scores

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] (ローカルサーチ)
ローカルサーチは，グローバルサーチの記憶した巡回路 P Lbest(3)

i,nを用いて少数の都市 (Nl = N ∗ LSrange ) で探索する．ロー
カルサーチの探索の手順はグローバルサーチと同様であり，[Step. 2]-[Step. 3] のように行う．ただし異なる点として，ローで表される．(0 <= 1)=λ<[Step. 3] (巡経路の評価)[Step. 2] で生成した巡経路の評価

カルサーチには初期化が存在する．これは，一定期間巡経路を行う．そして，Waggle Dance に従う確率を求める．

ローカルサーチは初期化され，t+1 の時新たな地点でローカ

1, Li = tour length
Li(4)

Mi
P fi
1 ∑
P fi GL(t) =P fcolony =Nbee g=1
P fcolony(5)

P fi =の更新が行われなかった場合 (tR (t) > tlimit )，現在の地点のルサーチを開始する．LSrange は，ローカルサーチの範囲を表しており，LSrange = 0 の場合はローカルサーチは行われず，

P fg はハチ g の評価値であり，これは総距離 Lg の逆数である．
P fcolony は Mg 匹のハチの評価値の平均．GL(t) は (t + 1) のLSrange = 1 の場合はローカルサーチはグローバルサーチを同様の範囲で行われることを表している．

[Step. 5] t = t + 1,tR (t + 1) = tR (t) + 1 を行う．t = tmaxに達していなければ，[Step. 2] に戻る．

—3—

3. 3 BCORR の性能の調査

3. シミュレーション

最後に，BCORR の性能を HCO，ACO と比較して調査す

本報告では，PBHCO の性能を TSP を用いて評価する．こる．それぞれの TSP における LSrange は表 4 に示す．またこのとき，比較対象には HCO に加えて ACO を使用する．試行

こで，HCORR に新たな機能を追加する．1 つは，グローバル

回数: tmax = 2000 回，シミュレーション回数: 100 回とする．

サーチに巨大近傍を用いること，そしてもう 1 つはローカル

ハチの数 M はそれぞれの都市数 N と等しいものとし，今回サーチを行う位置決定法である．ここでの巨大近傍はローカル

Mg = 50[%]，Ml = 50[%] とする．

サーチを行っているエリアのことを示し，グローバルサーチを行う際はローカルサーチを行っているエリアを 1 つの集合とし

λ = 0.95, α = 1, β = 10, tlimit = 50て見なし，都市の順番を固定する．そうすることでグローバル

α，β は制御パラメータであり，tlimit はローカルサーチの初期サーチで探索する都市数の減少に繋がり，相対的に局所探索を化カウントである．

行うことができる．ローカルサーチの位置決定法とは，GL に

3. 1 ローカルサーチの範囲 LSrange の調査

おける都市 i と都市 j の距離を最短経路と比較して順位付けす

ローカルサーチの範囲 LSrange を変化させ調査することでる．これを全ての都市間で行い，順位が最も遠い，つまり距離最適な LSrange のパラメータを決定する．使用する TSP はが最も遠い場所を基準としてローカルサーチを行う．最短経路

att48(N=48) と kroA100(N=100) の２種類を使用する．またと最も遠い場所の付近でローカルサーチを行うことで改善する

今回，ローカルサーチの位置決定はランダムとする．

可能性を高める効果が期待できる．

表 2 は，LSrange を変化させた際，ローカルサーチによる改表 3 は,BCORR と BCO，ACO でシミュレーションを行っ善が起こった回数を示している．att48 では，LSrange = 0.3 のた結果を示している．全ての場合で BCORR は，他の 2 つよ時に最も改善が多く起こったが，逆に LSrange = 0.5 以上ではり評価が良くなった．att48，kroA100 では，巨大近傍を使用改善が確認できなかった．kroA100 では，LSrange = 0.1 が最した場合が最も良く，st70 では 2 つの新しい機能を使用した場も多く，LSrange = 0.4 以上では確認できなかった．このこと合が最も良い結果となった．このことより，巨大近傍はグローより，ローカルサーチに最適な都市数が存在していると考えらバルサーチに効果的に働くことが確認できた．しかし，ローカれる．

ルサーチの位置決定法は st70 を除き，ランダム法より劣って(N = 48) : N × LSrange = 48 × 0.3 = 14.4.

(6)(N = 100) : 100 × 0.1 = 10.

(7)

上式はそれぞれの TSP で最適であった LSrange に含まれている都市数を求めたものである．これより，ローカルサーチにおける最適な都市数は約 10〜15 都市を考えられる．

いた．これは，問題の都市配置に大きく影響されている可能性がある．しかし，現在の位置決定法では都市配置が考慮されておらず，これより現在の位置決定法の改善あるいは新しい位置決定法の提案が必要だと考える．
表 4 The optimal LSrange for each TSPs

TSP
LSrange =表 2 The result of Number of updates

LSrange =0.10.2 0.3 0.4 0.5 0.6

att48

Number of updates

3747702900kroA100[time]

1825315000att48 st70 kroA1000.30.250.14. ま と め
本報告で，私たちは HCORR のローカルサーチの振る舞い

3. 2 ローカルサーチの振る舞いの調査の調査を行った．ローカルサーチは探索範囲の大きさによる影

次に，BCORR でのローカルサーチの効果の確認を行う．使
用する TSP は att48 とする．得られた解と最適解を比較するために次のような誤差率を用いる．

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

響が大きいことが分かった．今回，ローカルサーチの最適な探索範囲を求めることができ，そのパラメータを用いて BCO，ACO を比較することで性能を調査した．その結果，巨大近傍(8)この式は巡経路の長さが最適解と比べた場合，どれくらい長いかを示したものであり，誤差率が 0 に近いほど最適解に近い．
図 3 は，1 回のシミュレーション結果を取り出し，平均値と最小値の移り変わりを示した図である．BCO と BCORR の最小値は緩やかに移り変わっているが，BCORR の平均値を見ると激しく振動しているように見える．これは，ローカルサーチによって局所解から抜け出しているから起こったものだと考えることができ，ローカルサーチの効果が確認できる．また ACOを比較すると BCO，BCORR は明らかに異なる振る舞いをしているとこから，別種のアルゴリズムであると確認できる．の効果性はどの問題の場合も確認できたが，位置決定法は都市配置に強く依存しているので問題によっては従来手法より結果が悪くなった．今後の課題として，グローバルサーチだけでなくローカルサーチにも巨大近傍を適応することでより多くの都市数でローカルサーチを行うことができ，局所探索性能を高めるアルゴリズムの開発がある．また，都市数が多い問題で全ての場所でローカルサーチが行うことができない場合などに，的確に効果が与えることのできるような位置決定法を提案したいと考える．
文

献[1] V. Maniezzo and A. Colorni, “The ant system applied tothe quadratic assignment problem,” IEEE Transactions on—4—

averageminimum

0.6100.50.510

Error rate (%)

Error rate (%)

100.4

100.3

10average
minimum

0.6

100.4

100.3

100.20.2

100.110100.1

100200400600

800

1000

1200

1400

1600

1800

02000

200

400

600

800

(a) BCORR

1200

1400

1600

1800

2000

(b) BCOavarageminimum

0.14

100.1210

Error rate (%)

1000

Iteration (t)Iteration (t)0.1

100.08100.06100.04100.02100200

400

600

800

1000

1200

1400

1600

1800

2000

Iteration (t)(c) ACO

図 3 The behavior of three algorithms
表 3 The result of comparison of performance

ACO BCO BCORR BCORR BCORR BCORR
global search--

current

newcurrent

newlocal search--

current

current

new

new
1.54

att48

st70

kroA100

error rate [％]

Ave

2.67

2.11

1.76

1.48

1.83

Min

1.65

0.8

1.17

0

0.78

0Max

3.07

3.72

2.68

2.74

5.39

4.19

Ave

5.34

4.42

3.02

3

3.03

2.77

Min

3.06

2.68

1.07

0.6

0.4

0.73

Max

6.22

6.24

4.95

5.09

4.55

5.04

Ave

12.5

129.06

8.51

9.51

9.49

Min

11.9

9.92

4.76

3.85

4.71

7.58

Max

1414.212.6

12.8

1311.4Knowledge and Data Enginering vol. 11 no. 5, pp. 769-778,
1999.
[2] M. Dorigo and T. Stutzle, “Ant Colony Optimization,”
Bradford Books, 2004.
[3] H. Koshmizu, T. Saito, “Parallel Ant Colony Optimizers
with Local and Global Ants,” Proceedings of International
Joint Conference on Neural Networks, 2009.
[4] J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proc. IEEE Int. Conf. on Neural Networks, vol. 4,pp. 1942–1948, 1995.
[5] Blum and Merkel (eds), “Swarm Intelligence,” Springer,
2008.
[6] E. Bounabean, M. Dorigo and T. Stutzle, “Inspiration foroptimization from social insect behavior,”

plex Optimization Problems,” Intelligent Production Machines and Systems, pp. 454-459, Cardiﬀ University, UK,
2006.
[8] K. Guney and M. Onay, “Bees algorithm for interference
suppression of linear antenna arrays by controlling thephase-only and both the amplitude and phase,” Faculty ofEngineering, Erciyes University, 2007.
[9] 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.
[10] 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.

[7] D.T. Pham, A. Ghanbarzaden, E. Koc, S. Otri, S. Rahimand M. Zaidi, “The Bees Algorithm - A Novel Tool for Com-

—5—