论文部分内容阅读
受自然界生态系统中多物种协同进化现象的启发,人们提出了一类新型进化算法:协同进化算法(Co-Evolutionary Algorithm)。协同进化算法能有效解决许多传统进化算法难以解决的复杂问题,是近年来计算智能领域的一个研究热点。动态种群规模调节技术是进化算法中的一项重要技术,其目的在于自适应地平衡全局搜索能力和局部搜索能力之间的矛盾,合理分配计算资源以提高算法的整体性能。由于进化动力学机制的不同,传统进化算法中已有的动态种群规模调节技术并不适合协同进化算法;而协同进化算法的现有工作又大多集中在针对具体应用问题的算法设计方面,动态种群规模技术的研究几乎是一片空白。本文从协同进化算法的共性入手,以适应度评估过程中的个体相互作用为出发点,设计了一个具有通用性的动态种群规模调节策略,并在该策略的基础上构建了一个统一的协同进化算法模型,称为动态种群规模的协同进化算法模型(Model of Co-Evolutionary Algorithm with Dynamic population size),简称CEAD模型。该模型从协同进化算法的本质出发,描述了协同进化算法共通的进化机制,其算法体系涵盖了包括竞争型、合作型、混合型在内的各种协同进化算法,具有重要的指导意义。我们从动力学、稳定性、收敛性、计算复杂度等多个方面对CEAD模型及其算法体系作了全面的理论分析。理论分析指出,CEAD模型具有全局渐近稳定性,在其指导下设计的协同进化算法,可以保证种群规模能够自适应地调节至合适的水平,从而有效地平衡全局搜索能力和局部搜索能力之间的矛盾,合理地在子种群间分配计算资源,令算法能够稳定而高效地收敛到全局最优解。最后,我们完成了CEAD算法体系在两种典型复杂优化问题求解中的应用。在多峰函数优化问题中,对比实验表明在CEAD模型指导下设计的协同进化算法可以合理地调节种群规模,有效地利用计算资源,具有全局搜索能力强、收敛速度快优化性能好、求解效率高等优点。在空中流量优化调度中,针对多目标航班着陆调度模型这一带有大量约束的多目标优化问题,我们在CEAD模型的指导下设计了一个带有隐含的约束处理机制的协同进化算法,并取得了令人满意的优化结果,显示了CEAD算法体系优秀的复杂问颢求解能力。