Parallel Consultant-Guided Search Algorithm for Traveling Salesman Problem

近年，メタヒューリスティクスは組合せ最適化問題を解く手法として多くの研究が行われている．最近の研究では，コンサルタント誘導型探索（CGS）と呼ばれる新しいメタヒューリスティクスが提案されている．本研究では，CGS を用いた巡回セールスマン問題（TSP）に対する並列アルゴリズムを提案する．アルゴリズムの並列化では，CGS における仮想人間をそれぞれの計算機の各プロセッサコアに割当てることで効率良く解の探索を行う．また，仮想人間の集団を複数のサブ集団に分割し，各サブ集団同士で仮想人間の移住を行う島モデルをCGS に取り入れる．10 台の計算機を用いた性能評価実験を行い，都市数が5000 のTSPLIB のベンチマーク問題例に対して5%未満の誤差率を達成することを示す．Metaheuristic algorithms have been studied as a method for solving combinatorial optimization problems. Recently, the Consultant-Guided Search (CGS) for solving the Traveling Salesman Problem(TSP) has been proposed. In this paper, we propose a parallel method which assigns virtual consultants and virtual clients of the CGS to processes of computers, and calculates an approximation solution effectively for the TSP. In addition, we introduce the island model to increase the diversity of the solution. We execute computer experiments with the benchmark instances (TSPLIB) by 10 quad-core computers. Our algorithm provides a solution with less than 5% error rate for problem instances of 5,000 cities