文献

J-GLOBAL ID：201102216065337188   整理番号：11A0622772

改良Ant System Individualityの実装と評価

Implementation and Evaluation of Improved Ant System Individuality

著者 (2件)： TAKAYANAGI Keisuke (Hosei Univ., Tokyo, JPN) ,  LI Lei (Hosei Univ., Tokyo, JPN)
資料名： Information (Koganei)  (Information (Koganei))
巻： 14  号： 1  ページ： 251-264  発行年： 2011年01月 
JST資料番号： L7416A  ISSN： 1343-4500  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 最適化問題を現実的な計算時間で厳密解を求めることは極めて困難であるが,実用上は問題がない近似解を求めるためにヒューリスティックスアルゴリズムや近似アルゴリズムが用いられる。Ant Colony Optimization(ACO)はそのひとつであり,巡回セールスマン問題(TSP),グラフ彩色問題(GCP)などの組合せ最適化問題に対して他のヒューリスティックスアルゴリズムよりも良い結果を示すことが知られている。ACOを用いたアルゴリズムはAnt System(AS)とよばれる手法から派生した手法が多いが,ASには,初期学習の問題および試行錯誤性の問題があり,これらの問題を改善することはACOの研究において非常に重要であると考えられる。そこで,本稿では,これらの問題に対し,改良を加えた改良型ASI(IASI)の提案を行った。IASIでは,初期学習の問題に関してCI法をフェロモンの初期値に利用した。これにより,初期の段階から精度の良い学習を行えていることが確認できた。また試行錯誤性に関しては,2-opt法およびCL法を導入した。その結果,早い段階から最適解に近い巡回路の生成が行えていることが確認できた。すなわち,IASIは従来型のASIよりも性能向上が見られ,従来型のASの問題点であった初期学習の問題,試行錯誤性の問題を解消できたといえる。

シソーラス用語： *アルゴリズム ,  フェロモン ,  発見的方法 ,  *巡回セールスマン問題 ,  *組合せ最適化問題 ,  試行錯誤学習 ,  *改良
準シソーラス用語： *アントアルゴリズム ,  メタヒューリスティクス ,  性能改善

分類 (1件)： システム最適化手法  (IA02050Z)

引用文献 (13件)：

• Dorigo M., Maniezzo, V., and Coloni, A.: The Ant System: Optimization by a colony of cooperating agents, IEEETrans. On Systems, Man, and Cybernetics-Part B, Vol.26, No 1, pp. 1-13, 1996.
• Dorigo M., and L. M. Gambardella: Ant Colonies for the Traveling Salesman Problem, Biosystems, Vol.43, pp. 73-81, 1997.
• Stütze T., and Hoos, H.,“Max-Min Ant System, Future Generation Computer Systems, Vol.16, pp889-914, 2000.
• 井出秀和,“巡回セールスマン問題に対するAnt Systemの適用”, 東京理科大学工学部経営工学科, 卒業論文, 1998.
• 亀田陽介,”局所最適解をフェロモン初期化に用いたアントコロニー最適化法によるTSPの解法”, 筑波大学大学院システム情報工学研究科, 卒業論文, 2007.

タイトルに関連する用語 (2件)： 実装 ,  評価