高実用性を志向した遺伝的
アルゴリズムの開発,
および
多目的最適化へのアプローチ
渡邉 真也(同志社大学大学院)
Intelligent Systems Design Laboratory,
Doshisha University,Kyoto Japan
Doshisha Univ., Kyoto Japan
はじめに
発表内容
• 分散GAのiSight への実装
• 遺伝的アルゴリズムGAの概説
• 分散GAの概説
• 数値実験比較
• テスト関数による実験比較
• ディーゼルエンジン噴射スケジュール最適化
• 多目的最適化へのアプローチ
• 多目的最適化の概説
• 多目的GAの概説
• 多目的GAの適用例
Doshisha Univ., Kyoto Japan
背景
• 最適化は大きく2つの要素からなる
Optimizer
様々な手法に基づいて
探索点を決定
(例)変分法,動的計画法,
山登り法,線形計画法,
GA,SAなど
Analyzer
提示された探索点の評価値
を求める .つまり,対象とし
ている問題の評価.
Doshisha Univ., Kyoto Japan
遺伝的アルゴリズム
• 遺伝的アルゴリズム (Genetic Algorithm: GA)
– 生物の進化を模倣した最適化アルゴリズム
交叉
遺伝子を組み替えて新しい個体を生成
個体間の情報交換
突然変異
親個体が持たないビットを生み出す
母集団内の多様性の維持
選択
環境に適合した個体ほど
子孫を残しやすい
Doshisha Univ., Kyoto Japan
遺伝的アルゴリズム
• GAの特徴
利点
•
•
•
•
ほぼ全ての最適化問題に適用可能(汎用性)
コーディングが比較的容易
一般的にそこそこ良質な解が得られる
大域的探索を行うことができる
短所
•
•
•
•
計算コストが高い
最適解の保証が無い(ヒューリスティック)
設定パラメータが多い
コーディングに規範がなくプログラマの経験による部分が多
い
Doshisha Univ., Kyoto Japan
分散GAのiSightへの実装
• iSight に実装されていたGA
Bäckが1992年に公開したGENEsYs
最新の研究の結果が反映されていない.
分散GA (島モデル)
:母集団を複数の母集団に分割し,各島毎でGAを行う.
分散GAがGENEsYsと比べ
より有効な最適化手法であることを示す.
分散GAのiSightへの実装を目指す
Doshisha Univ., Kyoto Japan
分散GA
分散GA (Distributed GA:DGA)
• 母集団を幾つかのサブ母集団に分割
• サブ母集団ごとに各々GAが行われる
サブ母集団
個体
母集団
Doshisha Univ., Kyoto Japan
分散GA
移住
• 一定期間ごとに幾つかの割合の個体を交換
• 早熟収束の回避と多様性の維持を行う
Doshisha Univ., Kyoto Japan
分散GAの特徴
• 並列処理との親和性が高い
• 多様性の維持による解の精度の向上
• 移住操作により全体としての多様性が向上
• 移住操作に伴うパラメータの増加
Doshisha Univ., Kyoto Japan
数値実験(テスト関数)
• GENEsYsと分散GAの比較
• 7つの代表的なテスト関数を用いて性能を比較
Evaluation value
Rastrigin(10次元)
Schwefel(10次元)
0.00E+00
0.00E+00
-5.00E-01
-5.00E-01
-1.00E+00
-1.00E+00
-1.50E+00
-1.50E+00
-2.00E+00
-2.00E+00
GENEsYs
GENEsYs
-2.50E+00
分散GA
-2.50E+00
分散GA
-3.00E+00
-3.00E+00
0
50000
100000
150000
Number of evaluations
200000
0
50000
100000
150000
200000
Number of evaluations
分散GAはGENEsYsよりも高い解探索能力を持つ
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
対象問題
ディーゼルエンジンの燃料噴射スケジュール最適化
利点: 燃費がよい
耐久性が高い
欠点: 環境への悪影響
(NOx,すすの排出量が多い)
燃料の噴射特性を
変更することで削減可能
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
噴射率
HIDECS
分散GA
燃費,NOx,SMOKE
噴射率:燃料噴射量の時間的変化
HIDECS:ディーゼル燃焼のシミュレータ
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
目的
窒素 (NOx)排出量の最小化
制約
燃費 SFC (200以下)
すす SMOKE (0.25以下)
設計変数
クランク角 –5°から 13°における燃料噴
射のスケジュール
•6つの矩形により36分割された噴射スケジュールを表す
•扱う変数は,各矩形の縦・横の長さであり計12個ある
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
パラメータ
母集団
100
交叉率
1.0
交叉法
1点交叉
突然変異率
エリート個体数
0.01
5
島数
10
移住率
0.5
移住間隔
5
制約
SFC
SMOKE
< 200
< 0.25
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
多段噴射: NOx排出量を削減すると経験的に知られている
実問題においても良好な結果が得られた
Doshisha Univ., Kyoto Japan
多目的最適化へのアプローチ
• 現実の最適化では,扱う目的が複数である場合が
多い
– 各目的同士がトレードオフの関係にある場合
多目的最適化問題
複数の評価基準を同時に最適化
多目的最適化問題を解くことにより
各目的同士の関係を把握することができ,
より満足した解が得られる.
Doshisha Univ., Kyoto Japan
多目的最適化
• ディーゼルエンジン噴射最適化の場合
評価する目的
•SFC(燃費)最小
(Specific Fuel Consumption:SFC)
•NOx(窒素酸化物)排出最小
•SMOKE(すす)排出最小
これらの目的間に何らかのトレードオフ関
係があることは確認されている.
本来は多目的最適化問題である.
Doshisha Univ., Kyoto Japan
多目的最適化
●多目的最適化問題
(Multi-objective Optimization Problems :MOPs)
評価関数
・パレート最適解
複数存在
better
燃料噴射スケジュール
=[x1,x2,...,x12]
Feasible region
Pareto optimal solutions
NOx
設計変数
[g/kW h]
Min f1(X)=SFC
f2(X)=NOx
better
GAの多点探索が有効
SFC
[g/kW h]
Doshisha Univ., Kyoto Japan
GAによる多目的最適化への応用
・多目的GA
f2(x)
GAを用いてパレート最適解集合
の探索を行う
f1(x)
Doshisha Univ., Kyoto Japan
多目的進化的手法 (EMO)
• EMO
Evolutionary Multi-criterion Optimization
EMOにおける代表的手法
•VEGA
Schaffer (1985)
•MOGA
Fonseca (1993)
•DRMOGA Hiroyasu, Miki, Watanabe (2000)
•SPEA2
E. Zitzler, M. Laumanns (2001)
•NPGA2
Erickson, Mayer, Horn (2001)
•NSGA-II Deb, Goel (2001)
Doshisha Univ., Kyoto Japan
近傍培養型GA
• 近傍培養型GA
NCGA ~Neighorhood Cultivation GA~
従来までの探索に効果的な手法に近傍交叉を加えたモデル
特徴
• 近傍交叉
•
•
•
•
•
探索した優良解の保存
パレート保存個体群の利用
保存している優良個体の削減
探索個体に対する適合度割り当て
各目的スケールの正規化
Doshisha Univ., Kyoto Japan
近傍培養型GA
• 近傍交叉
f2(x)
– 多目的では,対象とする目的関数空間が広く
各個体ごとに探索している解領域が異なっている.
近傍でない個体と交叉を行っても,
効果的な探索は期待できない.
f1(x)
Doshisha Univ., Kyoto Japan
近傍培養型GA
• 近傍交叉
f2(x)
• 近傍同士のペアによる交叉
– 個体のソートを行う.
毎世代ペアが異なるよう
確率的な変動を加える.
f1(x)
Doshisha Univ., Kyoto Japan
適用手法とパラメータ
適用手法
GAオペレータ
• 交叉方法
• SPEA2
• NSGA-II
• NCGA
– 1点交叉
• 突然変異
– ビット反転
パラメータ
個体数
交叉率
突然変異率
終了世代
試行回数
100
250
1.0
0.01
250
2000
30
Doshisha Univ., Kyoto Japan
対象問題
• 連続関数テスト問題
– ZDT4
min
f1 ( x)  x1
min

x1 

f 2 ( x)  g ( x)  1 

g
(
x
)


10
g ( x)  91  xi  10 cos(4xi )
2
i 2
x1  [0,1]
xi  [5,5]
Doshisha Univ., Kyoto Japan
数値結果 (ZDT4)
• NCGAは,他手法に比べよ
り真のパレート解に近い分
布を示している.
Doshisha Univ., Kyoto Japan
対象問題
• 連続関数テスト問題
– KUR
min
min
f1 ( x)  i 1 (10exp(0.2 xi  xi 1 ))
100
2
2
f 2 ( x)  | xi |0.8 5 sin(xi )3 
xi  [5,5] , i  1,, n n  100
Doshisha Univ., Kyoto Japan
数値結果 (KUR)
• NCGAは,他手法に比べよ
り真のパレート解に近く幅
広い分布が得られている.
Doshisha Univ., Kyoto Japan
対象問題
• 多目的0/1ナップザック問題
– (750荷物2目的 : KP750-2 )
目的関数
制約条件
m
f i ( x )   pi , j  x j
j 1
m
 1,2,, n :  wi , j  x j  ci
j 1
x  ( x1, x2 ,, xm )  0,1m
pi , j  ナップザック iの荷物jにおける利益
wi , j  ナップザック iの荷物jにおける重量
ci  ナップザック iの許容重量
Doshisha Univ., Kyoto Japan
数値結果 ( KP750-2 )
• NCGAは,他手法に比べよ
り幅広い分布が得られてい
る.
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
評価関数
窒素 (NOx)排出量の最小化
燃費 (SFC)の最小化
すす(SMOKE) の最小化
設計変数 クランク角 –5°から 13°における燃料噴
射のスケジュール
パラメータ
•適用手法
個体数
NCGA
交叉率
突然変異率
3目的から形成される
終了世代
パレート解を探索し,
試行回数
各目的間の関係を把握する
100
1.0
0.01
100
10
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
•得られた3次元のパレート面
各目的間において
トレードオフが存在
している.
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
•各目的最小解における
噴射スケジュール
NOx Best
SFC:299.6
NOx:0.4309
SMOKE:0.1539
SFC Best
SFC:183.7
NOx:1.743
SMOKE:0.2605
SMOKE Best
SFC:267.8
NOx:1.05
SMOKE:0.09924
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
•SFC – NOx 間におけるトレードオフ
1
[SFC:183.7, NOx:1.74]
2
[SFC:184.43, NOx:1.51]
3
[SFC:196.13, NOx:0.78]
Doshisha Univ., Kyoto Japan
数値実験 (ディーゼルエンジン噴射スケジュール最適化)
•SFC – NOx 間におけるトレードオフ
4
5
[SFC:231.47, NOx:0.66] [SFC:275.365, NOx:0.49]
6
[SFC:299.556, NOx:0.43]
Doshisha Univ., Kyoto Japan
まとめ
• 分散GAのiSightへの実装
– テスト関数を用いて分散GAとGENEsYsの比較実験
• 分散GAは,使用した全てのテスト関数で良好な結果を示した.
– ディーゼルエンジン噴射スケジュール問題への適用
• 分散GAは,GENEsYsに比べ探索速度が速く結果も優れていた.
• 多目的最適化へのアプローチ
– GAを用いた多目的最適化では,一度の探索でパレート解が
得られる
– 近傍培養型GA (NCGA)の多目的ディーゼルエンジン噴射スケ
ジュール問題への適用
• 各目的間のトレードオフの関係を把握することができた.
Doshisha Univ., Kyoto Japan
補足
GAのパラメータ(現在のiSIGHT)
GAの最大の問題点:パラメータ設定の困難さ
現在のiSIGHTのパラメータ
Basic Parameters →設定が比較的容易.ユーザによる試行錯誤が可能なレベル
母集団サイズ(Population Size)
最大評価計算回数(Max Number of Evaluation)
Advanced Parameters →設定が困難.GAに関する専門的な知識が要求される
交叉率(Crossover Rate)
突然変異率(Mutation Rate)
ジェネレーションギャップ(Generation Gap Size)
Max value for ranking
Small Creep Seeding,Small Creep % Variance,Small Creep Probability
Large Creep Seeding,Large Creep % Variance,Large Creep Probability
Boundary Seeding %,Boundary Probability
Doshisha Univ., Kyoto Japan
補足
過去の研究に基づきパラメータの推奨値を設定
•分散GAにおける推奨パラメータ
母集団
100
世代数
100
交叉率
1.0
交叉法
2点交叉
突然変異率
選択手法
エリート個体数
島数
移住率
移住間隔
ユーザーの設定すべきパラメータは
探索時間に関わる世代数のみ
1 / 染色体長
トーナメント選択
(トーナメントサイズ4)
5
各島の個体数を10と固定
(島数=母集団サイズ / 10)
0.5
5
Doshisha Univ., Kyoto Japan
補足
•テスト関数実験に用いたパラメータ
母集団
100
交叉率
1.0
交叉法
2点交叉
突然変異率
選択手法
0.01
トーナメント選択(サイズ4)
エリート個体数
5
島数
10
移住率
0.5
移住間隔
5
試行回数
20試行平均
設計変数
10次元
対象問題
Rastrigin,Schwefel
Doshisha Univ., Kyoto Japan
補足
• 発表に用いたソースプログラム
– http://mikilab.doshisha.ac.jp/dia/downloa
d/index.html
• 進化的手法を用いた多目的全般に関して
– http://www.lania.mx/~ccoello/EMOO/EMO
Obib.html
• 多目的0 /1ナップザック問題に関して
– http://www.tik.ee.ethz.ch/~zitzler/
• 発表者の電子メールアドレス
– [email protected]
Doshisha Univ., Kyoto Japan
ダウンロード

PPT