ビット空間における ＧＡの解探索モニタリングシステム

Presentation on theme: "ビット空間における ＧＡの解探索モニタリングシステム"— Presentation transcript:

1 ビット空間における ＧＡの解探索モニタリングシステム
Monitoring System of Searching History of GA in a Bit Space † ‡ ‡ ○赤塚浩太，廣安知之，三木光範 † 同志社大学大学院工学研究科 ‡ 同志社大学工学部知識工学科

2 遺伝的アルゴリズム 生物の進化を模倣 数多くの問題に適用可能 多点探索 遺伝的操作 選択 交叉 突然変異 適合度の 高い個体が 多く生き残る
母集団 個体間の 情報交換 交叉 個体情報の 変更 突然変異 個体

3 コーディング GAは一般的に対象問題の 設計変数値をコード化し利用 探索空間がなんらかの 影響を受ける可能性 1 1 1 対象問題 z y
x 1 Decoding 1 Real Number Space Encoding 染色体 1 個体 Bit Space

4 ? コーディングの影響 GAは対象問題の 設計変数値をコード化し利用 我々が把握している外観とは異なった空間を探索している可能性 実数値空間
ビット空間 Encoding 1 1

5 対象問題とGAの解探索能力 136 331 Rastrigin Rosenbrock Ridge Rotated Rastrigin
終了 世代 100,000以上 終了世代 終了 世代 100,000以上 終了世代 136 331 我々が把握している関数の外観と， GAによる探索の困難さはまったく異なっている． ※ すべて10設計変数，1設計変数あたり10bit ※ 640個体を用い100,000世代x10試行の探索結果

6 研究目的 GAが対象問題の解探索に有効か否か 対象問題の設計変数値による外観とは異なる コーディングにより，GAが探索している空間と
実数値による空間が異なる可能性 コーディング後のGAの探索過程 　(適合度空間・ランドスケープ)を把握したい

7 探索過程を把握する手法 ハミング距離，適合度，頻度の３軸を用いる 離散的最適化問題向き 設計変数値を用いる手法 コーディング前の情報を利用
Ex．Stationary fitness-probability Landscape 　　　　　　　　　　　　　　　　　　　　　　　　 （内藤 ’94） 離散的最適化問題向き コーディング前の情報を利用 設計変数値を用いる手法 Ex．適合度空間のランドスケープ可視化と ユーザーの能動的探索による進化計算の高速化 　　　　　　　　　　　　　　　　　　　　 （林田，高木 ’01） Ex．ラディアルベーシス関数ネットワークと領域適応型 遺伝的アルゴリズムを用いた最適設計 　　　　　　　　　　　　　　　　　　　　 （荒川ら ’99）

8 解探索モニタリングシステムの提案 連続最適化問題において，コーディング後の ビット空間のランドスケープを把握するシステム 提案システム
視覚化 実数値空間 ビット空間 1 1 1 Encoding 情報抽出

9 提案システムの概観 初期化時(Parameter入力) 探索時 (いくつかの View mode がある)

10 提案システムの構成(出力) 提案システム GA部 Analyze部 GUI部 通常の GAを行う ビット空間を 把握する手法 (染色体から
情報を抽出) ユーザーから 　　　　の入力 出力情報 　 　の視覚化

11 提案システムの構成(出力) 提案システム GA部 Analyze部 GUI部 ビット空間 情報抽出 視覚化 Hamming Distance
1 1 1 Topology 実数値空間

12 染色体情報の抽出手法：Analyze部 Hamming Distance Analyze部 情報抽出 Hamming Distance
Topology Analyze部 情報抽出 Hamming Distance Topology

13 染色体情報の抽出手法：Analyze部 Hamming Distance 1 遺伝子座ごとに2個体を 比較し，異なる遺伝子座の数
Topology 1 遺伝子座ごとに2個体を 比較し，異なる遺伝子座の数 Hamming Distance = 3 同じ遺伝子が連続する 部分を1つのグループとし， そのグループ数 1 Topology = 4

14 染色体情報の抽出手法：Analyze部 Hamming Distance ハミング距離と 突然変異の回数に関係有り
Topologyが近い個体同士が交叉すると， Topologyが近い個体が生まれやすい Topology Topology = 4 Topology = 4 1 1 1 1 1 1 Topology = 5 Topology = 5

15 提案システムの構成(出力) 提案システム GA部 Analyze部 GUI部 ビット空間 情報抽出 視覚化 Hamming Distance
1 1 1 Topology 実数値空間

16 提案システムの構成:GUI部 実数値空間による表示 GUI部 対象問題の設計変数値を利用 視覚化 ビット空間による表示
Analyze部で抽出したTopology, Hamming Distanceを利用 探索履歴を用いた表示 過去の探索点を元に Topologyの分散を利用

17 GUI部：実数値空間による表示 対象問題の設計変数値を利用 Dim3 コーディング前の情報を用いる 3設計変数を抜き出して表示する Dim1
GAが探索している空間を 把握するには不向きだと考えられる

18 GUI部：実数値空間による表示 対象問題の設計変数値を利用 設計変数1 設計変数2 設計変数3 個体群

19 GUI部：ビット空間による表示 Analyze部からの，染色体から抽出した情報を利用 コーディング後の情報を用いる Topology
Evaluation Value GAが探索している空間を把握する のに比較的有効だと考えられる Hamming Distance 個体群 楕円(体) 密集した個体群の傾向を 把握するため，共分散を もとにした楕円体を用いる

20 GUI部：ビット空間による表示 Analyze部からの，染色体から抽出した情報を利用 ・島毎に色分け ・楕円体表示 Topology 個体群
Hamming Distance Topology Evaluation Value 個体群 真の解

21 GUI部：探索履歴を用いた表示 Topologyに注目，過去１００世代に渡って探索点を記憶 n世代 n+1世代 過去100世代を記録 …
適合度順にソート … グループに分割 全個体の Topologyを計算 … 2,3,1 5,9,8 Variance of Topology Fitness グループ毎に Topologyの分散を計算 … 4.24 1.33

22 GUI部：探索履歴を用いた表示 Topologyに注目，過去１００世代に渡って探索点を記憶 Variance of Topology
(High) Fitness (Low)

23 提案システムの特徴 ビット空間による表示 コーディング後の情報を 用いて視覚化を行うため よりGAの探索に近い情報が把握可能 楕円体による
1 ビット空間による表示 コーディング後の情報を 用いて視覚化を行うため よりGAの探索に近い情報が把握可能 楕円体による 個体群の傾向 を把握 複数母集団の 色分け表示 GA部はGUI部や Analyze部と独立 Ana-lyze GA GUI

24 数値実験 1: 遺伝的操作がGAの個体群に与える影響 分散GAの移住操作により個体群に どのような傾向が出るか検討
　　　　　　　　どのような傾向が出るか検討 2: GAの探索履歴による対象問題の分類 数学的テスト関数とトラス構造物を対象に， その解探索の難易度別に分類できるか検討

25 分散遺伝的アルゴリズム 並列モデルの1種 サブ母集団 個体 母集団を複数に分割 移住操作により分割母集団間で個体を交換 母集団

26 数値実験 1: 遺伝的操作がGAの個体群に与える影響 移住操作により個体群に どのような傾向が出るか検討
　　　　　　　　どのような傾向が出るか検討 2: GAの探索履歴による対象問題の分類 数学的テスト関数とトラス構造物を対象に， その解探索の難易度別に分類できるか検討

27 数値実験1:遺伝的操作が与える影響 遺伝的操作がGAの個体群に与える影響 移住操作により個体群に どのような傾向が出るか検討
　　　　　　　　どのような傾向が出るか検討 Dim1 Dim3 Dim2 実数値空間 Hamming Distance Topology Evaluation Value ビット空間 Rastrigin DGA 4島 200個体 移住有り，移住無しで比較

28 数値実験1:実数値空間による表示 　移住有り 　　移住無し Generation　100 I S D L

29 数値実験1:ビット空間による表示 　移住有り 　　移住無し Generation　100 I S D L

30 数値実験2:探索履歴による対象問題分類 GAの探索履歴による対象問題の分類 数学的テスト関数とトラス構造物を対象に，
その解探索の難易度別に分類できるか検討 Variance of Topology Fitness 履歴による表示 Rastrigin，Rosenbrock Ridge，Rotated Rastrigin Truss A，Truss B SGA 200個体 10bit/1設計変数 10設計変数

31 数値実験2:数学的テスト関数の結果 Rastrigin Rosenbrock R Rastrigin Ridge Fitness
Variance of Topology low high Rastrigin Rosenbrock R Rastrigin Ridge Generation　200 I S D L

32 数値実験2:探索履歴による対象問題分類 トラス構造物最適化問題 対象: 6接点10部材トラス構造物最適化問題
目的: 制約条件内で，総体積の最小化 設計変数: 各部材の体積 部材 1kN Truss A Truss B 変位 座屈 応力 制約条件 変位 制約条件

33 数値実験2:探索履歴による表示 Truss B Truss A Fitness Variance of Topology low high
High Fitness Low High Fitness Low Truss B Generation　200 I S D L

34 数値実験2:探索履歴による対象問題分類 実験結果 GAによる探索結果 Rastrigin 136世代 331世代 Ridge 100,000
世代以上 Rosenbrock R　Rastrigin 制約条件の数 Truss A 3つ Truss B 1つ 適合度の高いグループの分散値と， 問題の難易度に関係がある

35 数値実験2:探索履歴による対象問題分類 考察 適合度の高いグループの分散値と，問題の 難易度に関係がある High High 分散大 分散小
Fitness Fitness Low Low Topology Topology 解探索容易 解探索困難

36 結論 GAの探索過程を把握するシステムを構築 移住無しと移住有りでは それぞれ探索の様子が異なる事を把握可能．
分類することが可能． 提案システムはコーディング後のビット空間や GAの探索過程を把握するのに有効．

37 それぞれ探索の様子が異なる事を把握可能．
作成したシステム GAによる解探索が容易な問題と， 困難な問題を分類することが可能． 移住無しと移住有りでは それぞれ探索の様子が異なる事を把握可能．

38 数値実験1:GAの個体群に与える影響 対象問題がGAの個体群に与える影響 実数値空間とビット空間で比較し， 関数の違いが判別できるか検討
Dim1 Dim3 Dim2 実数値空間 Hamming Distance Topology Evaluation Value ビット空間 Rastrigin Rosenbrock SGA 200個体

39 数値実験1:実数値空間による表示 Rastrigin Rosenbrock Generation　200 I S D L

40 数値実験1:実数値空間による表示 Rastrigin Rosenbrock Generation　200 I S D L

41 数値実験1:実数値空間による表示 Rastrigin Rosenbrock Generation　200 I S D L

42 コーディングの影響 コーディング前 関数の設計変数値 による外観 コーディング後 染色体をもとに，真の解から n回の突然変異で到達する点の
平均評価値 0 1　 2　 3　(n) 3210 平 均 評 価 値 突然変異回数 3210 評 価 値 設計変数値 単峰性で比較的簡単 真の解に近いと評価値悪い

43 コーディングの影響 コーディングの影響 コーディング前 関数の設計変数値 による外観 コーディング後 染色体をもとに，真の解から
n回の突然変異で到達する点の 平均評価値 3210 設計変数値 評 価 値 0 1　 2　 3　(n) 3210 平 均 評 価 値 突然変異回数 多峰性で比較的複雑 真の解に向かって単調減少

44 コーディングの影響 GAは対象問題の 設計変数値をコード化し利用 設計変数値 真の解からの距離 (実数値) 真の解の変数値 4 3210 4
評 価 値 4 3 3 距離 評価値 真の解に近いほど 良い解 設計 変数値 評価値 1 3 設計変数値

45 コーディングの影響 GAは対象問題の 設計変数値をコード化し利用 真の解からの距離 （突然変異） 3210 0 1 2 3 4 染色体
3210 評 価 値 染色体 評価値 1 3 1 設計変数値 1 3 評価値 距離 真の解に近いほど 悪い解 1 Coding

46 関数の外観とGAによる探索 数値実験(1) 目的：関数の外観とGAによる探索の困難さ
　対象：Ratrigin, Rosenbrock, Ridge, Rotated Rastrigin 　方法：DGAを用い最適解発見に要する世代数 DGAのパラメータ 総個体数 640 選択方法 Roulette + Ranking 島数 8 Elite保存 1 移住間隔 5 交叉方法 1点 突然変異 0.01 Coding Gray 交叉率 1.0 移住率 0.3 試行回数 10

47 トラスの解の形状

48 内藤の手法 ハミング距離，フィットネス，頻度の３軸を用いる
Ex．Stationary fitness-probability Landscape 　　　　　　　　　　　　　　　　　　　　　　　　　 （内藤’94） 対象問題として組み合わせ最適化問題 最適解との ハミング距離 小(<L/8) 大(>L/8) frequency fitness value 連続最適化問題では，適合度値の最大と最小の差が 影響し，そのままでは利用できない

49 林田，高木の手法 適合度空間のランドスケープ可視化とユーザーの能動的探索による進化計算の高速化(2001)
SOMを用いてデータ間の関係性を保持したまま写像 n-D searching space 2D コーディング前の設計変数値を用いているため， ビット空間の適合度空間を把握できない可能性がある

50 荒川らの手法 ラディアルベーシス関数ネットワークと領域適応型遺伝的アルゴリズムを用いた最適設計(2001)
RBFを用いて目的関数を探索点から近似し，良好な近似大局解を求める コーディング前の設計変数値を用いているため， ビット空間の適合度空間を把握できない可能性がある

51 その他の検討手法(Analyze) ビルディング ブロックの エントロピー ビットの偏り

52 その他の検討手法(GUI) Histogram