【作者】 李航；

【导师】 寇纪淞；

【作者基本信息】 天津大学 ， 管理科学与工程， 2007， 博士

【摘要】 如何应用遗传算法求解多模态优化问题已经成为遗传算法乃至进化计算领域的一个广受关注的问题,它也是遗传算法理论和实际应用的基础。这方面的成果层出不穷,但理论研究相对薄弱。特别是研究外部参数如何影响遗传算法求解多模态优化问题的性能这方面仍然是个空白,本文着重进行了这方面的理论研究并对相应结论进行了推广。推广后的理论结果被用于改进遗传算法对多模态优化问题的搜索性能。本文的主要研究内容包括:1.对多模态优化问题和遗传算法进行了简单回顾,对应用遗传算法解决多模态优化问题的研究现状进行了分析,介绍了遗传算法的基础理论及其发展趋势。2.对经Walsh变换后的基因池遗传算法的无限种群模型进行了分析,刻画了“双峰函数”局部极值解的适值差与基因池遗传算法的搜索性能之间的关系,对上述理论结果进行了理论推广和实验验证。最后,根据所得结论设计出了针对多模态优化问题的两阶段遗传算法,并得到了满意的实验结果,这也从侧面说明了上述理论结果的正确性。3.讨论了局部极值解的吸引域对遗传算法收敛结果的影响,以及参数搜索空间规模对遗传算法搜索性能的影响,所得结论充分说明了对解空间进行合理划分的必要性。结合正交设计法,提出了基于解空间合理划分的遗传算法,通过仿真实验验证了该算法对多模态优化问题的有效性。4.分析了两类基于遗传算法无限种群模型的复杂进化系统,在此基础上构造了两类新的种群进化系统,并推导出了它们在单基因位情况下的动力方程。对新系统在稳态情况下的复杂动力行为进行了分析,通过相图、分岔图和Lyapunov指数谱图,严格地证明了其中一类系统具有混沌特性,而另一类系统具有复杂的周期特性。根据以上结论,提出了一种能够持续保持遗传算法的种群多样性的方法,它对求解多模态优化问题很有帮助。更多还原

【Abstract】 How to apply genetic algorithms to solve multi-modal optimization problems has been a focus in the research community of genetic algorithm and evolutionary computation. It is also fundamental to the basic theory and industrial applications of genetic algorithms. There have been many successful cases in real world, but the existing theoretic analyses are far from perfect. The influence of the external parameters on the efficiency of genetic algorithms is especially investigated, and the theoretic analyses are made and extended corollaries are derived. The theoretical achievements are used to the design of high-efficiency genetic algorithms for solving multi-modal optimization problems. The main contents of the dissertation are as follows:1. The development of the multi-modal optimization and genetic algorithms is summarized, and the current literatures of the application of genetic algorithms to the multi-modal optimization problems are reviewed. The basic theories of genetic algorithms are introduced, and the development trends of genetic algorithms are evaluated.2. The infinite population model of the gene pool genetic algorithm (GPGA) is built based on the Walsh transform, and the relation between the fitness difference of local optima of the BINEEDLE fitness function and the efficiency of GPGA is defined. The application scope of the theoretical corollaries are analyzed and proved via simulation tests. According to the theoretical propositions, we invent the two-step genetic algorithm for the multi-modal optimization problems, and get satisfactory empirical results. It also proves the theoretic corollaries indirectly.3. Both the influence of the attraction basins of the local optima on the convergence of genetic algorithms and the influence of the solution space spectrum on the efficiency of GPGA are investigated, which illustrates the significance of partition of the solution space. According to the orthogonal design, we propose a new genetic algorithm based on the rational partition of the solution space. The simulation experiments show that the improved algorithm converges to the global optimum more quickly, and can find more local optima than traditional methods on multi-modal optimization problems.4. Two complex evolution systems are analyzed based on infinite population model of the genetic algorithm. According to the analytical results, two new evolution systems are constructed, and the iterative equations of the dynamical system models of both evolution systems is derived in one-bit case. The complex behaviors of both systems in steady state are investigated by phase portraits, bifurcation diagrams and Lyapunov-exponent spectrums, which show that the first evolution system is a chaotic system and the second evolution system contains complex periodic behaviors. According to these conclusions, we present the method to keep the diversity of the population of the genetic algorithm, which is good for finding more useful solutions of multi-modal optimization problems.更多还原