2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法

摘要

For the quadratic assignment problem (QAP), a heuristic algorithm based on tabu search, which is implemented as hardware on FPGAs, is proposed to solve the problem efficiently. The proposed hardware algorithm is a systolic algorithm, in which multiple neighborhood solutions are evaluated in parallel, and for each solution, the objective function is evaluated in a pipeline fashion so as to shorten the computation time. The proposed method was implemented on an FPGA chip, and its effectiveness was shown.%2次割当問題（Quadratic Assignment Problem,QAP）に対し，タブー探索法に基づくヒューリスティック解法をハードウェアとして実現し，FPGA上に実装することで問題を高速に解くことを提案する．提案するハードウェア解法はタブー探索法をシストリックアルゴリズムとして実現することにより，複数の近傍解を並列処理により同時に評価し，かつ各近傍解に対する目的関数の評価をパイプライン処理することで計算時間を短縮する・提案手法をFPGA上に実現し，ソフトウェア解法と比較することにより提案手法の有効性を示した．