実数値遺伝的アルゴリズムにおける計算モデルの検討 A Discussion on Computational Models of Real-coded Genetic Algorithm 知的システムデザイン研究室 16980013 : 福永隆宏遺伝的アルゴリズム生物の進化を模倣した最適化アルゴリズム f (x1, x2) (2, 7) 候補解をビットストリングで表現確率的な多点探索エンコードデコード遺伝オペレータ交叉染色体個体・・・ 010111 x1 x2 突然変異評価選択設計変数 Intelligent Systems Design Lab - Doshisha Univ 遺伝的アルゴリズムの問題点ビットストリングによる染色体のコーディング探索空間に連続性が反映されていない連続性を考慮した探索実数値GA 高い計算負荷膨大な反復計算が必要なため計算負荷が高くなる計算負荷の軽減分散GA Intelligent Systems Design Lab - Doshisha Univ 実数値遺伝的アルゴリズム実数ベクトルによる染色体のコーディング実数値のための遺伝オペレータ（交叉法：BLX-α，UNDX）親個体の形質を効率よく引き継ぐ連続性を考慮した探索が可能 Intelligent Systems Design Lab - Doshisha Univ 分散遺伝的アルゴリズムサブ母集団（島）に分割各島内で独立した遺伝操作 Distribute 島間で移住解の高品質化が期待できる島モデルによる分散効果 Intelligent Systems Design Lab - Doshisha Univ 研究の目的問題点を解決するための手法実数値GA と分散GA それらの組み合わせによる解探索性能の検討交叉法突然変異の有無島数 4種類にモデルを設定 Intelligent Systems Design Lab - Doshisha Univ 分散実数値ＧＡの計算モデルの検討 Model-1 Model-2 Model-3 Model-4 交叉法突然変異の有無 BLX-α BLX-α UNDX UNDX ○ × ○ × BLX-α(Esheleman，93)：設計変数間に依存関係のない問題に有効 UNDX (ono，97) ：設計変数間に依存関係のある問題に有効＜数値実験＞連続関数最小化問題に適用設計変数間に依存関係のないRastrigin関数 Intelligent Systems Design Lab - Doshisha Univ 数値実験結果 Rastrigin関数設計変数間に依存関係のない問題に対しては Model-1（BLX-α，突然変異有り） Model-3（UNDX，突然変異有り）が有効 Intelligent Systems Design Lab - Doshisha Univ 数値実験のまとめ設計変数間に依存関係のない問題に対しては， Model-1（BLX-α，突然変異有り） Model-3（UNDX，突然変異有り）が有効これらのモデルが実問題にも有効であるか検討するアンテナ配置問題 Intelligent Systems Design Lab - Doshisha Univ アンテナ配置問題概要：アンテナ設置領域内に，あらかじめ用意されたアンテナを配置し，設計コストを最小にする問題制約：電波のカバー領域は，ある値以上でなければならないアンテナの設置できる領域が限定されている Intelligent Systems Design Lab - Doshisha Univ 探索の様子実験概要 4種類のアンテナ Radius Cost 2 5 5 20 10 100 20 400 目的設計コスト最小化制約最大設置アンテナ30本カバー率95% 海上にアンテナは設置できない Intelligent Systems Design Lab - Doshisha Univ 数値実験結果（設計コスト最小化） Model-1（BLX-α，突然変異有り）が良好な結果島モデルによる分散効果も確認 Intelligent Systems Design Lab - Doshisha Univ 結論実数値GAにおける，計算モデルを検討した設計変数間に依存関係のない問題に対しては，いずれの交叉法においても，突然変異を行うことで，良好な結果を得ることができた島モデルによる分散効果も確認された実数値GAを実問題に適用したテスト関数の場合と類似した探索傾向が確認されたテスト関数によるモデルの検討は有効である Intelligent Systems Design Lab - Doshisha Univ Intelligent Systems Design Lab - Doshisha Univ 補足資料 Intelligent Systems Design Lab - Doshisha Univ 研究背景最適化問題とは与えられた制約条件の下で，ある目的関数を最小（最大）にする設計変数を求める問題世の中には様々な最適化問題がある. ディーゼルエンジン燃料噴射スケジュール問題タンパク質の立体構造解析トラス構造物体積最小化問題 Intelligent Systems Design Lab - Doshisha Univ BLX-αとUNDX UNDX BLX-α （Eshelman 93）（Ono 97） • 2つの親個体の各成分距離 α倍拡張した領域内に生成 • 3つの親個体により定義される正規分布領域内に生成 • 設計変数間に依存関係のある問題に弱い • 設計変数間に依存関係のある問題に強い Intelligent Systems Design Lab - Doshisha Univ 実数値GAの突然変異 ① 一様突然変異（Uniform mutation） ② 境界突然変異（Boundary mutation） Intelligent Systems Design Lab - Doshisha Univ 遺伝的アルゴリズムの問題点ビットストリングによる染色体のコーディング探索空間に連続性が反映されていない連続性を考慮した探索実数値GA 高い計算負荷膨大な反復計算が必要なため計算負荷が高くなる計算モデルとしての有効分散GA 局所解への収束多峰性関数において局所解に陥る可能性が高い多様性を維持した探索世代交代モデル Intelligent Systems Design Lab - Doshisha Univ 世代交代モデル複製選択と生存選択を規定 SGA（Simple GA） - Goldberg,89 MGG（Minimal Generation Gap） - 佐藤,97 Intelligent Systems Design Lab - Doshisha Univ MGG 1ペアの両親に対して交叉を複数回行う Intelligent Systems Design Lab - Doshisha Univ 実数値ＧＡの計算モデルの検討（２）交叉法突然変異の有無世代交代モデル Model-1 Model-2 Model-3 Model-4 BLX-α BLX-α UNDX UNDX ○ × ○ × SGA Model-5 Model-6 Model-7 Model-8 BLX-α BLX-α UNDX UNDX ○ × ○ × MGG Intelligent Systems Design Lab - Doshisha Univ SGA（1 / 3）の結果 Rastrigin Schwefel Model-1,3は設計変数間に依存関係のない問題に有効 Intelligent Systems Design Lab - Doshisha Univ SGA（2 / 3）の結果 Griewank Rotated Rastrigin 設計変数間に依存関係のある問題には探索性能に問題がある Intelligent Systems Design Lab - Doshisha Univ SGA（3 / 3）の結果 Rosenbrock関数設計変数間に依存関係のある問題には探索性能に問題がある Intelligent Systems Design Lab - Doshisha Univ MGG（1 / 3）の結果 Rastrigin Schwefel 島モデルが解探索に悪影響を与えている突然変異をしない単一母集団が良好な結果 Intelligent Systems Design Lab - Doshisha Univ MGG（2 / 3）の結果 Griewank Rotated Rastrigin 突然変異は探索に悪影響を与えている Model-6をRotated Rastrigin関数に適用したとき島モデルによる分散効果を確認 Intelligent Systems Design Lab - Doshisha Univ MGG（3 / 3）の結果 Rosenbrock関数 Model-8でのみ，最適解を得ることができる Intelligent Systems Design Lab - Doshisha Univ 全モデルのまとめ対象問題と分散効果依存関係のない問題は分散効果が得やすい依存関係のある問題は分散効果が得にくい世代交代モデルの影響 SGAと突然変異の併用は分散効果が顕著に現れる MGGは遺伝オペレータに左右する Intelligent Systems Design Lab - Doshisha Univ SGAにおける設計コスト最小化 Model-1とmodel-3が良好な結果を示している Intelligent Systems Design Lab - Doshisha Univ 探索履歴（SGA） Rastrigin Model-1 Schwefel Model-3 Intelligent Systems Design Lab - Doshisha Univ 探索履歴（SGA） Griewank Model-4 Rosenbrock Model-4 Intelligent Systems Design Lab - Doshisha Univ 探索履歴（アンテナ配置問題） Model-1 Model-3 Intelligent Systems Design Lab - Doshisha Univ アンテナ配置問題おける個体表現アンテナに付随するパラメータアンテナの設置座標（２D） : （x,y）アンテナの有無 : e 電波の規模 : ｒアンテナの本数＊４個の設計変数が必要 Intelligent Systems Design Lab - Doshisha Univ 電波カバー率の決定方法あらかじめ設定したチェック点をアンテナがカバーしている割合決められた領域等間隔にチェック点を配置する 16/64 = 0.25 Intelligent Systems Design Lab - Doshisha Univ 実問題とテスト関数実問題の最適化における問題点評価に膨大な計算時間を要する予備実験として，数学的テスト関数に適用する有効な計算モデルを実問題へ適用 Intelligent Systems Design Lab - Doshisha Univ