並列分散遺伝的アルゴリズムにおけるハイブリッド生成交叉 Hybridization Crossover for Parallel Distributed Genetic Algorithms 正 ○学 三木 光範（同志社大工） 正 大向 一輝（同志社大院） 廣安 知之（同志社大工） Mitsunori MIKI, Doshisha University, Tatara Miyakodani 1-3, Kyo-Tanabe, Kyoto Tomoyuki HIROYASU, Doshisha University Ikki OHMUKAI, Graduate School of Engineering, Doshisha University, [email protected] Key word : Genetic Algorithms, Parallel Processing, Distributed Subpopulations, Crossover 1 はじめに らに，母個体と移住個体が交叉して生成された個体をハ 遺伝的アルゴリズム (Genetic Algorithm : GA) は生物 の進化プロセスを模倣した確率的な最適化アルゴリズム GA の並列化手法の 1 つに，母集団を複数のサブ母集 団に分割して GA を実行し，一定世代ごとに移住と呼ば れる個体の交換を行う並列分散 GA(Parallel Distributed GA : PDGA) がある．PDGA は並列化によって計算時間 が短縮されるだけでなく，単一母集団の GA と比較して より良好な解を得ることが可能である． 本論文では，PDGA の解探索メカニズムをさらに検討 し，それに適した新たな交叉スキームを提案する． PDGA における移住および交叉の役割 2.1 移住の機能が PDGA の性能に与える影響を検証するた め，以下の 3 つのスキームを用いて数値実験を行った．1） である． 2 イブリッドとする． 移住をしない (w/o Mig.) 2）移住後の第 1 世代は母個 体同士および移住個体同士の交叉のみを許可し，ハイブ リッドを生成しない (w/o Hybrid) 3）通常の移住およ び交叉 (Normal)． 対象問題は 10 次元のテスト関数 2) の最大化である． Rastrigin 関数は多峰性の関数であり，変数間に依存関係 はなく，GA では比較的解きやすい．Rosenbrock 関数は変 数間に極めて強い依存関係をもつ単峰性関数であり，GA では部分解を形成することができず，非常に解きにくい 問題であるとされている．Ridge 関数は Rastrigin 関数 と Rosenbrock 関数の中間的な性質を持つ単峰性の関数 母集団の分割と移住の効果 である． 単一母集団 GA では，比較的良好なスキーマを持つ個体 が多数を占めることによって他のスキーマの成長が妨げら れ，結果的に早熟収束を起こすことがある．一方，PDGA ではサブ母集団ごとの個体数は単一母集団 GA よりもさ ここでは，個体数を 400，サブ母集団数を 8，交叉率を 1.0，突然変異率を 1/L（染色体長 : 100bit），移住間隔 を 5 世代，および移住率を 0.5 とした．なお，結果は 20 試行の平均値である． らに小さくなり，早熟を起こしやすい．しかし，個々の サブ母集団は異なる傾向に進化することが多く，移住に Table 1 The effect of migration scheme よって個体を交換することで全体としては多様性を保つ ことが可能である．また，あるサブ母集団で生成された w/o Mig. w/o Hybrid Normal ＃ 733 ＃ 339 ＃ 292 良好なスキーマが，移住によって他のサブ母集団の個体 Rastrigin が持つスキーマと結合し成長するために，単一母集団 GA Ridge -4.46328 -1.07266 -0.93984 Rosenbrock -1.26808 -4.97602 -5.23925 よりも高品質な解を高速に求めることができる 1) ．すな わち，PDGA における移住の機能は，早熟を防ぎ多様性 を高めるとともに，その後の交叉によってスキーマを結 合させることにあると考えられる．特に，スキーマの結 合メカニズムには，移住後の第 1 世代での交叉が非常に 重要な役割を担っていると考えられる． 2.2 ハイブリッドの影響 次の議論のために，個体に 3 つの属性を定義する．あ るサブ母集団において移住が行われた後，そのサブ母集 1000 世代での適合度を Table 1 に示す．1000 世代まで に最適解を発見できたものについてはその世代（＃）を 示している． Rastrigin 関数と Ridge 関数では通常の交叉スキームが 最も高い性能を示している．移住後第 1 世代のハイブリッ ド生成を禁止したスキームは通常の交叉スキームと比較 して探索性能が劣る． 団に留まっている個体を母個体とし，移住によって他の 一方，GA における部分解の形成および組み合わせの サブ母集団から移動してきた個体を移住個体とする．さ 機能が有効に作用しない Rosenbrock 関数では，移住を行 わないスキームが最も良く，移住を行うスキームは両者 りも良い．一方，Rosenbrock 関数では，H = 1.0 とする ともに大きな違いはない． と他のスキームと比較しても最も性能が悪くなる．これ これらの結果より，PDGA における解探索を移住と交 叉が促進している場合には，移住後第 1 世代のハイブリッ らより，HX を用いることで，PDGA において移住が果 たす機能は最大化されることがわかる． Fig. 1 は Ridge 関数での適合度の推移である．H が GA ド生成が極めて重要であることがわかった． 3 の探索に及ぼす影響は探索の前半と後半で大きく異なる ハイブリッドの生成を促進する交叉 ことが明らかになった．まず，探索の前半では，H が高 前節の結果より，移住後にハイブリッドを多く生成す いほうが適合度の上昇は速い．これにより，移住および ることで PDGA の性能をさらに高めることができると考 交叉による解探索は，H を高めることによって有効に機 えられる． 能していることがわかる． 通常の交叉スキームでは，あるサブ母集団において移 住後第 1 世代の全個体に占めるハイブリッドの割合（H ） は次の式で求めることができる．Pc は交叉率（最大 1.0） であり，µ は移住率（最大 0.5）である． H = 2Pc µ(1 − µ) (1) 交叉率を 1.0，移住率を 0.5 としても，H の最大値は 0.5 となる．通常の交叉では PDGA における解探索の主 役であるハイブリッドは全体の 50 ％しか生成されない． 残りの 50 ％は母個体同士，あるいは移住個体同士から生 成される個体であり，移住の影響を受けていない． そこで，移住後第 1 世代のハイブリッドをさらに多く 生成する新たな交叉スキームとして，ハイブリッド生成 交叉（Hybridization Crossover : HX ）を提案する．この 交叉は，移住後の第 1 世代において移住個体を確実に母 Fig. 1 History of the fitness value 個体と交叉させることにより，従来よりも多くのハイブ リッドを生成するスキームである．HX を用いることに より，H は以下の式で求めることができる． H = 2Pc µ 探索の終盤では個体間の多様性が低くなり，母個体と (2) 移住個体が同じような傾向となる．そのため，生成され たハイブリッドによって大きく適合度が上昇することも 交叉率を 1.0，移住率を 0.5 とすることで，全ての個体 少ない．このことから，探索の後半では HX の効果は小 をハイブリッドにすることができる． さくなるといえる． 4 5 ハイブリッド生成交叉の効果 おわりに 移住後第 1 世代に生成されるハイブリッドの数が PDGA 並列分散 GA における解の成長メカニズムが単一母集 の性能に及ぼす影響を調べるため，2.2 節と同様の数値実 団の GA とは異なることに注目し，その性能をさらに高 験を行った．比較するパラメータ H は，0.2，0.5，およ める交叉スキームを提案した．並列分散 GA では，移住 び 1.0 とする． オペレータによってサブ母集団内の早熟を避けるととも に，その後の交叉によって母個体と移住個体から両者の Table 2 The performance of HX H = 0.2 H = 0.5 H = 1.0 ＃ 337 ＃ 296 ＃ 281 Ridge -1.40312 -1.32812 -0.94375 Rosenbrock -3.57505 -4.70237 -5.87565 Rastrigin スキーマを併せ持つハイブリッドを生成する機能をもつ． ハイブリッド生成交叉（HX）はこの解探索機能をさらに 高めるためものであり，提案手法を 3 つの代表的なテス ト関数に適用した結果，良好な結果を示した． 参考文献 1) 三木, 廣安, 金子. 分散母集団遺伝的アルゴリズムにおける 解探索能力. 人工知能学会全国大会, 1999. 実験の結果を Table 2 に示す．Rastrigin 関数と Ridge 関数においては，H が高いものほど良い性能を示してお り，特に Rastrigin 関数では，2.2 節の通常のスキームよ 2) S. Rana D. Whitley, K. Mathias and J. Dzubera. Building better test functions. International Conference on Genetic Algorithms, 1995. 出典： 日本機械学会 第 13 回計算力学講演会講演論文集 pp. 299 - 300 (2000 年 11 月 28-30 日) 問い合わせ先： 同志社大学工学部/ 同志社大学大学院工学研究科 知的システムデザイン研究室 (http://mikilab.doshisha.ac.jp)
© Copyright 2024 ExpyDoc
