- 著者
- 榎原 博之 中山 弘基 飯田 修平 長辻 亮太
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.57, no.1, pp.331-342, 2016-01-15
近年,メタヒューリスティクスは組合せ最適化問題を解く手法として多くの研究が行われている.最近の研究では,コンサルタント誘導型探索(CGS)と呼ばれる新しいメタヒューリスティクスが提案されている.本研究では,CGSを用いた巡回セールスマン問題(TSP)に対する並列アルゴリズムを提案する.アルゴリズムの並列化では,CGSにおける仮想人間をそれぞれの計算機の各プロ セッサコアに割り当てることで効率良く解の探索を行う.また,仮想人間の集団を複数のサブ集団に分割し,各サブ集団どうしで仮想人間の移住を行う島モデルをCGSに取り入れる.10台の計算機を用いた性能評価実験を行い,都市数が5,000のTSPLIBのベンチマーク問題例に対して5%未満の誤差率を達成することを示す.