F 4 Non-dominated
5.4 領域分割型多目的遺伝的アルゴリズム
前節の結果から，単一目的GAの分割母集団モデルを単純に適用した場合，多目的GA としての性能が劣化することが確認できた．その1つの解決策とし て提案した，非定期的 に全ての個体を用いて選択操作を行うTSGAは単一目的GAの分割母集団モデルに 比べ 良好な結果を示した．しかしながら，TSGAでは非定期的にしか全体としての選択操作を 行わない上，広範囲のパレ ート最適フロントを探索する多目的の特性が全く考慮されてい ない．
そこで，本研究ではより多目的の特性に特化した分割母集団モデルとして領域分割型多目 的遺伝的アルゴ リズム(Divided Range Multi-Objective Genetic Algorithm: DRMOGA) を提案する．本モデルは，サブ 母集団ごとに探索する目的関数空間の領域を定めることに より，探索の重なりを減らし ，全体とし て効率的な探索を実現しようとするモデルである．
5.4.1 領域分割型多目的GAのアルゴリズム
以下に提案するDRMOGAの流れを説明する．ここで，GAの総個体数をN，分割数を Kとし ，目的関数はf1からfM までM 個存在するものとする．
Step 1 N 個の個体をランダ ムに生成する．これらの個体が表現する設計変数は全ての制 約条件を満足するものとする．
Step 2 得られた解のうち，非劣解のみを選択する．
f
1(x)f
2(x)Min Max
division 1division 2
division 3
Pareto-optimal solution
図 5.9 Schematic of DRMOGA
Step 3 基準となる目的関数fiの値に従って各個体のソートを行う．本研究では，基準と する目的関数fiはランダ ムではなくf1からfM まで順に変更することとし てい る．また，基準とする目的関数の最大値から目的関数値の順に N/K 個ずつ個体 をサブ 母集団へ分配し ，N/K 個の個体からなるK個のサブ 母集団を形成する．
Step 4 サブ 母集団ごとに多目的GAを行う．本研究で行う多目的GAは次節で詳し く説 明する．また，世代ごとに終了判定を行い，条件を満たす場合には終了する．終 了判定で，条件を満たさない場合は，Step 5に進む．
Step 5 各母集団で多目的最適化GAがs世代行われたら Step 3に戻る．この世代数を ソート間隔と呼ぶ．
本研究では，分割数Kおよび ソート 間隔sはあらかじめ決定し ておくものとする．図 5.9には2目的の場合(M = 2)に目的関数f1 に沿って3分割(K = 3)している概念図を示 す．なお，図 5.9は最小化の場合の例である．
このDRMOGAに対して分散メモリ型並列計算機を用いて並列処理を行うことにより，
DGAと同等の処理速度の向上やSGAと同等，もし くはそれ以上の解の精度を持った解集 合を求めることが 期待できる．
5.4.2 数値実験
DRMOGAの有効性を検証するため，DGA，SGAとの比較実験を行う．なお，これら
全ての多目的GAはFonsecaらのMOGA19）である．
例題
DRMOGAの有効性を検証するためにNDP，VB3の2つの例題に対して実験を行う．
NDP
NDP:
min f1 =−x1 min f2 =−x2
... min fn−1 =xn−1 min fn =xn s.t.
gj =−xj(j= 1,2,· · ·, n) gn+k =xk−6(k= 1,2,· · ·, n) g2n+1= 1−x1×x2× · · · ×xn
(5.3)
式(5.3)に表されるNDPは，非常に単純な関数である．この関数の最大の特徴は，n
次元への拡張が容易に行え，問題の難易度を設定することができることである．また，式
(5.3)の制約式g2n+1がパレート最適フロントを形成するため，得られた非劣解の誤差を求
めることができる．
VB3
VB3:
minf1(x) = 0.5(x21+x22) + sin(x21+x22) minf2(x) =(3x1−2x2+ 4)2
8 +(x1−x2+ 1)2
27 + 15
minf3(x) = 1
x21+x22+1−1.1 exp(−x21−x22) s.t.
g1(x) =x1 ≥ −3 g2(x) =x2 ≤3
(5.4)
VB3は式(5.4)で表され，Veldhuizenらの論文で用いられていた3目的2変数の最小化
問題である36）．この例題の最大の特徴は，3つ目の目的関数式にある．3つ目の目的関数式 における最小値は，(x1, x2) = (0.0,0.0)のとき，f3(x) =−0.1であるが，設計変数の値が非 常に大きくなった場合（ 例えば，(x1, x2) = (∞,−∞)）にも，最小値に近似のf3(x) = 0.0 という値を得る．そのため，初期段階，および 探索の中盤段階でこのような設計変数の値
-6 -5 -4 -3 -2 -1 0 -6
-5 -4 -3 -2 -1 0
-6 -5 -4 -3 -2 -1 0
-6 -5 -4 -3 -2 -1 0
-6 -5 -4 -3 -2 -1 0
-6 -5 -4 -3 -2 -1 0
f1(x) f2(x)
f1(x) f2(x)
f1(x)
f2(x) DRMOGA
SGA DGA
図5.10 Pareto optimum individuals(NDP)
ばかりに個体が優越された場合，最終的に非劣解は広がらず，パレート最適解に近似した 値を得ることもできない．
さらにもう1つの問題として，パレート最適解全体が偏っていることが挙げられる．目的関 数2（f2(x)）は，f2(x)∈[15,17.5]までの値をとるにも関わらずパレート最適解全体として はf3(x) = 15付近に集中するような形態を持っているのである．そのためf2(x)∈[15,17.5]
の区間のパレート最適解を得ることが困難なのである．
なお,用いたパラメータは先ほど と同様の表 5.1を使用した．なお，DRMOGAにおけ るソート間隔sは，表 5.1における移住間隔と同値を用いた．
結果
得られた結果とし て，10試行の試行ご とに 得られた全ての非劣解集合のプ ロットを図 5.10，図 5.11に示す．VB3は特にf2(x)軸に関する探索が難しいという特徴を持つため，
f2(x)を横軸,f3を縦軸にとったプ ロット図を図 5.12に示す．また，NDPにおける誤差を 図 5.13に3 ，NDPおよびVB3の被覆率を図 5.14に示す．
3VB3のパレ ート 最適解は未知であるので，得られた非劣解とパレート最適解との誤差は評価できない.
0 2 4 6 8 15.515
16.516 17.517
–0.1 0 0.1
0 2 4 6 8
15.515 16.516 17.5–0.117
0 0.1
0 2 4 6 8
15.515 16.516 17.5–0.117
0 0.1
f1(x) f2(x)
f3(x)
f1(x) f2(x)
f3(x)
f1(x) f2(x)
f3(x)