提案手法 -- 環境分散スキームを用いた多目的遺伝的アルゴリズム


: next :

環境分散スキームを用いた多目的遺伝的アルゴリズム

ここでは,提案手法である「環境分散スキームを用いた多目的遺伝的アルゴリズム」について説明する.

名称

和名:環境分散分散スキームを用いた多目的遺伝的アルゴリズム
英名:Multiple Objective Genetic Algorithms with Distributed Environment Scheme
略称:MOGADES(もがです)

概要

本手法は,分散遺伝的アルゴリズムにおいて,各目的関数に対する重みパラメータを環境分散させることにより多目的最適化を行うものである.
本手法は,各島に異なった重みパラメータを与える「重み分散」,与えた重みパラメータを探索途中に変化させる「重み変化」,重み付けの類似した島との間で移住を行う「近傍移住」,探索によって得られたパレート個体群と優良個体群をアーカイブとして個体群とは別に保存する「パレート+エリート保存」,の4つの特徴を有している. これまでに,種々の多目的ナップサック問題,連続関数多目的最適化問題に適用した結果,本手法が良好な性能を示すことがわかっている.

用語説明

ここでは,本手法に関連する用語について説明する.

環境分散遺伝的アルゴリズム

遺伝的アルゴリズム(Genetic Algorithms : GA)の並列化手法の一つである分散GAは,母集団を分割しないGAと比較して良好な結果を示す反面,設定すべきパラメータが多く,最適なパラメータ設定を知るためには膨大な量の予備実験が必要となるという問題がある. この問題を緩和する手法の一つに,環境分散GAがある. 環境分散GAは分散GAの島ごとに異なったパラメータ(交叉率,突然変異率など)を設定するというものであり,複数のパラメータ設定を同時に行うためにパラメータ設定の煩雑性が緩和される.その一方で,性能面でも分散GAの最適なパラメータ設定には及ばないまでも良好な性能を示す.

重み分散

本手法では,各島に異なった重みパラメータを与える. これを「重み分散」とよぶ. 初期化の段階では特に操作しない限り均等に重みパラメータが割り当てられる. 目的数が3以上になると重みを均等に分割可能な島数が限定される. このため,本手法では設定した島数の中で最大限に均等に分割した後,余った島についてはランダムに重みを割り当てる.

重み変化

本手法では,各島の持つ重みパラメータが変化する. これを「重み変化」とよぶ. 重み変化は,ある目的関数Faに対する重みについて島をソートしたときに隣接する2島(これを近傍島と呼ぶ)との間で行う. 重み変化は移住の際に行い,近傍の2島との間でエリートの距離をはかり,遠い方の島に重みパラメータを近づけることによって行う.

近傍移住

本手法では,重み付けの近い島との間で移住を行う. これを「近傍移住」とよぶ. 移住の度に異なった目的関数を基準にして島をソートし,隣接する2島との間で移住を行う. 複数回の移住を経ることによってすべての目的関数に関する近傍と移住を行うことを期待する.

パレート+エリート保存

本手法では,各島で探索途中で発見されたパレート個体群とエリート個体群をアーカイブとして探索個体群とは別に保持する. これを「パレート+エリート保存」とよぶ. さらに,アーカイブを選択に参加させることによって,重み変化直後の探索効率低下を抑制し,重みを用いた手法では発見しにくい部分(例:非凸パレートフロントにおける中央部分)のパレート解を発見することができる.

参考文献

[1] 三木光範,廣安知之,金子美華, 畠中一幸."環境分散型並列遺伝的アルゴリズム",電子情報通信学会,1999
: next :

: TOP PAGE :
(1) 2001.12.14