遗传算法的机理与收敛性研究

On the Mechanism and Convergence of Genetic Algorithm

采用一种新的基于解空间分解的定量分析方法,对遗传算法的种群进化过程进行分析,阐明了选择、交叉和变异操作的寻优机理,给出了子代种群在解空间上的概率分布情况;理论上,证明了遗传算法具备寻找全局最优解的能力,并给出了具备寻找全局最优解能力的充分必要条件,即证明了积木块假设的结论是成立的.同时,建立了二进制编码有限群体的M arkov链模型,计算出在用于静态优化问题的交叉和变异操作下,种群在解空间上概率分布情况以及收敛到最优解的概率,并讨论了产生早熟现象和GA-欺骗问题的原因.

A new approach based on decomposition of solution space according to difference of genotype is presented to analyze quantitatively the evolutionary course of populations of GA. The analysis yields new insight into the properties of the three phases, mutation, crossover, and fitness selection of a genetic algorithm by representing them as acting on the solution space. The probability distribute of populations over solution space can be calculated by this approach. Theoretically, the capability of finding the global optimum is proved, and a necessary and sufficient condition is obtained namely, the conclusion of building block hypothesis is proved. Meanwhile, under crossover or mutation operator applied to static optimization problems, the probability distribution of populations over solution space can be calculated by means of a finite Markov chain model, and the probability of GA converging to the global optimum also can be estimated. Finally, the reasons about GA deceptive problem and premature convergence are discussed.