研究資料（2001年03月23日） 並列分散GAのiSIGHTへの実装 同志社大学大学院 知的システムデザイン研究室 廣安 知之， 吉田 純一 分散遺伝的アルゴリズム 単一母集団GA 並列分散GA 特徴： 母集団を複数のサブ母集団に分割 一定世代ごとに移住（パラメータ：移住率・移住間隔） 並列実装が容易．高い並列化効率 良好な解をより速く求めることが可能 Intelligent Systems Design Lab. Doshisha University 分散GAにおける解の成長 Subpopulation B 各サブ母集団では部分解を探索 Subpopulation A Native Immigrant crossover 各サブ母集団で成長した部分解 を交叉によって組み合わせる Hybrid Optimal solution ハイブリッド個体が重要な役割 を果たす Intelligent Systems Design Lab. Doshisha University 単一母集団GAと並列分散GAの比較 SGA - 400個体 早熟収束によって最適解は 得られない PDGA - 50個体 8サブ母集団 ・各サブ母集団では局所探索 ・移住によって多様性を保つ 高速に高品質な解が得られる 計算量自体が減少 Intelligent Systems Design Lab. Doshisha University GENEsYsとの性能比較（Rastrigin関数） GENEsYsとの比較 (Population size 400) 0.000E+00 -2.000E+00 -4.000E+00 -6.000E+00 GENEsYs mikilab_DGA -8.000E+00 mikilab_SGA -1.000E+01 0 100000 200000 300000 400000 500000 Intelligent Systems Design Lab. Doshisha University GENEsYsにおけるパラメータ設定 iSIGHTに実装されたGENEsYsの設定項目※ 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 パラメータの設定の簡略化が必要 理想はパラメータフリー ※送付していただいた画像をもとにリストを作成した Intelligent Systems Design Lab. Doshisha University 分散GAのパラメータとその解決策 基本パラメータ 母集団サイズ 最大評価計算回数 交叉率 交叉法◆ 突然変異率 → 設定が比較的容易．ユーザによる試行錯誤が可能 → 並列分散GAでは交叉率は 1.0 が最適 → 環境分散スキーム ：複数のパラメータを同時に用いることによって 設定を簡略化 突然変異法◆ 分散GAに固有のパラメータ 移住間隔◆ 移住率◆ → プール型移住スキーム ：移住をプール部との間に限定することで 移住パラメータによる環境分散が可能． 非同期の移住が可能． Intelligent Systems Design Lab. Doshisha University 環境分散スキーム 特徴 サブ母集団ごとに異なるパラメータ値を 設定 →パラメータチューニングが軽減 →分散GAと同等以上の性能 分散させる環境 交叉率と突然変異率※ ペナルティーパラメータ 個体数 etc ・・・ 様々な環境によって独自の領域を探索→多様性の維持 パラメータチューニングなしでも分散GAと同等以上の性能 ※“A Parallel Genetic Algorithm with Distributed Environment Scheme”， Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications,(2000)) Intelligent Systems Design Lab. Doshisha University 環境分散スキームの性能 対象問題 制約条件を与えたSphere関数（８設計変数） ペナルティーパラメータ値を分散 実験結果（最適解発見率） 1.0 Success rate 0.8 0.6 SPGA_20 SPGA_160 DGA_160 DEGA 0.4 0.2 0.0 | 0.0 10-2 10-1 100 101 102 103 104 DE Penalty parameter Intelligent Systems Design Lab. Doshisha University プール型移住スキーム 特徴 プール部 移住個体はプール部にプール サブ母集団同士で移住するのではなく プール部と移住操作を行う 非同期に移住が可能． 移住をプール部との間に限定 → 移住パラメータを各サブ母集団ごとに設定可能 （ランダム化も可能） Intelligent Systems Design Lab. Doshisha University プール型移住スキームの性能 対象問題 Rastrigin 関数（５変数） Total number of function call 実験結果（移住率＝0.2のとき） 350000 DGA Pooled DGA 300000 250000 200000 150000 100000 50000 0 1 2 3 4 5 6 7 8 9 10 Migration Interval Intelligent Systems Design Lab. Doshisha University まとめと今後の課題 分散GAは単一母集団のGAと比較して高い性能を示す GENEsYsには設定すべきパラメータが多い パラメータ設定の軽減が重要課題 環境分散スキーム，非同期移住スキームによってパラメータの 設定を軽減することが可能 環境分散スキーム，非同期移住スキームは分散GAと同等以上 の性能を示す 今後はより実問題に近いテスト関数でその有効性を検証 Intelligent Systems Design Lab. Doshisha University GENEsYsとの性能比較（Griewank関数） Intelligent Systems Design Lab. Doshisha University
© Copyright 2024 ExpyDoc
