著者

橘 達弘 村田 佳洋 柴田 直樹 安本 慶一 伊藤 実

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.49, no.1, pp.381-392, 2008-01-15

参考文献数

19

被引用文献数

1

---

多目的遺伝的アルゴリズム(Multi-Objective Genetic Algorithms,MOGA)は,多目的最適化問題を解くために単一目的遺伝的アルゴリズムを拡張した最適化手法である.MOGA では複数の個体群の多様性を維持するための手法であるニッチ法やランク戦略がよく用いられるため,単一目的GA よりさらに計算量が大きくなる傾向がある.本論文では,多目的最適化問題を高速に解くことを目的とし,ハードウェア化のためのMOGA のアーキテクチャを提案する.提案方式では,世代交代モデルとしてハードウェア化に適したMinimal Generation Gap モデルを採用する.既存のニッチ法やランク戦略をパイプライン処理で実装することは困難なため,パイプライン処理に適した多様性を維持する手法を設計,採用した.また,解探索能力の向上のために,島モデル型GA の各島の目的関数を改変した並列GA モデルに即した並列実行方式を設計し,提案アーキテクチャに採用した.実験の結果,提案アーキテクチャによるMOGA 回路はNSGA-II より優れた探索能力を持つことを確認した.Multi-Objective Genetic Algorithms (MOGAs) are enhancement of Single-Objective Genetic Algorithms (SOGAs) to solve multi-objective optimization problems. Since MOGAs require a special selection mechanism such as ranking strategy and niching method to preserve diversity of individuals, MOGAs require larger computation power than SOGAs. In order to improve calculation speed of MOGAs, we propose a new method to easily implement MOGAs as high performance hardware circuits. In the proposed method, we adopt a simple minimal generation gap model as the generation model, which is easy to be pipelined. Since it is difficult to implement niching method and ranking strategy as pipelined circuits, we developed a new selection mechanism which is suitable for hardware implementation. In order to improve search efficiency, our method also includes a parallel execution architecture based on island GA. In this architecture, we use different objective function for each island. Through experiments, we confirmed that our method has higher search efficiency than NSGA-II.