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

信学技報
TECHNICAL REPORT OF IEICE.

遺伝情報を用いるアントコロニー最適化の
巡回セールスマン問題への適用
下村将†

松下春奈††

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

本研究では、新しいアントコロニー最適化 (Ant Colony Optimization: ACO) として、遺伝情報を用いるアントコロニー最適化 (ACO using Genetic Information: GIACO) を提案する。GIACO アルゴリズムは ACO と遺伝的アルゴリズム (Genetic Algorithm: GA) のハイブリッドであり、ACO のフェロモンと GA の遺伝情報を用いて解を探索する。加えて、突然変異により、フェロモンを感じとることが出来ないアリが発生する。GIACO を巡回セールスマン問題に適用し、標準的な ACO と GA より効果的な結果を得ることを確認する。
キーワード

アントコロニー最適化、遺伝的アルゴリズム、巡回セールスマン問題、メタヒューリスティック

Ant Colony Optimization using Genetic Information for TSP
Sho SHIMOMURA† , Haruna MATSUSHITA†† , and Yoshifumi NISHIO†† Department of Electrical and Electronic Engineering Tokushima University, 2-1 Minami-Josanjima,
Tokushima 770-8506, JAPAN†† Department of Reliability-based Information Systems Engineering, Kagawa University, 2217-20
Hayashi-cho, Takamatsu, Kagawa 761-0396, JAPANE-mail: †{s-sho,nishio}@ee.tokushima-u.ac.jp, ††haruna@eng.kagawa-u.ac.jp
Abstract This study proposes an Ant Colony Optimization using Genetic Information (GIACO). GIACO algorithm combines Ant Colony Optimization (ACO) with Genetic Algorithm (GA). GIACO searches solutions using
the pheromone of ACO and the genetic information of GA. In addition, the ant which cannot trail the pheromone
is caused by the mutation. We apply GIACO to Traveling Salesman Problems (TSPs) and conﬁrm that GIACO
obtains more eﬀective results than the conventional ACO and the conventional GA.
Key words Ant Colony Optimization, Genetic Algorithm, Traveling Salesman Problem, meta-heuristic

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

アリは経路に置かれているフェロモンの強さに従って巡回路を題 (Traveling Salesman Problem: TSP) [2] や二次割り当て問形成する。フェロモンの強さによって他のアリとコミュニケー

題 (QAP) [3] 、グラフ色彩問題 [4] のような、複雑な組み合わションを取ることから、ACO アルゴリズムは最適解を見つけせ最適化問題を解くのに効果的である。中でも、TSP はオペることが出来る。しかしながら、ACO には局所解に陥りやす

レーションズ · リサーチと理論的なコンピュータサイエンスといという問題点がある。従って、アルゴリズムの柔軟性を改善して研究されている組み合わせ最適化問題である。TSP では、し、パフォーマンスを向上させることが重要である。

都市の座標が与えられ、全ての都市を一度だけ訪問し、出来る

遺伝的アルゴリズム (Genetic Algorithm: GA) [5] は生物進—1—

Startフェロモンの初期化 τ 0

t=1
Not < t max
Yes

最も良い解の出力ランダムにM アリを都市に配置。 k = 1
Endk ∈ S Mutate

No

Yes
選択確率 pij , D

選択確率 pij , I

k=k+1

都市 j を訪問

t=t+1

No
アリ ｋ が全ての都市を訪問

Yes
No
全てのアリが全ての都市を訪問

Yes
フェロモンの更新
アリの評価
選択交叉突然変異
遺伝情報の更新

図 1 GIACO のフローチャート化論の過程を模倣した学習アルゴリズムであり、解空間が不明報を受け継ぐことの両方が出来る。対照的に、突然変異アリはな問題を解くのに効果的である。GA では、解は遺伝子コードフェロモンを追跡することが出来ない上、遺伝情報も受け継ぐとして表現され、一つの個体が一つの遺伝子コードを持っていことが出来ない。IDACO の鈍いアリは突然変異であると考える。GA は複数の個体の集合から構成されており、交叉、突然たので、GIACO のアルゴリズムの突然変異によって、突然変変異、選定戦略を行うことで解を探索する。さまざまな研究者異アリが生じるとした。

が GA を改善するために多くの技術を開発し、染色体の表現や遺伝子操作の異なる方法が提案されている。また、効果的な解を見つけるために、GA は局所探索アルゴリズムと組み合わされることがある [6]。

2. 遺伝情報を用いるアントコロニー最適化 (GIACO)
提案する GIACO のアルゴリズムの詳細を説明する。GI-

一方、私たちの過去の研究 [7] では、敏感なアリと鈍いアリ

ACO のアルゴリズムのフローチャートを図 1 に示す。GIACOが共存するアントコロニー最適化 (Ant Colony Optimization

は IDACO と GA を組み合わせたアルゴリズムである。GIACO

with Intelligent and Dull Ants: IDACO) を提案した。IDACOのアリは、交叉や突然変異によって次世代に遺伝情報を伝えは標準のアリだけでなく、“鈍いアリ”と呼ばれているフェロモる。さらに、GIACO の重要な特徴としては、“敏感なアリ”とンを感じ取ることが出来ないアリを含めて構成されている。私“突然変異アリ”の二種類のアリが共存することである。敏感たちは、敏感なアリのみで構成されている従来の ACO より、なアリはフェロモンを追跡することが出来、また遺伝情報も受鈍いアリを含んでいる IDACO のほうが効果的であるという、け継ぐことが出来る。対照的に、突然変異アリはフェロモンを興味深い結果を得た。

追跡することが出来ず、更に遺伝情報も受け継ぐことが出来な

そこで本研究では、遺伝情報を用いるアントコロニー最適化

い。IDACO の鈍いアリはまさに突然変異であると考えたので、(Ant Colony Optimization using Genetic Information: GI-GIACO のアルゴリズムでは、突然変異によって突然変異アリACO) を提案する。GIACO は IDACO と GA の両方の特徴をが生じるとする。

持ち合わせている。GIACO のアリは、交叉と突然変異によって次世代に遺伝情報を伝える。従って、GIACO はフェロモンと遺伝情報の両方を用いて解を探索する。さらに、GIACO の重要な特徴は、IDACO のように二種類のアリが共存すること

都市数を N としたとき、TSP の都市集合 S は次式で表される。

S ≡ {P1 , P2 , · · · , PN }, Pi ≡ (xi , yi )(1)である。一つは “敏感なアリ”、もう一つは “突然変異アリ”で都市の座標は 0 から 1 に正規化され、Pi は i 番目の都市の場所ある。敏感なアリはフェロモンを追跡すること、及び、遺伝情を表している (i = 1, 2, · · · , N )。初期状態では、それぞれのア—2—

都市 2

都市 1

都市 3

pi 2, D (t )pi 2, I (t )巡回路
2→1→5→3→4

pi 3, I (t )2 1 5 3 4

図 3 置き換えの例。それぞれのアリによって得られた順回路は染色体

pi 3, D (t )pi1, D (t )pi1, I (t )置き換え 染色体として置き換えられる。

f4 : 8

都市 i
敏感なアリ個体の個体の選択確率

f 3 : 12pGA, 1pGA, 2pGA, 3pGA, 4

突然変異アリf 2 : 20

図 2 敏感なアリと突然変異アリの確率 pij (t)。敏感なアリが次に訪

f1 : 60

60/10020/10012/1008/100

れる都市は確率 pij,I (t) によって選ばれる。突然変異アリが次に訪れる都市は確率 pij,D (t) によって選ばれる。ここで、 確率pij,D (t) はフェロモンと遺伝情報を含まない。

図 4 ルーレット選択の例。pGA,k によって次世代に受け継ぐ個体を選択する。例えば、1 番目の個体の適応度 f1 を 60、2 番目の個体

リ (計 M 個) を都市にランダムに配置する。(1 − Pm ) × M 個の適応度 f2 を 20、3 番目の個体の適応度 f3 を 12、そして、4のアリは敏感なアリの集合 SIntel に、Pm × M 個のアリは突然番目の個体の適応度 f4 を 8 とする。これは、ルーレットを回したとき、高い適応度を持っている個体が選ばれ易くなっている。

変異アリの集合 SMutate にそれぞれ分類される。

[GIACO1](初期化): 繰り返し回数を t = 0 に設定する。τij (t)は繰り返し回数 t での都市 i と都市 j 間の経路 (i, j) に置かれるフェロモンの量であり、初期値を τ0 に設定する。同じく、遺ここで Tk (t) は k 番目のアリによって得られた巡回路であり、Lk (t) はその巡回路の長さである。それぞれの経路 (i, j) のフェロモン τij (t) に ∆τkij (t) を付加する。

伝情報 gij (t) は初期値 g0 に設定する。

[GIACO2](巡回路探索): それぞれのアリが訪れる都市は、図2 のように、確率 pij,I (t) と pij,D (t) によって選ばれる。k 番目

τij (t + 1) = (1 − ρ)τij (t) +M∑∆τkij (t),(5)k=1のアリが都市 i から都市 j に移動する確率は次式によって決定
ここで ρ ∈ [0, 1] はフェロモンの蒸発率であり、毎回フェロモされる。

pkij ,D (t) =[ηij ]βD,Σl∈Nk [ηil ]βDif k ∈ SMutate ,ンは蒸発していく。

(2)[GIACO4](評価): アリによって得られた解は遺伝子コードとして置き換えられ、図 3 のように表される。k 番目のアリの評

αpkij ,I (t) =βIγ[τij (t)] [ηij ] [gij (t)],Σl∈Nk [τil (t)]α [ηil ]βI [gij (t)]γotherwise. (3)価値 ek は次式で決定される。

ek =調整できるパラメータ α は敏感なアリのフェロモンの重みを制N,
Lk(6)御し、βI と βD は敏感なアリと突然変異アリの都市間の距離情

ここで ek は得られた解の質を表している。

報の重みをコントロールする。式 (2) において、経路に置かれ[GIACO5](選択): GIACO アルゴリズムでは良い解を得るたているフェロモンの量 τij (t) と τil (t)、遺伝情報 gij (t) と gil (t)めに、高評価のアリを次世代に残す必要がある。そこで、スが含まれていないため、突然変異アリはフェロモンを追跡するケーリングを実行し、評価値から適応度 fk を導く。スケーリことが出来ず、遺伝情報も受け継ぐことが出来ない。突然変異ングは次式で決定される。

アリは、次に訪れる都市を、現在の場所からの距離によってのみ評価する。対照的に、敏感なアリは次に訪れる都市を現在の

fk =[χ(ek − eave ) + (emax − ek )]eave,
emax − eave

(7)

場所からのフェロモンの強さ、距離、遺伝情報から評価する。

ここで χ はスケーリングパラメータ、 eave は全てのアリの評[GIACO3](フェロモン更新): すべてのアリが巡回路を生成し価値の平均、emax は全てのアリの中で最も高い評価値を表す。

た後、都市間に置かれている全フェロモンを更新する。ここで、

図 4 のように、次世代に受け継ぐアリは確率 pGA によって選突然変異アリはフェロモンを追跡することが出来ないが、フェばれる。この選択方法はルーレット選択と呼ばれている。k 番ロモンを置くことが出来るという点に注意しなければならな目のアリが選択される確率は次式で決定される。

い。巡回路長 Lk (t) を計算し、 k 番目のアリが経路 (i, j) 上に置くフェロモンの量 ∆τkij (t) は次式によって決定される。

{∆τkij (t) =10/Lk ,if (i, j) ∈ Tk (t)0,otherwise,(4)

fk
pGA,k = ∑M
k=1

.

(8)

fk

ここで、突然変異アリは遺伝情報を次世代に残すことが出来るが、[GIACO2] において次の都市選択では遺伝情報を受け継ぐ—3—

子1

親1

3. シミュレーション結果
GIACO の探索能力の評価とその振る舞いを調査するため交叉親2に、GIACO を 3 つの TSP に適用した。加えて、突然変異ア子2リの効果を確認するために、GA-ACO を考える。GA-ACO はGIACO と同じアルゴリズムであり、突然変異の操作は行うが、それによって突然変異アリが発生しないアルゴリズムである。
つまり、GA-ACO は敏感なアリのみで構成されている GIACO
図 5 Partially-mapped crossover operator (PMX).

Beforeである。GIACO の有効性を確認するために GA-ACO、標準的な ACO、GA と比較する。

After

このシミュレーションでは、標準的な ACO, GIACO GA-ACO におけるアリの数 M は、都市の数と同じに設定する突然変異
図6 逆(M = N )。標準的な GA における個体数 U は、U = 1024 に固定する。標準的な ACO に含まれているアリの都市選択確率位は、次式によって決定される。とが出来ないことに注意すべきである。

pkij (t) =[GIACO6](交叉): 個体群から 2 つの親が選ばれ、その親から[τij (t)]α [ηij ]β.
Σl∈Nk [τil (t)]α [ηil ]β(11)2 つの子が生成される。この操作は子の数が個体群と同じ数にGIACO は Pm × M 個の突然変異アリと (1 − Pm ) × M 個の敏なるまで繰り返される。しかし、交叉に参加する親の数は交叉感なアリによって構成される。すべての問題で 10 回のシミュ率 Pc によって決定される。また、交叉には様々な方法があり、レーションを繰り返し、平均を求める。パラメータは以下のよ

本研究では、Partially-mapped crossover operator (PMX) [8]うに設定する。と呼ばれる交叉方法を用いる。PMX は図 5 のような 2 点交叉τ0 = 10, g0 = 1, ρ = 0.3, α = 1, β = βI = βD = 5,である。まず、巡回路を置き換えた遺伝子コードからランダムに 2 つの切断箇所を選択する。2 つの切断箇所に挟まれた順列

γ = 5, χ = 100, Pc = 0.8, Pm = 0.05, tmax = 2000,

を他の親の遺伝子と交換する。

[GIACO7](突然変異): 交叉の後、突然変異が発生する。突然変異の確率は突然変異率 Pm によって決定される。本研究では、
図 6 のような、逆位と呼ばれる突然変異法を用いる。この突然変異法は、巡回路を置き換えた遺伝子コードからランダムに 2つの切断箇所を選択する。2 つの切断箇所の間の順列を逆転する。

[GIACO8](遺伝情報の更新): 遺伝操作が終わった後、得られここで、フェロモン蒸発率 ρ、フェロモンの重み α、都市間の距離の重み β, βI と βD 、遺伝情報の重み γ 、スケーリングパラ
メータ χ、交叉率 Pc 、突然変異率 Pm 、繰り返し回数 t = tmaxの値は固定値である。
得られた解と最適解を比較するために、次のような誤差率を用いる。
誤差率 [%] =(得られた解) − (最適解)× 100.
(最適解)(12)た巡回路長 Gk (t) を計算する。k 番目のアリが次世代に残す遺この式は、ACO などが得た巡回路の長さが、最適解よりどれぐ

伝情報 ∆gkij (t) は次式によって決定される。

{∆gkij (t) =10/Gk ,if (i, j) ∈ Tk (t)0,otherwise,

らい長いかを示している、すなわち、誤差率は 0 に近い方が望(9)ここで、Tk (t) は k 番目のアリによって得られた巡回路、Gk (t)はその長さである。それぞれの都市 (i, j) 間における遺伝情報

gij (t) は一度初期化を行い、その後 ∆gkij (t) を付加することによって決定される。

gij (t + 1) = g0 +gr120(都市数 N = 120) と呼ばれている TSP を用いる。また、その最適解を図 7 に示す。
標準的な ACO、GA、GA-ACO、そして、GIACO のシミュ
レーション結果を表 1 に示す。
表 1 標準的な ACO、GA、GA-ACO と GIACO の誤差率

M∑

∆gkij (t),

(10)

k=1

ここで、遺伝情報は毎回 g0 に初期化される。

[GIACO9] t = t + 1 とする。t = tmax に達していなければ[GIACO2] に戻る。

ましい。eil51 (都市数 N = 51)、kroC100 (都市数 N = 100)、

eil51

kroC100

gr120

ACO

7.43%

10.21%

7.16%

GA

7.52%

13.92%

12.41%

GA-ACO

6.32%

9.86%

7%

GIACO

5.15%

9.48%

6.91%

30.7%

7.15%

3.49%

ACO からの改善率

—4—

1

11

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

0.6

0.7

0.8

0.9

1

0
0

0.1

0.2

0.3

(b)

図7

0.4

0.5

0.6

0.7

0.8

0.9

1(c)

ベンチマーク問題 (a) eil51、 (b) kroC100, (c) gr120 とその最適解

ACO と GA を組み合わせた GA-ACO は標準的な ACO とGA より効果的な解を得たことを確認できる。この結果は、ACO と GA を組み合わせた手法は ACO 単体や GA 単体で使うより効果的であることを意味している。更に、突然変異アリと敏感なアリで構成されている GIACO と敏感なアリだけで構成されている GA-ACO を比較すると、GIACO は GA-ACOより効果的な解を得たことを確認した。これは、突然変異アリand Y. Nishio ”Ant Colony Optimization with Intelligentand Dull Ants” Proceedings of International Symposium on
Nonlinear Theory and its Applications (NOLTA’10), pp.
504-507, Sep. 2010[8] P. Larra naga, C. M. H. Kuijpers, R. H. Murga, I. Inza,and S. Dizdarevic, “Genetic Algorithms for the Traveling
Salesman Problem: A Review of Representations and Operators,” Artificial Intelligence ‘Review, vol. 13, pp 129-170,
1999.

が敏感なアリと異なる行動をすることで、局所解から抜け出す役割を果たしていると考えられる。

4. ま と め
本研究では、遺伝情報を用いるアントコロニー最適化 (GI-ACO) を提案した。GIACO はフェロモンだけでなく、GA の遺伝操作を用いて TSP の巡回路を最適化する。GIACO には敏感なアリと突然変異アリが存在し、突然変異アリは突然変異によって発生する。3 つの TSP に GIACO を適用し、その性能を調査した。突然変異アリと敏感なアリで構成されているGIACO は、敏感なアリだけで構成されている GA-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] V. Maniezzo and A.Colorni, “The ant system applied tothe quadratic assignment problem,” IEEE Transactions on
Knowledge and Data Engineering vol. 11 no. 5, pp. 769-778,
1999.
[4] M. Dorigo, G. D. Caro and L. M. Gambardella, “Ant Algorithms for Discrete Optimization,” Artificial Life vol. 5
no. 2, pp. 137-172, 1999.
[5] L. Homaifar, C. Guan, and G. Liepins, “A New Approachto the Traveling Salesman Problem by Genetic Algorithms,”
Proc. 5th Int. Conf. On Genetic Algorithms, Morgan Kaufmann, pp.460-466, 1993.
[6] B. Freisleben and P. Merz, “A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling
Salesman Problems,” Proceedings of the 1996 IEEE International Conference on Evolution Computation , pp. 616621, 1996.
[7] S. Shimomura, M. Sugimoto, T. Haraguchi, H. Matsushita—5—