数理モデルと問題解決研究会（2000年9月） 遺伝的アルゴリズムにおける最良組合せ交叉 Best Combinatorial Crossover in Genetic Algorithms 同志社大学大学院 / 同志社大学 ○吉田純一，三木光範，廣安知之，坂田善宣 Intelligent Systems Design lab. Doshisha University 発表の概要 GAにおける交叉の役割と問題点 最良組合せ交叉（BCX）の提案 単一母集団のGAと分散GA 最良組合せ交叉の評価 Intelligent Systems Design lab. Doshisha University 遺伝的アルゴリズム 生物の進化の過程を工学的に 応用した最適化手法 遺伝的オペレータ 交叉・突然変異・選択 幅広い工学的最適化問題に 適用可能 Intelligent Systems Design lab. Doshisha University 研究背景 親個体の遺伝子を組み替え 新しい個体を生成 個体間の情報交換 GAによる解探索の主役 良好なスキーマを組み合わせる ことが重要 Intelligent Systems Design lab. Doshisha University 代表的な交叉法 1点交叉 一様交叉 （1-point Crossover: 1X） （Uniform Crossover: UX） Intelligent Systems Design lab. Doshisha University 通常の交叉（1X）の問題点 1 1 2 2 :3 交叉点はランダムに決定 :2 →良好なスキーマが組み合わされ るか否かは確率的要素に依存 :5 :0 - 改良よりも改悪の方が多い（wu 97） :3 :2 うまく組み合わされても一方は淘汰 される → 多様性の減少につながる 部分解 確実に良好なスキーマを組み合わせる交叉法 最良組合せ交叉（Best Combinatorial Crossover : BCX） Intelligent Systems Design lab. Doshisha University 最良組合せ交叉（ＢＣＸ） 最良組合せ交叉 Best Combinatorial Crossover １点交叉で生み出しうる 全ての個体（候補個体） を評価 候 補 個 体 →最良の個体を選択 確率的な要素に左右されず 上位２個体を選択 に良好なスキーマを生成 Intelligent Systems Design lab. Doshisha University 評価計算の軽減 すべてのビット間での交叉は冗長 1 1 候 補 個 体 ２ ３ 親個体の染色体を検査、 候補個体の重複を禁止する 親個体の染色体が異なる部分で のみ交叉を行う ２ 候補個体には親個体も含まれる ３ Intelligent Systems Design lab. Doshisha University 対象問題 Intelligent Systems Design lab. Doshisha University 分散遺伝的アルゴリズム（DGA） 単一母集団GA（SＰGA） 分散母集団GA（DGA） 母集団を複数のサブ母集団に分割 一定世代ごとに移住（パラメータ：母集団数・移住率・移住間隔） 特徴 良好な解を速く求めることが可能 Intelligent Systems Design lab. Doshisha University パラメータ 母集団サイズ 400 交叉率 1.0 突然変異率 1/L 終了条件 2000世代 サブ母集団数 移住間隔 移住率 対象問題 8 5世代 0.5 Rastrigin Schwefel Griewank Ridge Intelligent Systems Design lab. Doshisha University BCXの適用（依存関係のない関数） Rastrigin Schwefel 1Xを用いたSPGAでは最適解が得られない Intelligent Systems Design lab. Doshisha University BCXの適用（依存関係のある関数） Griewank Ridge SPGA，DGA共に1Xでは最適解が得られない Intelligent Systems Design lab. Doshisha University BCXの適用 実験結果より ・1Xでは最適解が得られないことがある ・BCXでは全ての関数で最適解が得られた → BCXは高い解探索能力を持つ BCXのアルゴリズムの問題点 → 膨大な評価計算が必要 ※100bitの染色体で最大200回/交叉の評価計算 → 評価計算での評価 Intelligent Systems Design lab. Doshisha University 計算回数での評価（依存関係のない関数） Rastrigin Schwefel 1Xで解ける問題では計算コストが高すぎる Intelligent Systems Design lab. Doshisha University 計算回数での評価（依存関係のある関数） Griewank Ridge 依存関係のある問題は1Xでは解けない Intelligent Systems Design lab. Doshisha University 計算回数での評価（適合度の推移） Rastrigin Griewank Intelligent Systems Design lab. Doshisha University BCXと1Xの比較 BCX：交叉の中で多くの候補個体を評価 100bitの染色体長の場合 1回の交叉で最大200の候補個体を生成 ＝1Xの100世代に相当 どちらがよいのか？なにが違うのか？ - 探索領域を比較 Intelligent Systems Design lab. Doshisha University 1X 探索領域の推移（2変数Rastrigin関数） 4000 6000 BCX 2000 Intelligent Systems Design lab. Doshisha University 探索領域の比較（2変数Rastrigin関数） 1X BCX Optimum BCXの方が最適解付近を効率的に探索している Intelligent Systems Design lab. Doshisha University 1X 探索領域の推移（2変数Ridge関数） 6000 8000 BCX 4000 Intelligent Systems Design lab. Doshisha University 探索領域の比較（2変数Ridge関数） 1X BCX Optimum BCXの方が最適解付近を効率的に探索している Intelligent Systems Design lab. Doshisha University ここまでのまとめ BCXは1Xと比較して高い解探索能力を持つ － 全ての関数で最適解が得られた 評価計算回数での比較 － 依存関係のある問題：BCXの方が計算回数が少 探索領域の違い － BCXは最適解付近を効率的に探索 なぜBCXが高い解探索能力をもつのか? ・BCXのアルゴリズムに依存 Intelligent Systems Design lab. Doshisha University BCXのメカニズム Candidate Children Parents 候補個 体の生 成 Children 最良個 体の選 択 それぞれが解探索能力におよぼす影響を検討する Intelligent Systems Design lab. Doshisha University 候補個体数の影響 Candidate Children Parents 候補個 体の生 成 Children 最良個 体の選 択 候補個体数を変更し，解探索能力を比較する (2, 4, 6, 8, 10, 20, BCX) Intelligent Systems Design lab. Doshisha University 候補個体数の影響（依存関係のある関数） Griewank関数 候補個体を複数生成する 方が解探索能力は高まる Griewank関数では．．． BCXが最も計算コストが 小さい Intelligent Systems Design lab. Doshisha University 候補個体数の影響（依存関係のない関数） Rastrigin関数 候補個体を複数生成する 方が解探索能力は高まる BCXでは計算コストが高す ぎる -最適な候補個体数が存在 -最適値は問題依存 BCXはロバスト性が高い Intelligent Systems Design lab. Doshisha University 最良個体の選択の影響 Candidate Children Parents 候補個 体の生 成 Children 最良個 体の選 択 ・選択方法による影響を検討する （1位＋2位， 1位＋ランダム, ランダム＋ランダム） Intelligent Systems Design lab. Doshisha University 最良個体の選択の影響 Rastrigin(DGA) Griewank(DGA) BCXにおいては最良の個体（1st+2nd）の選択が有効 Intelligent Systems Design lab. Doshisha University 世代交代モデルとしてのＢＣＸ Candidate Children Parents Children 候補個 体の生 成 最良個 体の選 択 ＢＣＸは交叉の中で個体の選択を行う 選択オペレータと同様の役割 世代交代モデルとしても利用可能 MGGモデルと似た実装（佐藤，山村ら） Intelligent Systems Design lab. Doshisha University 世代交代モデルとしてのＢＣＸの性能 Rastrigin(DGA) Griewank(DGA) 選択を行わなくても最適解を得ることも可能 大域的な選択を行う方がより高性能 Intelligent Systems Design lab. Doshisha University まとめ BCXの特徴 ① 両親から生み出し得るすべての個体を評価する ② 候補個体から最良個体を選択する ・局所解に陥ることなく最適解を発見することができる ・1Xと比較して効率的な解探索が可能 Intelligent Systems Design lab. Doshisha University Intelligent Systems Design lab. Doshisha University MGGモデル 最良個体＋ルーレット ランダム Intelligent Systems Design lab. Doshisha University 2 1 0 –3 –2 Intelligent Systems Design lab. Doshisha University PDGAにおける解探索 Intelligent Systems Design lab. Doshisha University 計算回数での評価（適合度の推移） Intelligent Systems Design lab. Doshisha University 最良組合せ交叉（ＢＣＸ） 評 価 -2.4 -1.5 １点交叉で生み出しうる 全ての個体を評価 →上位２個体を選択 確率的要素に左右されず に良好なスキーマを生成 -3.1 -0.5 -1.6 -0.6 -0.8 -3.0 Intelligent Systems Design lab. Doshisha University Intelligent Systems Design lab. Doshisha University
© Copyright 2024 ExpyDoc
