进化算法中的模式定理及建筑块

Schemata Theorem and Building Blocks in Evolutionary Algorithms

探讨了进化算法中的模式定理及建筑块理论 .通过引入模式进化、模式进化能力、适度模式等概念 ,以标准遗传算法为例 ,证明了在变异算子独立的条件下 ,进化算法中模式的构成与多点交叉和变异的顺序无关 ,然后证明了具有强进化能力的模式 ,将以指数阶增长 .该文的模式理论有别于Holland等人提出的模式理论 ,特别是在交叉算子上采用了多点交叉算子 ,给出了相应的公式 ;并从这一推导过程论证了建筑块假设的合理性 ,可以称之为建筑块理论 .

Evolutionary algorithms have obtained great attention regarding their potential for solving complex problems, such as optimization of objectives, artificial intelligence, machine learning and so on. Also in the family of EA there exist many different algorithms variants, they have the same mechanism in schemata evolution. This paper shows the schema theorem and the building blocks hypothesis can be used for explanations of the foundation in EA, Here, some new concepts are introducing, such as schema evolution, schema evolvability and appropriate schema. Authors prove that when mutation is independent, it may be performed either before or after multi-point crossover, the consequences of schema in EA are probabilistically the same. Authors derive the schema theorem based on the concept of schema evolvability proving that schemata of more power than others accept an exponentially increasing number of trials over time. Specially, authors use multi-point crossover to obtain schemata evolution equation instead of one-point crossover. Holland's schema theorem and the building block hypothesis attempt to explain the power of Genetic Algorithms (GA), Schema theorem presented has the same purpose, but it is different from Holland's schema theorem in expression and essential. Finally, an argumentation of building blocks hypothesis is regarded as building blocks theorem.