巡回セールスマン問題における母集団・子集団の多様性を考慮した遺伝的アルゴリズム

カテゴリ：部門大会

論文No：TC4-2-2

グループ名：【C】2025年電気学会電子・情報・システム部門大会

発行日：2025/8/20

タイトル(英語)：Genetic Algorithm Considering Diversity of Population and Offspring for Traveling Salesman Problem

著者名：平木 尊（関西大学）,花田 良子（関西大学）

著者名(英語)： Takeru Hiragi (Graduate School of Science and Engineering, Kansai University),Yoshiko Hanada (Kansai University)

キーワード：巡回セールスマン問題,遺伝的アルゴリズム,枝組み立て交叉,タブー探索,枝エントロピー,Traveling Salesman Problem,Genetic Algorithm,Edge Assembly Crossover,Tabu Search,Edge Entropy

要約(日本語)：本研究では，巡回セールスマン問題(TSP)を解くための手法として，枝組み立て交叉（EAX）にタブ探索を併用した交叉EAX-tabuに，枝エントロピーに基づく生存選択を組み合わせた遺伝的アルゴリズムを提案する．本提案手法は，交叉において繰り返しのエッジ交換を防ぐことで生成子個体の多様性を向上させるとともに，発現確率が低い個体を生存させやすくすることで母集団の多様性を向上させる．TSPLIBとVLSI TSPの中規模の例題を用いて，提案手法の有効性を検証する．

本誌掲載ページ：209-215p

原稿種別：日本語

PDFファイルサイズ：2,264Kバイト