TSPにおけるアントコロニー・コンサルタント誘導型探索

書誌事項

タイトル別名
  • Ant Colony Consultant Guided Search for the Traveling Salesperson Problem

この論文をさがす

説明

アントコロニー最適化は，多くの組合せ最適化問題に適用され，良い解を見い出すメタヒューリスティック手法の 1 つである．そのため，多くの改善が為されアントコロニーシステムなど様々なアルゴリズムが提案されてきている．最近新しく提案されたメタヒューリスティック手法の 1 つにコンサルタント誘導型探索がある．この手法はコンサルタントと呼ばれる仮想の人間が持つ解をもとに，クライアントと呼ばれる仮想の人間が解を作成するアルゴリズムである．本研究では，コンサルタント誘導型探索におけるコンサルタントが持つ解を作成するためにアントコロニーシステムを利用し，組合せ最適化問題の代表例である巡回セールスパーソン問題 (TSP) の近似解を求めるアルゴリズムを提案する．最終的に，ベンチマーク問題 (TSPLIB) を用いて計算機実験を行った結果，都市数 1000 程度の問題において誤差率 1 パーセントを切る解を見つけ出した．Ant Colony Optimization is applied to a number of Combinatorial Optimization Problems and is one of the metaheuristic method that has been put out a good solution. Therefore, many improvements have been made, and various algorithms such as Ant Colony System have been proposed. Recently, Consultant Guided Search was proposed as one of metaheuristic methods. This approach is an algorithm that a virtual person called a client creates a solution based on a solution with a virtual person called a consultant. In this research, we propose an algorithm which uses Ant Colony System in order to create a solution with a consultant in Consultant Guided Search, and calculates an approximation solution for the traveling salesperson problem (TSP). Finally, we execute a computer experiment using the benchmark problems(TSPLIB), and our algorithm got a solution of less than 1% error rate for problem instances in a matter of 1000 cities.

収録刊行物

詳細情報 詳細情報について

  • CRID
    1572261552750477056
  • NII論文ID
    110009488582
  • NII書誌ID
    AA12055912
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ