应用常规的遗传算法求解函数优化问题尤其是维数较高的问题时,通常遇到算法过早收敛、搜索精度难以提高等问题。为此,研究人员提出了各种改进方法,其中一种是在算法中混合使用多种遗传算子。但目前对这种改进方法仍缺乏比较系统的研究。针对这种现状,本文从实数编码遗传算法杂交算子的组合入手,着重研究杂交算子的组合效应以及变异算子如何与组合杂交算子的配合等问题,并在此基础上构建了一种新的演化算法框架。
首先对实数编码遗传算法中各种杂交算子的基本搜索特点进行分析。对于离散重组算子,用组合数学分析了一点杂交、多点杂交和均匀杂交三种离散重组算子的组合能力,算子的组合能力用算子组合出新染色体数目的大小衡量。分析结果表明均匀杂交的组合能力最强。数值实验表明,算法的搜索性能与离散重组算子的组合能力有关,但不存在算子的组合能力越强,算法的搜索性能越好的简单关系。使用哪个算子比较合适,在很大程度上也与优化问题有关,表明离散重组算子具有问题依赖性。分析了选择和离散重组算子共同搜索的局部性。指出只有选择和离散重组算子共同搜索时,搜索范围只局限于初始群体所确定的最大矩体内。对于算术杂交算子,分析了算术杂交算子的收缩性。分析了选择和算术杂交算子共同搜索的局部性,指出只有选择和算术杂交算子共同搜索时,搜索范围也只局限于初始群体所确定的最大矩体内。分析了扩展算术杂交算子的随机伸缩性,指出其搜索范围比离散重组算子和算术杂交算子更大。
通过数值实验系统地研究了10种扩展算术杂交算子的12种并行组合和12种受限并行组合的组合效应。数值实验表明,在相同的实验条件下(群体规模相同,计算代价相同,求解次数相同),组合杂交算子存在抑制、协同和等效三种组合效应。组合算子的搜索效果不一定比单个算子好;算子多的组合不一定比算子少的组合搜索效果好;组合算子的搜索效果与单个算子一样具有问题依赖性,相比而言,多数组合算子的问题依赖性要比单个算子的问题依赖性弱。
理论分析和数值实验表明,某些扩展算术杂交算子或其组合具有一定的解空间探索能力。考虑到这一点,建立了一个基于混合杂交与间歇变异的演化算法框架。在算法中引入了间歇式变异操作,即变异不是每代都发生的,而是间断发生的。在变异发生的间隔期间,利用扩展算术杂交算子及其组合的局部搜索能力和有限的全局探索能力对解空间的各局部区域和整个解空间进行搜索,当群体聚集到一定程度,扩展算术杂交算子及其组合的探索能力有所下降时,再对群体进行变异操作,恢复群体的多样性,以此来提高扩展算术杂交算子及其组合的探索能力。按照这种新型的演化算法框架,提出了求解无约束优化问题的演化算法,在算法中,将数种扩展算术杂交算子通过并行组合及串并行组合的方式有机地结合到一起,以增强算法的搜索能力和拓宽算法的适应面。用它求解了100到500维不等的多种无约束测试函数,获得了比其他一些演化算法精度更高、更稳定的优化结果。对直接比较的约束处理方法和不可微精确罚函数法进行了讨论,在此基础上分别将它们结合到基于混合杂交与间歇变异的演化算法框架中,提出了几种求解约束优化问题的演化算法,其中有的算法采用了离散重组算子与扩展算术杂交算子构成的杂交算子网。用它们求解了5到200维不等的带等式或不等式约束的测试函数,也获得了比其他一些演化算法包括近来提出的算法精度更高、更稳定且约束满足更好的优化结果。
探索新的演化算法机制也是值得提倡的,通过模拟人口随经济重心而转移、随人口压力增加而扩散的机制,本文还提出了一种新的用于函数全局优化的搜索算法—人口迁移算法。数值实验表明该算法具有良好的全局优化性能。运用概率论的有关理论证明了该算法依概率收敛到全局最优解。给出了该算法工作在最坏情形时即分区域随机搜索时的收敛速度估计和计算时间复杂性估计,为该算法的应用打下了比较坚实的理论基础。
