分散確率モデル遺伝的アルゴリズムにおける解探索メカニズムの検討

Presentation on theme: "分散確率モデル遺伝的アルゴリズムにおける解探索メカニズムの検討"— Presentation transcript:

1 分散確率モデル遺伝的アルゴリズムにおける解探索メカニズムの検討
知的システムデザイン研究室 　　　　　　　　　平井　聡

2 研究背景 最適化とは 最適化問題 確率的手法 制約条件下で目的関数を最大または最小化する問題 離散最適化 連続最適化
（e.g. たんぱく質立体構造予測，トラス構造物最適化） 確率的手法 遺伝的アルゴリズム（Genetic Algorithm: GA） シミュレーテッドアニーリング（Simulated Annealing:SA）

3 遺伝的アルゴリズム（GA） 生物の進化を模倣した最適化アルゴリズム 母集団に対して，遺伝的操作を繰り返し適用
多点探索により，大域的な探索に優れている 多くの評価計算が必要であり，計算コストがかかる

4 分散確率モデル遺伝的アルゴリズム(DPMBGA)(廣安等:2003)
研究目的 GAの問題点 多くの評価計算回数が必要，多量の計算資源が必要 解決策 効率の高い解探索し，評価計算回数を少なくする 良質な親個体の形質を子個体が引き継ぐ 母集団の多様性の維持 設計変数間の依存関係の考慮 分散確率モデル遺伝的アルゴリズム(DPMBGA)(廣安等:2003) 分散GA (DGA) ＋ 確率モデルGA (PMBGA) DPMBGAの解探索性能が検証済み DPMBGAの解探索メカニズム アルゴリズムの改良 研究目的

5 分散遺伝的アルゴリズム（DGA） 母集団を複数のサブ母集団に分割 移住によりサブ母集団の個体を交換 母集団の多様性を維持

6 確率モデル遺伝的アルゴリズム（PMBGA）
子個体を親個体の正規分布より生成 子個体は良質な親個体の形質を引き継ぐ 個体の抽出 確率モデルの生成 　(正規分布等) 子個体の生成

7 確率モデル遺伝的アルゴリズム（PMBGA）
子個体を親個体の正規分布より生成 子個体は良質な親個体の形質を引き継ぐ 個体の抽出 確率モデルの生成 　(正規分布等) 子個体の生成

8 確率モデル遺伝的アルゴリズム（PMBGA）
子個体を親個体の正規分布より生成 子個体は良質な親個体の形質を引き継ぐ 個体の抽出 確率モデルの生成 　(正規分布等) 子個体の生成

9 確率モデル遺伝的アルゴリズム（PMBGA）
子個体を親個体の正規分布より生成 子個体は良質な親個体の形質を引き継ぐ 個体の抽出 確率モデルの生成 　(正規分布等) 子個体の生成

10 確率モデル遺伝的アルゴリズム（PMBGA）
子個体を親個体の正規分布より生成 子個体は良質な親個体の形質を引き継ぐ 個体の抽出 確率モデルの生成 　(正規分布等) 子個体の生成

11 確率モデル遺伝的アルゴリズム（PMBGA）
子個体を親個体の正規分布より生成 子個体は良質な親個体の形質を引き継ぐ 個体の抽出 確率モデルの生成 　(正規分布等) 子個体の生成

12 DPMBGAの概要 移住操作に多様性の維持 (DGA) 確率モデルによる子個体生成 (PMBGA)

13 解探索メカニズムの検討 多峰性関数 Rastrigin関数 設計変数間に依存関係がある関数 Rosenbrock関数 多峰性関数

14 多峰性の関数 Rastrigin関数は多数の局所解をもつ 母集団が局所解に陥り，最適解へ到達しない 母集団の多様性の維持が重要 序盤 中盤
終盤

15 多峰性の関数の探索履歴 Island 1 Island 2 各島で局所解に収束 Island 3
Next I want to show you the searching steps of PMBGA. This is the island 1 and island2 Searching points converge this local optima in Island 1 Island 2

16 多峰性の関数の探索履歴 Island 1 Island 2 個体が移住操作により， 異なる島に移動 Island 3
However, in the migration method individual in island 2 move to island1 At the same way, individual in island 1 moves to island2

17 多峰性の関数の探索履歴 Island 1 Island 2 子個体が最適解付近に生成 Island 3
Then we can make child individuals in these space.

18 多峰性の関数の探索履歴 Island 1 Island 2 最適解に到達 Island 3 多様性の維持が重要
Finally searching points reach to the optimal solution. So key issue is to maintain the diversity

19 数値実験 Total Population 512 Number of Island 1(PMBGA), 32(DPMBGA)
Number of Elite 1 Migration Interval 5 Migration Rate 0.625 Archive size for PCA 100 Sampling Rate 0.25 Amp of Variance 1.5 Chromosome Length 0.1/(Dim of function) Max Generation 1000

20 高次元のRastrigin関数の解探索履歴履歴
DPMBGA は最適解に到達 PMBGAは局所解に収束

21 解探索メカニズムの検討 多峰性関数 Rastrigin関数 設計変数間に依存関係がある関数 Rosenbrock関数

22 設計変数間に依存関係のある関数 依存関係のない関数 各設計変数が独立に最適値がある 依存関係のある関数 設計変数の最適値が他の設計変数に依存

23 設計変数間に依存関係のある関数 依存関係のない関数 各設計変数が独立に最適値がある 依存関係のある関数 設計変数の最適値が他の設計変数に依存

24 設計変数間に依存関係のある関数 依存関係のない関数 各設計変数が独立に最適値がある 依存関係のある関数 設計変数の最適値が他の設計変数に依存

25 設計変数間に依存関係のある関数 依存関係のない関数 各設計変数が独立に最適値がある 依存関係のある関数 設計変数の最適値が他の設計変数に依存

26 設計変数間に依存関係のある関数 依存関係のない関数 各設計変数が独立に最適値がある 依存関係のある関数 設計変数の最適値が他の設計変数に依存

27 DPMBGA + PCA 移住操作に多様性の維持 (DGA) 主成分分析による無相関化 (PCA)

28 設計変数に依存関係がある関数 多変量を少数の変量で表す方法 最良個体群から分散を計算 その分散値を用い，依存関係のない空間に 回転させる

29 依存関係のある関数の探索履歴

30 依存関係のある関数の探索履歴 PCAなし

31 依存関係のある関数の探索履歴 PCAなし PCA

32 依存関係のある関数の探索履歴 PCAなし PCA

33 依存関係のある関数の探索履歴 PCAなし PCA

34 高次元Rosenbrock関数の解探索履歴履歴
PCAを用いても単島では解けない 島モデルでは最適解に到達

35 確率分布 個体数512とした時，最良個体(PCAの基準)の履歴 分散島モデル(ＤＰＭＢＧＡ） 単島モデル(ＰＭＢＧＡ）

36 確率分布 個体数512とした時，最良個体(PCAの基準)の履歴 分散島モデル(ＤＰＭＢＧＡ） 単島モデル(ＰＭＢＧＡ）

37 確率分布 個体数512とした時，最良個体(PCAの基準)の履歴 収束が早い 多様性の維持 分散島モデル(ＤＰＭＢＧＡ）
単島モデル(ＰＭＢＧＡ）

38 確率分布 個体数512とした時，最良個体(PCAの基準)の履歴 最適解に到達する前に収束 最適解に到達 分散島モデル(ＤＰＭＢＧＡ）
単島モデル(ＰＭＢＧＡ） 分散島モデルは，全体をみると正確な確率モデルが構築できる

39 解探索メカニズムのまとめ 多峰性の関数 設計変数間に依存関係のある問題 単島だと局所解に収束 分散島である移住操作により最適解に到達
PCAにより，依存関係をなくすように近似する 分散島モデルにより，個々の島では正確な確率モデルの構築ができないが，全体で正確な確率モデルを構築

40 DPMBGAの問題点 抽出個体により収束が早くなる可能性がある 最適解に到達できない

41 DPMBGAの問題点の解決策 抽出個体が近いなら，子個体生成の範囲を大きくする 分散の増幅率を増加させる
子個体生成の範囲を調節するパラメータ

42 分散の増幅率 子個体を生成するとき，生成する範囲を調節するパラメータ 増幅率大 増幅率中 増幅率小 分散の増幅率を適応的に変化させる

43 DPMBAの改良 子個体を母集団より少し収束するように生成 母集団の一般化分散値を比較 子個体の一般化分散値が閾値なら次世代
それ以外，分散の増幅率を増加減少し子個体を再度生成

44 DPMBAの改良 子個体を母集団より少し収束するように生成 母集団の一般化分散値を比較 子個体の一般化分散値が閾値なら次世代
それ以外，分散の増幅率を増加減少し子個体を再度生成

45 数値実験 多峰性関数 Rastrigin関数 設計変数間に依存関係がある関数 Rosenbrock関数

46 パラメータ Total Population 1024 Number of Island 4(Improved), 64
Number of Elite 1 Migration Interval 10 Migration Rate (Improved),0.625 Archive size for PCA 100 Sampling Rate 0.25 Child Created Rate 95% Chromosome Length 0.1/(Dim of function) Max Generation 1000

47 解探索履歴 Rosenbrock関数 Rastrigin関数 評価計算回数はかかるが，最適解に到達することができる

48 まとめ 解探索メカニズムの検討 DPMBGAの改良 多峰性の関数 設計変数間に依存関係のある関数 抽出個体により，局所解に陥る可能性がある
母集団の多様性，移住することが重要 設計変数間に依存関係のある関数 PCAによる，依存関係をなくす手法が有効 DPMBGAの改良 抽出個体により，局所解に陥る可能性がある 子個体が母集団より，少し収束するように増幅率を適応的に変化させる

49 発表論文リスト 第3回情報科学技術フォーラム 遺伝的アルゴリズムを用いたコージェネレーションシステムの最適設計
廣安 知之，三木 光範，平井 聡，下坂 久司，梅田 良人，青木 修一，田中 洋一 The 2004 IEEE Conference on Cybernetics and Intelligent Systems Satisfactory Design of Cogeneration System using Genetic Algorithm Satoshi Hirai, Tomoyuki Hiroyasu, Mitsunori Miki, Hisashi Shimosaka, Yoichi Tanaka, Syuichi Aoki, Yoshito Umeda 第15回設計工学・システム部門講演会 分散確率モデル遺伝的アルゴリズムにおける解探索能力についての検討 平井聡，廣安知之，三木光範，下坂久司 The International Association of Science and Technology for Development CONSIDERATION OF SEARCHING ABILITY FOR Distributed Probabilistic Model-building Genetic Algorithm Satoshi Hirai, Tomoyuki Hiroyasu, Mitsunori Miki, Hisashi Shimosaka 情報処理学会「数理モデル化と問題解決研究会」第57回講演　 2006年3月17日予定 分散確率モデル遺伝的アルゴリズムにおける解探索メカニズムの検討

50

51 分散の増幅率による各関数の最適値 Rastriginの最適値は1.4 Rosenbrock関数の最適値は1.7
分散の増幅率を適応的に変化できるように改良する

52 DPMBGAの改良(一般化分散値が小) 母集団の一般化分散を計算(100) サンプリング個体数の抽出 分散の増幅率(2.0)で子個体を生成
子個体の一般化分散値を計算(20) 一般化分散値が小 増幅率を増加し，ステップ3に戻る

53 DPMBGAの改良(一般化分散値が大) 母集団の一般化分散を計算(100) サンプリング個体数の抽出 分散の増幅率(2.5)で子個体を生成
子個体の一般化分散値を計算(150) 一般化分散値が大 増幅率を減少し，ステップ3に戻る

54 DPMBGAの改良(一般化分散値が適切)
母集団の一般化分散を計算(100) サンプリング個体数の抽出 分散の増幅率(2.3)で子個体を生成 子個体の一般化分散値を計算(90) 一般化分散値が適切なら 次世代に進む

55 GAの問題点 Supernova Cluster Systemの構成
# Node 256 Processor AMD Opteron 1.8 GHz×2 Memory PC2700 Registered ECC 2GB Chipset AMD OS Turbolinux 8 for AMD64 Communication Library Mpich-1.2.5 Communication Medium Gigabit Ethernet Rpeak TFlops No.93 in 2003, No.499 in 2004 (Top 500 Supercomputers) Cogeneration System最適設計問題など実問題は，計算に膨大な計算時間がかかる

56 アーカイブ 主成分分析を行うための個体の情報を格納する 現在の世代までに発生した最良個体を格納する 解探索初期は格納のみ行う

57 主成分分析（PCA） 多くの変量を少数の指標で表す方法 最良個体から個体の分散V（情報量）を取得 そのVを軸とし個体を回転させ，無相関に移す

58 子個体生成 子個体の生成（PMBGA） 個体の相関を元に戻す 正規乱数に基づき設計変数を生成 子個体は独立に生成される
生成子個体の相関を元に戻す 母集団の全個体と置換

59 DPMBGAの特徴 特徴 パラメータ 実数値確率モデル遺伝的アルゴリズム 島モデルにより多様性の維持
新しい個体は設計変数間の依存関係を考慮した 主成分分析により生成 パラメータ 分散の増幅率 サンプリング個体数 アーカイブサイズ

60 正規乱数の分散の増幅率 正規乱数の発生範囲を広げ，子個体の多様性を維持 増幅率 高すぎる → 収束が行われない
高すぎる　→　収束が行われない 低すぎる　→　早熟収束する可能性が高い

61 数値実験 実験概要 対象問題 増幅率のパラメータ検討 2つのモデルで検討 （With PCA, Without PCA） 依存関係のない問題
Rastrigin関数，Schwefel関数 依存関係のある問題 Rosenbrock関数，Ridge関数

62 パラメータ Total Population 512 Number of Island 32 Number of Elite 1
Migration Interval 5 Migration Rate 0.625 Archive size for PCA 100 Sampling Rate 0.25 Amp of Variance From 0.1 To 3.0 Chromosome Length 0.1/(Dim of function) Max Generation 1000

63 解発見回数（Rastrigin関数， Schwefel関数）
増幅率1.1から1.5まで良好な結果 PCAを行わないモデルが良好な結果を示した

64 数値実験（ Rosenbrock関数, Ridge関数）
PCAを行わないと，依存関係のある問題は解けない 増幅率が1.4から2.0までが最も良好な結果を示した

65

66 (4)次世代の個体の相関を戻し，母集団と置き換える
DPMBGAの概要 (1)良好な子個体の抽出 母集団 (2)主成分分析を用い 設計変数の無相関化 (4)次世代の個体の相関を戻し，母集団と置き換える (3)正規乱数により 次世代の個体を生成

67 個体のサンプリング サンプリング個体 母集団内の評価値の高い個体より， 定めた個数を抽出する (1)良好な子個体の抽出 母集団
サンプリング個体群 サンプリング個体 母集団内の評価値の高い個体より， 定めた個数を抽出する

68 個体の無相関化 目的 アルゴリズム 設計変数の依存関係を考慮し， 子個体を生成する 主成分分析(PCA)を行い， ベクトルVを取得
(2)主成分分析を用い 設計変数の無相関化 主成分分析 多くの変量の値をできるだけ情報の損失なしに，少数個の総合的指標で代表させる方法

69 (4)次世代の個体の相関を戻し，母集団と置き換える
新しい個体の生成 子個体の生成 正規乱数に基づき設計変数 を生成 子個体は独立に生成される 母集団への置換 個体の相関を元に戻す 母集団の全個体と置換 母集団 (4)次世代の個体の相関を戻し，母集団と置き換える (3)正規乱数により 次世代の個体を生成

70 主成分分析 サンプル個体群の設計変数から，設計変数の平均値を引き，行列 X に格納 Xの共分散行列をS行列とする
Sの固有ベクトルV行列とする 固有ベクトルによりXの無相関化 子個体の発生(Yの分散・平均の正規乱数で生成)

71 正規乱数 ボックス・ミューラー法（Box-Muller transform） 平均μ，分散σ2 の正規分布(μ, σ2)
一様乱数(0,1)の要素α，βを次式で変換 上記の式より正規乱数(0,1)が生成できる 正規乱数(0,1)に平均　（AMP・・・分散の増幅率）

72 増幅率の検討(Griewank関数) 発見回数 PCA Griewank関数は次元数が多くなると依存関係が弱くなる

73 突然変異の解探索履歴 分散1.5での，突然変異の有無による解探索 突然変異を行わないとRastrigin関数は解けない
突然変異は多様性を維持する上で重要

74

75