遺伝的アルゴリズムにおける確率的揺らぎの効果 : スキーマの固定と消滅(進化的計算, <特集>第11回MPSシンポジウム: 複雑系の科学とその応用)  [in Japanese] Effect of Stochastic Fluctuations in Genetic Algorithms : Fixation and Extinction of Schemata (Evolutionary Computation, <Special Issue>MPS Symposium 2004 "Complex System Science and its Application")  [in Japanese]

遺伝的アルゴリズム(GA)では有限な個体数の集団を扱うため, 進化過程における確率的揺らぎの効果についての研究が必要である.本研究では, 積型適応度関数を例にとり, 有限な個体数がもたらす遺伝的揺動がGAの効率に及ぼす影響について調べた.有限個体数の数値実験では, 決定論的理論の予測と大きな差が見られた.このとき数値実験では, 有利な1次スキーマの消滅が起こっていた.また, 交叉を含むGA計算では, 集団の状態が連鎖平衡にあるものと仮定してよいことが分かった.そこで1次スキーマの頻度に注目した解析を行い, 進化の数学的解析において重要な役割を果たしてきたWright-Fisherモデルおよび拡散方程式を用い, その時間的変化を確率論的に求めた.これらの数理モデルにより, 1次スキーマの究極固定確率, 平均固定時間などの多くの値が理論的に予測できることを示した.

Since genetic algorithms (GAs) treat a population of finite size, it is necessary to study the effect of stochastic fluctuations in evolution processes. In this study, we investigated the influence of genetic drift due to finite population size on the performance of GA on the multiplicative landscape. We observed large difference between numerical experiments with finite population size and the prediction of deterministic theory, and noted the extinction of favorable first order schemata in the experiments. It was also noted that the population can be assumed to be in linkage equilibrium in GA calculations with crossover. Therefore, we performed the investigation of frequencies of the first order schemata, and calculated their changes in time by using the Wright-Fisher model and diffusion equations, which have played important roles in the mathematical analysis of evolution. We showed that these mathematical theories reasonably predict various quantities including the ultimate fixation probability and average fixation time.