環境分散遺伝的アルゴリズムの 有効性の検討 知的システムデザイン研究室 2005年度 714番 細江 則彰 研究背景 最適化問題 与えられた条件の中で 最も良いものを求める問題 連続最適化問題 トラス構造物最適化 など 組み合わせ最適化問題 巡回セールスマン問題 など トラス構造物 ヒューリスティック手法 遺伝的アルゴリズム（GA：Genetic Algorithm） シミュレーテッドアニーリング（SA） 巡回セールスマン問題 遺伝的アルゴリズム（Genetic Algorithm : GA） 生物の進化を模倣した確率的なアルゴリズム 遺伝的操作（選択，交叉，突然変異）を繰り返して探索 多数の探索点による大域的な探索 : 探索点 遺伝的アルゴリズム（Genetic Algorithm : GA） 生物の進化を模倣した確率的なアルゴリズム 遺伝的操作（選択，交叉，突然変異）を繰り返して探索 多数の探索点による大域的な探索 : 探索点 遺伝的アルゴリズム（Genetic Algorithm : GA） 生物の進化を模倣した確率的なアルゴリズム 遺伝的操作（選択，交叉，突然変異）を繰り返して探索 多数の探索点による大域的な探索 最適解 : 探索点 GAの問題点 問題点 膨大な計算量が必要 早熟収束による局所解への収束 パラメータやオペレータの設定が困難 GAの問題点 問題点 膨大な計算量が必要 早熟収束による局所解への収束 パラメータやオペレータの設定が困難 GAの問題点 問題点 膨大な計算量が必要 局所解 早熟収束による局所解への収束 パラメータやオペレータの設定が困難 GAの問題点 問題点 膨大な計算量が必要 並列化 局所解 早熟収束による局所解への収束 多様性（幅広い探索）の維持 パラメータやオペレータの設定が困難 分散遺伝的アルゴリズム（DGA） 母集団を複数のサブ母集団に分割 各サブ母集団内で独立に遺伝的操作 移住による個体の交換 DGAはGAより優れた解探索性能 並列化 多様性の維持 GAの問題点 問題点 膨大な計算量が必要 並列化 早熟収束による局所解への収束 多様性の維持 パラメータやオペレータの設定が困難 GAの問題点 問題点 膨大な計算量が必要 並列化 早熟収束による局所解への収束 多様性の維持 パラメータやオペレータの設定が困難 従来：予備実験によってパラメータの値や （膨大な計算コスト） オペレータの方法を決定 GAの問題点 問題点 膨大な計算量が必要 並列化 早熟収束による局所解への収束 多様性の維持 パラメータやオペレータの設定が困難 従来：予備実験によってパラメータの値や （膨大な計算コスト） オペレータの方法を決定 考えられる値や方法を全て『同時』に設定 環境分散遺伝的アルゴリズム（環境分散GA） 環境分散遺伝的アルゴリズム（環境分散GA） 異なる交叉率・突然変異率を用いた環境分散GA [三木，1999] 各サブ母集団に異なる環境（交叉率・突然変異率）を設定 交叉率・突然変異率について予備実験が不要 環境分散遺伝的アルゴリズム（環境分散GA） 異なる交叉率・突然変異率を用いた環境分散GA [三木，1999] 各サブ母集団に異なる環境（交叉率・突然変異率）を設定 交叉率・突然変異率について予備実験が不要 交叉率 突然変異率 ： 0.5？ 1.0？ ： 0.01？ 0.1？ 環境分散遺伝的アルゴリズム（環境分散GA） 異なる交叉率・突然変異率を用いた環境分散GA [三木，1999] 各サブ母集団に異なる環境（交叉率・突然変異率）を設定 交叉率・突然変異率について予備実験が不要 交叉率 突然変異率 ： 0.5？ 1.0？ ： 0.01？ 0.1？ 各サブ母集団に同一の設定 環境分散遺伝的アルゴリズム（環境分散GA） 異なる交叉率・突然変異率を用いた環境分散GA [三木，1999] 各サブ母集団に異なる環境（交叉率・突然変異率）を設定 交叉率・突然変異率について予備実験が不要 交叉率 突然変異率 ： 0.5？ 1.0？ ： 0.01？ 0.1？ 各サブ母集団に同一の設定 環境分散遺伝的アルゴリズム（環境分散GA） 異なる交叉率・突然変異率を用いた環境分散GA [三木，1999] 各サブ母集団に異なる環境（交叉率・突然変異率）を設定 交叉率・突然変異率について予備実験が不要 交叉率 突然変異率 ： 0.5？ 1.0？ ： 0.01？ 0.1？ 各サブ母集団に同一の設定 環境分散遺伝的アルゴリズム（環境分散GA） 異なる交叉率・突然変異率を用いた環境分散GA [三木，1999] 各サブ母集団に異なる環境（交叉率・突然変異率）を設定 交叉率・突然変異率について予備実験が不要 交叉率 突然変異率 ： 0.5？ 1.0？ ： 0.01？ 0.1？ 各サブ母集団に同一の設定 環境分散遺伝的アルゴリズム（環境分散GA） 異なる交叉率・突然変異率を用いた環境分散GA [三木，1999] 各サブ母集団に異なる環境（交叉率・突然変異率）を設定 交叉率・突然変異率について予備実験が不要 交叉率 突然変異率 ： 0.5？ 1.0？ ： 0.01？ 0.1？ 各サブ母集団に同一の設定 各サブ母集団に異なる設定 環境分散遺伝的アルゴリズム（環境分散GA） 異なる交叉率・突然変異率を用いた環境分散GA [三木，1999] 各サブ母集団に異なる環境（交叉率・突然変異率）を設定 交叉率・突然変異率について予備実験が不要 交叉率 突然変異率 ： 0.5？ 1.0？ ： 0.01？ 0.1？ 各サブ母集団に同一の設定 各サブ母集団に異なる設定 予備実験なしでも適切な設定をしたDGAと同等の性能 研究目的 異なる交叉率・突然変異率を用いた環境分散GAは， 予備実験なしで適切な設定のDGAと同等の性能 環境分散GAの概念（異なる設定）を応用 設定する環境は多々考えられる 解探索性能の向上 解探索の特徴の解明 『環境分散GAの解探索の特徴を示し、 あらゆる環境に対する環境分散GAの有効性を検討』 設定する環境 コード化方法 [De Jong，2004] 評価方法 傾斜法 設定する環境 コード化方法 [De Jong，2004] 性能の再検討 + 多様性の検討 （実験１） 評価方法 傾斜法 環境分散GA（コード化方法） GAでは設計変数をコード化したビット列を操作 コード化にはバイナリコードとグレイコード 一方にバイナリコード，他方にグレイコードを設定 数値実験（コード化方法） 比較手法 環境分散GA （グレイコード，バイナリコード） DGA （グレイコード×２） DGA （バイナリコード×２ ） 対象問題（10次元） Schwefel関数 Griewank関数 Rosenbrock関数 対象問題 Schwefel関数 n F x xi sin( xi ) i 1 512 xi 512 Griewank関数 2 n x xi F x 1 cos i i i 1 4000 i 1 512 xi 512 n Rosenbrock関数 n 1 F x 100 xi 1 xi i 1 1 x 2 2 2.048 xi 2.048 2 i パラメータ（コード化方法） 実験結果（コード化方法：解探索性能） 環境分散GAは最も良い解探索性能 実験結果（コード化方法：解探索性能） 環境分散GAは最も良い解探索性能 実験結果（コード化方法：分散値） 特に探索序盤において 環境分散GAが最も大きな分散値 多様性の維持 実験結果（コード化方法：分散値） 特に探索序盤において 環境分散GAが最も大きな分散値 多様性の維持 設定する環境 コード化方法 [De Jong，2004] 2つのコード化を用いた環境分散GAは有効 評価方法 傾斜法 設定する環境 コード化方法 [De Jong，2004] 評価方法 性能の検討 + 多様性の検討 （実験２） 傾斜法 環境分散GA（評価方法） 多様性の維持は重要 どの程度の多様性が必要かは分からない 個体群の分散値（中心からの距離）も考慮したサブ母集団 両サブ母集団を移住することで適応的に多様性の維持 数値実験（評価方法） 比較手法 環境分散GA （目的関数，目的関数＋分散） DGA （目的関数×２） 対象問題（10次元） Schwefel関数 Griewank関数 Rosenbrock関数 実験結果（評価方法：解探索性能） 環境分散GAは最も良い解探索性能 実験結果（評価方法：解探索性能） 環境分散GAは最も良い解探索性能 実験結果（評価方法：分散値） 環境分散GAは極めて大きな分散値 多様性の維持 実験結果（評価方法：分散値） 環境分散GAは極めて大きな分散値 多様性の維持 設定する環境 コード化方法 評価方法 異なる評価方法を用いた環境分散GAは有効 傾斜法 設定する環境 コード化方法 評価方法 傾斜法 性能の検討 環境分散GA（傾斜法） 多様性を維持しつつ，早く解を得たい 収束の早い手法 SQP（非線形最適化問題を解く代表的な手法） 少ない評価計算回数で収束することが可能 初期点によっては局所解に収束する 各サブ母集団で局所解への収束が起こっても 全体としては多様性が維持できる DGAの中にSQPを組み込む 環境分散GA（傾斜法） エリート個体（母集団で最も良好な個体）が更新 エリート個体にSQPを実行 環境分散GA（傾斜法） エリート個体（母集団で最も良好な個体）が更新 エリート個体にSQPを実行 環境分散GA（傾斜法） エリート個体（母集団で最も良好な個体）が更新 エリート個体にSQPを実行 環境分散GA（傾斜法） エリート個体（母集団で最も良好な個体）が更新 エリート個体にSQPを実行 環境分散GA（傾斜法） エリート個体（母集団で最も良好な個体）が更新 エリート個体にSQPを実行 全てのサブ母集団でSQPを実行すると評価計算回数が増加 一部のサブ母集団でSQPを実行 数値実験（傾斜法） 比較手法 DGA (サブ母集団数10) SQPなし DGA (サブ母集団数10) 1つのサブ母集団のみSQP適用 (環境分散GA) DGA (サブ母集団数10) 全サブ母集団でSQP適用 対象問題（20次元） Schwefel関数 Griewank関数 Rosenbrock関数 パラメータ（傾斜法） 実験結果（傾斜法：解探索性能） SQPを用いると収束が早い 全てのサブ母集団にSQPを用いると必要な評価計算回数は増加 1つのサブ母集団のみSQPを用いると良好な結果 実験結果（傾斜法：解探索性能） SQPを用いると収束が早い 全てのサブ母集団にSQPを用いると必要な評価計算回数は増加 1つのサブ母集団のみSQPを用いると良好な結果 まとめ 様々な環境を考え，環境分散GAの有効性を検討 異なる交叉率・突然変異率を用いた環境分散GA 予備実験が不要 異なるコード化方法を用いた環境分散GA 解探索性能の向上 DGAより更に多様性の維持が可能 異なる評価方法，傾斜法を用いた環境分散GA 解探索性能の向上 更に多くの環境に対して，環境分散GAの適用も考えられる 環境分散GAは有効な手法である 遺伝的オペレータ 選択 ： 良好な個体ほど選択されやすい 交叉 ： 親個体において交叉点を選択し，設計変数を交換 突然変異 ： ある確率に従って微小な変化を与える 交叉率・突然変異率 数値実験（交叉率・突然変異率） 比較手法 環境分散GA（9つのパターン×1母集団） DGA （0.3 – 0.001×9母集団） DGA （0.6 – 0.001×9母集団） ： DGA （1.0 – 0.1×9母集団） 対象問題 Schwefel関数 Griewank関数 Rosenbrock関数 パラメータ（交叉率・突然変異率） 実験結果（交叉率・突然変異率：解探索性能） DGAはパラメータによって性能が悪い 環境分散GAは収束は遅いものの チューニングしたDGAと同等 実験結果（交叉率・突然変異率：解探索性能） DGAはパラメータによって性能が悪い 環境分散GAは収束は遅いものの チューニングしたDGAと同等 対象問題 Rastrigin関数（10次元） n F x 10n ( xi 10cos(2xi )) i 1 2 5.12 xi 5.12 実験結果（交叉率・突然変異率：解探索性能） 実験１ コード化 バイナリコード 整数を2進法によって 表現したもの グレイコード 連続する２つの符号間 のハミング距離が１ グレイコードとバイナリコードの特徴 個体の分布（コード化方法）：Griewank関数 個体の分布（コード化方法）：Rastrigin関数 個体の分布（コード化方法）：Schwefel関数 個体の分布（コード化方法）：Rosenbrock関数 移住の効果（コード化方法） Griewank関数 Rastrigin関数 移住の効果（コード化方法） Schwefel関数 Rosenbrock関数 移住の効果（コード化方法）：Griewank関数 実験結果(コード化方法)：Rastrigin関数 解探索性能 分散値 実験２ 適合度の決定方法 目的関数による評価： 目的関数と分散による評価： max , min は設計変数の最大値と最小値 実験結果(評価方法)：Rastrigin関数 解探索性能 分散値 実験３ SQP (Sequential Quadratic Programming) 目的関数を2次近似，制約条件を線形近似した 2次計画問題の解を反復計算する手法 ラグランジュ関数のヘッセ行列を求めるのは困難 BFGS公式でヘッセ行列を近似して更新 解xを求め，探索方向を 次の反復点を とし，ステップサイズαを決定し， とする． 実験結果（実験３ ：解探索性能） 実験結果（実験３ ：解探索性能） Schwefel関数 Griewank関数 実験結果（実験３ ：解探索性能） Rosenbrock関数 Rastrigin関数
© Copyright 2024 ExpyDoc
