论文部分内容阅读
从上世纪70年代进化计算(Evolutionary Computation，EC)创立以来，这种全新的优化算法引起人们极大的研究兴趣。进化计算包括遗传算法(Genetic Algorithm,GA)、进化规划(Evolutionary Programming，EP)、进化策略(Evolution Stratcgy,ES)与遗传编程(Genetic Programming，GP)等,本文主要研究了进化计算复杂性，阐述了一些复杂性分析方法以及在某些条件下的进化计算的复杂性情形。并提出了一种改进遗传算法，并对它在SAT问题和密码代数攻击问题上做了实验分析。
第一章介绍遗传算法的生物学基础，回顾进化计算各分支的起源和发展，概括进化计算的主要特点，总结进化计算的理论研究及应用现状，简要介绍若干相关的优化算法，如禁忌搜索、人工神经网络、粗糙集理论、蚁群优化算法、粒子群优化算法和拟物拟人算法等。
第二章系统介绍进化计算的基本原理，包括标准遗传算法、进化规划、进化策略和模拟退火的基本构成和基本实现技术。然后再介绍了一些理论研究，包括一般收敛性理论、模式理论以及欺骗问题。
第三章研究遗传算法的计算复杂性。此种复杂性是一种关于随机算法的平均时间(average time)复杂性，不同于确定性算法的复杂性理论。详细阐述了两种分析复杂性的方法：基于马尔科夫链(Markov Chain：M.C)的分析方法和姚新等人用漂移(drift)的思想进行遗传算法的分析方法，并在此基础上提出了一种基于drift和群体多样性的改进遗传算法(DDGA)。这一算法的特点是，通过引入一种新的参数算子，使得遗传算法的每一代群体的平均适应值的期望增加，通过修改参数，可以控制收敛速度。另外我们还引入一种动态的增加群体多样性的方法，在收敛速度和群体多样性之间做出好的平衡。
第四章将DDGA在函数优化、可满足性问题以及流密码的代数攻击中做了实验分析，说明了DDGA的参数对性能的影响以及其大小选择，并比较了算法与其他算法的性能优势。