部分更新指数減衰カオスタブーサーチハードウェアシステムのデジタル回路によるコスト計算実装に対する考察

摘要

指数減衰カオスタブーサーチは，組合せ最適化問題に対する有力なメタヒューリスティック解法の1つである．我々は，この指数減衰カオスタブーサーチが内包する複雑系としてのロバスト性を活用して，小型で高性能な大規模ハードウェアシステムに適した，部分更新指数減衰カオスタブーサーチアルゴリズムを提案し，そのハードウェア実現の研究を進めている．二次割当問題を解く部分更新指数減衰カオスタブーサーチシステムを実現する際，目的関数値の計算をアナログ回路で実装することは困難であるため，この計算にはデジタル回路を用いる．しかし，デジタル計算は逐次処理であるため，大規模な問題の場合，システムの動作速度のボトルネックとなる．そこで本稿では，デジタルコスト計算を高速に行うための専用回路を設計する．この際，DSPとFPGAによる実装の性能を比較し，パイプライン処理を用いたFPGAによる実装が適していることを示す．