演化动态优化研究

论文摘要

作为求解复杂问题的一种强有力的搜索和优化技术,演化算法的诞生受演化生物学的启发,并且已经被成功应用于很多领域,如规划(如路由、调度等)、设计(如信号处理等)、模拟和识别、控制以及分类(如机器学习、模式识别等)。传统的演化算法研究大多关于求解静态优化问题,求解目标一般为找到给定问题的最优解。然而,实际应用中,一般来说待求解问题会随时间不断变化。例如目标函数、问题实例或者约束条件等与待求解问题有关的因素在不同的时刻都可能是不同的。此时的优化目标一般为找到待求解问题在每一时刻的最优解,即追踪随时间不断变化的追踪解。在解决这类动态优化问题时,传统的演化算法由于易于收敛到搜索空间中某个较小的区域而无法较好地适应环境的变化。为解决收敛的问题,一种很自然的想法为使得种群在演化过程中始终保持一定程度的多样性,而种群迁移策略则是基于该目标的一种简单有效的方法。为了保持种群多样性,种群迁移策略在每一代引入按一定机制生成的迁移个体来替换当前种群中的部分个体。我们首先根据迁移个体的生成机制,将现有的种群迁移策略分类为直接以及间接种群迁移策略。然后通过一系列实验分析比较了两类种群迁移策略在动态环境中的行为。实验结果表明,大多数情况下,直接种群迁移策略性能优于间接种群迁移策略,而鲁棒性则比间接种群迁移策略差。基于此分析,我们提出了一种混合种群迁移策略,即混合了两种类型种群迁移策略生成的迁移个体。实验结果表明该策略能够很好的平衡算法在动态环境中的性能和鲁棒性。此外,我们研究了种群迁移策略中替换率大小对算法性能的影响,实验表明,对于不同的种群替换策略,不同的问题,不同的环境,以及不同的搜索阶段,最佳的替换率值不同且差异较大。为了减轻调整参数的负担,我们提出了一种基于自适应替换率的种群迁移策略,它根据引入的迁移个体在当前时刻的有效程度来调整替换率的大小。实验表明,对于不同的种群迁移策略以及不同的环境,该自适应机制均能获得良好的性能,从而避免了为特定问题、特定环境以及特定算法调节参数的麻烦。接下来,我们指出了当以追踪最优解为目标时,传统的演化动态优化在实际应用中面对的诸多难题。提出了一种新的解决方案,即动态鲁棒优化,该方案的优化目标为寻找时间域上的鲁棒解序列。然后阐述了动态鲁棒优化与动态优化、鲁棒优化之间的区别和联系,并在离散时间动态优化问题上分析了动态鲁棒优化的性质。基于此分析,我们提出了一种衡量时间域上鲁棒性的方法,并设计了一个基于适应度值估计和预测的动态鲁棒优化求解框架。作为该框架下的一个算法实例,我们使用了多峰粒子群优化算法、径向基函数以及自回归模型技术。为了方便衡量和对比算法之间的性能,我们提出了一系列适用于动态鲁棒优化的测试函数以及评价指标。通过实验,我们验证了提出的算法框架能够有效求解动态鲁棒优化问题。最后,我们将研究对象设定为给定的一个问题集,而将优化目标设定为寻找该问题集上的鲁棒解集。我们将此问题称作多解鲁棒优化,并阐述了其实际意义,说明了其与动态优化、鲁棒优化以及动态鲁棒优化之间的区别和联系。然后,我们给出了多解鲁棒优化的一种形式化定义,并且基于该定义,提出了一种双层次优化算法,将多解鲁棒优化过程分解为寻找备选解以及选择、分配最终解两个层次。接下来我们提出了适用于多解鲁棒优化的一系列测试问题集,在此问题集上,我们通过实验验证了双层次优化算法能够有效求解多解鲁棒优化问题。

论文目录

• 摘要
• ABSTRACT
• 表格
• 插图
• 第一章 绪论
• 1.1 演化计算概述
• 1.1.1 生物学动机
• 1.1.2 设计原则
• 1.2 演化动态优化概述
• 1.2.1 问题概述
• 1.2.2 研究现状和难点
• 1.3 本论文主要研究内容与创新之处
• 1.4 本论文的组织结构
• 第二章 基于种群迁移策略的演化动态优化研究
• 2.1 研究现状
• 2.2 迁移种群生成机制研究
• 2.2.1 研究思路
• 2.2.2 研究的算法
• 2.2.3 动态测试环境
• 2.2.4 实验设计和结果分析
• 2.3 基于自适应替换率种群迁移策略的动态演化算法研究
• 2.3.1 研究思路
• 2.3.2 基于自适应替换率的种群迁移策略
• 2.3.3 实验设计和分析
• 2.4 本章小结
• 第三章 基于适应度值估计和预测的演化动态鲁棒优化研究
• 3.1 传统动态优化的局限性
• 3.2 相关研究工作简介
• 3.2.1 鲁棒优化
• 3.2.2 传统动态优化
• 3.2.3 动态鲁棒优化
• 3.3 离散时间动态优化问题
• 3.3.1 离散时间动态优化问题
• 3.3.2 动态鲁棒优化
• 3.4 基于适应度值估计和预测的种群优化算法
• 3.4.1 求解框架的主要组件
• 3.4.2 时间域上的鲁棒性评估
• 3.4.3 评估器的性能要求
• 3.4.4 一个基于径向基函数模型和自回归模型的算法实例
• 3.5 实验设计和分析
• 3.5.1 适用于动态鲁棒优化的测试问题
• 3.5.2 算法性能评估指标
• 3.5.3 比较的算法
• 3.5.4 参数设置
• 3.5.5 实验结果和分析
• 3.6 本章小结
• 第四章 多解演化鲁棒优化研究
• 4.1 研究对象及研究动机
• 4.2 相关工作简介
• 4.3 问题描述和形式化定义
• 4.3.1 问题描述
• 4.3.2 形式化定义
• 4.4 一种基于双层次优化框架（2-phase）的多解鲁棒优化算法
• 4.4.1 求解多解鲁棒优化的基本思路
• 4.4.2 算法框架的实现实例
• 4.5 实验设计和分析
• 4.5.1 测试函数和评价标准
• 4.5.2 考察的算法
• 4.5.3 参数设置
• 4.5.4 实验结果和分析
• 4.6 本章小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 研究成果
• 5.3 未来展望
• 参考文献
• 致谢
• 攻读博士学位期间发表的学术论文与取得的研究成果