The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 1 -
動的環境
適応 向
蟻
ー最適化手法
相対評価 実装
Implementation of relative evaluation to the ant colony optimization method toward adaptation to dynamic environments
直人
*1高橋
二
*2Naoto Noguchi Tatsuji Takahashi
*1
東京電機大学大学院
*2東京電機大学
Graduate School of Tokyo Denki University Tokyo Denki University
For combinatorial optimization like Traveling salesman problem (TSP), many efficient methods have been invented. However, in a real environment, the map can change through time. A supply route for chain stores calculated as optimal can be made useless if a path is blocked up. Traffic situation that determines the weight (efficiency or distance) of paths constantly varies. We propose an algorithm which is a variant of the ant colony optimization (ACO). It implements relative evaluation of the value of paths which is known to be effective in decision-making under uncertainty.
1.
はじめに
蟻 ー 最 適 化 (Ant Colony Optimization:以 ACO)
[M.Dorigo 96] いう蟻 給餌行動 基 作 最適化手法
あ . 手法 組 合わ 最適化問題, 特 巡回 ー
ン問題(Traveling Salesman Problem: TSP) [山本 97] い
非常 優秀 成績 示 知 い [原 12]. 組 合わ
最適化問題 条件 制約さ い , 序や割当
う 条件 満 解 組 合わ 問題 あ . 問題
多岐 わ 分 研究さ い , 問題 規模 大
解 組 合 わ 数 膨 大 組 合 的 爆 発
(combinatorial explosion) 発生 . 計算 増大
や , 現実的 時間 最適解求 困 .
ACO ュー テ 手法 用い , 最適解
求 諦 代わ , 現実的 時間 最適解 比較
的近い準最適解 求 .
組 合わ 最適化問題 例 TSP や ップ ッ 問題
あ [ 川 12]. 問題 環境 変化 い
定常環境 問題 あ . 他方，現実世界 ，最適化
計算時間 無視 い ば，最適化 途中 環境 動
的 変化 問題 扱う必要性 出 . ACO 探索
的 行う , 焼 法や遺伝的 [久保 09]
, 他 ュー テ 手法 比 非定常問題 対
有効 あ . 手法 , あ 程度探索 進 解 収束
起 , 解 再探索 行わ . 解 収束
起 環境 変化 起 最適解 得 時間
う.
本研究 動的 意思決定課題 い 有用 あ さ
相対評価法 ACO 付加 ,既存手法 い 困
動的 環境 変化 巡回 ー ン問題 い 有効
手法 提案
2.
巡回セーラスボン問題
巡回 ー ン問題(TSP) 代表的 組合 最適化問
題 一 あ . TSP 始 n 個 都 市 合V =
, , ⋯ , n , 都市i 都市j 間 C 与え .
任意 都市 巡回 始 , 全都市 訪問 後 最初 都
市 戻 . 巡回路 総 最 短い経路 求 . ,
TSP C = C 対称TSP , C ≠ C 非対称
TSP あ , 本論文 対称TSP い 考え . TSP 最
適解 求 う , 都市数 小さい場合 容 求
. , 都市数 大 組合 的爆発
起 経路数 飛躍的 増大 , 現実的 時間
解 う. う 性質 TSP NP
Non-deterministic Polynomial 完全問題 分類さ , 都市数n 関
, 多 式時間 解法 存在 い さ い . 実際
的 計算時間 , 較的良い精度 準最適解 与え う 手
法 必要 , 多 手法 提案さ .
3. Ant Colony Optimization
ACO ,蟻 巣 餌場 経路 形成 給餌行動
基 作 最適化手法 総称 あ . 手法 , ン
ュー テ ッ 情報 基 確率的 解 生成 , 生成
解 ン 更新 いう 繰 返 行う.
組 合わ 最適化問題 探索空間 ン 限定
効率 探索 行う 出来 . 基本原理 具体
化 Ant System (以 :AS) あ .
3.1 Ant System
AS ACO ュー テ 基 最初 実装さ
手法 あ , TSP 解法 Dorigo 提案さ 手
法 あ .AS 用いTSP 解 , 蟻 見立 m個 ー
ン 各都市 ン 配置 . 各 ー ン 単純
ー 都市間 設置さ ン 都市間
距 逆数 比例 確率 都市 推移 , 巡回路 形成
.
, あ ー ン , k 都市i 都市j 推移
確率 次 う 定義さ .
= {
(� ) (� )
∑∈� (� ) (� ) ∈ �
ℎ �
k ー ン 番 = , , ⋯ , m 示 , N
ー ン k 未訪問 合 示 .� 都市i,j間 置
い ン . � 問題領域固有 情報 あ , TSP
一般 都市i.j間 距 d 逆数 用い . 式(1) ,
ン 問題領域固有 値 比例 選択確率 得 .
, α β 非負 実数 , ン 段階的
形成さ 大域的 情報 , 問題領域固有 値
連絡先：
氏 ： 直人, E-mail：[email protected]
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 2 -
局所的 情報 程度 視 示 ー あ
.
, m 個 ー ン 式(1) 用い巡回路 生成
動作 1 , t 目 任意 2 都市i,j
間 設置さ い ン
τ
次 う 定義さ .
� + = � ∙ � + ∆�
∆� = ∑ = ∆�
∆� = { � , ∈ �
ℎ �
ρ ン 蒸発率 表 ー あ , <
ρ < 間 設定さ . 蒸発効 , 通 い経路
ン 薄 い , 過去 行動 情報 新 い行動 情報
適応的 変化さ 解 収束 行う 出来 . ∆� , t
目 m個 ー ン 経路i,j 設置 ン
総 示 . ∆� ー ン k 都市i,j間 設置
ン 示 , Q ー ン 1 設置
ン 定 示 ー , �ｋ ー ン k 生成
巡回路 経路長 あ , � ー ン k 通 経路
合 あ . 即 経路 設置さ ン 経路長
逆数 決定さ , 経路長 短い経路 大 い
ン 置 , 逆 経路長 長い経路 少 い
ン 置 .
AS 基本動作 ン 初期化 行い, 式(1)
用いm個 ー ン 確率的 巡回路 生成 . 後
式(2), 式(3), 式(4) 用い ン 更新 , 終了条件 満
繰 返 .
3.2 Max-Min Ant System
Max-Min Ant System(以 ：MMAS) AS 改良 手法
あ .AS 間 経路 ン 中 解 収束
起 , 経路 抜 出 困 う.
MMAS , 各経路 置 ン 限値 限値
区間� �,� ] 限定 .さ ン 更新
各 最 成績 良い ー ン 経路 用い .
限値 限値 限定 , 解 収束 起 僅
確率 全 経路選択 出来 解 多様性
保 出来 . さ 優秀 ー ン 経路 使う
, 優 経 路 素 早 解 収 束 行 う 出 来 .
MMAS � � , � 以 式 定 い .
� � = − ×� − −
� =� �( − √ )
( ⁄ − ) √
C − o− t 目 最短 巡回路長
あ , n 都市数, � ン 標準化 際 限値
関 ー あ .
4.
相対評価
既存手法 経路 評価方法, 即 ン 更新
ー ン 通 経路 設置 い絶対評価 あ .
あ 経路 評価 , あ い 昇 場合, 周
辺 経路 対 価値 伝搬さ , 再評価 機会 与え
必要 考え . う , あ 評価対象 評価 他
評価対象 影響 与え 評価方法 相対評価 呼ば , 動的
意思決定課題 い 有用 あ 示さ い
[Tversky 74]. 相対評価 ACO 付加 , 解 収束
探索 安定 起 際 , 環境 変化 周辺 経路
伝播 素早 環境 変化 対応 出来
考え .
5.
提案手法
MMAS ン更新 式(2), 式(3), 式(4) う 都市i,j
あ 既存 ン� 揮発 数ρ 減衰さ ,
新 ー ン 設置 ン∆� 加算 手法
あ . 手法 , 環境 変化 直接影響 受
辺 , ー ン 通 辺 . 環境 変
化 ばや 対応 出来 い 考え . 本研究
, ー ン 通 経路 選択 評価対象 , 通
経路 他 評価対象 , 選択 評価対象 評価 ,
他 評価対象 影響さ 相対評価的 ン 更新
手法Ant System with Relative Evaluation 以 :AS-RE 提案
. AS-RE t 目 最 成績 良い ー ン 通
辺i,k ー ン 通 い い辺 i,j
ン更新式 以 式(7), 式(8) 分 .
� + = � + ��
� + = �� + ���
�� = �� +
� − − −�
= � − � +
� − − (9)
�� t t 目 ン 変化 , 既存手法
∆� 相当 . 微少 数μ 辺i,k 評価 隣接 辺i,j
与え 影響 調節 行 い . 提案手法 ー ン
通 経路 式(7) う 辺 設置さ い ン
変化 加算 . ー ン 通 経路 式
(8) う , 辺 設置さ ン 蒸発 数ρ
減少さ 辺i,k間 変化 僅 加算さ .
変化 �� t 他 経路 拡散さ 等 い. あ
程度探索 進 解 収束 起 , 経路 一定
式(9) ⁄C − o− 一定 値 , ρ − τ t 値
減少 い 変化 �� t 0 近 , � t 一定 値
収束 . MMAS � � 一定 確率 全
経路 選択さ . 経路 i,j � 確率 選ば ,
τ 含 新 経路 総 小さ 場合, 変化
�� t 増大 . 式(8) 他 経路 ン
増え , あ 程度収束 後 解 再探索 出
来 .
さ , 解 収束 変化 �� t 0 近 い , 環
境 変化 起 通 い 経路 経路長 大
場合, 変化 �� t 負 値 辺i,k ン 減
少さ . 他 経路 対 負 変化 伝播さ 微少
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 3 -
相対的 他 経路 評価 再探索 出来
い 考え .
6.
シポュリーション
本論文 動的 環境 再現 , 図1 う 2
心 状 数 都市 均等 並 都市配置 TSP
. 都市配置 側 都市郡 都市, 外側 都市郡
外 都市 呼ぶ. 問題 都市 外 都市 半 比
最適解 図1 う C型, O型 う 変化 . 外
都市 半 固定 都市 半 変化さ , C
型 O型 最適解 入 替わ 境界線 半 R .
都市 R 側 配置 最適解 C型 , R
外側 配置 最適解 O型 .
型 最短経路C , C 式(10), 式(11) 得 .
� = { + − + − }
� = + + −
外 都市 半 , 都市 半 , n
都市 外 都市 配置さ い 都市数 表 い .
本実験 最初 都市 R 側 配置 .
R 都市 差 r . 状態 探索 行いC型
最適解 求 . 最適解 求 後解 収束 行う
100 探索 . 後, 都市 R r
外側 再配置 環境 変化 起 . 状態 探索 再
開 O型 最適解 得 数 評価 1試
行 ュ ー ョン 行 . 本実験 , 都市 再配
置 行わ 5000 超え 場合, 探索 局所解
陥 最適解 発見 探索 終了 .
ュ ー ョン 用い MMAS AS-RE ー ,
ン = . , 可視化 = . , ー ン 1
落 ン 総 Q = . , ン 蒸
発 数ρ = . , τ 影響度μ = . × � ⁄ � �× .
図1：2 都市配置 最適解 局所解
6.1 結果
r 初期値 0.1 ュ ー ョン 行い, 100試行 , r
0.001刻 減少さ , r = . 施行 結 図2 示
. 縦軸 再配置 最適解 得 数, 横軸
境界線半 R 都市 半 差r 示 い . 図2
r = . 環境 変化 大 い MMAS AS-RE
1 最適解 求 出来 い .
r 小さ 環境 変化 小さ 問題
MMAS AS-RE 最適解 見 数
増え い わ . AS-RE MMAS 常 少
い 数 最適解 発見 確 .
既存手法 非定常環境 適応 図 い
考え .
図2：動的環境 実験結
7.
結論
本研究 , 動的環境 適応 相対評価 ACO
付加 既存手法 性能 向 図 . 結 ,
本実験 使用 動的環境 い 性能 向 見
出来 . , 既存手法 ン 更新 絶対評価
決定さ い , 提案手法 ー ン 通
経路 変化 通 い い経路 影響さ , 相対評価
考え . 相対評価 解 収束 起 い
解 再探索 出来 既存手法 良い結
得 考え . 今後 課題 , 他 動的環境
提案手法有効性 他 ュー テ 相対評価 有
用性 検証 い.
参考文献
[M.Dorigo 96] M. Dorigo, V. Maniezzo, A. Coloni (1996): The Ant System:Optimization by a Colony of Cooperating Agents, IEEE Trans. SMC-Part B, Vol. 26, No. 1, pp. 29-41. [山本 97] 山本芳嗣, 久保幹 (1997): 巡回 ー ン問題
招 , 朝倉書店.
[原 12] 原元 , 梶 大輔, 堀 匡 (2012): ACO 分割統
治型TSP近似解法, 知能 情報 日本知能情報 学
会 Vol. 24, No. 6, pp. 1101-1105.
[ 川 12] 川正志, 川 敬, 渡辺美知子, 木 正博, 山本 人,
鈴木育男: ュー テ ュ ン ューテ
ン , 社,2012
[久保 09] 久保幹 , J. P. ペ ソ (2009): ュー テ
数理, 共立出版.
[ 川 12] 川正志, 川 敬, 渡辺美知子, 木 正博, 山本
人, 鈴木育男 (2012): ュー テ ュ ン
ューテ ン , 社.
