多目的GAのための分散協力型モデル

第 51 回 月例発表会（ 2002 年 7 月）
知的システムデザイン研究室
多目的 GA のための分散協力型モデル
DCMOGA: Distributed Cooperation model of Multi Objective Genetic Algorithms
奥田 環
Tamaki OKUDA
Abstract: In this paper, a new algorithm of Genetic Algorithm for Multi-Objective Optimization
Problems, called Distributed Cooperation model of MOGA (DCMOGA), is proposed. In the proposed algorithm, there are several sub populations. One of them is for finding a Pareto optimum set
and the others are for finding an optimum solution of one of the objectives. These sub populations
sometimes exchange their searching information respectively. The proposed algorithm is applied to
some MOPs. Comparing to the conventional multi objective optimization methods, the proposed
model found the better and much widespread Pareto solutions.
1
MOGA Group
はじめに
SPEA
MOGA
多目的最適化問題において非劣解集合を求める場合，
得られた解が目的関数もしくは設計変数空間上の広範囲
かつパレート最適解付近に求まっていることは重要な要
DGA
素といえる．広範囲に広がる解を求めるためには，次の
DGA
2 つの要素が必要である．すなわち，解が集中するので
はなく均等に存在すること，各目的関数を単一目的とし
た際の最適解が得られていることである．
SOGA(F1) Group
そこで本研究では，解の広がりを持った非劣最適解の
SOGA(F2) Group
Fig. 1 DCMOGA
探索を目的とし，各目的関数の最適解の探索と非劣解集
合の前進を同時に行う新たな多目的分散 GA モデルを提
案する．提案モデルに代表的な多目的 GA の手法を組み
3.2
込み，解探索能力の変化について検証する．
2
GA パラメータ
各個体は，全ての問題においてビットコーディングを
用いた．また，各問題におけるビット長は，KP750-m で
分散協力型モデル (DCMOGA)
は 750 ビットを，他の問題では設計変数数× 20 とした．
さらに，交叉方法として 2 点交叉，突然変異にはビット
提 案モデ ル で あ る多 目的分 散協 力型モデ ル（ Dis-
反転を用いた．
tributed Cooperation model of MOGA : DCMOGA ）
本研究で用いた GA パラメータは，個体数および 終
は，多目的 GA を行う個体群 (MOGA 個体群) と各目的
了条件が，文献
間数における最適解を探索する個体群（ SOGA 個体群）
1)
を参考に Table 1 のように設定した．
を用いて解探索を行う．また MOGA 個体群，SOGA 個
また，多目的個体群と各手法での GA パラメータは同様
体群で得られた解の交換や各個体群の個体数を増減さ
の値を用い，試行回数は 30 とした．
せることにより，協調探索を実現している．そのため，
DCMOGA を用いることで，より広範囲に分布し，かつ
KP750-2
KP750-3
KUR
ZDT4,6
SPH-m
500000
600000
1000
250
10000
精度の高い非劣解集合の探索を期待することができる．
DCMOGA の 2 目的の場合の様子を Fig. 1 に示す．
3
Table 1 Terminal condition
数値実験
3.3
3.1
対象問題
評価方法
得られた非劣解集合に対する評価方法は，適用したモ
対象問題には，荷物数が 750 ，目的数が 2,3 のナップ
デルの定量的な評価を行う上で必要不可欠である．これ
サック問題 (KP750-m) ，SPH-2，KUR，ZDT4,6，以上
までに，進化的多目的最適化の分野においても幾つかの
の 6 つの問題を用いた．
手法が提案されている
1
2)
．
本研究では，Ziztler の提案する Coverage を評価方法
として用いた
3.3.1
3)
．
Coverage of two sets
集合 A,B いおいて，Coverage(C) は次のように表さ
れる．
| {b ∈ B | ∃a ∈ A : a b} |
|B|
C(A, B) :=
(1)
Fig. 6 plot(DC)
C は [0, 1] であり，C(A, B) = 1 の場合，集合 B は集
合 A によって優越されている．一方，C(A, B) = 0 の場
0
0.33
合，集合 B には，集合 A によって優越されている解が
Fig. 7 plot(non-DC)
4.0E-3
0.67
ないことを示している．
0
0.26
7.2E-3
0.74
3.3.2
Coverage difference of two sets
0
0.20
0.80
集合 A,B いおいて，Coverage(D) は次のように定義
0
される．
D(A, B) := S(A + B) − S(B)
(2)
Fig. 8 Coverage(C)
Fig. 9 Coverage(D)
S(X) は 集 合 X の 個 体に 優 越され た 領 域で あ り，
D(A, B) は B には優越されず，A に優越されている領域
サイズを表す．D は一般的に S(X) とともに用いられる．
ZDT4 に適用した場合にも，より精度の高い非劣解集
合を得ていることが，Fig. 6，Fig. 7 からわかる．これ
は Fig. 8，Fig. 9 からもわかる．
数値実験結果
3.4
これらから，SOGA 個体群による探索が MOGA 個体
提案する DCMOGA に MOGAs，SPEA2，NSGA-II
群に良い影響を及ぼしていると考えられる．
を組み込んだモデル，および各手法のみで数値実験を
4
行った結果を以下に示す．ここでは，KP750-2 ，ZDT4
に適用した結果得られた非劣解集合のプロット図，およ
結論
提案手法である DCMOGA に幾つかの多目的最適化
び Coverage を用いた評価結果を示す．
手法を組み込み，そのそれぞれの探索能力の変化をを検
証した．
数値実験結果から，DCMOGA に各手法を組み込ん
だ場合，非劣解集合はより幅広く分布し，その精度もほ
ぼ同等程度であることが多い．特にパレートフロントの
両端が得られにくい問題では，SOGA 個体群を導入に
よって広域に分布する非劣解集合を得ることができた．
Fig. 2 plot(DC)
これにより，DCMOGA を用いた非劣解集合の探索は有
Fig. 3 plot(non-DC)
効な探索であり，本提案モデルは有効的なモデルである
0.73
7.2E-4
0.27
6.9E-3
0.85
0.15
1.9E-3
C(DC,nonDC)
3.5
1) E. Zitzler and M. Laumanns and L. Thiele. SPEA2:
Improving the Performance of the Strength Pareto Evolutionary Algorithm
Technical Report 103, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich, 2001
0
5.4E-2
1.0
Fig. 4 Coverage(C)
参考文献
1.9E-3
C(nonDC,DC)
0.0
と言える．
Fig. 5 Coverage(D)
2) Kalyanmoy Deb. Multi-Objective Optimization using
Evolutionary Algorithms
Chichester, UK : Wiley, 2001
考察
Fig. 3 からわかるように，NSGA-II 単体では広域に分
3) E. Zitzler. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications Swiss
Federal Institute of Technology (ETH) Zurich. TIKSchriftenreihe Nr. 30, Diss ETH No. 13398, Shaker Verlag, Germany, ISBN 3-8265-6831-1, 1999
布する非劣解集合を得られていない．それに対し ，Fig.
2 では得られた非劣解集合が幅広く分布していることが
わかる．Fig. 5 で DCMOGA が優位な結果となったの
は，非劣解集合が広がっているためである．
2