並列分散遺伝的アルゴリズムにおけるハイブリッド生成交叉

(1)

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の解探索メカニズムをさらに検討し，それに適した新たな交叉スキームを提案する．

2 PDGA

における移住および交叉の役割

2.1 母集団の分割と移住の効果

単一母集団GAでは，比較的良好なスキーマを持つ個体が多数を占めることによって他のスキーマの成長が妨げられ，結果的に早熟収束を起こすことがある．一方，PDGA ではサブ母集団ごとの個体数は単一母集団GAよりもさらに小さくなり，早熟を起こしやすい．しかし，個々のサブ母集団は異なる傾向に進化することが多く，移住によって個体を交換することで全体としては多様性を保つことが可能である．また，あるサブ母集団で生成された良好なスキーマが，移住によって他のサブ母集団の個体が持つスキーマと結合し成長するために，単一母集団GA よりも高品質な解を高速に求めることができる¹⁾．すなわち，PDGAにおける移住の機能は，早熟を防ぎ多様性を高めるとともに，その後の交叉によってスキーマを結合させることにあると考えられる．特に，スキーマの結合メカニズムには，移住後の第1世代での交叉が非常に重要な役割を担っていると考えられる．

2.2 ハイブリッドの影響

次の議論のために，個体に3つの属性を定義する．あるサブ母集団において移住が行われた後，そのサブ母集団に留まっている個体を母個体とし，移住によって他のサブ母集団から移動してきた個体を移住個体とする．さ

らに，母個体と移住個体が交叉して生成された個体をハイブリッドとする．

移住の機能がPDGAの性能に与える影響を検証するため，以下の3つのスキームを用いて数値実験を行った．1）

移住をしない(w/o Mig.) 2）移住後の第1世代は母個体同士および移住個体同士の交叉のみを許可し，ハイブリッドを生成しない(w/o Hybrid) 3）通常の移住および交叉(Normal)．

対象問題は10次元のテスト関数²⁾ の最大化である．

Rastrigin関数は多峰性の関数であり，変数間に依存関係

はなく，GAでは比較的解きやすい．Rosenbrock関数は変数間に極めて強い依存関係をもつ単峰性関数であり，GA では部分解を形成することができず，非常に解きにくい問題であるとされている．Ridge関数はRastrigin関数

とRosenbrock関数の中間的な性質を持つ単峰性の関数

である．

ここでは，個体数を400，サブ母集団数を8，交叉率を 1.0，突然変異率を1/L（染色体長 : 100bit），移住間隔を5世代，および移住率を0.5とした．なお，結果は20 試行の平均値である．

Table 1 The eﬀect of migration scheme w/o Mig. w/o Hybrid Normal

Rastrigin ＃733 ＃339 ＃292

Ridge -4.46328 -1.07266 -0.93984 Rosenbrock -1.26808 -4.97602 -5.23925

1000世代での適合度をTable 1に示す．1000世代までに最適解を発見できたものについてはその世代（＃）を示している．

Rastrigin関数とRidge関数では通常の交叉スキームが最も高い性能を示している．移住後第1世代のハイブリッド生成を禁止したスキームは通常の交叉スキームと比較して探索性能が劣る．

一方，GAにおける部分解の形成および組み合わせの機能が有効に作用しないRosenbrock関数では，移住を行

(2)

わないスキームが最も良く，移住を行うスキームは両者ともに大きな違いはない．

これらの結果より，PDGAにおける解探索を移住と交叉が促進している場合には，移住後第1世代のハイブリッド生成が極めて重要であることがわかった．

3

ハイブリッドの生成を促進する交叉

前節の結果より，移住後にハイブリッドを多く生成することでPDGAの性能をさらに高めることができると考えられる．

通常の交叉スキームでは，あるサブ母集団において移住後第1世代の全個体に占めるハイブリッドの割合（H）

は次の式で求めることができる．Pcは交叉率（最大1.0）

であり，µは移住率（最大0.5）である．

H = 2P_cµ(1−µ) (1) 交叉率を1.0，移住率を0.5としても，H の最大値は 0.5となる．通常の交叉ではPDGAにおける解探索の主役であるハイブリッドは全体の50％しか生成されない．

残りの50％は母個体同士，あるいは移住個体同士から生成される個体であり，移住の影響を受けていない．

そこで，移住後第1世代のハイブリッドをさらに多く生成する新たな交叉スキームとして，ハイブリッド生成交叉（Hybridization Crossover : HX）を提案する．この交叉は，移住後の第1世代において移住個体を確実に母個体と交叉させることにより，従来よりも多くのハイブリッドを生成するスキームである．HXを用いることにより，Hは以下の式で求めることができる．

H = 2P_cµ (2) 交叉率を1.0，移住率を0.5とすることで，全ての個体をハイブリッドにすることができる．

4

ハイブリッド生成交叉の効果

移住後第1世代に生成されるハイブリッドの数がPDGA の性能に及ぼす影響を調べるため，2.2節と同様の数値実験を行った．比較するパラメータHは，0.2，0.5，および1.0とする．

Table 2 The performance of HX H = 0.2 H = 0.5 H = 1.0 Rastrigin ＃337 ＃296 ＃281 Ridge -1.40312 -1.32812 -0.94375 Rosenbrock -3.57505 -4.70237 -5.87565

実験の結果をTable 2に示す．Rastrigin関数とRidge 関数においては，Hが高いものほど良い性能を示しており，特にRastrigin関数では，2.2節の通常のスキームよ

りも良い．一方，Rosenbrock関数では，H = 1.0とすると他のスキームと比較しても最も性能が悪くなる．これらより，HXを用いることで，PDGAにおいて移住が果たす機能は最大化されることがわかる．

Fig. 1はRidge関数での適合度の推移である．HがGA の探索に及ぼす影響は探索の前半と後半で大きく異なることが明らかになった．まず，探索の前半では，Hが高いほうが適合度の上昇は速い．これにより，移住および交叉による解探索は，Hを高めることによって有効に機能していることがわかる．

Fig. 1 History of the ﬁtness value

探索の終盤では個体間の多様性が低くなり，母個体と移住個体が同じような傾向となる．そのため，生成されたハイブリッドによって大きく適合度が上昇することも少ない．このことから，探索の後半ではHXの効果は小さくなるといえる．

5

おわりに

並列分散GAにおける解の成長メカニズムが単一母集団のGAとは異なることに注目し，その性能をさらに高める交叉スキームを提案した．並列分散GAでは，移住オペレータによってサブ母集団内の早熟を避けるとともに，その後の交叉によって母個体と移住個体から両者のスキーマを併せ持つハイブリッドを生成する機能をもつ．

ハイブリッド生成交叉（HX）はこの解探索機能をさらに高めるためものであり，提案手法を3つの代表的なテスト関数に適用した結果，良好な結果を示した．

参考文献

1) 三木,廣安,金子. 分散母集団遺伝的アルゴリズムにおける解探索能力. 人工知能学会全国大会, 1999.

2) S. Rana D. Whitley, K. Mathias and J. Dzubera. Build- ing better test functions. International Conference on Genetic Algorithms, 1995.

(3)

出典：

日本機械学会第13回計算力学講演会講演論文集 pp. 299 - 300

(2000年11月28-30日)

問い合わせ先：

同志社大学工学部/同志社大学大学院工学研究科知的システムデザイン研究室

(http://mikilab.doshisha.ac.jp)