訪問順序制約をもつTSPに対するGAの提案

カテゴリ: 部門大会

論文No: OS7-4

グループ名: 【C】平成16年電気学会電子・情報・システム部門大会講演論文集

発行日: 2004/09/02

タイトル(英語): A Proposal of Genetic Algorithm for TSP with a Constraint on Visiting Order

著者名: 遠山 宏明(前橋工科大学),井田 憲一(前橋工科大学),阿部 直子(前橋工科大学)

著者名(英語): Hiroaki Tohyama(Maevashi Insutitute of Technology Graduate School),Kenichi Ida(Maevashi Insutitute of Technology Graduate School),Naoko Abe(Maevashi Insutitute of Technology Graduate School)

キーワード: 遺伝的アルゴリズム|巡回セールスマン問題|訪問順序訪問順序|Genetic Algorithm|Traveling Salesman Problem|Visiting Order

要約(日本語): 巡回セールスマン問題（TSP）はNP困難であることが知られている典型的な組合せ最適化問題である．遺伝的アルゴリズム（GA）は，その使用が簡単で，比較的高い確率でよい解を短時間で求めることができるため，TSPに対してよく適用されている．最近提案されているGAのTSPに対する手法の多くは，良い形質を辺と定めたものが多い．しかし，応用問題を考慮するとき訪問順序を必要とする場合も存在する．本論文では，個体の良い形質を都市の巡回順位と定め，遺伝的操作を行う上での指針として利用する．さらに，数値的実験により提案する遺伝的操作の効果を検証する．

PDFファイルサイズ: 2,113 Kバイト