進化的計算手法による 多目的最適化 廣安 知之 三木 光範 渡邉 真也 同志社大学

最適化問題 目的関数 F(x) 制約条件 g j (x)(j=1,2,…k) 設計変数 x={ x 1,x 2,….,x n }

多目的最適化 複数の目的（基準）を考慮しながら， その中で最適な解を求める． ・多目的最適化とは・・・ Ex ） 車の購入 選考基準は・・ ・車種 ・性能（排気量） ・価格 ・外観 ・メーカ名 など どれが良いかな？

売上高 １．三井物産 ２．三菱商事 ３．トヨタ自動車 ４．伊藤忠商事 ５．住友商事 ６．日本電信電話 ７．丸紅 ８．日立製作所 ９．松下電器産業 １０．日商岩井 経常利益 １．日本電信電話 ２．トヨタ自動車 ３．エヌ・ティ・ティ・ドコモ ４．東京電力 ５．武田製薬工業 ６．ブリジストン ７．関西電力 ８．三共 ９．セブン・イレブン・ジャパン １０． JT 週間ダイヤモンド ２０００年１０ / ７号

売上高経常利益率 １．立飛企業 ２．小野製薬工業 ３．キーエンス ４．セブン・イレブン・ジャパン ５． SANKYO ６．ユーエスエス ７．大和工業 ８．ローム ９．ヒロセ電機 １０．大正製薬 週間ダイヤモンド ２０００年１０ / ７号 不動産賃貸業（必要経費がかからない） 財務的マネジメントがうまい 競争力のある商品を扱っている

文科省の重点プロジェクト 生命科学航空宇宙環境物質材料 地震防災

DEEP BLUE BLUE GENE (1PetaFLOPs) チェスの世界チャンピオン，カスパロフを 破った 他の分野でもこれに比肩する偉業が達成される可能性 “ タンパク質の構造解析 ” にチャレンジ！！ コンピュータの設計およびアーキテクチャに対して 従来とはまったく異なるタンパク質に適したアプ ローチをとる IBM のチャレンジ

最適化の未来 ますます必要になる 従来とは違う分野の開拓が必要 計算機資源の拡大に伴い、対決をせまられている

進化的計算手法による多目的最適 化の概要 各種アプローチの概要 進化的計算手法の抱える問題点と その解決方法の現状 進化的計算手法の並列処理 進化的計算の最近の動向？？ 進化的計算手法による多目的最適化

多目的最適化問題 ● Multi-Criterion Optimization Problems (MOPs) 設計変数 目的関数 制約条件 G i (x)<0 ( i = 1, 2, …, k) F={f 1 (x), f 2 (x), …, f m (x)} X={x 1, x 2, …., x n }

パレート最適解集合 f 2 (x) f 1 A BC f 2 Feasible region f 1 (x) Weak pareto optimal solutions Pareto optimal solutions

進化的計算手法 （ Evolutionary Multi-criterion Optimization: EMO ） による多目的最適化 生物の遺伝と進化の仕組み 確率的探索手法 多点探索 パレート解集合（多点集合）を求めるのに適している．

遺伝的アルゴリズム Iteration End (Find solution) Start (Initialization) Crossover Mutation Selection Evaluation crossover individuals mutation population

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 EMO 各手法

VEGA ベクトル評価遺伝的アルゴリズム （ Vector Evaluated Genetic Algorithms: VEGA ） t 世代 個体集合 t+1 世代 部分個体集合 選択交叉・突然変異

ランキング法 Ranking Rank ＝ １＋ number of dominant individuals f 2 f Pareto optimal solutions

f1 (x) 1 st generation 5 th generation 10 th generation f 2 (x) Pareto optimal solutions 50 th generation GA によるパレート解集合の探 索 30 th generation

探索に必要なメカニズム 真のパレート解集 合への接近 広い範囲での 解の分布 より少ない個体数で のパレート解集合の 表示（解が集中しな い）

真のパレート解集合への接近 ローカルサーチ エリート保存 個体からパレートフロントへの適切な距離 設定 制約条件 その他

個体の引き戻し（ 1 ） 制約条件境界 ＝ 真のパレート解 交叉･突然変異の結果 – 制約条件外の 個体を条件内 に引き戻す より精度の良い 個体を得る 制約条件外制約条件内 交叉・突然変異 f2f2 f1f1

広い範囲での解の分布 グローバルサーチ VEGA 各目的関数の最適解 その他

f1f1 f2f2 Real Pareto Solutions ランダム 初期個体 f 2 ：最適解 初期個体 f 1 ：最適解 初期個体 各目的関数の最適値をあらか じめ挿入する手法 パレートランキング法（パレート的） に VEGA （非パレート的）の特長を取り 入れる

解の多様性 シェアリング その他

個体間距離ｄを導入し （ σ share は適応度を割り引く近傍の大きさを調整するパラメータ） この s(d) を用いて適応度 f i s を次式で変換 シェアリング 選択後 f 1 (x) f 2 含有個体数＝ 5 f 1 (x) f 2 選択前

個体数の決定 シェアリング半径 終了条件 評価方法 表示方法 テスト関数 その他 EMO の問題点

得られたパレート解集合の図示（ 3 次元ま で） 得られたランク１の数 複数手法で得られた総パレート個体の再ラ ンキングと生存率 誤差 被覆率 必要な計算時間 各目的関数の最大値と最小値 その他 評価方法 精度 広がり 多様性

再ランキングによる生存率 個体を再評価し，どの程度の個体が再 びパレート解となったか．その割合． f2f2 f1f1 手法 1 手法 2 非パレート解 個体数前後 手法 1 53 手法 2 54 手法 1 手法 2 生存率 60%80%

被覆率の評価方法 被覆率 (f 1 )=8/10=0.8 f 1 (x) f 2 被覆率 (f 2 )=9/10=0.9 f 1 (x) f 2 被覆率 いかに真のパレート解を幅広く，かつ隙間無く 求めているかに関する評価項目． 最大値「 1 」 に近いほど 良い解

連続問題 テスト問題 Tamaki et al. (1995) Veldhuizen and Lamount (1999) K. Deb (1999) 離散問題 E. Zitzler (1998) ナップサック問題

Tamaki et al. (1995) Objective functions Constraints

Veldhuizen and Lamount (1999) Objective functions Constraints f1f1 f3f3 f2f2

f1f1 f2f2 K. Deb (1999) Objective functions ・・・ x1x1 f1f1

1 101),,( 2 2     N x xxg N i i N ・・・ K. Deb (1999) Objective functions f1f1 f2f2

0/1 ナップサック問題 0/1 ナップサック問題とは， – ナップサック → “ 制約条件 ” – 荷物（ item ）のセット → “ 重量 ” と “ 価値 ” – 総価値が最大 多目的 0/1 ナップサック問題 – 複数のナップサックと荷物のセット – 代表的なテスト問題

分散 GA モデル マスタ･スレーブモデル セルラ GA モデル その他 EMO の並列化 SW-HUB

DGA model f 1 (x) f 2 f 1 f 2 f 1 f 2 Island 1 Island 2

単目的 GA 多目的 GA f ｘ f １ （ｘ ） f 2 （ｘ ） 多様性の維持 局所探索 多様性の維持・局所探索

f (x) f 1 2 Division 1 Division 2 Max Pareto Optimum solution Min f 1 (x) f 2 Division 1 f 1 (x) f 2 Division 2 Divided Range Multi-Objective GA(1) 1 st The individuals are sorted by the values of focused objective function. 2 nd The N/m individuals are chosen in sequence. 3 rd SGA is performed on each sub population. 4 th After some generations, the step is returned to first Step

f 2 (x) f 1 (x) f 2 (x) f 1 (x) ・ DGA( Island model) ・ DRMOGA f 2 (x) f 1 (x) f 2 (x) f 1 (x) + = f 2 (x) f 1 (x) f 2 (x) f 1 (x) + = Divided Range Multi-Objective GA(2)

Master-Slave model with Local Cultivation 全個体を入れ替えた時点で 1 世代終了

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, , (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 state- of the art”, evolutionary computation, vol. 8, no. 2, (2000), , summer 2000 Zitzler, Deb and Thiele, “Comparison of multiobjective evolutionary algorithms: Empirical results”, Evolutionary Computation, vol. 8, no. 2, , 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, , Reviews

GECCO IEEE CEC EMO その他 国際会議 Web

EMO の今後  重要な実問題への適応  制約条件を目的関数としての取り扱い （ Robust)  平行処理  その他

個体の引き戻し（ 2 ） 0/1 ナップサック問題では， 重量制限を超えた場合 – ナップサックに入っている荷物から ランダムに荷物を減らす 制約条件内に収まる個体を得る

対象問題と GA パラメータ 対象問題 100 荷物 2 目的ナップサック問題 GA オペレータ・パラメータ 終了世代個体数交叉率突然変異率 選択手法交叉突然変異 パレート保存戦略一点交叉ビット反転

数値実験結果（ 1 ）

パレート解の評価と考察 パレート個体数 個体を引き戻した方が， より良いパレート解集合を得ることが 可能 再評価前再評価後生存率 Delete % Pull back %

多目的 GA の評価・選択 2 種類のアプローチ パレート的アプローチ – パレート最適性を明示的に評価する – パレートランキング法 非パレート的アプローチ – パレート最適性を明示的に評価しない –VEGA

数値実験結果（ 2 ）

パレート解集合の評価 被覆率 個体数と再評価後の生存率 従来の手法 34% 提案手法 56% 再評価前再評価後生存率 従来の手法 % 提案手法 %

数値実験結果（ 3 ）