信学技報
TECHNICAL REPORT OF IEICE.

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

敏感なアリと鈍いアリによるアントコロニー最適化
下村将†

杉本雅樹†

原口卓†

松下春奈††

西尾芳文†† 徳島大学〒 770-8506 徳島県徳島市南常三島町 2-1†† 法政大学〒 184-8584 東京都小金井市梶野町 3-7-2
E-mail: †{s-sho,sugimoto,nishio}@ee.tokushima-u.ac.jp, ††haruna.matsushita.pd@k.hosei.ac.jp
あらまし

本研究では新しいアントコロニー最適化 (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†† , andYoshifumi 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, JAPANE-mail: †{s-sho,sugimoto,nishio}@ee.tokushima-u.ac.jp, ††haruna.matsushita.pd@k.hosei.ac.jp
Abstract This study proposes a new Ant Colony Optimization (ACO) method; ACO with Intelligent and DullAnts (IDACO). In IDACO algorithm, two kinds of ants coexist: intelligent ants and 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 theintelligent ants.
Key words Ant Colony Optimization, Traveling Salesman Problem, meta-heuristic

1. ま え が きわせを探す問題である。ACO のアルゴリズムでは、“アリ” と呼ばれる並列的に行動する複数の解が存在し、そのアリは都市アントコロニー最適化 (Ant Colony Optimization: ACO) [1]間をつないでいる経路にフェロモンを置く。そのフェロモンはは、生物学的なメカニズムから発想を得、アリのフェロモンのアリの振る舞いに依存して更新され、アリは経路に置かれてい効果を用いた最適化アルゴリズムであり、巡回セールスマン問るフェロモンの強さに従って巡回路を形成する。つまり、これ

題 (Traveling Salesman Problem: TSP) [2] や二次割り当て問らのアリが経路に置かれたフェロモンを通じてのみで他のアリ

題 (QAP) [4] 、グラフ色彩問題 [3] のような、複雑な組み合わとコミュニケーションを取ることから、アルゴリズムは最適解せ最適化問題を解くのに効果的である。中でも、TSP は様々を見つけることが出来る。しかしながら、ACO には局所解にな組み合わせ最適化問題の基礎として研究されており、メタ陥りやすいという問題点がある。従って、アルゴリズムの柔軟ヒューリスティクス解法のベンチマーク問題として取り上げら性を改善し、パフォーマンスを向上させることは重要であるとれることが多い。TSP とは、都市の座標が与えられ、全ての都言える。

市をちょうど一度ずつ訪問した後に最初の都市に戻ってくる巡

一方、現実のアリの世界には、“鈍いアリ” と呼ばれている回路の組み合わせのうち、できるだけ最短で戻ってくる組み合不必要なアリが約 20 パーセント存在するというレポートがあ—1—

る [5]。他のアリは巣から出て食物を探し回っているのに対し鈍いアリて、この鈍いアリは自分達の巣の周りでただじっとしているのである。また、正確にフェロモンをたどることが出来る敏感なCity i

アリと、フェロモンをたどることが出来ない鈍いアリを用いて、食料収集についてのコンピュータによるシミュレーション実験

pi 3, D (t )City 3pi 3, I (t )敏感なアリ
敏感なアリを行った。それによると、鈍いアリを含んでいるグループは敏

pi1, I (t )感なアリだけのグループより多くの食物を集めることが出来たという、大変興味深い結果を残している。これは、敏感なアリ

pi 2, D (t )pi1, D (t )pi 2, I (t )と鈍いアリの共生が、食物収集の有効性を改善したことを意味

City 2City 1している。
本研究では、敏感なアリと鈍いアリによるアントコロニー最適化 (ACO with Intelligent and Dull Ants: IDACO) という、新しい ACO アルゴリズムを提案する。IDACO の重要な特徴
は、“敏感なアリ” と “鈍いアリ” と呼ばれる 2 種類のアリが存在するということである。これら 2 種類のアリの内、敏感なア

図 1 敏感なアリと鈍いアリの選択確率。敏感なアリが次の都市を選択する確率は pij,I (t)。鈍いアリが次の都市を選択する確率はpij,D (t)。ただし、フェロモンの量 τij (t) と τil (t) は含んでいない。

リはフェロモンをたどることが出来るが、鈍いアリはフェロモンをたどることが出来ないという性質を持つ。これらの特徴は現実のアリコロニーの構造を反映していると言えることから、

pkij ,D (t) =IDACO は、従来の ACO よりも実社会に近い考え方からの最適[ηij ]βD,Σl∈Nk [ηil ]βD

if k ∈ Sdull(2)化を可能とする。シミュレーションでは、提案する IDACO を様々な TSP に応用し、標準 ACO と比較することで、IDACO

pkij ,I (t) =の有効性を確認する。

2. 敏感なアリと鈍いアリによるアントコロニー
最適化 (IDACO)
提案する IDACO アルゴリズムについて詳しく説明する。

IDACO アルゴリズムにおいて最も重要な特徴は、敏感なアリと鈍いアリと呼ばれる 2 種類のアリが存在することである。敏感なアリは標準 ACO のアリと同等に、正確にフェロモンをたどることが出来る。しかし、反対に、鈍いアリはフェロモンを[τ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) を含んでいないので、鈍いアリはフェロモンをたどることは出来ない。つまり、鈍いアリは次たどることが出来ないという性質を持つ。に訪れる都市を現在の場所からの距離によってのみ評価する。

TSP の N 個の都市集合 S は次式で表される。

一方、敏感なアリは次に訪れる都市を、置かれたフェロモン量S ≡ {P1 , P2 , · · · , PN }, Pi ≡ (xi , yi )(1)

都市の座標は 0 から 1 に正規化し、Pi は i 番目の都市の場所を表している (i = 1, 2, · · · , N )。初期状態では、それぞれのアリと現在の場所からの距離によって評価する。アリは全ての都市を訪問し終わるまで、次に訪れる都市を繰り返し選択する。

[Step3](フェロモンの更新): 全てのアリが巡回路を生成した(計 M 個) を都市上にランダムに配置する。(1 − d) × M 個の後、都市間に置かれているフェロモンの量を更新する。ここで、アリは敏感なアリの集合 SIntel に、d × M 個のアリは鈍いアリ

鈍いアリはフェロモンをたどることが出来ないが、フェロモンの集合 Sdull に分類する。ここで、d は全てのアリにおける鈍いアリの割合である。

を置くことは出来るという点に注意すべきである。k 番目のアリが経路 (i, j) に置くフェロモンの量 ∆τkij (t) は、次式で決定される。

[Step1](初期化): 繰り返し回数を t = 0 とする。τij (t) は 繰り
返し回数 t 回目のときの都市 i と都市 j 間の経路 (i, j) に置かれるフェロモンの量を表す。τij (0) = τ0 に初期化する。

(∆τkij (t) =1/Lk ,if (i, j) ∈ Tk (t)0,otherwise(4)[Step2](巡回路の生成): 図 1 に示されるように、敏感なアリがここで、Tk (t) は k 番目のアリによって得られた巡回路、Lk (t)次に訪れる都市は、確率 pij,I (t) によって、鈍いアリが次に訪はその巡回路の長さである。それぞれの経路 (i, j) のフェロモれる都市は、確率 pij,D (t) によって選択される。k 番目のアリン τij (t) を ∆τkij (t) に従って更新する。

が都市 i から都市 j に移動する確率は次式によって決定される。

τij (t + 1) = (1 − ρ)τij (t) +MX∆τkij (t)(5)k=1—2—ここで、ρ ∈ [0, 1] はフェロモンの蒸発率である。

を得ることができた。しかしながら、d = 0.5 の IDACO は標[Step4] t = t + 1 とする。t = tmax に達していなければ、

準 ACO より悪かったことに注目する。この結果から、鈍いア[Step2] に戻る。

リが多すぎると得られる結果は悪くなることがわかる。
表 1 標準 ACO と IDACO を att48 に適用した結果

3. シミュレーション結果

ACO

IDACO

d=0d = 0.2 d = 0.5

2.87%

2.62%

3.84%

最小値 2.43%

1.46%

2.09%

8.7%

−33.8%IDACO の探索能力の評価とその振る舞いを調査するために、様々な鈍いアリの割合を用いた IDACO を 2 つの TSP に適用

平均誤差率

し、標準 ACO を比較した。
シミュレーションでは、標準 ACO と IDACO のアリの数 M

ACO からのは都市数と同数に設定する。標準 ACO は敏感なアリのみで構改善率-成されており、式 (3) によって選択確率が決定される。IDACOは d × M 個の鈍いアリと、(1 − d) × M 個の敏感なアリで構

3. 2 Simulation 2: kroA100成される。鈍いアリの割合 d は、それぞれのシミュレーション

1で 0.2 と 0.5 に設定する。全ての問題で 10 回繰り返してシミュ0.90.8レーションを行い、その平均をとる。標準 ACO と IDACO の0.7

パラメータは以下のように設定する。

0.60.5

τ0 = 10, ρ = 0.3, α = 1, βI = βD = 5, tmax = 2000

0.40.3

ここで、フェロモンの蒸発率 ρ、フェロモンの依存度 α、距離0.20.1の依存度 βI と βD そして、繰り返し回数 t = tmax の値は変化00させない。

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

0.20.3

0.4

0.5

0.6

0.70.80.91

図 4 ベンチマーク問題 kroA100 とその最適解得られた解と最適解を比較するために次のような誤差率を用いる。

0.1

次に、kroA100 (都市数 N = 100) と呼ばれている TSP と、(6)その最適解を図 4 に示す。標準 ACO と IDACO のシミュレーション結果を表 2 に示す。図 5 は、10 回のシミュレーションのこの式は、ACO が得た巡回路の長さが最適解よりどれぐらいうちの、標準 ACO と IDACO で得られた最も良い解を示して長いかを示していることから、誤差率は 0 に近い方が望ましいる。

い。さらに、IDACO の解が ACO よりどれぐらい改善されたかを評価するために次式の改善率を用いる。

表 2 より、IDACO は標準 ACO より良い解を得ることができていることがわかる。さらに、att48 と同様に、kroA100 の)−(IDACO の誤差率)
改善率 [%] = (ACO の誤差率
× 100
(ACO の誤差率)(7)

結果においても、d = 0.2 の IDACO は d = 0.5 の IDACO より良い解が得られている。これは、鈍いアリの割合が現実の世界とほぼ同じ場合、IDACO が効果的な結果を得ることを確認

3. 1 Simulation 1: att48

できたことを意味する。特に、多くの都市で構成されている
1TSP の場合、IDACO は標準 ACO の結果を大きく改善すると0.9いえる。

0.80.70.6

表 2 標準 ACO と IDACO を kroA100 に適用した結果

0.5

ACOIDACO

d=0d = 0.2 d = 0.5

1.27%

1.12%

1.13%

最小値 1.22%

1.12%

1.12%

0.4
0.3
0.2

誤差率

0.1
000.2

0.4

0.60.81

図 2 ベンチマーク問題 att48 とその最適解

平均ACO からの改善率-11.81% 11.02%

att48 (都市数 N = 48) と呼ばれている TSP と、その最適解を図 2 に示す。この問題に対して行った、標準 ACO と IDACOのシミュレーション結果を、表 1 に示す。図 3 は、10 回のシミュレーションのうち、標準 ACO と IDACO で得られた最も良い解を示している。
表 1 において、d = 0.2 の IDACO は標準 ACO より良い解—3—

11

1

0.9

0.9

0.9

0.8

0.8

0.8

0.7

0.7

0.7

0.6

0.6

0.6

0.5

0.5

0.5

0.4

0.4

0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

0.1

000
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.1

0.2

0.3

0.4

(a)

0.5

0.6

0.7

0.8

0.9

1000.1

0.2

0.3

0.4(b)

0.5

0.6

0.7

0.8

0.9

1

0.7

0.8

0.9

1(c)

図 3 3 つの ACO で得られた att48 の最も良い解 (a) 標準 ACO (b) IDACO (d = 0.2)(c) IDACO (d = 0.5)

11

1

0.9

0.9

0.9

0.8

0.8

0.8

0.7

0.7

0.7

0.6

0.6

0.6

0.5

0.5

0.5

0.4

0.4

0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

00

0.1
0.1

0.2

0.3

0.4

(a)

0.5

(b)0.60.70.80.91000.10.20.30.40.50.6(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, Bradford Books, 2004.
[2] M. Dorigo and L. M. Gambardella, “Ant Colonies for theTraveling Salesman Problem,” BioSystems, vol. 43, pp. 73–81, 1997.
[3] M. Dorigo, G. D. Caro and L. M. Gambardella, “Ant Algorithms for Discrete Optimization”, Artificial Life vol. 5,
no. 2, pp. 137-172, 1999.
[4] V. Maniezzo and A.Colorni, “The ant system applied tothe quadratic assignment problem”, IEEE Transactions onKnowledge and Data Engineering vol. 11, no. 5, pp. 769778, 1999.
[5] H. Hasegawa, “Optimization of GROUP Behavior,” Japan
Ethological Society Newsletter, no. 43, pp. 22–23, 2004 (inJapanese).

—4—