动态种群规模的协同进化算法模型、理论与应用

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 目录
• 第1章 引言
• 1.1 研究背景
• 1.2 协同进化算法简介
• 1.3 本文的研究动机
• 1.4 本文的主要工作与创新之处
• 1.5 本文的章节安排
• 第2章 协同进化算法研究现状
• 2.1 什么是协同进化算法
• 2.2 竞争型协同进化算法
• 2.3 合作型协同进化算法
• 2.4 协同进化算法的典型应用
• 2.5 本章小结
• 第3章 统一的协同进化模型研究
• 3.1 研究动机
• 3.2 协同进化算法的基本框架
• 3.3 通用的动态种群规模调节策略
• 3.3.1 设计思想
• 3.3.2 具体实现
• 3.4 统一的协同进化模型CEAD
• 3.5 CEAD模型中的个体采样技术
• 3.5.1 设计思想
• 3.5.2 具体实现
• 3.6 CEAD模型指导下的协同进化算法设计
• 3.7 本章小结
• 第4章 CEAD模型的理论基础
• 4.1 CEAD模型的动力学方程
• 4.2 CEAD模型的稳定性分析
• 4.2.1 局部渐近稳定性
• 4.2.2 全局渐近稳定性
• 4.3 CEAD模型的收敛性分析
• 4.4 CEAD模型的计算复杂度分析
• 4.5 本章小结
• 第5章 基于CEAD模型的多峰函数优化
• 5.1 背景介绍
• 5.2 相关工作
• 5.2.1 单种群进化算法
• 5.2.2 协同进化算法
• 5.3 基于CEAD模型的协同进化算法
• 5.3.1 算法的设计与实现
• 5.3.2 算法的描述
• 5.4 对比实验
• 5.4.1 目标多峰函数
• 5.4.2 实验结果与分析
• 5.5 本章小结
• 第6章 基于CEAD模型的空中流量优化调度
• 6.1 背景介绍
• 6.1.1 空中交通流量管理
• 6.1.2 航班着陆调度问题
• 6.2 多目标优化问题
• 6.2.1 问题定义
• 6.2.2 多目标进化算法
• 6.3 我们采用的模型
• 6.4 基于CEAD模型的协同进化算法
• 6.5 对比实验
• 6.5.1 实验数据
• 6.5.2 实验结果与分析
• 6.6 本章小结
• 第7章 结束语
• 7.1 本文工作总结
• 7.2 进一步工作展望
• 参考文献
• 致谢
• 在读期间发表的学术论文与取得的研究成果