高いスループットを実現する組み合わせ生成アルゴリズムの提案と実装

摘要

Combinatorial optimization problems are widely exist. Generally they are solved by approximate means like greedy method because they are categorized as NP-hard. However, in several cases, the solution is likely to be local optimized. In the worst case, no solutions can be obtained. Meanwhile, even if brute force method like enumeration method is used, there is a possibility that optimized solutions can be obtained within realistic time because of resent performance improvement of processors and other reasons. For speeding up the enumeration method, a method of fast combination generation is required. In this paper, we clarify the problems for speeding up of enumeration method through performance evaluations of existing combination generation algorithms. Moreover, we propose a faster combination generation algorithm than existings. In the results of the performance evaluations, the dedicated hardware of the proposed algorithm achieves about 500 times faster than software of the existing algorithm and about 10 times than the dedicated hardware of that.%組み合わせ最適化問題と呼ばれる問題は世の中に広く存在している．組み合わせ最適化問題はNP困難な問題であるため,一般的にはgreedy法のような近似解法を用いて解かれている．しかし，近似解法では，問題によっては局所解に陥り，最通解との差が大きくなってしまう場合や，解を算出できない場合がある．一方，ハードウェアの性能向上などの要因により,組み合わせを総当たりで調べる列挙法を用いた場合でも，最適解を現実的な時間で得ることができる可能性が出てきている.列挙法の高速化のためには，組み合わせを高速に生成する必要がある．そこで，本稿では列挙法の高速化を目的とし,既存の組み合わせ生成アルゴリズムの性能評価を行い，高速化のための課題を明らかにする.さらに，従来よりも高速に組み合わせの生成を行うことが可能なアルゴリズムを提案する．FPGAを対象デバイスとして提案アルゴリズムをハードウェア化し，性能評価を行った結果，既存の組み合わせ生成アルゴリズムを汎用CPUを用いて実行した場合に比べて500倍以上，専用ハードウェアで生成した場合に比べて10倍以上の速度で組み合わせを生成可能であることが示された．