遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類

Presentation on theme: "遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類"— Presentation transcript:

1 遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類
Classed Problems by Landscape of Genetic Algorithms 廣安知之，三木光範，○赤塚浩太 † ‡ † 同志社大学工学部知識工学科 ‡ 同志社大学大学院工学研究科

2 ？ 研究背景 多くの連続問題最適化手法は 対象問題の設計変数値をそのまま利用 対象問題の性質の 把握が比較的容易
　　　　　対象問題の設計変数値をそのまま利用 我々が把握している外観を元に探索 対象問題の性質の 把握が比較的容易 GAは対象問題の設計変数値をコード化し利用 我々が把握している外観とは異なった空間を探索 ？ 対象問題の性質の 把握が困難

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

4 関数の外観とＧＡによる探索 240 100,000 190 Rastrigin Rosenbrock Schwefel 関数名 関数 の
２設計 変数 終了 世代 More　than 240 100,000 190

5 関数の外観とＧＡによる探索 Ridge Griewank 1,900 16,000

6 関数の外観とＧＡによる探索 数値実験(1) 結果 我々が把握している関数の外観と， GAによる探索の困難さはまったく異なっている．
Rastrigin Rosenbrock Schwefel Ridge Griewank 推測される結果 ＧＡ探索結果 多峰性 単峰性 困難 容易 240 100,000 190 1,900 16,000 我々が把握している関数の外観と， GAによる探索の困難さはまったく異なっている．

7 コード化された対象問題のランドスケープを 把握する手法
コード化された対象問題のランドスケープを 　　　　　　　　　　　　　　　　　　　　把握する手法 対象問題全域 精度に問題 GA探索中のエリートと対象問題の最適解 エリートから最適解までのGA探索による経路を把握 GAによる探索＝交叉，突然変異 エリート ００１０１ ０１１０１ 最適解 ０１００１ ００１００ 交叉 エリートから交叉して最適解に達する時 ００１０１ ００１００ 突然変異 エリートから突然変異して最適解に達する時 ００１０１　０ ０ １０１ エリートと最適解の両方の遺伝子情報を持つ

8 コード化された対象問題のランドスケープを 把握する手法
コード化された対象問題のランドスケープを 　　　　　　　　　　　　　　　　　　　　把握する手法 エリートと最適解の両方の遺伝子情報を持つ個体が生成 個体の適合度が悪ければ，選択で淘汰 両方の遺伝子をもつ個体を多数生成しその適合度を評価 両方の遺伝子情報を持つ個体は，エリートの 遺伝子中任意のn bitを最適解と同じにし，生成 生成した個体の適合度に基づき多数の個体を分類し， 適合度毎の頻度を求めグラフ化し，ランドスケープを把握 エリート 適合度 最適解 頻度 ハミング距離

9 数値実験(2) 目的：提案手法によるランドスケープの表示
　　目的：提案手法によるランドスケープの表示 　　対象：Ratrigin,Rosenbrock,Schwefel,Griewank,Ridge frequency O Optimum hamming distance 1 2 3 0.5 fitness 1.0 m Elite E

10 数値実験(2)-Rastrigin O 100世代 200世代 探索容易 O E E

11 数値実験(2)-Rosenbrock O 100世代 探索困難 O E 1000世代 探索困難 E

12 数値実験(2)-Schwefel O 100世代 探索容易 O E 1000世代 探索容易 E

13 数値実験(2)-Ridge O 100世代 探索中程度 O E 1000世代 探索普中程度 E

14 数値実験(2)-Griewank O 100世代 探索中程度 O E 1000世代 探索困難 E

15 数値実験(2)-考察 提案手法による関数の外観と， GAによる探索の困難さがほぼ一致． 100世代目 1000世代目 ＧＡ探索結果
Rastrigin Rosenbrock Schwefel Ridge Griewank 容易 困難 中程度 容易 困難 中程度 240 100,000 190 1,900 16,000 提案手法による関数の外観と， GAによる探索の困難さがほぼ一致．

16 数値実験(3) 目的：提案手法が実問題に有効である事の検証 対象：6接点10部材トラス構造物最適化問題 1KN 変異制約 圧縮座屈 引張応力
　　目的：提案手法が実問題に有効である事の検証 　　対象：6接点10部材トラス構造物最適化問題 1KN 変異制約 圧縮座屈 引張応力 ５ ６ 問題TYPE-1 1KN ３ ４ 0.3m 問題TYPE-2 変異制約 １ ２ 0.4m

17 数値実験(3)-Truss 提案手法による関数の外観と，対象問題の 難しさ（制約条件の数）がほぼ一致． 探索困難 探索容易 O
Type-1 100世代 探索困難 O E Type-2 100世代 探索容易 E 提案手法による関数の外観と，対象問題の 難しさ（制約条件の数）がほぼ一致．

18 結論と今後の課題 5つのテスト関数による実験の結果， 提案手法の有効性を示すことができた 実問題への適用例としてトラス構造物で
関数の外観とGAによる探索の困難さは違う GAの探索空間を把握する手法を提案 5つのテスト関数による実験の結果， 提案手法の有効性を示すことができた 実問題への適用例としてトラス構造物で 実験を行った結果，提案手法の有効性を さらに確認することができた 今後は最適解を必要としない手法への発展が必要

19 6接点10部材トラス構造物最適化 1KN 変異制約 圧縮座屈 引張応力 0.4m 0.3m １ ２ ３ ４ ５ ６ 制約条件
座屈が生じない 40MPa以下 その他の設定 ヤング率 1.0GPa

20 コード化された対象問題のランドスケープを 把握する手法
コード化された対象問題のランドスケープを 　　　　　　　　　　　　　　　　　　　　把握する手法 具体的な手順 エリート個体中，全長のLビットのうち 最適解と値が異なるmビットを抽出する 最適解 ０１００１ ００１００ エリート ００１０１ ０１１０１ m=4bit エリート個体の適合度と最適解の適合度の間を 等間隔に10分割する． 適合度 最適解 エリート

21 コード化された対象問題のランドスケープを 把握する手法
コード化された対象問題のランドスケープを 　　　　　　　　　　　　　　　　　　　　把握する手法 具体的な手順 n=1～mとして以下の操作( )を繰り返す 抽出したmビット中ランダムにnビットを最適解と同じにする n=1 ００１０１　０１１０１ ０ n=2 ００１０１　０１１０１ １ ０ この操作を400回行い，400個体生成する． P1-1 ００１０１　０１１０１ ０ P2-1 ００１０１　０１１０１ １ ０ P1-2 ００１０１　０１１０１ ０ P2-2 ００１０１　０１１０１ １ ０ P1-400 ００１０１　０１１０１ １ P2-400 ００１０１　０１１０１ １ ０

22 コード化された対象問題のランドスケープを 把握する手法
コード化された対象問題のランドスケープを 　　　　　　　　　　　　　　　　　　　　把握する手法 具体的な手順 生成した400個体の適合度が，エリートと最適解を 10分割したどこに当てはまるか計算する． P1-1，P1-2，･･･，P1-400 P2-1，P2-2，･･･，P2-400 最適解 適合度 エリート 最適解 適合度 エリート 10分割された適合度のそれぞれに何個体存在するかを 　　 そのハミング距離，適合度での頻度とする． 頻度 ０ ２ １ ０ １ ０ ０ １ １ ０ ０ 頻度 ０ ０ ０ １ １ １ １ １ １ ０

23 コード化された対象問題のランドスケープを 把握する手法
コード化された対象問題のランドスケープを 　　　　　　　　　　　　　　　　　　　　把握する手法 具体的な手順 n=1～mとしてこれまでの操作（ ）を繰り返した後 x軸に適合度，y軸にn，z軸に頻度を用いてグラフ化する Optimum Elite n=1 n=2 n=3 Hamming Distance Fitness 頻度

24 最適解とエリートの間に個体を生成 エリート ００１０１ ０１１０１ 最適解 ０１００１ ００１００ 最適解と異なるビット列
1ビット最適解に近づける ０１１０１ ０１１０１ ００１０１ ００１０１ ００００１ ０１１０１ ００１０１ ０１１００ 2ビット最適解に近づける ０１１０１ ００１０１ ００００１ ００１０１ ００００１ ０１１００ ０１１０１ ０１１００