2026-04-16T12:03:57Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00195414 2025-01-19T23:07:23Z 581:9633:9636

他個体を参照した進化的計算による巡回セールスマン問題の解法 A Novel Evolutionary Algorithm for Solving the Traveling Salesman Problem 佐藤, 豊浩 穴田, 一 Toyohiro, Sato Hajime, Anada [一般論文（特選論文）] 進化的計算，進化的アルゴリズム，遺伝的アルゴリズム，巡回セールスマン問題 進化的計算は，生物学的進化から着想を得た操作により，生物個体を模した複数の解候補を解空間上で移動させることで高精度な解を探索するという近似解法の枠組みの1つである．しかし，進化的計算の考えを基に設計された既存手法には，自然界の生物の仕組みに囚われ過ぎている部分がある．加えて，探索集団が持ち合わせない新規要素の発見が乱数に強く依存している．そこで，本研究では進化的計算の考えを基に，自然界の仕組みよりも巡回セールスマン問題を解くことに重点を置いた，乱数に強く依存しない突然変異を導入した新たなアルゴリズム，参照進化（Referential Evolution，RE）を構築した．そして，巡回セールスマン問題のベンチマーク問題を用いて，近似解を高精度かつ高速に求めることでその有効性を確認した． 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. 2019-03-15 jpn journal article https://ipsj.ixsq.nii.ac.jp/records/195414 1882-7764 AN00116647 情報処理学会論文誌 60 3 926 933 https://ipsj.ixsq.nii.ac.jp/record/195414/files/IPSJ-JNL6003026.pdf application/pdf 1.9 MB 2021-03-15