情報処理学会全国大会分散遺伝的アルゴリズムの性能におよぼす交叉法とコーディング法の影響三木光範（同志社大学）廣安知之（同志社大学）吉田純一（同志社大学）金子美華（同志社大学大学院）研究背景 GAでは交叉の働きが重要個体間の情報交換＝GAにおける本質的操作交叉法やコーディング法に依存単一母集団GAにおける研究は多いが分散GAに関するものは少ない連続関数の最大化問題において分散GAの性能に交叉とコーディングはどのような影響をおよぼすのか？分散GA（DGA）単一母集団GA（SGA）分散母集団GA（DGA）特徴：母集団を複数のサブ母集団に分割一定世代ごとに移住（パラメータ：移住率・移住間隔）利点：良好な解を速く求めることができる分散GAにおける交叉の役割サブ母集団2の染色体移住サブ母集団１の染色体最適解移住してきた個体との交叉移住してきた個体と良好なスキーマを交換することでよりよい解が求まる各サブ母集団移住・交叉局所探索・部分解の探索部分解の交換・多様性の維持 Exploitation-Explorationバランス GAにおいて効率のよい解探索のためには情報の利用（exploitation）の調和が重要未知の領域の探索（exploration）情報の有効利用未知の領域の探索トレードオフ exploitation Ex. 山登り法 exploration Ex. ランダムサーチ交叉のE-Eバランス複数のサブ母集団による独立実行 exploitation exploration 単一母集団GA 分散GA 分散GAにおける交叉の条件情報の利用に優れた交叉スキーマを保存・個体間で交換可能交叉法 1点交叉（1X）親個体のスキーマの大半を子に継承局所解に陥りやすい２点交叉(2X) exploitation 一様交叉(UX) １Ｘ交叉点が多い（L/2）→スキーマを破壊大域的な探索が可能スキーマの大半を子に継承２Ｘスキーマを破壊 UＸ exploration コーディング法コーディング：染色体に実数値を符号化バイナリコード一般的な2進数の表現すべての変化が同じ確立で起こるグレイコード隣り合う値のハミング距離が１大きな変化は起こりにくく，効率的 Real value BINARY 0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 （1）（2）（1）（3）（1）（2）（1） GRAY 000 001 011 010 110 111 101 100 （1）（1）（1）（1）（1）（1）（1）（）内の数字はハミング距離実験（対象問題）関数名関数 n Rastrigin f Rastrigin  10n   ( xi2  10cos(2xi ) n   x  xi2  1     cos i    i  i 1 4000 i 1  f Griewank n Schwefel 変数の数なし n=10 あり（中程度） n=10 なし n=10 i 1 n Griewank 依存関係 fSchwefel    xi2 sin i 1  x i 各関数のグラフ（２変数） Rastrigin Griewank Schwefel 実験（パラメータ設定）交叉法コーディング法 1X 2X UX グレイバイナリ最大世代数染色体長交叉率突然変異率選択エリート保存母集団サイズサブ母集団数移住率移住間隔 1000 100bit 0.6 なし 1/L ルーレットあり 450 900 9 0.3 10 分散GAの性能におよぼす交叉法とコーディング法の影響を調べる突然変異を行わない場合 1000世代での適合度の違い Griewank Schwefel Eval value Rastrigin 1X 2X UX GRAY: DGA SGA 1X 2X UX 1X 2X BINARY: DGA SGA 問題によって最適な交叉法，コーディング法は異なる UX 突然変異（1/L）を行う場合 1000世代での適合度の違い Griewank Schwefel Eval value Rastrigin 1X 2X UX GRAY: DGA SGA 1X 2X UX 1X BINARY: DGA SGA すべての関数で同じような傾向グレイコードの分散GA（）が良い成績 2X UX 突然変異を行う場合（２）最適解に収束するまでの世代数（グレイ-分散 1X 2X UX Rastrigin 471 520 923 Griewank -0.156 -0.164 -0.252 Schewfel 510 455 793 1X・2Xに有意な差は見られない UXでは移住による部分解の交換は期待できない分散GAにおいては１点交叉・２点交叉がよい性能を示した）個体分布の推移（分散GA・1点交叉）移住前の5世代 2D Rastrigin 移住後の5世代 2 移住 0 –2 2 –2 0 2 0 –2 –2 0 2 移住と交叉による部分解の交換によって探索空間が変化している個体分布の推移（分散GA・一様交叉）移住前の5世代 2D Rastrigin 移住後の5世代 5 5 移住 0 0 5 –5 –5 0 –5 –5 5 0 0 –5 –5 0 5 一様交叉の破壊的な性質により部分解の交換の効果は得られない 5 結論コーディング法の影響 GAにとって有利な条件の場合グレイコーディングがよい成績を示す GAにとって不利な条件の場合個体数の不足、設計変数間の依存関係などグレイよりもバイナリコーディングの方がよいこともあるいずれのコーディング法を実装しても分散GAによって性能は向上結論（２）交叉法の影響１点交叉・２点交叉がよい成績を示した分散GAにおいては情報の利用（Exploitation）に優れた交叉を行わなくてはならない一様交叉が悪い成績を示したスキーマを破壊するオペレータでは分散GA による性能の向上を期待できない