■Pre ■Up ■Next
■3.5.2　NCGA (Neighborhood Cultivation GA)
　
1

　

 はじめに

多目的GAは大域的な探索を行うため，探索個体同士の目的関数空間距離が大きく離れ効果的な交叉をできないといった問題点が生じる．この問題点を防ぐために，交叉のためのペア個体を選ぶ際，何らかの個体同士の近接度合いを考慮する必要がある．

　
2 近傍培養型遺伝的アルゴリズム（ＮＣＧＡ）

ＮＣＧＡでは探索個体群に対し，任意の目的関数軸を基準にソートを行い，隣り合う2つの個体群をペア個体群として選択し，遺伝的操作を行う．隣り合う個体同士は，比較的に目的関数空間における個体間の距離が近いため，効果的な交叉を実現することが期待される．

　
3

NCGAのアルゴリズム

STEP1．初期化
初期個体群を生成し，各個体の評価を行う．この初期個体群をアーカイブ個体群（At）とする．

STEP2．コピー
アーカイブ個体群（At）を探索個体群（Pｔ）にコピーし，Ptを一つの目的関数値を基準にソートし並び替える．この着目する目的関数は毎世代ごと変更する．また，順番を示す変数 ｉ を0に初期化する．

STEP3．選択
STEP2でソートされた探索個体群（Ｐｔ）の， i 番目と i+1番目をペア個体群として選択する．

STEP4．ＧＡ
選択された２個体のペア個体群を用いて交叉，突然変異，評価を行い新たなペア個体群を生成する．この新たなペア個体群を親個体と入れ替える．変数 i に２を加え，個体数と等価になるまでSTEP3，STEP4を繰り返す．こうして探索個体群（Ｐｔ）をすべて更新しＰｔ+1とする．

STEP5．環境選択
更新された探索個体群（Ｐｔ+1）とアーカイブ個体群（Ａｔ）の中から，ＳＰＥＡ２における環境選択の手法によって個体を選択し，アーカイブ個体群の更新を行う（Ａｔ+1）．

STEP6．終了判定
終了判定を満たしていれば終了．満たしていなければSTEP2に戻る．

　

　

　

4 ソート

ソートを行う際，常にある一定の目的関数軸を基準に行うと繰り返し同じペア同士でも交叉になる恐れがあるため，以下のような方法を用いている．

・毎世代ごとに基準となる目的関数の変更．

・ソート後の探索個体群に対して母集団サイズの1割程度の幅において近傍個体の並び替えを実行．