2 0 0 0 OA 巡回セールスマン問題に対する粒子群最適化の提案と性能評価
- 著者
- 本庄 将也 飯塚 博幸 山本 雅人 古川 正志
- 出版者
- 日本知能情報ファジィ学会
- 雑誌
- 知能と情報 (ISSN:13477986)
- 巻号頁・発行日
- vol.28, no.4, pp.744-755, 2016-08-15 (Released:2016-09-28)
- 参考文献数
- 18
- 被引用文献数
- 3
近年注目されている実数値最適化手法の一つに粒子群最適化(Particle Swarm Optimization, PSO)がある.PSOは群知能の一種であり,複数の探索単位(粒子)が互いに情報共有を行いながら解の探索を行う.多点探索を行うメタヒューリスティクスとしては遺伝的アルゴリズム(Genetic Algorithm, GA)が有名であるが,多くの実数値最適化問題においてPSOのほうがGAに比べて高速に良い解を発見できることが知られている.本研究では,組合せ最適化問題の一種である巡回セールスマン問題(Traveling Salesman Problem, TSP)に対して短時間で良い解を得ることを目的として,PSOを基にしたアルゴリズムである挿入操作PSO戦略を提案する.提案手法では,粒子の解候補は実数値ベクトルではなく巡回路として表現され,粒子間の相互作用は部分経路挿入によって行われる.本論文では,挿入操作PSO戦略について説明し,数値計算実験からパラメータと得られる解の良さと必要な時間の関係について調査し,パラメータ調整の指針を示す.また,各ベンチマーク問題に対して提案手法とGAなどの代表的なメタヒューリスティクスを適用し,提案手法がこれらの手法より短時間で良い解を求められることを示す.
1 0 0 0 OA 粒子群最適化に基づく巡回セールスマン問題に対する近似解法に関する研究
近年注目されている実数値最適化手法の一つに粒子群最適化(Particle Swarm Optimization, PSO)がある.PSOは群知能の一種であり,複数の探索単位(粒子)が互いに情報共有を行いながら解の探索を行う.多点探索を行うメタヒューリスティクスとしては遺伝的アルゴリズム(Genetic Algorithm, GA)が有名であるが,多くの実数値最適化問題においてPSOのほうがGAに比べて高速に良い解を発見できることが知られている.本研究では,組合せ最適化問題の一種である巡回セールスマン問題(Traveling Salesman Problem, TSP)に対して短時間で良い解を得ることを目的として,PSOを基にしたアルゴリズムである挿入操作PSO戦略を提案する.提案手法では,粒子の解候補は実数値ベクトルではなく巡回路として表現され,粒子間の相互作用は部分経路挿入 によって行われる.本論文では,挿入操作PSO戦略について説明し,数値計算実験からパラメータと得られる解の良さと必要な時間の関係について調査し,パラメータ調整の指針を示す.また,各ベンチマーク問題に対して 提案手法とGAなどの代表的なメタヒューリスティクスを適用し,提案手法がこれらの手法より短時間で良い解を求められることを示す.