大会名称 |
---|
2019年 ソサイエティ大会 |
大会コ-ド |
2019S |
開催年 |
2019 |
発行日 |
2019/8/27 |
セッション番号 |
A-10 |
セッション名 |
システム数理と応用 |
講演日 |
2019/9/11 |
講演場所(会議室等) |
C棟 2F C206講義室 |
講演番号 |
A-10-10 |
タイトル |
粒子群最適化を用いた巡回セールスマン問題の解法 |
著者名 |
◎山田悠希, 穴田 一, |
キーワード |
粒子群最適化, Traveling Salesman Problem |
抄録 |
工業や経済の問題の多くは,最も効率が良い組み合わせを求める組み合わせ最適化問題に帰着することができる.その中に,与えられた全ての都市を巡る最短経路を求める巡回セールスマン問題 (Traveling Salesman Problem,TSP) という問題がある.本研究では,実数値最適化手法の一つである粒子群最適化(Particle Swarm Optimization,PSO)をこのTSPに適用させた新たなアルゴリズムを構築した.この提案手法は,PSOで用いられている各粒子のそれまでの最良解と近傍の粒子の最良解の情報に加え,解空間上で最も遠い粒子の解の情報を現在の解に重ね合わせた解の集合を用いて,解の更新を行うよう設計した.そして,TSPLIBに掲載されているベンチマーク問題を用いて既存手法と提案手法を比較することで,その有効性を確認した. |
本文pdf |
PDF download
|