遗传算法的全局动力学形态分析

目前，对遗传算法的运行机理分析大都集中在算法的极限收敛性等问题，对算法的全局动力学形态研究较少．从一个具有代表性的、简化的2—bit问题入手，可以对遗传算法中常用的各种进化算子及其组合进行形式化描述，从而全面分析GA的全局动力学形态．针对各种参数的选取，分别建立了4个数学模型．通过分析这些模型中各个不动点的吸引性，揭示出不同进化算子对动力学形态的影响．对于这个问题，证明了算法的全局收敛性．并指出，当存在两个被此竞争的局部极值点时，模型中只有两个吸引点和一个鞍点(或排斥点)，不存在其他的不动点或周期点．算法的收敛结果完全由初始条件处于状态空间中的位置所决定，相应的收敛区域的比例完全由模型的参数决定．

Global Dynamic Shape Analysis of a Genetic Algorithm

At present, although the theory analysis of GA's convergence focuses attention on limit behavior, it is lacking global dynamic researching In this paper, the GA's global dynamic shape is first analyzed in accordance with a simple 2 bit problem The common evolution operators and their combination are described formally Four mathematic models are established based on different parameters selection of canonical genetic algorithms The effects are discovered that every operator has on GA's dynamic shape through the attraction analysis of model's fixed points The global convergence is proved for this problem There are two attractive fixed points, one saddle point (or one ejective point) and no other fixed point or period point in the mathematic models when two competitive local peaks exist Which local peak can be converged is determined by the position of initial condition in status space, and the proportion of each domain is determined by the model's parameters