プール型移住メカニズムを用いた 分散遺伝的アルゴリズムの非同期モデルの検討 同志社大学大学院工学研究科知識工学専攻 知的システムデザイン研究室 学籍番号 36990723 根上 昌巳 Intelligent Systems Design Laboratory 本発表の流れ 分散GAの概説 分散GAの利点と問題点 プール型移住メカニズムを用いた分散GAの利点 数値実験 結論 プール型移住メカニズムを用いた 分散GAの有効性の検証． Intelligent Systems Design Laboratory 分散遺伝的アルゴリズム(分散GA) 母集団を幾つかのサブ母集団に分割． サブ母集団ごとに各々GAが行われる． 並列処理により計算時間の短縮． サブ母集団 個体 母集団 Intelligent Systems Design Laboratory 移住操作 移住間隔 移住率 一定期間ごとに幾つかの割合の個体を交換． 早熟収束の回避と多様性の維持を行う． 通信は移住のみであり通信負荷が少ない． Intelligent Systems Design Laboratory 終了判定 終了判定の条件は設定困難なパラメータ． 母集団全体が多様性を失えば探索を終了． 分散GAでは移住以外の通信が必要． 終了判定の時期が問題となる． 母 集 団 全 体 Intelligent Systems Design Laboratory GAにおける多様性 多様性の検出法 平均遺伝子を用い，探索の方向を把握． エリートとの比較により，多様性の喪失を判断． 染色体 0 1 0 0 1 1 0 1 1 0 1 1 0 0 遺伝子 0 0 1 1 0 1 1 平均遺伝子 0 1 0 1 1 1 0 1 ×2 > 0 ×1 1 Intelligent Systems Design Laboratory 分散GAの利点と問題点 分散GA →母集団を分割 並列処理による処理速度の向上． 早熟収束の回避と多様性の維持． パラメータの増加（移住率・移住間隔）． 母集団全体の個体情報を得ることが困難． 終了判定が困難． プール型移住メカニズムを用いた分散GA Intelligent Systems Design Laboratory プール型移住メカニズムを用いた分散GA (Pooled DGA) 並列計算機上のノードにプール部を分配． サブ母集団ごとにプール部と移住操作を行う． プール部に移住個体をプールする． 個母 体集 情団 報全 の体 一の 部 プール部 Intelligent Systems Design Laboratory Pooled DGAの利点 分散GAの問題点 パラメータの増加（移住率・移住間隔）． 母集団全体の個体情報を得ることが困難． Pooled DGA 移住パラメータの設定が容易． 母集団全体の個体情報の取得が容易． サブ母集団ごとにプール部と移住操作を行う． プール部に移住個体をプールする． 移住パラメータをサブ母集団ごとに容易に設定． →母集団全体の個体情報の一部を保有． 有効な分散GAのモデル 移住パラメータの非同期化． Intelligent Systems Design Laboratory 数値実験 対象問題 関数名 10 Rastrigin 依存 定義 f ( xi |i 1,10 ) 100 xi2 10 cos2xi i 1 なし 設計変数間に依存関係がなく 格子状に複数の準最適解を持つ x = (0,…,0)の時，最小値0をとる Intelligent Systems Design Laboratory 数値実験 各種パラメータ設定 DGA Decoding gray code Chromosome length １0bit × 5 Selection Crossover Mutation rate Total Population size Number of Sub Populations Sub Population size Pooled DGA Roulette Selection + Elitist preservation Selection One point Crossover (Crossover rate=0.6) 1/L (L is the chromosome length) 280 7 6 40 Pool size Migration method 40 random ring Intelligent Systems Design Laboratory Pooled DGAの移住操作 移住率・移住間隔の設定が必要． 移住率のランダム化は有効． 移住パラメータをランダム化することが容易． Pooled DGAでの移住操作 移住率 = Random(0.1～0.5) 移住間隔 = Random(1～10世代) →Random model Intelligent Systems Design Laboratory Pooled DGAの移住操作 多様性が失われた時点で移住する． 移住パラメータをサブ母集団ごとに設定する ことが容易なモデル． Pooled DGAでの移住操作 移住率 = Random(0.1～0.5) 移住間隔 =サブ母集団ごとの平均遺伝子と エリート個体とのハミング距離が0． →Diversity model Intelligent Systems Design Laboratory Pooled DGAの移住操作 Comparison of Random model and Diversity model 298356 30000 25000 20000 15000 10000 5000 0 60000 Total number of function call Execution Time (msec) 35000 50000 40000 30000 20000 10000 0 Optimum 0 Evaluation value 122112 -0.005 Pooled DGA: Random model Pooled DGA: Diversity model Pooled DGA: Migration rate = 0.2 DGA: Migration rate = 0.2 -0.01 Intelligent Systems Design Laboratory Pooled DGAの移住操作 History of the evaluation value of Diversity model Evaluation value 0 -10 -20 -30 0 10 20 30 40 50 Generation 60 Migration Sub population A Sub population B Sub population C 70 80 90 Intelligent Systems Design Laboratory Pooled DGAの移住操作 History of the evaluation value of Diversity model Evaluation value 0 -0.05 Migration Sub population A Sub population B Sub population C -0.1 100 110 120 130 140 150 Generation 160 170 180 Intelligent Systems Design Laboratory Pooled DGAでの実装上の非同期移住 プール部への同時アクセスはプール部の 不整合を引き起こす． 移住はサブ母集団の多様性の維持． プール部 Intelligent Systems Design Laboratory 非同期モデルの検討 Comparison of Asynchronous access model 25000 20000 15000 10000 5000 0 50000 40000 30000 Optimum 0 Evaluation value 30000 60000 Total number of function call Execution Time (msec) 35000 -0.005 20000 10000 0 Random model Asynchronous Random model -0.01 Intelligent Systems Design Laboratory Pooled DGAの利点 分散GAの問題点 パラメータの増加（移住率・移住間隔）． 母集団全体の個体情報を得ることが困難． Pooled DGA 移住パラメータの設定が容易． 母集団全体の個体情報の取得が容易． 多様性を考慮した終了判定を容易に実装 Intelligent Systems Design Laboratory Pooled DGAでの多様性を考慮した終了判定 分散GAでの終了判定 終了判定の時期 毎世代終了判定を行う． 終了判定の条件 サブ母集団ごとの平均遺伝子間のハミング距離が0． Pooled DGAでの終了判定 終了判定の時期 サブ母集団ごとの平均遺伝子と エリート個体とのハミング距離が0． 終了判定の条件 サブ母集団ごとの平均遺伝子と プール部の平均遺伝子間のハミング距離が0． Intelligent Systems Design Laboratory Pooled DGAでの多様性を考慮した終了判定 Execution time of migration rate = 0.2 Execution Time (msec) 140000 DGA Pooled DGA 120000 100000 80000 60000 40000 20000 0 1 2 3 4 5 6 7 8 9 10 Migration Interval Intelligent Systems Design Laboratory Pooled DGAでの多様性を考慮した終了判定 Total number of function call of migration rate = 0.2 Total number of function call 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 Laboratory Pooled DGAでの多様性を考慮した終了判定 Fitness value of migration rate = 0.2 Evaluation value Optimum 0 -0.005 DGA Pooled DGA -0.01 1 2 3 4 5 6 7 8 9 10 Migration Interval Intelligent Systems Design Laboratory 結論 分散GAの問題点 パラメータの増加（移住率・移住間隔）． 母集団全体の個体情報を得ることが困難． Pooled DGA 移住パラメータの設定が容易． 母集団全体の個体情報の取得が容易． 有効な分散GAのモデル Intelligent Systems Design Laboratory 発表論文リスト １．廣安知之，三木光範，根上昌巳： 並列分散遺伝的アルゴリズムの移住率のランダム化，理工学研究報告，40巻２号，pp25-34 ，1999 ２．廣安知之，三木光範，○根上昌巳： 非同期移住型分散遺伝的アルゴリズム，ISCIE, (1999) , pp.379-380 ３． ○廣安知之，三木光範，根上昌巳： Distributed Genetic Algorithms with Randomized Migration Rate ， IEEE Proceedings of Systems, Man and Cybernetics Conference SMC'99, Vol. 1, (1999) , pp.689-694 ４．廣安知之，三木光範，○根上昌巳： 貯蓄型分散遺伝的アルゴリズムにおける移住と移住間隔， 情報処理学会情報処理学会研究報告99-MPS-28, (2000) , pp.29-32 Intelligent Systems Design Laboratory Intelligent Systems Design Laboratory
© Copyright 2024 ExpyDoc
