分散遺伝的アルゴリズムにおける最適な交叉率および突然変異率三木光範廣安知之同志社大学工学部 ○大向一輝金子美華 intelligent systems design laboratory, Doshisha University 同志社大学大学院 I S D L 1 発表の概要研究背景実験最適な交叉率最適な突然変異率結論 I S D L 2 分散GAとは単一母集団GA SGA DGA 分散GA ・母集団を分割・一定世代ごとに移住分散GAは単一母集団GAと比較して，良好な解を速く求めることが可能である I S D L 3 最適な交叉率と突然変異率 SGA 交叉率突然変異率 DeJong DeJong (1975) 0.6 Grefenstette (1986) 0.95 Bäck 0.75~0.95 (1996) (1975) 0.001 Grefenstette (1986) 0.01 Schaffer (1989) 0.005~0.01 Bäck (1996) 1/L （Lは染色体長）分散GAにおける最適な交叉率および突然変異率に関する研究は少ない I S D L 4 実験 - 対象問題 Rastrigin関数（10次元） n f Rastrigin  10n   ( x  10cos(2xi ) i 1 2 i 変数間の依存関係なし Schwefel関数（10次元） n x fSc hwefe l   x i2 sin i 1 i 変数間の依存関係なし Griewank関数（10次元） n   xi   xi2  1     cos    i  i 1 4000 i 1  n f Griewank 変数間の依存関係ありこれらの関数の最大化（大域的最適解 0） I S D L 5 実験 - パラメータ設定交叉率 0.0 突然変異率 0/L 個体数サブ母集団数 0.1 180 0.3 0.01/L 0.1/L 450 1 (SGA) 0.6 1.0 1/L 10/L 900 1620 9 (DGA) 移住率 0.3 ルーレット選択エリート保存移住間隔 5 グレイコード終了世代 1000 最高の適合度を得ることのできる交叉率および突然変異率の設定を調べた I S D L 6 解の探索能力最高の適合度分散GAでは単一母集団GAと比べて，良好な解を得ることができる I S D L 7 最適な交叉率例：Schwefel関数・総個体数1620 SGA 世代によって最適な交叉率が異なる DGA 全ての世代で 1.0 が良好 I S D L 8 最適な交叉率最高の適合度が得られた交叉率 SGA 対象問題によって傾向が異なる DGA 対象問題・個体数に関わらず 1.0 が良好 I S D L 9 移住と交叉による解の探索分散GAでは，母集団を分割することで全体として多様性を保持している交叉率が高いほど，解の探索能力は高くなる I S D L 10 移住と交叉による解の探索 SGA 高い交叉率は良好な解を破壊する可能性がある DGA サブ母集団内での多様性が低い部分的なスキーマを形成すればよい分散GAでは高い交叉率を与えても問題はない以上の理由により，分散GAにおける最適な交叉率は 1.0 であるといえる I S D L 11 最適な突然変異率 DGA 総個体数と突然変異率の関係（Rastrigin関数）交叉率1.0 20*9 早期収束を防ぐ働きを持つ 180*9 解を破壊し，適合度の上昇を遅らせる I S D L 12 最適な突然変異率最高の適合度が得られた突然変異率 SGA 対象問題によって傾向が多少異なる DGA 個体数が増えるに従い突然変異率は減少 I S D L 13 結論分散GAにおける最適な交叉率対象問題・個体数に関わらず 1.0 が良いパラメータ設定の困難さが軽減できる分散GAにおける最適な突然変異率個体数に少ない場合には 1 / L が良く，個体数が増えるに従い減少させる I S D L 補足資料 - 最適な突然変異率突然変異率の減少傾向は対象問題によって異なる母集団の分割数との関係は薄い I S D L 補足資料 - 最適な突然変異率 Griewank関数のような「完全に解けない」問題であっても突然変異率は個体数に応じて減少する I S D L 11 移住と交叉による解の探索あるサブ母集団内における新しい個体と交叉率との関係（理論値）交叉率1.0のとき 1世代で42% 5世代で約100%の新しい個体が生み出されるこの理由により，分散GAでは交叉率は 1.0 と設定するのが良いと考えられる I S D L 3 交叉と突然変異の性質交叉個体間での情報交換初期個体に含まれるビットを適切に組み合わせる突然変異多様性の保持交叉のみでは生成できない個体を生み出す I S D L