粒子群最適化に基づく巡回セールスマン問題に対する近似解法に関する研究

• Material Type: 博士論文
• Title: 粒子群最適化に基づく巡回セールスマン問題に対する近似解法に関する研究
• Author/Editor: 本庄, 将也
• Author Heading: 本庄, 将也
• Publication, Distribution, etc.: Hokkaido University
• Publication Date: 2016-09-26
• Publication Date (W3CDTF): 2016-09-26
• Contributor: 山本, 雅人; 栗原, 正仁; 小野, 哲雄; 川村, 秀憲; 飯塚, 博幸
• Degree grantor/type: 北海道大学
• Date Granted: 2016-09-26
• Date Granted (W3CDTF): 2016-09-26
• Dissertation Number: 甲第12400号
• Degree Type: 博士(情報科学)
• Conferring No. (Dissertation): 甲第12400号
• Text Language Code: jpn
• NDC: 500
• Target Audience: 一般
• Note (General): 近年注目されている実数値最適化手法の一つに粒子群最適化（Particle Swarm Optimization, PSO）がある．PSOは群知能の一種であり，複数の探索単位(粒子)が互いに情報共有を行いながら解の探索を行う．多点探索を行うメタヒューリスティクスとしては遺伝的アルゴリズム（Genetic Algorithm, GA）が有名であるが，多くの実数値最適化問題においてPSOのほうがGAに比べて高速に良い解を発見できることが知られている．本研究では，組合せ最適化問題の一種である巡回セールスマン問題（Traveling Salesman Problem, TSP）に対して短時間で良い解を得ることを目的として，PSOを基にしたアルゴリズムである挿入操作PSO戦略を提案する．提案手法では，粒子の解候補は実数値ベクトルではなく巡回路として表現され，粒子間の相互作用は部分経路挿入 によって行われる．本論文では，挿入操作PSO戦略について説明し，数値計算実験からパラメータと得られる解の良さと必要な時間の関係について調査し，パラメータ調整の指針を示す．また，各ベンチマーク問題に対して 提案手法とGAなどの代表的なメタヒューリスティクスを適用し，提案手法がこれらの手法より短時間で良い解を求められることを示す．; (主査) 教授 山本 雅人, 教授 栗原 正仁, 教授 小野 哲雄, 教授 川村 秀憲, 准教授 飯塚 博幸; 情報科学研究科（複合情報学専攻）
• DOI: 10.14943/doctoral.k12400; https://doi.org/10.14943/doctoral.k12400
• Persistent ID (NDL): info:ndljp/pid/10224552; https://dl.ndl.go.jp/pid/10224552
• Collection: 障害者向け資料
• Collection (Materials For Handicapped People:1): テキストデータ
• Collection (particular): 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文; https://dl.ndl.go.jp/collections/A00014
• Acquisition Basis: 博士論文（自動収集）
• Date Accepted (W3CDTF): 2016-12-01T22:39:34+09:00
• Format (IMT): PDF
• Access Restrictions: 国立国会図書館内限定公開
• Service for the Digitized Contents Transmission Service: 図書館・個人送信対象外
• Availability of remote photoduplication service: 可
• Periodical Title (URI): http://dx.doi.org/10.14943/doctoral.k12400; http://hdl.handle.net/2115/63269
• Is Referenced By (URI): http://hdl.handle.net/2115/63267
• Data Provider (Database): 国立国会図書館 : 国立国会図書館デジタルコレクション; https://dl.ndl.go.jp

• Summary, etc.: 近年注目されている実数値最適化手法の一つに粒子群最適化（Particle Swarm Optimization, PSO）がある．PSOは群知能の一種であり，複数の探索単位(粒子)が互いに情報共有を行いながら解の探索を行う．多点探索を行うメタヒューリスティクスとしては遺伝的アルゴリズム（Geneti...