分割統治型アルゴリズムによるTSP近似解法

カテゴリ: 全国大会

論文No: 3-025

グループ名: 【全国大会】令和2年電気学会全国大会論文集

発行日: 2020/03/01

タイトル(英語): Divide and Conquer Technique for Travelling Salesman Problems

著者名: 今田祐介（松江工業高等専門学校）,三島諒亮（北陸先端科学技術大学院大学）,原元司（松江工業高等専門学校）

著者名(英語): Yusuke Imada (NIT, Matsue College),Ryosuke Mishima (Japan Advanced Institute of Science and Technology),Motoshi Hara (NIT, Matsue College)

キーワード: 分割統治型アルゴリズム|巡回セールスマン問題|遺伝的アルゴリズム|ブンカツトウチガタアルゴリズム|ジュンカイセールスマンモンダイ|イデンテキアルゴリズム

要約(日本語): 近年，巡回セールスマン問題（TSP）の近似解法として，各種の手法が盛んに研究されている．著者らの研究室でも，TSPに対して大域探索と局所探索のバランスを備えた分割統治型近TSP似解法（DAS）を提案している．このDASは蟻コロニー最適化（ACO）の一種であるアントシステム（AS）をベースにしているが，LKアルゴリズムとの併用やほかの近似解法での適用についてこれまで検討を行っていない．そこで，本研究では遺伝的アルゴリズム（GA）にDASで導入した分割統治アルゴリズムの考え方を導入し，分割統治アルゴリズムについての考察を行ったので報告する．

本誌掲載ページ: 36-37 p

原稿種別: 日本語