並列分散遺伝的アルゴリズムの有効 性 学績番号 36980705 畠中 一幸 知的システムデザイン研究室 Intelligent Systems Design Laboratory.

Presentation on theme: "並列分散遺伝的アルゴリズムの有効 性 学績番号 36980705 畠中 一幸 知的システムデザイン研究室 Intelligent Systems Design Laboratory."— Presentation transcript:

1 並列分散遺伝的アルゴリズムの有効 性 学績番号 36980705 畠中 一幸 知的システムデザイン研究室 Intelligent Systems Design Laboratory

2 Intelligent Systems Design Laboratory,Doshisha University 講演内容 最適化と遺伝的アルゴリズム 最適化と遺伝的アルゴリズム 並列分散遺伝的アルゴリズム 並列分散遺伝的アルゴリズム 計算時間の短縮 計算時間の短縮 解探索過程の比較 解探索過程の比較 環境分散遺伝的アルゴリズム 環境分散遺伝的アルゴリズム 結論 結論

3 Intelligent Systems Design Laboratory,Doshisha University 最適化とは 問題解決のために，選択肢の中から 最も良いと思われる方法を選ぶこと Ex. 携帯電話の料金プラン，最短経路 探索

4 Intelligent Systems Design Laboratory,Doshisha University 従来の手法による最適化 目的関数の 傾きを利用 頂点が増える 最適化困難

5 Intelligent Systems Design Laboratory,Doshisha University 生物の進化 遺伝子の コピーミスが 起こる 有性生殖により 生まれた子供は 両親の特徴を 併せ持つ 交叉 自然淘汰優れた個体ほど 子孫を残しやすい 突然変異 生物は長い年月を経るうちに， 環境に適合するように進化してきた．

6 Intelligent Systems Design Laboratory,Doshisha University GA による最適化 評価 1 1 2 2 選択 遺伝的操作

7 Intelligent Systems Design Laboratory,Doshisha University問題点 計算時間が膨大 局所解への収束 パラメータ設定 傾きを利用しない 確率的多点探索 GA の特徴 並列分散化 解決策

8 Intelligent Systems Design Laboratory,Doshisha University 従来の GA 並列分散 GA 速い 遅い

9 Intelligent Systems Design Laboratory,Doshisha University 並列分散 GA における移住 移住間隔 移住率 n 世代 2n 世代 1 世代 分割母集団間での個体の交換操作

10 Intelligent Systems Design Laboratory,Doshisha University 対象問題 節点 4 と６に 10 ｋＮの水平荷重 目 的目 的目 的目 的 総体積の最小化 ６番節点の変位が臨界値以内 各部材が座屈破壊を起こさない 引張応力が臨界値以内 制 約 条 件制 約 条 件制 約 条 件制 約 条 件 節点 1 と 2 は単純支持 5kN

11 Intelligent Systems Design Laboratory,Doshisha University 計算条件 個体数 320 個体 終了条件 500 世代 選択ルーレット選択＋エリート保存 交叉方法一点交叉 交叉率 60 ％ 突然変異率遺伝子長の 1 分割数が 2 n 個の GA に対し， 10 試行の試行平均で比較． パラメータ 比較項目

12 Intelligent Systems Design Laboratory,Doshisha University 計算時間の短縮

13 Intelligent Systems Design Laboratory,Doshisha University 初期値依存性の減少

14 Intelligent Systems Design Laboratory,Doshisha University 移住の効果

15 Intelligent Systems Design Laboratory,Doshisha University 解探索過程の比較 初期母集団の個体は ランダムに生成されてい る 上位 8 個体の断面積分布（ 0 世代） 同じ初期母集団に対し， 以下の GA を適用 SGA 移住なし PGA 隔移住あり PGA 移住間隔 50 世代 移住率 30% 解探索過程の比較を行う

16 Intelligent Systems Design Laboratory,Doshisha University 上位 8 個体の断面積分布（中間世代） PGA 各母集団毎に固有の 個体が生成されている SGA 単一母集団のため 個体の性質が似ている

17 Intelligent Systems Design Laboratory,Doshisha University 最終結果（ SGA ） 1.875×10 -3 （ m 3 ） 最適解の 1.25 倍 変数の分布が最適解と異なり，個体同士の形状が類 似 ＝大域的最適解 → 最適解を得るには，多くの世代が必要

18 Intelligent Systems Design Laboratory,Doshisha University 最終結果（ PGA ：移住なし） 1.624×10 -3 （ m 3 ） 最適解の 1.08 倍 ＝大域的最適解 分割母集団 1 の解が最適解と類似 → しかし初期値依存性の問題は残る

19 Intelligent Systems Design Laboratory,Doshisha University 最終結果（ PGA ：移住あり） ＝大域的最適解 1.548×10 -3 （ m 3 ） 最適解の 1.02 倍 どの分割母集団においても 最適解に非常に類似した解が得られている

20 Intelligent Systems Design Laboratory,Doshisha University 環境分散遺伝的アルゴリズム 環境分散アルゴリズム を提案適切なパラメータ設定に関する問題 GA の探索パフォーマンスは， パラメータ設定に大きく影響される． 最適なパラメータ設定は問題によって異な る DGA,SGA, との比較により，有効性を検 証

21 Intelligent Systems Design Laboratory,Doshisha University パラメータ設定に関する予備実験 0.60.30.6 1.00.30.6 1.00.30.6 1.0 1.0 0.3 0.1/L 1/L 0.1/L 1/L 10/L10/L 10/L 10/L 注） L は個体長 9 つのパラメータ設 定 を SGA と DGA に適 用 パラメータ設定が， 解探索に与える影響 をしらべる

22 Intelligent Systems Design Laboratory,Doshisha University 適合度の履歴（ SGA ）

23 Intelligent Systems Design Laboratory,Doshisha University 適合度の履歴（ DGA ）

24 Intelligent Systems Design Laboratory,Doshisha University 分散 GA の効果 パラメータ設定が等し ければ， DGA が良い しかしながら， パラメータ設定の 問題は残る

25 Intelligent Systems Design Laboratory,Doshisha University 環境分散遺伝的アルゴリズム 従来の DGA 環境分散 GA

26 Intelligent Systems Design Laboratory,Doshisha University Worst = 1.38 Avg. 1.58 Best = 1.74 Avg. 1.70 Best = 1.78 Worst = 1.58 環境分散 GA の効果 1.75

27 Intelligent Systems Design Laboratory,Doshisha University 結 論 並列処理を行うことにより，計算時間が短縮し た． 母集団を分割し移住を行うことで 解の品質と信頼性が向上した． 環境分散 GA は最適な交叉率， 突然変異率が不明な場合に有効 制約条件付き最適化問題に SGA と並列分散 GA を適用することにより， 以下のことがらが判明した．

28 Intelligent Systems Design Laboratory,Doshisha University 今後の課題 総個体数と分割数． – 効率的に探索を行うにはどうすれば良いのか． 適切な移住スキームの提案． – 「いつ」，「どこで」，「どのような個体」と行 うのか． 分割母集団での役割分担 – 選択方法や，交叉方法を各母集団で変化させる．

29 Intelligent Systems Design Laboratory,Doshisha University 論文リスト 1. 三木光範, 畠中一幸 : 分散並列 GA による計算時間の短縮と最適解の高品質化, 第 10 回 超並列計算研究会, (1998). 2. 三木光範, 畠中一幸 : 並列分散 GA による計算時間の短縮と解の高品質化, 日本機械学 会 [No.98-14], 第 3 回最適化シンポジウム講演論文集, pp..59-64, (1998). 3.Mitsunori MIKI, Tomoyuki HIROYASU and Kazuyuki HATANAKA: Parallel Genetic Algorithms with Distributed-Environment Multiple Population Scheme,Proc. 3rd World Congress of Structural and Multidisciplinary Optimization (WCSMO), Vol. 1, pp.186- 191,(1999). 4. 三木光範, 廣安知之, 金子美華, 畠中一幸 : 環境分散型並列遺伝的アルゴリズム, 電子情 報通信学会電子情報通信学会技術研究報告 AI99011~21, pp.87-94,(1999). 5. 畠中一幸, 三木光範, 廣安知之 : 分割母集団 GA における移住間隔の最適化, 日本機械学 会, (1999). 6. 畠中一幸 : 並列分散遺伝的アルゴリズム, 第 1 回 同志社大学工学部並列研究会, (1999). 7. 三木光範, 廣安知之, 金子美華, 畠中一幸 : 環境分散遺伝的アルゴリズムにおける探索メカ ニズム, 情報処理学会 ９９年度秋期全国大会, (1999). 8.Mitsunori MIKI, Tomoyuki HIROYASU, Mika KANEKO and Kazuyuki HATANAKA: A Parallel Genetic Algorithm with Distributed Environment Scheme,IEEE Proceedings of Systems, Man and Cybernetics Conference SMC'99, (1999), pp.695-700 (1999).

30 Intelligent Systems Design Laboratory,Doshisha University Appendix 補 足 資 料

31 Intelligent Systems Design Laboratory,Doshisha University 最適化問題の定式化 目的関数 設計変数 制約条件

32 Intelligent Systems Design Laboratory,Doshisha University 従来の最適化手法 長所 : 高速 短所 : 勾配の評価，初期値依存性 線形計画法 非線形計画法

33 Intelligent Systems Design Laboratory,Doshisha University 遺伝的アルゴリズム シミュレーテッドアニー リング 確率的戦略 モンテカルロ 法 モンテカルロ 法 長所 : 初期値依存性が無い，勾配の評価が不要 短所 : 計算コストが高い ランダム 重点的

34 Intelligent Systems Design Laboratory,Doshisha University 進化的戦略 遺伝的アルゴリズム（ Genetic Algorithms:GA ） 遺伝的プログラミング（ Genetic Programming:GP ）， 進化戦略（ Evolutionary Strategy:ES ） 進化的プログラミング（ Evolutionary Programming:EP ）， クラシファイアシステム（ Classify System ） ニューラルネットワーク（ Neural Network:NN ）， セルラーオートマトン（ Cellar Automata:CA ）， シミュレーテッドアニーリング (Simulated Annealing:SA ）も， 進化戦略との類似性が高い． 生物の営みの一部を工学的にモデル化した手法 これらの方法を用いた最適化手法の特徴は， 目的関数の感度を用いない点である．

35 Intelligent Systems Design Laboratory,Doshisha University 遺伝的アルゴリズム 生物の進化を工学的にモデル化した手法 海外 1985 ICGA: International Conference on Genetic Algorithms 1990 PPSN: International Conference on Parallel Problem Solving from Nature 1994 ICEC: International Conference on Evolutionary Computation 1999 GECCO: 国内 人工知能学会，情報処理学会，日本ファジィ学会等 J.H.Holland ： Adaptation In Natural and Artificial Systems, University of Michigan Press,(1975). D.E.Goldberg: Genetic Algorithms in Search Optimization and Machine Leraning. Addison-Wesley,Reading,Mass. (1989).

36 Intelligent Systems Design Laboratory,Doshisha University 単一母集団を使用 個体の評価を並列に行う 共有メモリ型の 並列計算機向き 大規模並列化モデル

37 Intelligent Systems Design Laboratory,Doshisha University 粗粒度並列化モデル 母集団を 複数のサブ母集団に分割 「移住」と言う解交換を 行う．

38 Intelligent Systems Design Laboratory,Doshisha University 細粒度並列化モデル プロセッサ 1 つに 1 つまたは比較的少数の個体 解交換は近傍のみ 計算効率は優れているが， 距離の離れたプロセッサ間で の 情報交換が行えない

39 Intelligent Systems Design Laboratory,Doshisha University Performance of DEGA

40 Intelligent Systems Design Laboratory,Doshisha University パラメータ設定の影響 (SGA) Mutation Rate 0.1/L1/L10/L

41 Intelligent Systems Design Laboratory,Doshisha University パラメータ設定の影響 (DGA) Mutation Rate 0.1/L1/L10/L

42 Intelligent Systems Design Laboratory,Doshisha University 環境分散遺伝的アルゴリズム 分割母集団毎に， 異なる突然変異率と， 交叉率を設定

43 Intelligent Systems Design Laboratory,Doshisha University 最適解の形状 5kN

44 Intelligent Systems Design Laboratory,Doshisha University 特徴 多峰性関数 依存関係が無い 設計変数間に依存関係が無い で最小値 0 となる Rastrigin 関数

45 Intelligent Systems Design Laboratory,Doshisha University Rosenbrock 関数 特徴 単峰性関数 強い依存関係 設計変数間に強い依存関係がある で最小値 0 となる

46 Intelligent Systems Design Laboratory,Doshisha University 移住間隔の最適化 初期段階 分離された母集団の 独立性を高めることが重要初期段階 分離された母集団の 独立性を高めることが重要移住間隔大移住間隔大 収束段階 分割母集団全体で 良好な解の交換が必要収束段階 分割母集団全体で 良好な解の交換が必要移住間隔小移住間隔小 解探索の進行と共に減少 移住間隔を解探索の進行と共に減少させる方法を提案

47 Intelligent Systems Design Laboratory,Doshisha University 提案手法の効果（ Rastrigin ） 100501051

48 Intelligent Systems Design Laboratory,Doshisha University 提案手法の効果（ Rosenbrock ） 100501051

49 Intelligent Systems Design Laboratory,Doshisha University 提案手法の効果（トラス構造物） 100501051

50 Intelligent Systems Design Laboratory,Doshisha University 適合度の履歴（ SGA:pop.2430 ）

51 Intelligent Systems Design Laboratory,Doshisha University