进化算法中基于排序选择下的准确模式理论

Exact schemata theorem based on ranking selection in evolutionary algorithms

进化计算中的模式理论是解释进化计算工作机理的一个有力工具.文章以遗传算法为例,通过引入红皇后假说及模式进化能力等概念,使用排序选择代替了依概率选择,证明了在进化算子采用排序选择、多点交叉和多点变异的情况下,具有较强进化能力的模式,将以指数阶增长,并给出了排序选择下准确的模式进化公式.

This paper shows that the schema theorem can be used for explanations of the mechanism in evolutionary algorithms. Some new concepts are introduced, such as schema evolvability and red queen hypothesis. We derive the schema theorem based on the concept of schema evolvability, and proves that schemata with a higher evolvability than others will accept an exponentially increasing number of trials over time. Specially, we use a multi-point crossover to obtain schemata evolution equation instead of one-point crossover. At the same time, ranking selection is substituted for proportional selection.