论文部分内容阅读
遗传算法(Genetic Algorithm, GA)是一种基于Darwin进化论和Mendel遗传学说的优化搜索算法。它因具有简单、通用、鲁棒性强的特点,自诞生以来,获得了广泛的关注和应用,美国Michigan大学Holland教授在GA理论和方法的系统性研究方面作了很多开创性的工作,相关研究也日渐成为计算机科学、信息科学与最优化领域研究的热点。遗传算法在实际应用方面已取得了巨大的成就,但其基础理论的研究却相对滞后,尤其是缺乏广泛而完整的遗传算法收敛性理论。遗传算法的收敛性是关系到算法是否有效执行的关键。针对遗传算法的早熟收敛、收敛缓慢甚至不收敛等多种不足,国内外学者进行了大量的研究,并提出了许多的改进措施,以提高遗传算法的收敛速度。这些改进的方法在很大程度上提高了算法性能,有力地推动了遗传算法的发展。然而这些算法大都只是用实验的方法进行了验证,缺乏相应的理论分析和证明。郑金华教授提出的基于空间交配遗传算法(Genetic Algorithm Based on Space Mating, GASM)有效克服了早熟收敛,实验效果好,但也缺少相关理论的证明。为此,该论文把基于空间交配遗传算法作为研究对象,对其收敛性进行分析和证明,同时提出另外一种改进的遗传算法。论文的主要研究内容包括以下两个方面:(1)本文采用马尔可夫链分析了基于空间交配遗传算法的收敛性。证明了采用最优个体保留机制的GASM,可以收敛到全局最优解;同时证明了,在没有变异算子的情况下,GASM以概率1收敛到全局最优解。通过4个测试问题(其中3个为多峰值复杂问题)的对比实验,结果表明,GASM在求解多峰值复杂问题时,比采用最优个体保留机制的经典遗传算法(Elitist Genetic Algorithm, EGA),具有更好的收敛性。同时与快速蜂群优化算法进行了比较试验,实验表明,GASM在绝大部分函数中仍可体现出其优越性。(2)针对单个种群的遗传算法容易陷入局部收敛而出现早熟的情况,本文提出了一种改进的遗传算法—基于多种群进化的遗传算法(A Genetic Algorithm Based on Multi-Population Evolution, MPGA),用多线程并行处理的方法实现种群之间同步进化。实验证明,基于多种群的遗传算法能够有效地避免局部收敛问题,通过与经典遗传算法进行比较,表明本文所提出的算法不仅收敛速度快,而且收敛效率也很高,是一种可行、有效的算法。