文献

J-GLOBAL ID：201702258972332625   整理番号：17A0040609

巡回セールスマン問題に対する粒子群最適化の提案と性能評価

著者 (4件)： 本庄将也 (北海道大学大学院情報科学研究科) ,  飯塚博幸 (北海道大学大学院情報科学研究科) ,  山本雅人 (北海道大学大学院情報科学研究科) ,  古川正志 (北海道情報大学)
資料名： 知能と情報(Web)  (日本知能情報ファジィ学会誌(Web))
巻： 28  号： 4  ページ： 744-755(J-STAGE)  発行年： 2016年 
JST資料番号： U0688A  ISSN： 1881-7203  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 近年注目されている実数値最適化手法の一つに粒子群最適化(Particle Swarm Optimization, PSO)がある.PSOは群知能の一種であり,複数の探索単位(粒子)が互いに情報共有を行いながら解の探索を行う.多点探索を行うメタヒューリスティクスとしては遺伝的アルゴリズム(Genetic Algorithm, GA)が有名であるが,多くの実数値最適化問題においてPSOのほうがGAに比べて高速に良い解を発見できることが知られている.本研究では,組合せ最適化問題の一種である巡回セールスマン問題(Traveling Salesman Problem, TSP)に対して短時間で良い解を得ることを目的として,PSOを基にしたアルゴリズムである挿入操作PSO戦略を提案する.提案手法では,粒子の解候補は実数値ベクトルではなく巡回路として表現され,粒子間の相互作用は部分経路挿入によって行われる.本論文では,挿入操作PSO戦略について説明し,数値計算実験からパラメータと得られる解の良さと必要な時間の関係について調査し,パラメータ調整の指針を示す.また,各ベンチマーク問題に対して提案手法とGAなどの代表的なメタヒューリスティクスを適用し,提案手法がこれらの手法より短時間で良い解を求められることを示す.(著者抄録)

シソーラス用語： *最適化 ,  *巡回セールスマン問題 ,  探索問題 ,  発見的方法 ,  遺伝的アルゴリズム ,  シミュレーテッドアニーリング ,  組合せ最適化問題 ,  実験 ,  パラメータ ,  *評価試験
準シソーラス用語： メタヒューリスティクス ,  *ベンチマークテスト ,  数値実験 ,  多点探索 ,  *粒子群最適化

著者キーワード (4件)： 粒子群最適化 ,  巡回セールスマン問題 ,  Particle Swarm Optimization ,  Traveling Salesman Problem

分類 (3件)： ネットワーク法  (KA03040X) ,  システム最適化手法  (IA02050Z) ,  数値計算  (JE02000J)

引用文献 (18件)：

• [1]山本,久保,巡回セールスマン問題への招待,朝倉書店,1997.
• [2]W.J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press, 2012,松浦俊輔(訳):驚きの数学巡回セールスマン問題,青土社,2013.
• [3]柳浦,茨城,組合せ最適化問題に対するメタ戦略について,電子情報通信学会論文誌.D-I,情報・システム,I-情報処理,J83-D-I-1,3-25,2000.
• [4]J. Kennedy and R.C. Eberhart, Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, 1942-1948, 1995.
• [5]R . Poli , J . Kennedy and T . Blackwell , Particle swarm optimization, Swarm Intelligence, 1-1, 33-57, 2007.

タイトルに関連する用語 (4件)： 巡回セールスマン問題 ,  粒子群最適化 ,  提案 ,  性能評価