社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS
信学技報
TECHNICAL REPORT OF IEICE.
敏感なアリと鈍いアリによるアントコロニー最適化
下村 将
†杉本 雅樹
†原口 卓
†松下 春奈
††西尾 芳文
†† 徳島大学
〒 770-8506 徳島県徳島市南常三島町 2-1
†† 法政大学
〒 184-8584 東京都小金井市梶野町 3-7-2
E-mail: †{ s-sho,sugimoto,nishio } @ee.tokushima-u.ac.jp, †† [email protected]
あらまし
本研究では新しいアントコロニー最適化 (Ant Colony Optimization: ACO) として、敏感なアリと鈍いア リによるアントコロニー最適化 (ACO with Intelligent and Dull Ants: IDACO) を提案する。IDACO アルゴリズムに は、敏感なアリと鈍いアリ２種類のアリが存在することから、標準 ACO アルゴリズムよりも現実のアリのコロニー に近い性質を持つと言える。IDACO を巡回セールスマン問題 (Traveling Salesman Problem: TSP) に適用し、敏感 なアリだけが存在する標準 ACO より、IDACO の方が効果的な結果を得ることを確認する。
キーワード
アントコロニー最適化，巡回セールスマン問題，メタヒューリスティック
Behavior of Ant Colony Optimization with Intelligent and Dull Ants
Sho SHIMOMURA
†, Masaki SUGIMOTO
†, Taku HARAGUCHI
†, Haruna MATSUSHITA
††, and Yoshifumi NISHIO
†† Dept. of E.E. Eng., Tokushima University, 2-1 Minami-Josanjima, Tokushima 770-8506, JAPAN
†† Dept. of E.E. Eng., Hosei University, 3-7-2 Kajino-cho, Koganei-city, Tokyo 184-8584, JAPAN E-mail: †{ s-sho,sugimoto,nishio } @ee.tokushima-u.ac.jp, †† [email protected]
Abstract
This study proposes a new Ant Colony Optimization (ACO) method; ACO with Intelligent and Dull Ants (IDACO). In IDACO algorithm, two kinds of ants coexist:
intelligent antsand
dull ants. IDACO algorithm isnearer to the real ant colony than the standard ACO algorithm. We apply IDACO to Traveling Salesman Problems (TSPs) and confirm that IDACO obtains more effective results than the standard ACO which consists of only the intelligent ants.
Key words
Ant Colony Optimization, Traveling Salesman Problem, meta-heuristic
1. ま え が き
アントコロニー最適化(Ant Colony Optimization: ACO) [1]
は、生物学的なメカニズムから発想を得、アリのフェロモンの 効果を用いた最適化アルゴリズムであり、巡回セールスマン問 題(Traveling Salesman Problem: TSP) [2]や二次割り当て問 題(QAP) [4]、グラフ色彩問題[3]のような、複雑な組み合わ せ最適化問題を解くのに効果的である。中でも、TSPは様々 な組み合わせ最適化問題の基礎として研究されており、メタ ヒューリスティクス解法のベンチマーク問題として取り上げら れることが多い。TSPとは、都市の座標が与えられ、全ての都 市をちょうど一度ずつ訪問した後に最初の都市に戻ってくる巡 回路の組み合わせのうち、できるだけ最短で戻ってくる組み合
わせを探す問題である。ACOのアルゴリズムでは、“アリ”と 呼ばれる並列的に行動する複数の解が存在し、そのアリは都市 間をつないでいる経路にフェロモンを置く。そのフェロモンは アリの振る舞いに依存して更新され、アリは経路に置かれてい るフェロモンの強さに従って巡回路を形成する。つまり、これ らのアリが経路に置かれたフェロモンを通じてのみで他のアリ とコミュニケーションを取ることから、アルゴリズムは最適解 を見つけることが出来る。しかしながら、ACOには局所解に 陥りやすいという問題点がある。従って、アルゴリズムの柔軟 性を改善し、パフォーマンスを向上させることは重要であると 言える。
一方、現実のアリの世界には、“鈍いアリ”と呼ばれている 不必要なアリが約20パーセント存在するというレポートがあ
— 1 —
る[5]。他のアリは巣から出て食物を探し回っているのに対し て、この鈍いアリは自分達の巣の周りでただじっとしているの である。また、正確にフェロモンをたどることが出来る敏感な アリと、フェロモンをたどることが出来ない鈍いアリを用いて、
食料収集についてのコンピュータによるシミュレーション実験 を行った。それによると、鈍いアリを含んでいるグループは敏 感なアリだけのグループより多くの食物を集めることが出来た という、大変興味深い結果を残している。これは、敏感なアリ と鈍いアリの共生が、食物収集の有効性を改善したことを意味 している。
本研究では、敏感なアリと鈍いアリによるアントコロニー最 適化(ACO with Intelligent and Dull Ants: IDACO)という、
新しいACOアルゴリズムを提案する。IDACOの重要な特徴 は、“敏感なアリ”と“鈍いアリ”と呼ばれる2種類のアリが存 在するということである。これら2種類のアリの内、敏感なア リはフェロモンをたどることが出来るが、鈍いアリはフェロモ ンをたどることが出来ないという性質を持つ。これらの特徴は 現実のアリコロニーの構造を反映していると言えることから、
IDACOは、従来のACOよりも実社会に近い考え方からの最適 化を可能とする。シミュレーションでは、提案するIDACOを 様々なTSPに応用し、標準ACOと比較することで、IDACO の有効性を確認する。
2. 敏感なアリと鈍いアリによるアントコロニー 最適化 (IDACO)
提案するIDACOアルゴリズムについて詳しく説明する。
IDACOアルゴリズムにおいて最も重要な特徴は、敏感なアリ
と鈍いアリと呼ばれる2種類のアリが存在することである。敏 感なアリは標準ACOのアリと同等に、正確にフェロモンをた どることが出来る。しかし、反対に、鈍いアリはフェロモンを たどることが出来ないという性質を持つ。
TSPのN個の都市集合Sは次式で表される。
S≡ {P1, P2,· · ·, PN}, Pi≡(xi, yi) (1) 都市の座標は0から1に正規化し、Piはi番目の都市の場所を 表している(i= 1,2,· · ·, N)。初期状態では、それぞれのアリ (計M 個)を都市上にランダムに配置する。(1−d)×M 個の アリは敏感なアリの集合SIntelに、d×M個のアリは鈍いアリ の集合Sdullに分類する。ここで、dは全てのアリにおける鈍 いアリの割合である。
[Step1](初期化): 繰り返し回数をt= 0とする。τij(t)は 繰り 返し回数t回目のときの都市iと都市j間の経路(i, j)に置か れるフェロモンの量を表す。τij(0) =τ0に初期化する。
[Step2](巡回路の生成): 図1に示されるように、敏感なアリが 次に訪れる都市は、確率pij,I(t)によって、鈍いアリが次に訪 れる都市は、確率pij,D(t)によって選択される。k番目のアリ が都市iから都市jに移動する確率は次式によって決定される。
City i
City 2 City 1
City 3
)
,
(
1
t
p
i I)
,
(
1
t
p
i D)
,
(
2
t
p
i I)
,
(
2
t
p
i D)
,
(
3
t
p
i D)
,
(
3
t
p
i I鈍 鈍 鈍 鈍いアリ いアリ いアリ いアリ
敏感 敏感 敏感 敏感なアリ なアリ なアリ なアリ
図1 敏感なアリと鈍いアリの選択確率。敏感なアリが次の都市を選 択する確率はpij,I(t)。鈍いアリが次の都市を選択する確率は pij,D(t)。ただし、フェロモンの量τij(t)とτil(t)は含んでい ない。
pkij,D(t) = [ηij]βD
Σl∈Nk[ηil]βD, ifk∈Sdull
(2)
pkij,I(t) = [τij(t)]α[ηij]βI
Σl∈Nk[τil(t)]α[ηil]βI otherwise, (3) ここで、k= 1,2,· · ·, M であり、ηijは経路(i, j)間の距離の 逆数、Nkはk番目のアリがまだ訪れていない都市集合である。
パラメータβIとβDは、敏感なアリと鈍いアリの都市間の距 離情報の重みをそれぞれ制御し、パラメータαは敏感なアリ のフェロモンの情報の重みを制御する。したがって、αとβを 変化させることで、探索能力は上下する。式(2)は落とされる フェロモンの量τij(t)とτil(t)を含んでいないので、鈍いアリ はフェロモンをたどることは出来ない。つまり、鈍いアリは次 に訪れる都市を現在の場所からの距離によってのみ評価する。
一方、敏感なアリは次に訪れる都市を、置かれたフェロモン量 と現在の場所からの距離によって評価する。アリは全ての都市 を訪問し終わるまで、次に訪れる都市を繰り返し選択する。
[Step3](フェロモンの更新): 全てのアリが巡回路を生成した 後、都市間に置かれているフェロモンの量を更新する。ここで、
鈍いアリはフェロモンをたどることが出来ないが、フェロモン を置くことは出来るという点に注意すべきである。k番目のア リが経路(i, j)に置くフェロモンの量∆τkij(t)は、次式で決定 される。
∆τkij(t) =
( 1/Lk, if (i, j)∈Tk(t)
0, otherwise (4)
ここで、Tk(t)はk番目のアリによって得られた巡回路、Lk(t) はその巡回路の長さである。それぞれの経路(i, j)のフェロモ ンτij(t)を∆τkij(t)に従って更新する。
τij(t+ 1) = (1−ρ)τij(t) + XM k=1
∆τkij(t) (5)
— 2 —
ここで、ρ∈[0,1]はフェロモンの蒸発率である。
[Step4] t = t+ 1とする。t = tmax に達していなければ、
[Step2]に戻る。
3. シミュレーション結果
IDACOの探索能力の評価とその振る舞いを調査するために、
様々な鈍いアリの割合を用いたIDACOを2つのTSPに適用 し、標準ACOを比較した。
シミュレーションでは、標準ACOとIDACOのアリの数M は都市数と同数に設定する。標準ACOは敏感なアリのみで構 成されており、式(3)によって選択確率が決定される。IDACO はd×M 個の鈍いアリと、(1−d)×M個の敏感なアリで構 成される。鈍いアリの割合dは、それぞれのシミュレーション で0.2と0.5に設定する。全ての問題で10回繰り返してシミュ レーションを行い、その平均をとる。標準ACOとIDACOの パラメータは以下のように設定する。
τ0= 10, ρ= 0.3, α= 1, βI =βD= 5, tmax= 2000 ここで、フェロモンの蒸発率ρ、フェロモンの依存度α、距離 の依存度βIとβDそして、繰り返し回数t=tmaxの値は変化 させない。
得られた解と最適解を比較するために次のような誤差率を用 いる。
誤差率[%] =(得られた解)−(最適解)
(最適解) ×100 (6) この式は、ACOが得た巡回路の長さが最適解よりどれぐらい 長いかを示していることから、誤差率は0に近い方が望まし い。さらに、IDACOの解がACOよりどれぐらい改善された かを評価するために次式の改善率を用いる。
改善率[%] = (ACOの誤差率)−(IDACOの誤差率)
(ACOの誤差率) ×100 (7) 3. 1 Simulation 1: att48
0 0.2 0.4 0.6 0.8 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
図2 ベンチマーク問題att48とその最適解
att48(都市数N= 48)と呼ばれているTSPと、その最適解 を図2に示す。この問題に対して行った、標準ACOとIDACO のシミュレーション結果を、表1に示す。図3は、10回のシ ミュレーションのうち、標準ACOとIDACOで得られた最も 良い解を示している。
表1において、d= 0.2のIDACOは標準ACOより良い解
を得ることができた。しかしながら、d= 0.5のIDACOは標 準ACOより悪かったことに注目する。この結果から、鈍いア リが多すぎると得られる結果は悪くなることがわかる。
表1 標準ACOとIDACOをatt48に適用した結果
ACO IDACO
d= 0 d= 0.2 d= 0.5 誤差率 平均 2.87% 2.62% 3.84%
最小値 2.43% 1.46% 2.09%
ACOからの
- 8.7% −33.8%
改善率
3. 2 Simulation 2: kroA100
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
図4 ベンチマーク問題kroA100とその最適解
次に、kroA100(都市数N = 100)と呼ばれているTSPと、
その最適解を図4に示す。標準ACOとIDACOのシミュレー ション結果を表2に示す。図5は、10回のシミュレーションの うちの、標準ACOとIDACOで得られた最も良い解を示して いる。
表2より、IDACOは標準ACOより良い解を得ることがで きていることがわかる。さらに、att48と同様に、kroA100の 結果においても、d= 0.2のIDACOはd= 0.5のIDACOよ り良い解が得られている。これは、鈍いアリの割合が現実の世 界とほぼ同じ場合、IDACOが効果的な結果を得ることを確認 できたことを意味する。特に、多くの都市で構成されている TSPの場合、IDACOは標準ACOの結果を大きく改善すると いえる。
表2 標準ACOとIDACOをkroA100に適用した結果
ACO IDACO
d= 0 d= 0.2 d= 0.5 誤差率 平均 1.27% 1.12% 1.13%
最小値 1.22% 1.12% 1.12%
ACOからの
- 11.81% 11.02%
改善率
— 3 —
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
(a)
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
(b)
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
(c) 図3 3つのACOで得られたatt48の最も良い解 (a) 標準ACO (b) IDACO (d = 0.2)
(c) IDACO (d= 0.5)
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
(a)
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
(b)
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
(c) 図5 3つのACOで得られたkroA100の最も良い解(a)標準ACO (b) IDACO (d= 0.2)
(c) IDACO (d= 0.5)
4. ま と め
本研究では、敏感なアリと鈍いアリによるアントコロニー最 適化(IDACO)を提案した。IDACOを2つのTSPに適用す ることによって、IDACOの能力を調査した。シミュレーショ ン結果より、鈍いアリを含んでいるIDACOが敏感なアリのみ のACOより良い解を得られることを確認した。これは、鈍い アリが局所解に陥るのを防ぐ役割があるからだと考えられる。
さらに、鈍いありの割合が20%のIDACOが、全てのTSPに おいて標準ACOより良い解を得ることができた。これらの結 果から、IDACOは、ACOより実社会に近い考え方で最適化 行うことにより、より効果的な結果を得られるアルゴリズムで ある、と言うことが出来る。
文 献
[1] M. Dorigo and T. Stutzle,Ant Colony Optimization, Brad- ford Books, 2004.
[2] M. Dorigo and L. M. Gambardella, “Ant Colonies for the Traveling Salesman Problem,”BioSystems, vol. 43, pp. 73–
81, 1997.
[3] M. Dorigo, G. D. Caro and L. M. Gambardella, “Ant Al- gorithms for Discrete Optimization”,Artificial Lifevol. 5, no. 2, pp. 137-172, 1999.
[4] V. Maniezzo and A.Colorni, “The ant system applied to the quadratic assignment problem”,IEEE Transactions on Knowledge and Data Engineeringvol. 11, no. 5, pp. 769- 778, 1999.
[5] H. Hasegawa, “Optimization of GROUP Behavior,”Japan Ethological Society Newsletter, no. 43, pp. 22–23, 2004 (in Japanese).
— 4 —
