表紙 分散遺伝的アルゴリズムのための 新しい交叉法

概要

遺伝子を組み替え新しい個体を生成 個体間の情報交換 親個体が持たないビットを生み出す 母集団内の多様性の維持 GAのプロセス 遺伝子を組み替え新しい個体を生成 個体間の情報交換 親個体が持たないビットを生み出す 母集団内の多様性の維持 環境に適合した個体ほど 子孫を残しやすい

並列処理・並列GA 目的関数の形質を直接利用しない 確率的な多点探索 初期値依存による早熟収束 計算コストが高い 最適なパラメータ設定が困難 特徴・問題点 目的関数の形質を直接利用しない 確率的な多点探索 初期値依存による早熟収束 計算コストが高い 並列処理・並列GA 最適なパラメータ設定が困難

特徴 母集団を複数のサブ母集団に分割 一定世代ごとに移住（移住率，移住間隔） 並列計算機との親和性が高い 並列分散GA 並列計算機との親和性が高い 母集団を複数のサブ母集団に分割 一定世代ごとに移住（移住率，移住間隔） 単一母集団のSGAでは，その名の通り全ての個体を単一の母集団で処理しますが，並列分散GAでは，母集団を複数のサブ母集団に分割し，各サブ母集団で独立にGAを実行します． その上で，移住間隔とよばれる周期ごとにサブ母集団間で個体を交換します．このときに交換する個体の割合を移住率と呼びます． 並列分散GAでは各サブ母集団が独立に解探索を行い，しかもサブ母集団間で個体情報を交換することでSGAより多様性を維持したまま探索を進めることが可能です． このため，SGAよりも高速に高品質な解が得られます． また，移住の処理以外は各サブ母集団ごとに独立に実行するため，サブ母集団ごとにプロセッサを割り当てるだけで高い並立か効率を得ることが可能です． 特徴

プロセッサ数に比例した速度向上が期待できる GAの並列分散化（台数効果） PCクラスタを用いて 実行時間を測定 Rastrigin関数 母集団サイズ ：800個体 最大世代数 ：1000世代 プロセッサ数に比例した速度向上が期待できる

SGA - 400個体 早熟収束によって最適解は PDGA - 50個体 8サブ母集団 高速に高品質な解が得られる 計算量自体が減少 　早熟収束によって最適解は 　得られない PDGA - 50個体　8サブ母集団 ・各サブ母集団では局所探索 ・移住によって多様性を保つ　　 高速に高品質な解が得られる 計算量自体が減少

パラメータチューニング 並列分散GA 計算コストが高い・早熟収束 ・並列計算機との親和性が高い ・高速に高品質な解が得られる 特徴・問題点 計算コストが高い・早熟収束 並列分散GA ・並列計算機との親和性が高い ・高速に高品質な解が得られる 最適なパラメータ設定が困難 パラメータチューニング

パラメータチューニング パラメータチューニング ・交叉法 ・交叉率 ・突然変異率 ・選択法

最適な交叉率

代表的な交叉法

実験：最適な交叉率

対象問題

交叉率：実験結果１

交叉率：実験結果２

交叉率：実験結果３

交叉率：実験結果４

実験：交叉法

交叉法：実験結果 s

これは，並列分散GAの解探索メカニズムに依存 実験結果のまとめ 実験結果のまとめ 実験結果 並列分散GAに最適な 　　交叉率　　1.0 　　交叉法　　１Ｘ，２Ｘ：スキーマを保存する交叉 これは，並列分散GAの解探索メカニズムに依存

ハイブリッド個体 NativeとMigrantの子 PDGAにおける解探索 ハイブリッド個体 NativeとMigrantの子

最適な交叉スキーム

（Best Combinatorial Crossover : BCX） 交叉 良好なスキーマが組み合わされるかは確率的要素に依存 うまく組み合わされても一方は淘汰される 　→多様性の減少 確実に良好なスキーマを組み合わせる交叉法 最良組合せ交叉 （Best Combinatorial Crossover : BCX）

最良組合せ交叉（BCX） 確率的要素に左右されずに 良好なスキーマを育てる １点交叉で生み出しうる 全ての個体を評価 →上位２個体を選択 -2.4 -1.5 -3.1 -0.5 -1.6 -0.6 -0.8 -3.0 評　価 確率的要素に左右されずに 良好なスキーマを育てる １点交叉で生み出しうる 全ての個体を評価 →上位２個体を選択

BCX：実験

BCX：実験結果１

BCX：実験結果２

（Hybridization Crossover:HX） PDGAにおける交叉の役割 交叉の役割（HX前） 移住前　　サブ母集団内で良好なスキーマを生成 最良組合せ交叉（BCX） 移住後　　良好なスキーマを組み合わせる 実験結果：最適な交叉率＝1.0 これをさらに高めるための交叉スキーム ハイブリッド生成交叉 （Hybridization Crossover:HX）

ハイブリッド生成交叉（HX） 先ほどのBCXがサブ母集団内でのスキーマの形成を促進するのに対し，次に提案するハイブリッド生成交叉は，移住後の交叉によるスキーマの組合せを促進するためのものです． 具体的には，移住が行われたとき，移住個体すなわちMigrantとサブ母集団内にもともといた個体すなわちNativeとを強制的に交叉させます．これによって並列分散遺伝GAにおける解探索の主役であるハイブリッド個体を多く生み出すというものです．

ハイブリッド生成率 通常の交叉 ハイブリッド生成交叉（HX） 0.5 0.5 0.3 0.5 1.0 0.6 移住率 移住率 ハイブリッド 先に述べた実験の結果から，並列分散GAの性能を高めるためには交叉率1.0が有効であると述べましたが，移住率を0.5，交叉率を1.0とにも場合にも，移住後の交叉でハイブリッドが生まれる確率，ハイブリッド生成率は，0.5にすぎません．これは，移住後にMggrant同士，Native同士の交叉が行われるためです． 一方，ハイブリッド生成交叉では，サブ母集団内の個体を２つのグループに分割し，Migrantはどちらか一方に集中して配置するために，移住率を0.5とする事でハイブリッドの生成率を100%にする事が可能です．また，移住率を変更することで，確率的な要素に左右されることなくハイブリッド生成率を調整することも可能です． 移住率 0.5 移住率 0.5 0.3 ハイブリッド 生成率 ハイブリッド 生成率 0.5 1.0 0.6

実験：HX

HX：実験結果

HX：実験結果２ s

結論

ご静聴ありがとうございました

補足資料

BCX+HX１

BCX+HX

交叉率：実験結果

交叉率：発見世代

交叉率：対象問題による違い

交叉法：実験結果

HX:実験結果

交叉法：実験結果（３関数）

交叉法：実験結果２

BCX：実験結果

BCX：実験結果２（表）

ハイブリッド生成率（グラフ）