パラメータの適応的調整を伴う遺伝的アルゴリズムのハードウェア化

概要

論文の詳細を見る
工学における様々な分野において複雑な制約を持つ多くの大規模最適化問題が知られているが, それらの問題は数理的手法や組合せ最適化アルゴリズムを用いて実用的な計算時間で最適解を求めることは困難なため, ヒューリスティック手法を用いて解を求めることが一般的である。このようなヒューリスティック手法の一つとして遺伝的アルゴリズム(Genetic Algorithm, GA)が知られている。GAは生物の進化の過程にヒントを得た手法であり, アルゴリズムの実行中は複数の解(個体)を保持し, これに遺伝的操作を適用して解の改善を行なう。GAは多くのパラメータを持つため, それらのパラメータの値を調整してGAの探索能力を最大限に利用することは一般に難しい。そこでDavisらはGAを用いて問題を解くのと並行して, 内部パラメータの値を動的に調整し, 効率的にGAを実行する方法を提案し, 比較的良い結果を得ている。また著者らは文献[3]においてエリート度の概念を提案し, これに基づく複数の交叉手法の適応的選択手法を提案している。本稿では著者らが提案したエリート度に基づく交叉の選択手法を組み込んだGAのハードウェア化を議論する。GAをハードウェアで実現することによりソフトウェアによる実行に比べて, 非常に高速なアルゴリズムの実行が可能となる。また, 並列処理やパイプライン処理などの導入によりさらに効率の良い解の探索が期待できる。一方, GAの適用対象問題を特定すればその問題に対するGAをハードウェア化するのは容易であるが, 適用対象問題を特定しない場合, ハードウェア化したGAに汎用性を持たせる必要が生じる。これを解決するために, 問題に依存した部分についてはFPGA等の再構成可能なハードウェアで実現し, 問題に依存しない部分は通常のハードウェアで実現することが考えられる。本稿で提案するGAのハードウェア化においても, 問題に依存する部分はFPGA, 依存しない部分はLSIで実現することとしている。
一般社団法人情報処理学会の論文
1997-09-24

パラメータの適応的調整を伴う遺伝的アルゴリズムのハードウェア化

スポンサーリンク

概要

著者

関連論文

スポンサーリンク