進化的計算手法による多目的最適化

進化的計算手法による
多目的最適化
廣安知之
三木光範
渡邉真也
同志社大学
最適化問題
目的関数
F(x)
制約条件
gj(x)
(j=1,2,…k)
設計変数
x={x1,x2,….,xn}
多目的最適化
・多目的最適化とは・・・
複数の目的（基準）を考慮しながら，その
中で最適な解を求める．
Ex）車の購入
選考基準は・・
・車種
・性能（排気量）
・価格
・外観
・メーカ名など
どれが良いかな？
売上高
１．三井物産
２．三菱商事
３．トヨタ自動車
４．伊藤忠商事
５．住友商事
６．日本電信電話
７．丸紅
８．日立製作所
９．松下電器産業
１０．日商岩井
経常利益
１．日本電信電話
２．トヨタ自動車
３．エヌ・ティ・ティ・ドコモ
４．東京電力
５．武田製薬工業
６．ブリジストン
７．関西電力
８．三共
９．セブン・イレブン・ジャパン
１０．JT
週間ダイヤモンド２０００年１０/７号
売上高経常利益率
１．立飛企業
２．小野製薬工業
３．キーエンス
４．セブン・イレブン・ジャパン
５．SANKYO
６．ユーエスエス
７．大和工業
•不動産賃貸業（必要経費がかからない）
８．ローム
•財務的マネジメントがうまい
９．ヒロセ電機
•競争力のある商品を扱っている
１０．大正製薬
週間ダイヤモンド２０００年１０/７号
文科省の重点プロジェクト
生命科学
航空宇宙
環境
物質材料
地震防災
IBMのチャレンジ
DEEP BLUE
チェスの世界チャンピオン，カスパロフを破った
他の分野でもこれに比肩する偉業が達成される可能性
BLUE GENE (1PetaFLOPs)
“タンパク質の構造解析”にチャレンジ！！
コンピュータの設計およびアーキテクチャに対して従来と
はまったく異なるタンパク質に適したアプローチをとる
最適化の未来
ますます必要になる
従来とは違う分野の開拓が必要
計算機資源の拡大に伴い、対決をせまられている
進化的計算の最近の動向？？
進化的計算手法による多目的最適化
進化的計算手法による多目的最適
化の概要
各種アプローチの概要
進化的計算手法の抱える問題点とそ
の解決方法の現状
進化的計算手法の並列処理
多目的最適化問題
●Multi-Criterion Optimization Problems (MOPs)
設計変数
X={x1, x2, …. , xn}
目的関数
F={f1(x), f2(x), … , fm(x)}
制約条件
Gi(x)<0 ( i = 1, 2, … , k)
パレート最適解集合
B
f2(x)
f2(x)
Weak pareto optimal solutions
A
Feasible
region
Pareto optimalCsolutions
f1(x)f1(x)
進化的計算手法
（Evolutionary Multi-criterion Optimization: EMO ）
による多目的最適化
生物の遺伝と進化の仕組み
確率的探索手法
多点探索
パレート解集合（多点集合）を求めるのに適している．
遺伝的アルゴリズム
Start
(Initialization)
Evaluation
crossover
individuals
Selection
Crossover
Iteration
Mutation
End
(Find solution)
mutation
population
EMO 各手法
VEGA Schaffer (1985)
VEGA+Pareto optimum individuals Tamaki (1995)
Ranking Goldberg (1989)
MOGA Fonseca (1993)
Non Pareto optimum Elimination Kobayashi (1996)
Ranking + sharing Srinvas (1994)
Others
VEGA
ベクトル評価遺伝的アルゴリズム
（Vector Evaluated Genetic Algorithms: VEGA）
選択
交叉・突然変異
部分個体集合
t世代
t+1世代
個体集合
個体集合
部分個体集合
ランキング法
f2
3
1
1
Pareto optimal solutions
f1
Ranking
Rank ＝１＋ number of
dominant individuals
GAによるパレート解集合の探索
5th
generation
1st generation
f2(x)
10th generation
30th generation
Pareto optimal solutions
f 1 (x)
50th generation
探索に必要なメカニズム
真のパレート解集合
への接近
より少ない個体数での
パレート解集合の表示
（解が集中しない）
広い範囲での
解の分布
真のパレート解集合への接近
ローカルサーチ
エリート保存
個体からパレートフロントへの適切な距離設定
制約条件
その他
個体の引き戻し（1）
• 制約条件境界＝真のパレート解
• 交叉･突然変異の結果
– 制約条件外の
個体を条件内
に引き戻す
f2
交叉・突然変異
より精度の良い
個体を得る
制約条件内
f1
制約条件外
広い範囲での解の分布
グローバルサーチ
VEGA
各目的関数の最適解
その他
各目的関数の最適値をあらかじ
め挿入する手法
• パレートランキング法（パレート的）に
VEGA（非パレート的）の特長を取り入れる
Real Pareto Solutions
f2
f2：最適解
初期個体
ランダム
初期個体
f1：最適解
初期個体
f1
解の多様性
シェアリング
その他
シェアリング
個体間距離ｄを導入し

d 
s(d )  max0,1 


sha re 

（σshareは適応度を割り引く近傍の大きさを調整するパラメータ）
このs(d)を用いて適応度fisを次式で変換
fi
fi 
N
j 1 s(d ( xi , y j ))
s
f2(x)
f2(x)
含有個体数＝5
選択前
選択後
f1(x)
f1(x)
EMOの問題点
個体数の決定
シェアリング半径
終了条件
評価方法
表示方法
テスト関数
その他
評価方法
精度
広がり
多様性
得られたパレート解集合の図示（3次元まで）
得られたランク１の数
複数手法で得られた総パレート個体の再ランキ
ングと生存率
誤差
被覆率
必要な計算時間
各目的関数の最大値と最小値
その他
再ランキングによる生存率
• 個体を再評価し，どの程度の個体が再び
パレート解となったか．その割合．
個体数
手法1
f2
手法1
非パレート解
手法1
生存率
後
5
5
手法2
手法2
f1
前
60%
3
4
手法2
80%
被覆率の評価方法
いかに真のパレート解を幅広く，かつ隙間無く
求めているかに関する評価項目．
0.8  0.9

2
 0.85
2
2
f (x)
f (x)
被覆率
f (x)
1
被覆率(f 1)=8/10=0.8
f (x)
1
被覆率(f 2)=9/10=0.9
最大値「1」
に近いほど
良い解
テスト問題
連続問題
•Tamaki et al. (1995)
•Veldhuizen and Lamount (1999)
•K. Deb (1999)
離散問題
E. Zitzler (1998)
ナップサック問題
Tamaki et al. (1995)
Objective functions
f1  2 x1
f2  x1 (1 x2 )  5
Constraints
x1  1 0 4  x1  0
x2 1  0 2  x2  0
Veldhuizen and Lamount (1999)
Objective functions
f1  0.5(x  x2 ) sin(x  x )
(3x1  2x2  4)2 (x1  x2 1)2
f2 

15
8
27
1
2
2
f3  2
1.1exp(x
x
2
1
2 )
x1  x2  1
Constraints
x1  3
x2  3
2
2
1
2
2
f3
2
1
f2
f1
K. Deb (1999)
f2
Objective functions
f1  1 exp(4x1 ) sin 6 (5x1 )
f2  gh
  f 2
1


1



h( f1 , g )    g  ,
 0,
if
0.25
f1  g
f1
f1
  xi 
 i 2 
g ( x2 ,・
・・, xN )  1  10
 N 1 


N
oherwise.
x1
K. Deb (1999)
Objective functions
f2  gh
g ( x2 , ・・・ , xN
f2
f1  x1

)  1  10
 f1 
h( f1, g )  1  
g
N
i 2
f1
xi
N 1
0.25
f1
 sin(10f1 )
g
0/1 ナップサック問題
• 0/1ナップサック問題とは，
– ナップサック → “制約条件”
– 荷物（item）のセット → “重量”と“価値”
– 総価値が最大
• 多目的0/1ナップサック問題
– 複数のナップサックと荷物のセット
– 代表的なテスト問題
http://www.tik.ee.ethz.ch/~zitzler/
EMOの並列化
分散GAモデル
マスタ･スレーブモデル
セルラGAモデル
その他
SW-HUB
Island 1
f2 (x)
f2(x)
f2 (x)
DGA model
f 1(x)
Island 2
f1(x)
f 1(x)
単目的GA
多様性の維持
局所探索
多目的GA
多様性の維持・局所探索
多様性の維持・局所探索
f(x)
2
f2(x)
Divided Range Multi-Objective GA(1)
Division 1
Division 1
f1(x)
f2(x)
Division 2
Division 2
Pareto Optimum solution
Min
Max
f1(x)
1st
The individuals are sorted by the values of focused objective function.
2nd The N/m individuals are chosen in sequence.
3rd SGA is performed on each sub population.
4th After some generations, the step is returned to first Step
f1(x)
Divided Range Multi-Objective GA(2)
f2(x)
f2(x)
f2(x)
・DGA( Island model)
=
+
f1(x)
f1(x)
f1(x)
f2(x)
f2(x)
f2(x)
・DRMOGA
=
+
f1(x)
f1(x)
f1(x)
Master-Slave model with Local Cultivation
全個体を入れ替えた時点で1世代終了
Reviews
Fonseca and Fleming: An Overview of Evolutionary Algorithms in
Multiobjective Optimization, Evolutionary Computation, 3(1), 1-16(1995)
Tamaki, Kita and Kobayashi: Multi-Objective Optimization by Genetic
Algorithms: A Review, Porc. of the 1996 IEEE International Conference
on Evolutionary Computation, 517-522, (1996)
Horn: Multicriterion Decision Making, in Back, Fogel and Michalewicz
(eds.): Handbook of Evolutionary Computation, Part F (section F1.9),
Oxford Univ. Press (1997)
Coello: An Updated Survey of Evolutionary Multiobjective Optimization
Techniques: State of the Art and Future Trends, Porc. of the 1999 IEEE
International Conference on Evolutionary Computation, 3-13, (1999)
Reviews
Veldhuizen, “Multiobjective evolutionary algorithms: analyzing the stateof the art”, evolutionary computation, vol. 8, no. 2, (2000), 125-147,
summer 2000
Zitzler, Deb and Thiele, “Comparison of multiobjective evolutionary
algorithms: Empirical results”, Evolutionary Computation, vol. 8, no. 2,
173-195, summer 2000
Ziztler Thiele, “Multiobjective evolutionary algorithms: A comparisonn
case study and the strength Pareto Approach”, IEEE Trans. On
Evolutionary Computation, vol. 3, no. 4, 257-271, 1999.
国際会議
GECCO
IEEE CEC
EMO
その他
Web
http://www.lania.mx/~ccoello/EMOO/EMOObib.html
EMOの今後
重要な実問題への適応
制約条件を目的関数としての取り扱い
（Robust)
平行処理
その他
個体の引き戻し（2）
0/1ナップサック問題では，
• 重量制限を超えた場合
– ナップサックに入っている荷物から
ランダムに荷物を減らす
• 制約条件内に収まる個体を得る
対象問題とGAパラメータ
対象問題
• 100荷物2目的ナップサック問題
GAオペレータ・パラメータ
選択手法
交叉
突然変異
パレート保存戦略
一点交叉
ビット反転
終了世代
200
個体数
100
交叉率
1.0
突然変異率
0.01
数値実験結果（1）
4000
3900
3800
Knapsack2
3700
3600
3500
3400
3300
3200
3100
3000
3000
3200
3400
3600
Knapsack1
3800
4000
pullback
4200
del
パレート解の評価と考察
• パレート個体数
再評価前再評価後生存率
Delete
23.1
4.8
21%
Pull back
32.4
27.8
86%
• 個体を引き戻した方が，
より良いパレート解集合を得ることが可能
多目的GAの評価・選択
2種類のアプローチ
• パレート的アプローチ
– パレート最適性を明示的に評価する
– パレートランキング法
• 非パレート的アプローチ
– パレート最適性を明示的に評価しない
– VEGA
数値実験結果（2）
4200
4000
knapsack2
3800
3600
3400
3200
3000
3000
3200
3400
3600
3800
knapsack1
4000
randam only
4200
4400
include optimical
パレート解集合の評価
従来の手法
• 被覆率
提案手法
34%
56%
• 個体数と再評価後の生存率
再評価前
従来の手法
提案手法
25.2
42.2
再評価後
14.4
31.2
生存率
57%
74%
数値実験結果（3）
4200
4000
knapsack2
3800
3600
3400
3200
3000
3000
3200
3400
3600
3800
4000
4200
4400
knapsack1
randam only
include optimical

Download Report