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”.

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

Doshisha Univ., Kyoto Japan 背景 最適化は大きく2つの要素からなる Optimizer Analyzer 提示された探索点の評価値を求める ．つまり，対象としている問題の評価． 様々な手法に基づいて 探索点を決定 （例）変分法，動的計画法， 山登り法，線形計画法， GA，SAなど Doshisha Univ., Kyoto Japan

Doshisha Univ., Kyoto Japan 遺伝的アルゴリズム 遺伝的アルゴリズム (Genetic Algorithm: GA) 生物の進化を模倣した最適化アルゴリズム 遺伝子を組み替えて新しい個体を生成 個体間の情報交換 交叉 親個体が持たないビットを生み出す 母集団内の多様性の維持 突然変異 環境に適合した個体ほど 子孫を残しやすい 選択 Doshisha Univ., Kyoto Japan

Doshisha Univ., Kyoto Japan 遺伝的アルゴリズム GAの特徴 利点 ほぼ全ての最適化問題に適用可能（汎用性） コーディングが比較的容易 一般的にそこそこ良質な解が得られる 大域的探索を行うことができる 短所 計算コストが高い 最適解の保証が無い（ヒューリスティック） 設定パラメータが多い コーディングに規範がなくプログラマの経験による部分が多い Doshisha Univ., Kyoto Japan

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

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

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

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

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

Doshisha Univ., Kyoto Japan 数値実験 (ディーゼルエンジン噴射スケジュール最適化) 分散GA HIDECS 噴射率 燃費，NOx，SMOKE 噴射率：燃料噴射量の時間的変化 HIDECS：ディーゼル燃焼のシミュレータ Doshisha Univ., Kyoto Japan

Doshisha Univ., Kyoto Japan 数値実験 (ディーゼルエンジン噴射スケジュール最適化) 目的 窒素 (NOx)排出量の最小化 燃費 SFC (200以下) すす SMOKE (0.25以下) 制約 クランク角 –5°から 13°における燃料噴射のスケジュール 設計変数 6つの矩形により36分割された噴射スケジュールを表す 扱う変数は，各矩形の縦・横の長さであり計12個ある Doshisha Univ., Kyoto Japan

Doshisha Univ., Kyoto Japan 数値実験 (ディーゼルエンジン噴射スケジュール最適化) パラメータ 母集団 100 交叉率 1.0 交叉法 1点交叉 突然変異率 0.01 エリート個体数 5 島数 10 移住率 0.5 移住間隔 制約 SFC < 200 SMOKE < 0.25 Doshisha Univ., Kyoto Japan

Doshisha Univ., Kyoto Japan 数値実験 (ディーゼルエンジン噴射スケジュール最適化) 多段噴射：　NOx排出量を削減すると経験的に知られている 実問題においても良好な結果が得られた Doshisha Univ., Kyoto Japan

Doshisha Univ., Kyoto Japan 多目的最適化へのアプローチ 現実の最適化では，扱う目的が複数である場合が多い 各目的同士がトレードオフの関係にある場合 多目的最適化問題 複数の評価基準を同時に最適化 多目的最適化問題を解くことにより 各目的同士の関係を把握することができ， より満足した解が得られる． 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

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

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 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.

Doshisha Univ., Kyoto Japan 近傍培養型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.

Doshisha Univ., Kyoto Japan 近傍培養型GA 近傍交叉 多目的では，対象とする目的関数空間が広く 各個体ごとに探索している解領域が異なっている． f2(x) f1(x) 近傍でない個体と交叉を行っても， 効果的な探索は期待できない． Doshisha Univ., Kyoto Japan

Doshisha Univ., Kyoto Japan 近傍培養型GA 近傍交叉 近傍同士のペアによる交叉 個体のソートを行う． f2(x) 毎世代ペアが異なるよう 確率的な変動を加える． f1(x) Doshisha Univ., Kyoto Japan

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オペレータを示します．

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

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

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

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

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

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

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

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

Doshisha Univ., Kyoto Japan 数値実験 (ディーゼルエンジン噴射スケジュール最適化) 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:0.09924 Doshisha Univ., Kyoto Japan

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

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

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.

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

Doshisha Univ., Kyoto Japan 補足 過去の研究に基づきパラメータの推奨値を設定 分散GAにおける推奨パラメータ 母集団 100 世代数 交叉率 1.0 交叉法 2点交叉 突然変異率 1 / 染色体長 選択手法 トーナメント選択 （トーナメントサイズ4） エリート個体数 5 島数 各島の個体数を10と固定 　（島数＝母集団サイズ / 10） 移住率 0.5 移住間隔 ユーザーの設定すべきパラメータは 探索時間に関わる世代数のみ Doshisha Univ., Kyoto Japan

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

Doshisha Univ., Kyoto Japan 補足 発表に用いたソースプログラム http://mikilab.doshisha.ac.jp/dia/download/index.html 進化的手法を用いた多目的全般に関して http://www.lania.mx/~ccoello/EMOO/EMOObib.html 多目的0 /1ナップザック問題に関して http://www.tik.ee.ethz.ch/~zitzler/ 発表者の電子メールアドレス sin@mikilab.doshisha.ac.jp Doshisha Univ., Kyoto Japan