提案手法のアルゴリズム

提案手法のアルゴリズムを述べる。提案手法は優越関係に基づく選択操作と分割に 基づく選択操作を両立させるために，2段階の選択操作を用いる点で特徴的である。提 案手法の流れの概略図を図4.2，提案手法のアルゴリズムをAlgorithm 4.1に示す。提 案手法の基本的な構造は分割に基づく手法に立脚しており，各探索点は対応する重みベ クトルw (∑r

k=1w_k = 1, wk >0)を有している。つまり，各世代の開始時にはm個の 重みベクトルが存在する。

Step 2では(a)探索点の状態判断と分類を行う。G世代目のすべての探索点x∈P^G に対して状態評価を行う。「他の探索点に優越されている」または「混雑している」と 判断された探索点は優越関係に基づく選択操作を適用するため，対応する重みベクトル 削除する。

Step 3では，探索点から子個体集合Q^Gを生成する。探索点P^Gと子個体Q^Gを足し 合わせた集合をR^G=P^G∪Q^Gとする。

Step 4では，分割に基づく選択操作を行う。Step 2で削除されなかった重みベクト

ルに対して，スカラー化関数の値が最小となる解をR^Gから選択し，次世代の探索点集 合P^G+1に加える。

Step 5では，優越関係に基づく選択操作を行う。R^Gのうち，他の解に優越されてお

らずかつ多様性維持への貢献度の高い解から順にP^G+1に加える。Step 5で選択された 探索点に対応する新たな重みベクトルを追加する。

(a) 各世代の初期状態 (b) Step 2の概略図

(c) Step 4の概略図 (d) Step 5の概略図

図4.2提案手法の探索の流れ

第4章 機能分担に基づく探索戦略 40

Algorithm 4.1: 提案手法 Step 0: 初期化

1: 初期個体集団P⁰，重みベクトル集合Wを与える（|P⁰|=|W|=m）。

2: 各個体x_i∈P⁰に重みベクトルw_i∈Wを割り当てる。

3: 理想点z_{を求める。ここで，}z_k= min_xi∈P⁰f_k(xi)である。

4: G= 0とする。

Step 1: 状態判断と分類

5: すべての個体間の距離を計算する。

6: 最も近い他の個体までの距離をd_i(i= 1,2,· · ·, m)とする。

7: d_i(i= 1,2,· · ·, m)の平均値をd¯とする。

8: forすべての個体x_i ∈P^G do 9: if d_i < C×d¯または then

10: 個体iに割り当てられた重みベクトルを削除する。

11: end if 12: end for

Step 2: 子の生成

13: 子個体集合をQ^G =∅^とする。

14: fori= 1, . . . ,^m₂ do

15: ランダムにP^Gから2つの親個体を選ぶ。

16: 交叉・突然変異で2つの子個体を生成する。

17: 生成された子個体をQ^Gに加える。

18: end for

Step 3: スカラー化適合度に基づく選択 19: P^G+1=∅^とする。

20: R^G=P^G∪Q^G_とする。

21: forすべての重みベクトルw_i ∈W do 22: x_i = argmin

x∈R^G

S(x|w_i,z) 23: x_iをP^G+1に加える。

24: x_iをR^G_{から削除する。}

25: end for

Step 4: パレートランキングに基づく選択 26: while|P^G+1|< mdo

27: 式(4.7)によりx∈R^Gに適合度を与える。

28: 最も適合度が優れた解xをP^G+1に加える。

29: 最も適合度が優れた解xをR^Gから削除する。

30: end while

Step 5: 終了判定 31: if G < G_max then

32: G:=G+ 1としてStep 1へ戻る。

33: end if