【作者】 张廷玉；

【导师】 李法朝；

【作者基本信息】 河北科技大学 ， 应用数学， 2009， 硕士

【摘要】 遗传算法是由美国自动控制论专家Holland于1975年提出的一种基于生物进化论及孟代尔基因遗传理论的搜索型优化算法,遗传算法主要是借鉴物种进化思想,从一组随机生成的初始可行种群出发,借助选择、交叉、变异等遗传操作,逐步逼近所研究问题的最优解。这种方法避开了所研究问题的复杂数学特征,对目标函数没有特殊的要求。但随着科学技术的发展,所研究问题规模的不断扩大,以及复杂度不断增加,对遗传算法求解质量和运行速度都提出了更高的要求,遗传算法在处理这些问题时的“未成熟”收敛性以及收敛解精度不高等方面的缺点暴露出来,该问题制约了遗传算法在复杂系统优化问题中的应用。本文针对遗传算法存在的这些问题作了相应的研究。首先针对基本十进制编码遗传算法在求解复杂系统优化问题,尤其是寻优范围大、精度要求高的优化问题时经常出现的“未成熟”收敛及收敛解精度不高等缺点,结合生物进化的基本特征,从结构化和可视化的角度出发,提出一种变异准则函数,建立了一类基于复合变异的GA(简记为CM-GA)。进而,利用Markov链理论讨论了CM-GA的全局收敛性,并结合实例,比较和分析了CM-GA的收敛性能。针对基本二进制编码遗传算法运行过程中出现的解的范围变动比较大,不易于收敛到最优解的特点。本文结合生物进化的基本特征,从保护生物的优良特征的角度出发,提出了一种基于模式的复合变异策略,建立了一类基于模式变异的遗传算法(简记为SM-GA)。进而,利用Markov链理论讨论了SM-GA的全局收敛性,并结合实例,比较和分析了SM-GA的收敛性能。最后结合属性约简的特点,提出了一种基于模式变异遗传算法的属性约简算法。更多还原

【Abstract】 Genetic Algorithm (GA for short), proposed by Holland in 1975, is a kind of search optimization algorithm based on the theory of evolution and the genetic mutation theory of Mendel. Genetic Algorithm, with the evolutionary theory and operation of selection, crossover and mutation, gradually approaching the optimal solution of the problem from a set of randomly initial feasible groups, The method has the feature of no consideration the complex mathematics characteristic of real problems and no restriction on objective function. However, with the development of science and technology, the scale of the problem expanding, and Increasing complexity, genetic Algorithm for the quality and speed have a higher demand. GA can not cover the shortcomings of poor convergence and premature phenomenon. The problem restricts greatly the application of GA to complex systems optimization problems. Considering this, we have the following findings.Firstly, in view of the poor convergence and the low precision of convergence solution of B10GA, In feature of solving optimization problems of complex systems, especially the optimization range, high accuracy optimization problem. Combining with the essential, we propose the concept of mutation criteria function describing mutation characteristic from structural and visualized angle, and establish a genetic algorithm based on compound mutation (denoted by CM-GA, for short). Further, we discuss the global convergence of CM-GA by using the Markov chain theory, and analyze the performance of CM-GA through an example. Second, in the process of B2GA running, The scope of solutions can have a relatively large change and difficult to converge to the optimal solution. In this section, for protecting the fine features of biological and combining with the essential feature, we establish a genetic algorithm based on schema mutation (denoted by SM-GA, for short). Further, we discuss the global convergence of CM-GA by using the Markov chain theory, and analyze the performance of SM-GA through an example. Finally, we put forward a kind of attribute reduction algorithm based on schema mutation genetic algorithm combining with the feature of attribute reduction.更多还原