進化計算アルゴリズムの改良研究〜アリコロニー最適化を例に〜
情報工学 EP 模擬講義

横浜国立大学 田邊遼司 (准教授)最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

最適化問題と巡回セールスパーソン問題• 最適化問題: ある目的関数を最適化• 入力: 解空間, 解の良し悪しを評価する目的関数• 出力: 目的関数を最小化 / 最大化する最適解• 巡回セールスパーソン問題: 有名な問題の一つ• 販売員が n 個の都市をちょうど 1 度づつ訪問し開始地点に帰る際, どの順番で訪問すれば最短距離になるか?

2 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

進化計算: 人工知能の一分野• 人工知能 = { 機械学習, 自然言語処理, ...., 進化計算 }• 人工知能 ̸= Deep Learning• 一部の確率的反復最適化アルゴリズムの総称• 昔: 生物進化・生物の振る舞いから着想を得た最適化
アルゴリズムの総称• いつも必ず最適解を求められる保証はない• 代表的な進化計算アルゴリズム• 遺伝的アルゴリズム• 遺伝的プログラミング• 進化戦略• アリコロニー最適化
3 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良まとめ

本講義: 進化計算アルゴリズムの改良研究を紹介
アリコロニー最適化アルゴリズムを例に, アルゴリズムをどのように改良できるか紹介• 進化計算の実応用では「低計算コストで良い解が獲得できる」ことが求められる• 良い解が獲得できても, 数年かかるなら嬉しくない• 計算が短時間でも, 悪い解なら嬉しくない• アルゴリズムの改良: 進化計算の研究の一つ• アルゴリズム: ある問題を解くための手順

4 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

アリの行列

5 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

非常に大まかなアリの特性 (注意: アリに関しては素人)
1

視力が悪い• 最短経路を目視で選んでいるわけではない

2

互いに高度なコミュニケーションは取れない• 互いに最短経路を直接伝達しあっているわけでない

3揮発性のフェロモンを排出しながら行動• 通った道にフェロモンが撒かれる

4

フェロモンは一定時間で蒸発する• 恒久的に留まり続けるわけではない

5

経路選択の際, フェロモンに誘引される• よりフェロモンが多い経路を選択しやすい (非決定的)
6 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

障害物を置いた際の, アリの経路探索行動 [Dorigo 96]

Marco Dorigo, Vittorio Maniezzo, Alberto Colorni:
Syst. Man Cybern. Part B 26(1): 29-41 (1996)

Ant system: optimization by a colony of cooperating agents. IEEE Trans.

7 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

障害物を置いた際の, アリの経路探索行動 [Dorigo 96]
1

始めは, 左右の経路を等確率で選択2

右の経路の方が短いので, アリが通る間隔が短い

3フェロモンが蒸発される前に, 次々に上乗せ

8 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

障害物を置いた際の, アリの経路探索行動 [Dorigo 96]
4左の経路は長いので, アリが通る間隔が長い

5

フェロモンが蒸発しやすくなる

9 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

障害物を置いた際の, アリの経路探索行動 [Dorigo 96]
6

結果, 右の経路の方がフェロモン濃度が高くなる

7

フェロモンに誘引され, アリは右の経路を選ぶ

8

最終的に左の経路上のフェロモンは消える

10 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

アリコロニー最適化 (ant colony optimization, ACO)

• アリの経路発見現象に着想を得た手法群 [Dorigo 04]• アリ: 採餌行動にて, 短い経路で餌を運んでいる• この経路発見メカニズムを使って, 巡回セールスパー
ソン問題の良い解を求められないか?

• オリジナル: アリの行動を比較的忠実に模倣
123µ 個のアリを用いて µ 個の巡回路を生成µ 個の巡回路を元にフェロモン更新
上記 2 ステップを終了条件を満たすまで繰り返す• 注意• 本物のアリは不使用 (あくまでシミュレーション)• 性能は良くない (例えば「Concorde TSP」で検索)
Marco Dorigo, Thomas Stützle: Ant colony optimization. MIT Press 2004

11 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良まとめ

各アリによる巡回路の生成方法
開始都市を n 都市からランダムに 1 つ選択
2 フェロモンに基づき未訪問都市を 1 つ選択
3 2 を繰り返し全 n 都市を訪問後, 開始都市に戻る
112 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめµ 個の巡回路を元にフェロモン更新 (蒸発 → 追加)• フェロモンが増える経路• 多くのアリがその経路を選んでいる• その経路は短い巡回路に含まれている• フェロモンが減る経路• 少ないアリしかその経路を選んでいない• その経路は長い巡回路に含まれている
13 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

burma14 における性能評価実験

ビルマ (現ミャンマー) の 14 都市問題
最適巡回路, 長さ = 3323
x2x2

14 都市の配置x1x1• アリコロニー最適化アルゴリズムの設定• アリの数 µ = 100, 蒸発率 ρ = 0.5• 探索打ち切り条件: 実行時間が 2 秒経過したら• ACOTSP の C コードを使用• http://www.aco-metaheuristic.org/aco-code/
14 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

burma14 にてオリジナルが探索中に求めた最良巡回路最適巡回路 (長さ 3323) を求めることに失敗

x1x1

2997 反復目, 長さ = 3426

13022 反復目, 長さ = 3346

x2x231 反復目, 長さ = 3740x2x21 反復目, 長さ = 4067

x1x1
15 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

Q. なぜオリジナル版の探索は失敗したのか?
A. 経験則を不使用だったため• 経験則: 「この問題はこうするとうまくいく」• 巡回セールスパーソン問題の経験則:• 最適巡回路は近い都市同士上の経路を含みやすい

改良: 選択確率 = フェロモン量+ 1/ 現都市からの距離16 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

burma14 にて改良版が探索中に求めた最良巡回路最適巡回路 (長さ 3323) を求めることに成功
5 反復目, 長さ = 3371

x2x2

1 反復目, 長さ = 3496

x2x135 反復目, 長さ = 3323

x2x112 反復目, 長さ = 3336

x1x117 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

都市数をスケールアップした実験
eil51: 51 都市から成る TSP

最適巡回路, 長さ = 426x2x2

51 都市の配置

x1x118 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

eil51 にて改良版が探索中に求めた最良巡回路最適巡回路 (長さ 426) を求めることに失敗
80 反復目, 長さ = 443

x2x2

1 反復目, 長さ = 566

156 反復目, 長さ = 438

1946 反復目, 長さ = 431

x2x1x2x1x1x1

19 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

Q. なぜ改良版の探索は失敗したのか?
A. 探索終盤では追加するフェロモン量に差がないから各アリが追加するフェロモン量 = 1/ 巡回路長
• 探索序盤: 各アリが生成する巡回路はバラつく• そのため, 1/ 巡回路長もバラつく• 序盤の例: 1/470 ≈ 0.00212 vs. 1/520 ≈ 0.00192• 探索終盤: 各アリが生成する巡回路はほぼ同じ• そのため, 1/ 巡回路長もほぼ同じ• 終盤の例: 1/430 ≈ 0.00233 vs. 1/431 ≈ 0.00232• 改良: 最良巡回路を生成したアリにボーナス
最良なアリがさらに追加するフェロモン量= 100/ 巡回路長
20 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

eil51 にて改改良版が探索中に求めた最良巡回路
431 よりは良いが, 最適な 426 には未到達
20 反復目, 長さ = 437x2x2

1 反復目, 長さ = 656

25 反復目, 長さ = 4311067 反復目, 長さ = 428

x2x1x2x1x1x1

21 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

Q. なぜ改改良版の探索は失敗したのか?
A. フェロモンが最良巡回路の経路に偏り過ぎたため• 最良巡回路と同じ巡回路をアリは繰り返し生成• アリは袋小路に陥っている
22 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ改改改良: フェロモンの値に上限下限を導入• フェロモンの極端な偏りを解消• どの経路も一定の確率で選ばれる

23 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良

まとめ

eil51 にて改改改良版が探索中に求めた最良巡回路最適巡回路 (長さ 426) に到達
753 反復目, 長さ = 437x2x21 反復目, 長さ = 656

x2x12564 反復目, 長さ = 426x2x12446 反復目, 長さ = 428x1x124 / 25

最適化問題進化計算

アリの採餌行動

アリコロニー最適化

アルゴリズムの改良まとめ

まとめ: 進化計算アルゴリズムの改良研究を
アリコロニー最適化を例に紹介した
進化計算アルゴリズムの改良の手順
1 欠点を実験的 / 理論的に明らかにする
2

その欠点を補う要素を組み込む

重要: 元のアイディアに囚われないこと• フェロモン量に上限下限を設けるアリはいない• 模倣はあくまで手段であって, 目的ではない

25 / 25