■Pre ■Up ■Next
■3.5.1 DRMOGA(領域分割多目的遺伝的アルゴリズム) 


1.はじめに

通常の分割母集団モデルを用いて多目的GAを並列化する場合,各サブ母集団の個体数は単一母集団と比べると減少する.多目的GAでは個体数が多ければ多いほど広範囲で精度の高いパレート解が得られるため,各サブ母集団で得られるパレート解の質は,単一母集団で求められるパレート解よりも質が悪くなる.


2.DRMOGA(Divided Range Multi-Objective Genetic Algorithm )

分割母集団モデルの並列処理でもたらされる計算速度を保持したまま,単一母集団と同等の精度のパレート解を求めるために提案された手法が DRMOGA である.DRMOGAでは得られたパレート最適個体をサブ母集団に分割する際に,無作為に個体を選ぶのではなく,目的関数に沿って領域を分け,その領域内の個体でサブ母集団を生成する手法を取っている.全領域において,近傍個体同士でサブ母集団を形成するため,帯域的探索を保ちつつ局所探索も期待できる.





3.DRMOGAの流れ
DRMOGAの流れは以下の通りである.GAの総個体数をN ,分割数をmとし,目的関数はƒ1から ƒLまでL個存在するものとする.

STEP1.
N個の個体をランダムに生成する.これらの個体が表現する設計変数はすべて制約条件を満足するものとする.

STEP2.
得られた個体のうちランク1(個体の中で優越されない個体,つまりパレート最適個体)のものだけを選択する.

STEP3.
注目する目的関数ƒi の値に従って各個体のソートを行う.注目する目的関数ƒ iはランダムではなく,ƒ1からƒ Lまで順に変更することとする.さらに注目する目的関数の最大値ƒ i(x)から目的関数順にN/m個の個体を選択し,m個のサブ母集団を形成する.

STEP4.
サブ母集団ごとに多目的最適化GAを行う.各世代ごとに終了判定を行い,条件を満たす場合には終了し,満たさない場合はSTEP5に移る.

STEP5.
各母集団で多目的最適化GAk世代行われたらSTEP3に戻る.この世代数をソート間隔と呼ぶ.分割数mおよびソート間隔kはあらかじめ決定しておくものとする.