巡回セールスマン問題の遺伝的アルゴリズムに対する凸包の応用

• 竹中 要一

  大阪大学大学院基礎工学研究科情報数理系専攻

• 船曵 信生

  大阪大学大学院基礎工学研究科情報数理系専攻

書誌事項

タイトル別名

• An Application of Convex Hull to Genetic Algorithm for Traveling Salesman Problem

抄録

本論文では, 巡回セールスマン問題の遣伝的アルゴリズムに対して凸包による訪問順序制限定理を用いた求解性能向上方法の提案を行う. 凸包とは点集合の任意の2要素を結ぶ閉線分を内部に含む最小の凸多角形であり, 要素数nの点集合の凸包を求めるアルゴリズムの計算量の下界はO (n log n) である. 訪問順序制限定理は凸包を用いてユークリッド平面上の巡回セールスマン問題の最短巡回路となる為の必要条件を示している. また, 遣伝的アルゴリズムは自然界の自然淘汰の過程をモデルとした解法であり, 巡回セールスマン問題の近似解探索アルゴリズムの中でも優れた解法の一つとして知られている. 本論文では, 凸包によって与えられる最短巡回路の必要条件を充足する巡回路を初期染色体とする事により, 遺伝的アルゴリズムの求解性能の向上を図る. ベンチマーク問題を用いたシミュレーションによる性能評価の結果, 都市数の大きい問題において訪問順序制限定理を用いた解法の求解精度が向上した.

収録刊行物

• 電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス

  電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス 97 (521), 17-24, 1998-01-29

  一般社団法人電子情報通信学会

キーワード

• 巡回セールスマン問題
• 訪問順序制限定理
• 遺伝的アルゴリズム
• 凸包
• 近似解探索アルゴリズム

詳細情報

• CRID: 1571417127416379136
• NII論文ID: 110003276784
• NII書誌ID: AN10013287
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles