他個体を参照した進化的計算による巡回セールスマン問題の解法

• Item type: Journal(1)
• 公開日: 2019-03-15
• タイトル: 他個体を参照した進化的計算による巡回セールスマン問題の解法
• タイトル / 言語: en
• タイトル: A Novel Evolutionary Algorithm for Solving the Traveling Salesman Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文（特選論文）] 進化的計算，進化的アルゴリズム，遺伝的アルゴリズム，巡回セールスマン問題
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京都市大学大学院工学研究科
• 著者所属: 東京都市大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Tokyo City University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Tokyo City University
• 著者名: 佐藤, 豊浩; 穴田, 一
• 著者名(英): Toyohiro, Sato; Hajime, Anada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 進化的計算は，生物学的進化から着想を得た操作により，生物個体を模した複数の解候補を解空間上で移動させることで高精度な解を探索するという近似解法の枠組みの1つである．しかし，進化的計算の考えを基に設計された既存手法には，自然界の生物の仕組みに囚われ過ぎている部分がある．加えて，探索集団が持ち合わせない新規要素の発見が乱数に強く依存している．そこで，本研究では進化的計算の考えを基に，自然界の仕組みよりも巡回セールスマン問題を解くことに重点を置いた，乱数に強く依存しない突然変異を導入した新たなアルゴリズム，参照進化（Referential Evolution，RE）を構築した．そして，巡回セールスマン問題のベンチマーク問題を用いて，近似解を高精度かつ高速に求めることでその有効性を確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Evolutionary computation (EC) is an evolution-inspired algorithm and is one of the approximation algorithms. EC's emphasis lies in the mechanism of biological evolution. Therefore, we constructed a new algorithm named Referential Evolution (RE) whose main emphasis is not biological evolution. This was done to solve non-deterministic polynomial-time hard combinational problems. We confirmed the effectiveness of our proposed algorithm by comparing it to other EC-based algorithms using several benchmark problems taken from the TSPLIB, which is a library of traveling salesman problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 60, 号 3, p. 926-933, 発行日 2019-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764