Doshisha Univ., Kyoto Japan

Doshisha Univ., Kyoto Japan
高実用性を志向した遺伝的アルゴリズムの開発，および多目的最適化へのアプローチ渡邉真也（同志社大学大学院） Intelligent Systems Design Laboratory， Doshisha University，Kyoto Japan Doshisha Univ., Kyoto Japan Thank you Chairperson. I’m Shinya Watanabe and a graduate student of Doshisha University in Kyoto Japan. Now I’m talking about our study, the title is “Parallel Evolutionary Multi-Criterion Optimization for Mobile Telecommunication Networks Optimization”.

はじめに発表内容分散GAのiSight への実装遺伝的アルゴリズムGAの概説分散GAの概説数値実験比較テスト関数による実験比較ディーゼルエンジン噴射スケジュール最適化多目的最適化へのアプローチ多目的最適化の概説多目的GAの概説多目的GAの適用例 Doshisha Univ., Kyoto Japan

背景最適化は大きく2つの要素からなる Optimizer Analyzer 提示された探索点の評価値を求める．つまり，対象としている問題の評価．様々な手法に基づいて探索点を決定（例）変分法，動的計画法，山登り法，線形計画法， GA，SAなど 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 (Distributed GA：DGA)
母集団を幾つかのサブ母集団に分割サブ母集団ごとに各々GAが行われるサブ母集団個体母集団 Doshisha Univ., Kyoto Japan

分散GA 移住一定期間ごとに幾つかの割合の個体を交換早熟収束の回避と多様性の維持を行う Doshisha Univ., Kyoto Japan

分散GAの特徴並列処理との親和性が高い多様性の維持による解の精度の向上移住操作により全体としての多様性が向上移住操作に伴うパラメータの増加 Doshisha Univ., Kyoto Japan

数値実験（テスト関数） GENEsYsと分散GAの比較 7つの代表的なテスト関数を用いて性能を比較 Rastrigin(10次元) Schwefel(10次元) 分散GAはGENEsYsよりも高い解探索能力を持つ Doshisha Univ., Kyoto Japan

数値実験 (ディーゼルエンジン噴射スケジュール最適化) 対象問題ディーゼルエンジンの燃料噴射スケジュール最適化利点：燃費がよい耐久性が高い欠点：環境への悪影響（NOx，すすの排出量が多い）燃料の噴射特性を変更することで削減可能 Doshisha Univ., Kyoto Japan

数値実験 (ディーゼルエンジン噴射スケジュール最適化) 分散GA HIDECS 噴射率燃費，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 移住間隔制約 SFC < 200 SMOKE < 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

Pareto optimal solutions
多目的最適化 ●多目的最適化問題 (Multi-objective Optimization Problems ：MOPs) 評価関数 Min f1(X)=SFC f2(X)=NOx Feasible region SFC [g/kW h] NOx [g/kW h] Pareto optimal solutions better 設計変数燃料噴射スケジュール =[x1,x2,...,x12] ・パレート最適解複数存在 GAの多点探索が有効 Doshisha Univ., Kyoto Japan

GAによる多目的最適化への応用・多目的GA GAを用いてパレート最適解集合の探索を行う f 2 (x) f 1 (x) Doshisha Univ., Kyoto Japan 多目的GAでは，SGAと同様交叉・突然変異を用いてパレート最適解集合を直接探索を行います．概念的には，図のように世代が進むに連れ徐々にパレート最適解に近づいていき，最終的に最も真のパレート解に近い解集合を得ることができるものと思われます．

多目的進化的手法（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 Multi-criterion optimization problems solved by Evolutionary algorithms are often called EMO. The study on EMO is not few. Many of the studies in this category get good results. These are a part of leading researches in this category. And There are many other researches in this category. Like this way, there are several models of multi objective GA and they can derive the good Pareto optimal solutions. In this study, MOGA method is used.

近傍培養型GA 近傍培養型GA NCGA ～Neighorhood Cultivation GA～従来までの探索に効果的な手法に近傍交叉を加えたモデル特徴近傍交叉探索した優良解の保存パレート保存個体群の利用保存している優良個体の削減探索個体に対する適合度割り当て各目的スケールの正規化 Doshisha Univ., Kyoto Japan On the other hand , As MSLC is one of the Master-Slave model , there are a few master processes and several slave processes. This model adopt the concept of Minimal Generation Gap model. This figure shows the concept of the MSLC. You can see, Master node and slave node repeatedly exchange two populations as sub populations each other. At first, in master process two individuals are chosen and are sent to a slave process. Secondly, slave process receives two individuals from master process and performs GA operators (cross over, mutation , evaluation and selection). After the selection, the selected two individuals are sent back to master process. After receiving two individuals from the slave process, master process substitute these individuals to old individuals. These operation is performed until all the individuals are sent and received . Therefore, One Loop is finished when all populations are exchanged to new ones. And the master process has pareto archive apart from search individuals. The reason is to prevent the lack of solutions that are looked on search.

近傍培養型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 交叉率 1.0 突然変異率 0.01 パラメータ終了世代 250 2000 試行回数 30 Doshisha Univ., Kyoto Japan 本発表で用いた手法は，SGA，DGA，NMSの3手法です．用いたパラメータ及び用いた各種GAオペレータを示します．

対象問題連続関数テスト問題 ZDT4 Doshisha Univ., Kyoto Japan

数値結果 (ZDT4) NCGAは，他手法に比べより真のパレート解に近い分布を示している． Doshisha Univ., Kyoto Japan

対象問題連続関数テスト問題 KUR Doshisha Univ., Kyoto Japan

数値結果 (KUR) NCGAは，他手法に比べより真のパレート解に近く幅広い分布が得られている． Doshisha Univ., Kyoto Japan

対象問題多目的0/1ナップザック問題 (750荷物2目的： KP ) 目的関数制約条件 Doshisha Univ., Kyoto Japan 多目的ナップザック問題はこのような式で定式されます．目的関数におけるpは利益を表しており，xは0もしくは1をとるベクトル，設計変数値です．xが1であるならばその荷物は選択され，0であれば選択されていないことを意味します．制約条件は，各荷物の総量が各ナップザックの許容重量以下であることを意味しています．

数値結果 ( KP750-2 ) NCGAは，他手法に比べより幅広い分布が得られている． Doshisha Univ., Kyoto Japan

数値実験 (ディーゼルエンジン噴射スケジュール最適化) 評価関数窒素 (NOx)排出量の最小化燃費 (SFC)の最小化すす(SMOKE) の最小化設計変数クランク角 –5°から 13°における燃料噴射のスケジュールパラメータ適用手法 NCGA 個体数交叉率突然変異率終了世代試行回数 100 1.0 0.01 10 3目的から形成されるパレート解を探索し，各目的間の関係を把握する Doshisha Univ., Kyoto Japan

数値実験 (ディーゼルエンジン噴射スケジュール最適化) 得られた3次元のパレート面各目的間においてトレードオフが存在している． Doshisha Univ., Kyoto Japan

数値実験 (ディーゼルエンジン噴射スケジュール最適化) Doshisha Univ., Kyoto Japan

数値実験 (ディーゼルエンジン噴射スケジュール最適化) 各目的最小解における噴射スケジュール SFC Best SFC:183.7 NOx:1.743 SMOKE:0.2605 NOx Best SFC:299.6 NOx:0.4309 SMOKE:0.1539 SMOKE Best SFC:267.8 NOx:1.05 SMOKE: Doshisha Univ., Kyoto Japan

数値実験 (ディーゼルエンジン噴射スケジュール最適化) SFC – NOx 間におけるトレードオフ [SFC:183.7, NOx:1.74] [SFC:184.43, NOx:1.51] [SFC:196.13, NOx:0.78] 1 2 3 Doshisha Univ., Kyoto Japan

数値実験 (ディーゼルエンジン噴射スケジュール最適化) SFC – NOx 間におけるトレードオフ [SFC:231.47, NOx:0.66] [SFC: , NOx:0.49] [SFC: , NOx:0.43] 4 5 6 Doshisha Univ., Kyoto Japan

まとめ分散GAのiSightへの実装テスト関数を用いて分散GAとGENEsYsの比較実験分散GAは，使用した全てのテスト関数で良好な結果を示した．ディーゼルエンジン噴射スケジュール問題への適用分散GAは，GENEsYsに比べ探索速度が速く結果も優れていた．多目的最適化へのアプローチ GAを用いた多目的最適化では，一度の探索でパレート解が得られる近傍培養型GA (NCGA)の多目的ディーゼルエンジン噴射スケジュール問題への適用各目的間のトレードオフの関係を把握することができた． Doshisha Univ., Kyoto Japan Now I’d like to show you the conclusions. In this study, We introduced and formulated antenna arrangement problem. we proposed new parallel model for EMO. That is Master-Slave model with Local Cultivation model. The proposed model is applied to antenna arrangement problem of mobile telecommunications. The results of proposed model were compared with those of SGA and DGA , I can say that The searching ability of the proposed model was almost better than SGA and DGA in numerical examples. Since MSLC has high searching ability. We can say that MSLC is a good model for parallel EMO. Thank you for your kind attention. I’m afraid I have run overtime. Thank you again all of you.

補足 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 世代数交叉率 1.0 交叉法 2点交叉突然変異率 1 / 染色体長選択手法トーナメント選択（トーナメントサイズ4）エリート個体数 5 島数各島の個体数を10と固定　（島数＝母集団サイズ / 10）移住率 0.5 移住間隔ユーザーの設定すべきパラメータは探索時間に関わる世代数のみ Doshisha Univ., Kyoto Japan

補足テスト関数実験に用いたパラメータ母集団 100 交叉率 1.0 交叉法 2点交叉突然変異率 0.01 選択手法トーナメント選択（サイズ4）エリート個体数 5 島数 10 移住率 0.5 移住間隔試行回数 20試行平均設計変数 10次元対象問題 Rastrigin，Schwefel Doshisha Univ., Kyoto Japan

補足発表に用いたソースプログラム進化的手法を用いた多目的全般に関して多目的0 /1ナップザック問題に関して発表者の電子メールアドレス Doshisha Univ., Kyoto Japan

Doshisha Univ., Kyoto Japan

Similar presentations

Presentation on theme: "Doshisha Univ., Kyoto Japan"— Presentation transcript:

Similar presentations

About project

フィードバック

ログインする

Auth with social network:

Doshisha Univ., Kyoto Japan

Similar presentations

Presentation on theme: "Doshisha Univ., Kyoto Japan"— Presentation transcript:

Similar presentations

About project

フィードバック