第14回自律分散システム・シンポジウム（2002年1月25日） ベイジアンネットワークを遺伝的操作に利用した 実数値遺伝的アルゴリズム 同志社大学工学部／同志社大学大学院 ○吉田 純一，廣安 知之，三木 光範 発表の概要 遺伝的アルゴリズムの問題点 確率モデル遺伝的アルゴリズム ガウシアン最適化アルゴリズム（GOA） GOAの連続関数最適化問題への適用 まとめ Intelligent Systems Design Lab. Doshisha University 遺伝的アルゴリズム 評 価 選 択 生物の進化の過程を工学的に 応用した最適化手法 遺伝的オペレータ 交叉・突然変異・選択 交 叉 突然変異 幅広い工学的最適化問題に 適用可能 Intelligent Systems Design Lab. Doshisha University GAにおける交叉の役割 評 価 選 択 交 叉 親個体の遺伝子を組み替え 新しい個体を生成 個体間の情報交換 積み木仮説（Holland 1975） 複数の個体がビルディングブロック を探索．交叉によってこれが組み合 わされる 突然変異 GAによる解探索の主役と 考えられてきた Intelligent Systems Design Lab. Doshisha University GAにおける交叉の問題点 発見されたビルディングブロックを母集団全体に広め， 多様性を失わせる．親個体のもつビルディングブロック を破壊することが多い.（Wu 1997） 適合度に小さな変化または大きな改悪を生む事が多い． （Nordin 1995） 新しいアプローチ 分布推定アルゴリズム 確率モデル遺伝的アルゴリズム Intelligent Systems Design Lab. Doshisha University 分布推定アルゴリズム（EDAs）の概要 分布推定アルゴリズム（Muhlenbein1996） Estimation of distribution algorithms:EDAs （１）良好な個体を母集団 から選択 分布の推定 （２）分布を推定し 確率モデルを構築 母集団 （３）新しい個体を生成し 母集団内の個体と置き換え 確率モデル 母集団内の良好な個体群の分布にもとづいて 確率的に新しい個体を生成する Intelligent Systems Design Lab. Doshisha University GAとEDAの比較 GA EDA 評 価 評 価 選 択 選 択 交 叉 分布推定・ モデル構築 突然変異 個体生成 EDA：交叉・突然変異を「分布推定」と「モデルに従った 個体の生成」に置き換えたもの 確率モデルGA（Probabilistic Model Building GAs） Intelligent Systems Design Lab. Doshisha University 確率モデルGAの分類（Pelikan1999） 設計変数のコード化手法による分類 f (x1, x2) ビットストリング型 実数値ベクトル型 0 1 0 1 0 1 x1 x2 設計変数間の依存関係の考慮の程度による分類 依存関係を考慮しない（No Interactions） 2変数間の依存関係を考慮する（Pairwize Interactions） 3変数以上の依存関係を考慮する（Multivariable Interactions） Intelligent Systems Design Lab. Doshisha University 確率モデルGAの分類 ビットストリング 依存関係を PBIL（Baluya1994） 考慮しない UMDA（Muhelembein1996） ｃGA（Lobo1998） 実数値ベクトル SHCLVND （Rudolf1996） Real-coded PBIL （Sevet1997） PIPE（Salustowicz1997） PBMGA （筒井2000） 2変数を MIMIC（DeBonet1997） 考慮 BMDA（Pelikan1999） GOA 3変数以上を ガウシアン最適化アルゴリズム ECGA（Harik1999） EGNA （Etxeberria1999） 考慮 Gaussian Optimization Algorithm:GOA FDA （Muhelembein1999） BOA （Pelikan1999） 2変数間の依存関係を考慮した EBNA （Etxeberria1999） 実数値確率モデルGA Intelligent Systems Design Lab. Doshisha University 提案手法の特徴 ガウシアン最適化アルゴリズム Gaussian Optimization Algorithm:GOA • 実数値ベクトルの染色体 • 確率モデルGA • 分布の推定にガウス分布 • 確率モデルにガウシアンネットワーク • ガウシアンネットワークの構造はQ-Learningで学習 Intelligent Systems Design Lab. Doshisha University GOAの概要 （１）良好な個体を母集団 から選択 分布の推定 （２）分布を推定 母集団 ガウシアンネット （6）母集団内の個体と置き換え （４）新しい個体を生成 （3）モデルを決定 （5）良好な個体を生成した ネットワークを学習 Q学習 Intelligent Systems Design Lab. Doshisha University 分布の推定 母集団からサンプル個体を選択 サンプル率 s トーナメント選択 サンプル 個体群 サンプル個体群の統計量を求める 各設計変数の平均値，標準偏差 サンプル個体群はガウス分布 すると仮定 変数間の相関係数ρ 変数ごとの関わりを考慮する Intelligent Systems Design Lab. Doshisha University 個体の生成 各変数を独立に決定する場合 変数ごとに正規乱数を発生 2変数の依存関係を考慮する場合（GOA） xa と xb の間に依存関係があるとき xb 0.4 2変量正規分布を利用 0.3 0.2 2 0.1 0 0 平均値，標準偏差，相関係数 -2 xa 0 -2 2 xa の値をもとに xbの値を決定 Intelligent Systems Design Lab. Doshisha University 個体の生成（２） xa と xb の間に依存関係があるとき xa xb xa の値をもとに xbの値を決定 n変数を扱うときには xa xb xc xn 依存関係を有向グラフで表現 各変数の値はガウス分布すると仮定 ガウシアンネットワーク （ベイジアンネットワークの一種） ガウシアンネットのグラフ構造をどのように決定するか？ Intelligent Systems Design Lab. Doshisha University Q-Learning GOAでは依存関係はQ-Learningで学習 強化学習 エージェント 教師なし学習 行動選択の手がかり：報酬 エージェントは試行錯誤を通じて 適切な制御規則を獲得 行動 状態観測 報酬 環 境 Q-Learning ある状態でとりうる行動に評価値：Q値 評価値に応じて行動を選択 Intelligent Systems Design Lab. Doshisha University Q学習によるネットワークの学習 3変数の場合 ネットワークを決定 2 3 1 2 1 3 2 3 3 1 2 ε-greedy選択（ε=0.5） 1 0 3 個体を生成 2 3 1 2 1 1 2 3 ノード：変数，パス：行動 個体を評価 良好な個体を生成したネット ワークには報酬 Intelligent Systems Design Lab. Doshisha University ネットワークの学習 探索が進むと・・・ 2 3 枝ごとにQ値に偏りが生じる 1 0 3 2 1 3 3 1 2 1 1 2 2 太い枝は選択されやすい 太い枝のネットワークは良好 な個体を生成する可能性が 高い 3 Q値を観測することで対象 問題の依存関係がわかる？ Intelligent Systems Design Lab. Doshisha University GOAのまとめ （１）良好な個体を母集団 から選択 分布の推定 （２）分布を推定 母集団 ガウシアンネット （6）母集団内の個体と置き換え （４）新しい個体を生成 （3）モデルを決定 （5）良好な個体を生成した ネットワークに報酬 Q学習 Intelligent Systems Design Lab. Doshisha University 数値実験 ガウシアンネットの有効性 実数値GAとの性能比較 ネットワークの学習 Intelligent Systems Design Lab. Doshisha University 対象問題 変数間に依存関係なし 変数間に依存関係あり FGriewank Intelligent Systems Design Lab. Doshisha University 実験１：ガウシアンネットの有効性 ガウシアンネットワークは変数間の依存関係を表現 xa xb xc xn 設計変数間に依存関係のある問題において 効率的な探索が期待される GOAとガウシアンネットワークを用いないGOAを 比較しガウシアンネットの有効性を確認する Intelligent Systems Design Lab. Doshisha University 実験1：ガウシアンネットの有効性 GOAとネットワークなしGOA 分布の推定 分布の推定 母集団 母集団 ガウシアンネット パラメータ 母集団サイズ： 200 サンプル率： 0.1 突然変異率： 0.1 学習 0.3 率：割 0.3 引率： ※20試行の平均値で比較 Intelligent Systems Design Lab. Doshisha University ガウシアンネットの有効性（１） 設計変数間に依存関係のない問題では差はない Intelligent Systems Design Lab. Doshisha University ガウシアンネットの有効性（２） 設計変数間に依存関係のある問題では有効 Intelligent Systems Design Lab. Doshisha University 実験2：実数値GAとの性能比較 比較に用いた実数値GA 母集団サイズ： 200 世代交代モデル： MGG（sato1997） 交叉法： BLX-α （eshelman1993）, UNDX （ono1997） ※20試行の平均値で比較 Intelligent Systems Design Lab. Doshisha University 実数値GAとの性能比較（１） GOAは実数値GAよりも高速に良好な解を得る Intelligent Systems Design Lab. Doshisha University 実数値GAとの性能比較（２） 10D Griewank 10D Ridge GOAは実数値GAよりも高速に良好な解を得る Intelligent Systems Design Lab. Doshisha University 実験3：ネットワークの学習 探索が進むと・・・ 2 3 枝ごとにQ値に偏りが生じる 1 0 3 2 1 3 3 1 2 2 1 1 2 3 ノード：変数，パス：行動 太い枝からなるネットワーク →良好な個体を生成した ネットワーク Q値を観測することで対象 問題の依存関係がわかる？ 対象問題 Rastrigin, Ridge（4変数） Intelligent Systems Design Lab. Doshisha University ネットワークの学習（１） 4D Rastrigin関数 設計変数間に依存関係がない 相関係数は小さい ネットワークを用いなくても性能は 変わらない Q値に偏りがない 学習が進む前に最適解を得る Intelligent Systems Design Lab. Doshisha University ネットワークの学習（２） 4D Ridge関数 設計変数間に依存関係がある ネットワークを用いた方が性能がよい Q値に偏りがある 何らかの学習がなされている 問題の性質を把握は今後の課題 Intelligent Systems Design Lab. Doshisha University まとめ 新しい実数値確率モデルGAとしてガウシアン最適化 アルゴリズムを提案した． 設計変数間に依存関係のある問題において ガウシアンネットワークによる個体分布の推定は有効． GOAは実数値GAよりも少ない計算回数で良好な解 を得ることができる． GOAは設計変数間に依存関係のある問題において その性質を学習することができる（解析は今後の課題）． Intelligent Systems Design Lab. Doshisha University Intelligent Systems Design Lab. Doshisha University 補足資料 Intelligent Systems Design Lab. Doshisha University GOAの流れ図 選 択 分布推定 モデル構築 個体生成 評 価 学 習 Intelligent Systems Design Lab. Doshisha University Rastrigin GOAは実数値GAよりも高速に良好な解を得る Intelligent Systems Design Lab. Doshisha University 全試行の履歴 多峰性関数においては局所解で停滞することもある Intelligent Systems Design Lab. Doshisha University GOAの問題点 サンプル個体群=母集団内の優良個体 X0 個体１ 個体2 個体３ 平均値 X１ X２ X３ 0， 0, 0， 0, 0， 0, 4, 5, 3, 0 0 0 0， 0, 0.4, 0 X0 X１ X２ X３ 0， 0, 0， 0, 0， 0, 1, 5, 3, 0 0 0 0， 0, 0.3, 0 GAでは，選択によってエリートの数が増える GOAでは数は増えず，統計量のみが変化する 探索終盤での局所解からの脱出は困難？ GOAではビルディングブロックの交換はできない Intelligent Systems Design Lab. Doshisha University GOAの問題点 ビルディングブロックの交換ができない 0, 0, 0, 0, 0 0, 0, 0, 1, 0 0, 0, 0, 0, 1 0, 0, 0, 0.5, 0.5 Intelligent Systems Design Lab. Doshisha University ベイジアンネットワーク 不確定性を含む事象を表現するために有向グラフを用いる 確率モデル 確率変数の間の定性的な依存関係をグラフ構造で表す xa xb このとき xb は xa に依存する． xa は xb の親ノード． 確率変数間の定量的な依存関係を条件付き確率で表す P( X b | X a ) P( X b | ( X b )) ここで ( X b ) はxbの親ノード群 Intelligent Systems Design Lab. Doshisha University 条件付き確率の例 Intelligent Systems Design Lab. Doshisha University ガウシアンネットワーク 離散変数をベイジアンネットワークで扱う場合 条件付確率はすべての状態における条件付確率を並べた 表（CPT）によって表す． a = 1 のとき b = 0 である確率は 10% a = 2 のとき b = 0 である確率は 10% ・・・ 連続変数をベイジアンネットワークで扱う場合 各変数の条件付確率を特定の連続関数に従うと仮定 このときガウス分布すると仮定するもの ガウシアンネットワーク Intelligent Systems Design Lab. Doshisha University Q-Learning Q-Learningの例 A S1 B A S2 B A S3 B S4 ：状態 ：行動 ：報酬 Q値 S1 S2 S3 S4 A B Intelligent Systems Design Lab. Doshisha University ネットワークの学習：Rosenbrock 4D Rosenbrock関数 設計変数間に依存関係がある 相関係数が大きい Intelligent Systems Design Lab. Doshisha University 相関係数の影響 ρ=0.0 ρ=0.2 ρ=0.4 1 1 1 0.8 0.8 0.8 0.6 0.6 0.6 0.4 0.4 0.4 0.2 0.2 0.2 -3 -2 -1 1 2 3 -3 -3 0.4 -2 -1 1 2 -1 1 2 3 1 0.4 0.3 -2 3 0.8 0.3 0.6 0.2 2 0.1 0.2 2 0.1 0 0.2 0 0 0 -2 -2 0 0 -2 2 0 0 -2 0 2 0.4 -2 -2 2 2 Intelligent Systems Design Lab. Doshisha University GOAの世代交代モデル GOAでは任意の世代交代モデルが利用できる 本研究で用いた世代交代モデル P（t） サンプル個体群 の選択 S（t） 子個体の生成 O（t） P（t）+O（t） 世代交代 P（t+1） Intelligent Systems Design Lab. Doshisha University 交叉の問題点（1点交叉の例） 1 2 :3 交叉点はランダムに決定 :2 →良好なスキーマが組み合わされ るか否かは確率的要素に依存 1 :5 :0 2 :3 :2 部分解 - 改良よりも改悪の方が多い（wu 97） うまく組み合わされても一方は淘汰 される → 多様性の減少につながる Intelligent Systems Design Lab. Doshisha University 実数値遺伝的アルゴリズム 実数値をそのまま遺伝子型とする 連続関数最適化問題において，ビットストリングを用いるGA より有効である （Davis 91） Intelligent Systems Design Lab. Doshisha University 実数値GAにおける交叉法 BLX-α UNDX （Eshelman 1993） （Ono 1997） • 2つの親個体の各成分距離を α倍拡張した領域 • 3つの親個体により定義される 正規分布領域 • 領域内に子個体はランダムに生成 • 領域内に2つの親の中点を対称に 子個体を生成 • 設計変数間に依存関係のある 問題に弱い • 設計変数間に依存関係のある 問題に強い Intelligent Systems Design Lab. Doshisha University 確率モデルGA研究の動向 ビットストリング型の手法に関する研究が先行 実数値ベクトル型の手法で変数間の依存関係を 考慮したものは少ない ガウシアン最適化アルゴリズム Gaussian Optimization Algorithm: GOA 2変数間の依存関係を考慮した実数値確率モデルGA Intelligent Systems Design Lab. Doshisha University ■ ■公聴会用資料■ ■ Intelligent Systems Design Lab. Doshisha University エンジンの実験結果 500 0.87 450 0.86 400 350 0.85 300 0.84 250 200 0.83 150 100 0.82 50 0.81 0 0 200 400 600 800 1000 1200 1 2 3 4 5 6 Intelligent Systems Design Lab. Doshisha University 2001年度 同志社大学大学院 工学研究科 知識工学専攻 修士論文公聴会（2002年2月1日） ガウシアンネットワークを用いた 確率モデル遺伝的アルゴリズム Probabilistic Model Building Genetic Algorithm using Gaussian Network 博士前期課程 2000年度 0737番 知的システムデザイン研究室 吉田 純一 発表論文リスト 三木光範，廣安知之，吉田純一，金子美華： 分散GA の性能におよぼす交叉法とコーディング法の影響， 第59 回情報処理学会全国大会，岩手県立大学（1999.09） 三木光範，廣安知之，吉田純一，大向一輝： 並列分散遺伝的アルゴリズムにおける最適な交叉スキーム， 第6 回MPS シンポジウム，同志社大学（2000.03） 三木光範，廣安知之，吉田純一，大向一輝： 並列分散遺伝的アルゴリズムにおける新しい交叉法， 電子情報通信学人工知能と知識処理研究会，筑波大学（2000.05） 三木光範，廣安知之，畠中一幸，吉田純一： 並列分散遺伝的アルゴリズムの有効性， 日本計算工学会Transactions of JSCES, Paper No.20000038（2000.08） 吉田純一，三木光範，廣安知之，坂田善宣： 遺伝的アルゴリズムにおける最良組み合わせ交叉， 第31 回情報処理学会MPS 研究会，東北大学（2000.09） 三木光範，廣安知之，吉田純一，大向一輝： 分散遺伝的アルゴリズムのための新しい交叉法， 同志社大学理工学研究報告書，第41 巻，第3 号，pp.162-170（2000.10） M.Miki, T.Hiroyasu, J.Yoshida, I.Ohmukai： New Crossover Scheme for Parallel Distributed Genetic Algorithms，IASTED international conference on Parallel and Distributed Computing and Systems (PDCS 2000)，Riviera Hotel and Casino, Las Vegas, Nevada, U.S.A （2000.11） 吉田純一，廣安知之，三木光範： 汎用分散遺伝的アルゴリズムシステムによるディーゼルエンジンの燃料噴射 スケジュール最適化，第8 回MPS シンポジウム，同志社大学（2001.10） J.Yoshida, T.Hiroyasu, M.Miki： Distributed Genetic Algorithms for Real-World Problems， Super Computing (SC2001)，Colorado convention center, Denver, Colorado, U.S.A （2001.11） 吉田純一，廣安知之，三木光範： ベイジアンネットワークを遺伝的操作に利用した実数値遺伝的アルゴリズム， 第14 回自律分散シンポジウム，東京大学 （2002.1） ほか計15件 Intelligent Systems Design Lab. Doshisha University 発表論文リスト（ALL） 三木光範，廣安知之，吉田純一，金子美華：分散GA の性能におよ ぼす交叉法とコーディング法の影響 第59 回情報処理学会全国大会，岩手県立大学（1999.09） 吉田純一，大向一輝，廣安知之，三木光範：PC クラスタシステム のベンチマークとツールの紹介 第15 回超並列計算研究会，同志社大学（1999.11） 三木光範，廣安知之，吉田純一，大向一輝：並列分散遺伝的アル ゴリズムにおける最適な交叉スキーム 第6 回MPS シンポジウム，同志社大学（2000.03） 吉田純一，大向一輝，廣安知之，三木光範：クラスタにおけるジョブ 管理ツールDQSの紹介 第18 回超並列計算研究会，日本原子力研究所（2000.05） 三木光範，廣安知之，水田伯典，吉田純一：並列分散遺伝的アル ゴリズムを用いた巡回セールスマン問題の解法 情報処理学会第61 回全国大会講演論文集，pp.173-174 （2000.11） M.Miki, T.Hiroyasu, J.Yoshida, I.Ohmukai：New Crossover Scheme for Parallel Distributed Genetic Algorithms IASTED international conference on Parallel and Distributed Computing and Systems (PDCS 2000)，Riviera Hotel and Casino, Las Vegas, Nevada, U.S.A（2000.11） 廣安知之， 三木光範， 谷村勇輔， 吉田純一， 佐野正樹：分散遺 伝的アルゴリズムを用いたPCクラスタのベンチマーク 日本機械学会日本機械学会第13 回計算力学講演会講演論文集， pp.497-498（2000.11） 三木光範，廣安知之，吉田純一，大向一輝：並列分散遺伝的アル ゴリズムにおける新しい交叉法 電子情報通信学人工知能と知識処理研究会，筑波大学（2000.05） 三木光範，廣安知之，福永隆宏，吉田純一：実数値遺伝的アルゴリ ズムの分散効果の検討 情報処理学会第63 回全国大会講演論文集，pp.111-112 （2001.09） 三木光範，廣安知之，畠中一幸，吉田純一：並列分散遺伝的アル ゴリズムの有効性 日本計算工学会Transactions of JSCES, Paper No.20000038 （2000.08） 吉田純一，廣安知之，三木光範：汎用分散遺伝的アルゴリズムシ ステムによるディーゼルエンジンの燃料噴射スケジュール最適化 第8 回MPS シンポジウム，同志社大学（2001.10） 吉田純一，三木光範，廣安知之，坂田善宣：遺伝的アルゴリズムに おける最良組み合わせ交叉 第31 回情報処理学会MPS 研究会，東北大学（2000.09） J.Yoshida,T.Hiroyasu, M.Miki：Distributed Genetic Algorithms for Real-World Problems Super Computing 2001，Colorado convention center, Denver, Colorado,U.S.A（2001.11） 三木光範，廣安知之，吉田純一，大向一輝：分散遺伝的アルゴリズ ムのための新しい交叉法 同志社大学理工学研究報告書，第41 巻，第3 号，pp.162-170 （2000.10） 吉田純一，廣安知之，三木光範：ベイジアンネットワークを遺伝的 操作に利用した実数値遺伝的アルゴリズム 第14 回自律分散シンポジウム，東京大学（2002.1） Intelligent Systems Design Lab. Doshisha University Genetic Algorithms (1) f (x1, x2) 遺伝的アルゴリズム（GA） Candidate solution 生物の進化を工学的に模倣した 最適化手法 encode decode (3, 5 ) 個体＝探索点（候補解） 各個体は設計変数情報を持つ Individual : 0 1 0 1 0 1 x1 x2 設計変数は実数からビット列 （染色体）に符号化 chromosome Intelligent Systems Design Lab. Doshisha University Genetic Algorithms (2) The new searching points are generated by genetic operators. - Selection, Crossover, Mutation many generations Initialization Get a good solution in result. Evaluation Iteration Selection Crossover Disadvantage Genetic operator Mutation End(find solution) High calculation cost - GAs needs a lot of iteration Performing GAs on parallel computers Intelligent Systems Design Lab. Doshisha University Intelligent Systems Design Lab. Doshisha University
© Copyright 2024 ExpyDoc
