集中多段交叉を用いた 2個体分散遺伝的アルゴリズム 同志社大学大学院 工学研究科 2003年度0713番 勝﨑 俊樹 Intelligent Systemｓ Design Lab. Doshisha University 研究背景 最適化とは 与えられた候補の中から最も良好な結果を探し出すこと トラス構造物の最適化 集積回路の配置 利得透過フィルタの設計 最適解に近い解を実用的な計算コストで探索する技法 遺伝的アルゴリズム(Genetic Algorithm:GA) Intelligent Systemｓ Design Lab. Doshisha University 遺伝的アルゴリズム ・生物の進化を模倣した最適化手法 ・多点探索 ・遺伝的オペレータ(選択，交叉，突然変異)を繰り返し 個体(解)を成長させる 個体 母集団 Intelligent Systemｓ Design Lab. Doshisha University 遺伝的アルゴリズムの特徴 初期生成した個体を進化させることによる解探索手法 長所 ・傾向の異なる個体を組み合わせて 解探索を行うので，広域な探索が可能 Intelligent Systemｓ Design Lab. Doshisha University 遺伝的アルゴリズムの特徴 初期生成した個体を進化させることによる解探索手法 短所 ・個体同士の情報交換によって解探索を 行うため，世代が進むと個体の傾向が 同じになる ・一度全ての個体が同じ傾向になって しまうと，他の傾向の個体を生み出す ことができない 局所解から脱出できない(早熟収束) Intelligent Systemｓ Design Lab. Doshisha University 早熟収束の回避 単一母集団のGAの短所 早熟収束によって局所解から脱出できなくなる 主な対処法 ・母集団を複数のサブ母集団（島）に分割 ・Distributed Genetic Algorithm（DGA） ・Dual individual DGA（Dual DGA） ・高い多様性を保つ世代交代モデル（選択方法）の利用 Minimal Generation Gap（MGG） Intelligent Systemｓ Design Lab. Doshisha University 分散遺伝的アルゴリズム（DGA） ・母集団を複数のサブ母集団に分割する ・一定世代ごとに各サブ母集団間で移住を行う ・部分解を組み合わせた解探索が可能 Intelligent Systemｓ Design Lab. Doshisha University 2個体分散遺伝的アルゴリズム（Dual DGA） ・サブ母集団サイズを2個体に固定したDGA ・パラメータチューニングの負荷が低い （DGAと比べ，交叉率，突然変異率，移住率のパラメータが不要） ・DGAよりも解探索の信頼性に優れる Intelligent Systemｓ Design Lab. Doshisha University Dual DGAの遺伝的操作（移住） 移住 ・2個体のうち，一方のコピｰを他のサブ母集団へ送る ・適合度の低い個体と移住個体を交換する 移住個体と ランダムに移住個体を選択 適合度の低い個体を交換 Intelligent Systemｓ Design Lab. Doshisha University Dual DGAの遺伝的操作（交叉，突然変異） 交叉 2個体の親個体から2個体の子個体を生成 突然変異 子個体の1ビットを対立遺伝子に変換 Intelligent Systemｓ Design Lab. Doshisha University Dual DGAの遺伝的操作（選択） 選択 親個体，子個体からそれぞれ適合度の高い個体を 選択する 低 高 低 高 次世代へ生き残る Intelligent Systemｓ Design Lab. Doshisha University DGAにおける部分解の生成 DGA，Dual DGAの特徴 サブ母集団で生成される良好な部分解を 組み合わせることによる解探索 サブ母集団ごとに異なった傾向を持つ良好な 部分解を生成することが重要 各サブ母集団における解探索に，部分解の生成に特化した メカニズムを組み込む Intelligent Systemｓ Design Lab. Doshisha University 提案手法 Dual DGA/MX 集中多段交叉を用いた2個体分散遺伝的アルゴリズム Dual DGA with Multiple Crossover(Dual DGA/MX) ・集中多段交叉を用いた集中的かつ多段の解探索 ・サブ母集団サイズを2としたDual DGAの構造 各サブ母集団で複数の子個体を生成 複数の子個体に対して突然変異を適用 集中多段交叉 エリート＋ランキングルーレット選択で 次の交叉の親個体を決定 Intelligent Systemｓ Design Lab. Doshisha University 集中多段交叉 ・1世代の交叉，突然変異で複数の子個体を生成 ・複数の子個体から次の交叉の親個体を選択 ・Dual DGAに適用することで各サブ母集団で集中的な 局所探索が可能 Intelligent Systemｓ Design Lab. Doshisha University Dual DGA/MXの遺伝的操作（移住） 移住 ・2個体のうち，1個体を他のサブ母集団へ送る ・無条件で移住個体は新たなサブ母集団の個体となる ランダムに移住個体は決定 Intelligent Systemｓ Design Lab. Doshisha University Dual DGA/MXの遺伝的操作（交叉，突然変異） 交叉 2個体の親個体から複数の子個体を生成 突然変異 生成された全ての子個体に突然変異を適用 Intelligent Systemｓ Design Lab. Doshisha University Dual DGA/MXの遺伝的操作（選択） 選択 親個体と複数の子個体から評価値の最も高い個体と， ランキングルーレット選択で選ばれた個体を次世代に残す Intelligent Systemｓ Design Lab. Doshisha University テスト問題による性能検証 対象問題 ・連続問題(Griewank関数，Schwefel関数:30次元) ・部分だまし問題(4bit部分だまし問題，10bit部分だまし問題) 比較手法 ・Simple GA [Goldberg 1989] ・世代交代モデルMGG [佐藤 1997] ・Dual DGA [廣安 2002] ・提案手法Dual DGA/MX Intelligent Systemｓ Design Lab. Doshisha University テスト問題の導入（連続問題） Griewank関数 2 n xi xi F x 1 cos i i 1 4000 i 1 512 xi 512 n 30 次元 n Schwefel関数 n F x xi sin( xi ) i 1 512 xi 512 n 30 次元 Intelligent Systemｓ Design Lab. Doshisha University パラメータ（連続問題） Intelligent Systemｓ Design Lab. Doshisha University 連続問題における解の信頼性 Griewank関数 ・・・ 他手法より良好な解の信頼性 Schwefel関数 ・・・ 他手法と同等以上の解の信頼性 Intelligent Systemｓ Design Lab. Doshisha University 連続問題に要する評価計算回数 対象問題：Griewank関数 提案手法Dual DGA/MXに要する評価計算回数は 他手法よりも多い Intelligent Systemｓ Design Lab. Doshisha University テスト問題の導入（部分だまし問題） 4bit部分だまし問題 n F x yi i 1 n 100 次元 （ yi は設計変数の評価値） 評価値 bit”1”が全て揃った状態以外ではbit”0”が多いほど評価値 は高いため，bit”0”が全て揃った状態は局所解となる Intelligent Systemｓ Design Lab. Doshisha University テスト問題の導入（部分だまし問題） 10bit部分だまし問題 n F x yi i 1 n 40 次元 （ yi は設計変数の評価値） Intelligent Systemｓ Design Lab. Doshisha University パラメータ（部分だまし問題） Intelligent Systemｓ Design Lab. Doshisha University 部分だまし問題における解の信頼性 対象問題：4bit部分だまし問題 提案手法Dual DGA/MXで得られる評価値は他手法と比較して 非常に高い Intelligent Systemｓ Design Lab. Doshisha University 部分だまし問題における解の信頼性 対象問題：10bit部分だまし問題 提案手法Dual DGA/MXで得られる評価値は他手法と比較して 非常に高い Intelligent Systemｓ Design Lab. Doshisha University 部分だまし問題に要する評価計算回数 対象問題：4bit部分だまし問題 提案手法Dual DGA/MXに要する評価計算回数は 他手法よりも多い Intelligent Systemｓ Design Lab. Doshisha University 部分最適解による検証 設計変数における部分最適解の合計の履歴 ・部分最適解の生成に関する性能 ・部分最適解の維持に関する性能 部分最適解あり 部分最適解あり 部分最適解なし Intelligent Systemｓ Design Lab. Doshisha University 部分最適解による検証結果 対象問題：4bit部分だまし問題 提案手法Dual DGA/MXは他手法と比較して部分最適解の 維持の性能に優れている Intelligent Systemｓ Design Lab. Doshisha University 部分最適解による検証結果 対象問題：10bit部分だまし問題 提案手法Dual DGA/MXは他手法と比較して 部分最適解の維持および生成の性能に優れている Intelligent Systemｓ Design Lab. Doshisha University 結論 提案手法Dual DGA/MX テスト問題による解探索性能の検証 ・高い解探索の信頼性 ・問題に対する汎用性 部分最適解を用いた検証 ・部分最適解を維持する性能に優れる ・部分最適解を生成する性能に優れる Dual DGA/MXは部分最適解の生成と維持の性能に優れた， 高い解探索性能と問題に対する汎用性を持つ手法 Intelligent Systemｓ Design Lab. Doshisha University 発表論文リスト 三木光範，廣安知之，勝崎俊樹，水田伯典： 離散最適化のための大域的交叉メカニズムを持つ分散遺伝的アルゴリズム 日本計算工学会論文集，No．20040001（2004.01） 三木光範，廣安知之，勝崎俊樹，森隆史： 分散遺伝的アルゴリズムにおける多様性を考慮した世代交代モデルの効果 同志社大学理工学研究報告，第45巻，第3号（2004.10） 三木光範，廣安知之，勝崎俊樹： リフレッシュ型分散遺伝的アルゴリズム 第17回人工知能学会全国大会，新潟県・朱鷺メッセ（2003.06） 三木光範，廣安知之，勝崎俊樹： リフレッシュ型分散遺伝的アルゴリズムの組み合わせ最適化問題への適用 第46回数理化と問題解決（MPS）研究会，広島市立大学（2003.09） Intelligent Systemｓ Design Lab. Doshisha University Intelligent Systemｓ Design Lab. Doshisha University 参考資料 Intelligent Systemｓ Design Lab. Doshisha University 部分最適解の生成に関する検証 各設計変数での部分最適解の組み合わせ Intelligent Systemｓ Design Lab. Doshisha University 部分最適解の組み合わせを用いた検証 各設計変数での部分最適解の組み合わせ ① 部分最適解同士の組み合わせ 割合が増えるほど最適解に近づく ② 部分最適解と部分最適解でないものの組み合わせ 割合が高ければ，設計変数間に有効な多様性が 存在する ③ 部分最適解でないもの同士の組み合わせ 割合に変化が見られれば，設計変数内の 多様性が高い（部分最適解の生成が期待できる） Intelligent Systemｓ Design Lab. Doshisha University 部分最適解の組み合わせを用いた検証 検証対象：Simple GA 対象問題：4bit部分だまし問題 Intelligent Systemｓ Design Lab. Doshisha University 部分最適解の組み合わせを用いた検証 検証対象：Minimal Generation Gap 対象問題：4bit部分だまし問題 Intelligent Systemｓ Design Lab. Doshisha University 部分最適解の組み合わせを用いた検証 検証対象：Dual DGA 対象問題：4bit部分だまし問題 Intelligent Systemｓ Design Lab. Doshisha University 部分最適解の組み合わせを用いた検証 検証対象：提案手法Dual DGA/MX 対象問題：4bit部分だまし問題 Intelligent Systemｓ Design Lab. Doshisha University 検証結果のまとめ 提案手法Dual DGA/MXの特徴 ・他手法と比較して，部分最適解と部分最適解 でないものの組み合わせから新たな部分最適解同士の 組み合わせが生まれやすい 解探索に有効な多様性を設計変数間で 保つことができる ・早い世代から部分最適解でないもの同士の組み合わせ から他の組み合わせが長い世代で生まれている 設計変数内でも有効な多様性を保ち，新たな 部分最適解を生み出すことができる Intelligent Systemｓ Design Lab. Doshisha University 結論 提案手法Dual DGA/MX テスト問題による解探索性能の検証 ・高い解探索の信頼性 ・問題に対する汎用性 部分最適解を用いた検証 ・設計変数間に有効な多様性を保つことができる ・設計変数内に有効な多様性を保つことができる Dual DGA/MXはサブ母集団間で有効な解の組み合わせを 行うことができるため，高い解探索性能と問題に対する 汎用性を持つ Intelligent Systemｓ Design Lab. Doshisha University 世代交代モデル ・Simple GA （sGA） ［Goldberg,1989］ 毎世代すべての個体を更新 ・Minimal Generation Gap（MGG） ［佐藤,1996］ 毎世代 2 個体のみ更新 ｓGA 早熟収束 MGG 多様性の維持 Intelligent Systemｓ Design Lab. Doshisha University Minimal Generation Gap（MGG） 局所的な世代交代を実現する世代交代モデル[佐藤 1997] ≫初期収束の回避，探索終盤の多様性維持に優れている Intelligent Systemｓ Design Lab. Doshisha University テスト問題の導入（連続問題） Rastrigin関数（F１） n F x 10n ( xi 10cos(2xi )) i 1 2 5.12 xi 5.12 n 30 次元 Griewank関数（F２） 2 n xi xi F x 1 cos i i 1 4000 i 1 512 xi 512 n 30 次元 n Intelligent Systemｓ Design Lab. Doshisha University テスト問題の導入（連続問題） Ridge関数（F３） n i i 1 j 1 F x ( x j ) 2 64 xi 64 n 30 次元 Schwefel関数（F４） n F x xi sin( xi ) i 1 512 xi 512 n 30次元 Intelligent Systemｓ Design Lab. Doshisha University パラメータ（連続問題） Intelligent Systemｓ Design Lab. Doshisha University 連続問題における解の信頼性（F1,F2） 世代交代モデルMGGにDGAを適用しても，解の信頼性の 向上はほとんど見られない Intelligent Systemｓ Design Lab. Doshisha University 連続問題における解の信頼性（F3,F4） 世代交代モデルMGGにDGAを適用しても，解の信頼性の 向上はほとんど見られない Intelligent Systemｓ Design Lab. Doshisha University 連続問題における解収束速度（F1） 世代交代モデルMGGにDGAを適用した場合， 解探索速度は遅くなってしまう Intelligent Systemｓ Design Lab. Doshisha University テスト問題の導入（部分だまし問題） 4bitだまし問題（F５） n F x yi i 1 n 100 次元 （ yi は設計変数の評価値） 評価値 bit”1”が全て揃った状態以外ではbit”0”が多いほど評価値 は高いため，bit”0”が全て揃った状態は局所解となる Intelligent Systemｓ Design Lab. Doshisha University テスト問題の導入（部分だまし問題） 10bitだまし問題（F６） n F x yi i 1 n 40 次元 （ yi は設計変数の評価値） Intelligent Systemｓ Design Lab. Doshisha University パラメータ（だまし問題） Intelligent Systemｓ Design Lab. Doshisha University だまし問題における解の信頼性（F5） 世代交代モデルMGGにDGAを適用することで，はっきりと 解の信頼性の向上を確認できる Intelligent Systemｓ Design Lab. Doshisha University だまし問題における解の信頼性（F6） 世代交代モデルMGGにDGAを適用することで，はっきりと 解の信頼性の向上を確認できる Intelligent Systemｓ Design Lab. Doshisha University だまし問題における解収束速度（F5） 世代交代モデルMGGにDGAを適用した場合， 解探索速度は遅くなってしまう Intelligent Systemｓ Design Lab. Doshisha University だまし問題における解収束速度（F6） 世代交代モデルMGGにDGAを適用した場合， 解探索速度は遅くなってしまう Intelligent Systemｓ Design Lab. Doshisha University だまし問題に対するまとめ だまし問題に対して世代交代モデルMGGをDGAに適用 ・解探索性能の信頼性はMGGを単一母集団GAに 適用した場合よりも高い ・解探索速度は世代交代モデルSGAを用いた場合より 劣ってしまう ・サブ母集団サイズに関しては，多い方が良好な結果が 得られるが，解探索速度は落ちる だまし問題に対して世代交代モデルMGGをDGAに適用する ことにより，解探索の信頼性を向上できる Intelligent Systemｓ Design Lab. Doshisha University 部分最適解形成の履歴(補足) 部分最適解あり 部分最適解あり 部分最適解なし Intelligent Systemｓ Design Lab. Doshisha University 連続関数の部分解形成の履歴(Griewank) Intelligent Systemｓ Design Lab. Doshisha University 連続関数の部分解形成の履歴(4bit) Intelligent Systemｓ Design Lab. Doshisha University MGGをDual DGAに適用する意味 ・世代交代モデルMGG＋単一母集団GA 選択による淘汰を減らすことに効果 ・世代交代モデルMGG＋2個体分散GA(Dual DGA) サブ母集団内の集中的かつ多段の探索 ＋Dual DGAによる部分解の組み合わせに効果 Intelligent Systemｓ Design Lab. Doshisha University ランキングルーレット選択 Intelligent Systemｓ Design Lab. Doshisha University
© Copyright 2024 ExpyDoc
