基于多方法融合的进化算法研究

论文摘要

作为一类新兴的计算理论与方法,进化算法（EvolutionaryAlgorithm（EA））已在许多工程与科研应用领域展现出优越的性能。相比于传统优化算法,EA只需要极少的参数设定以及少量的问题先验知识便可以实施寻优;对于工程优化问题中所存在的多个约束条件,EA无需进行复杂的归一化处理。此外,EA在多峰优化问题和多变量相关联的优化问题上也展现出了明显的性能优势。近二十年来,EA的研究已经取得了许多重要进展,但是,当应用于一些复杂的工程应用问题时,此前的EA算法版本仍然存在许多问题有待研究解决。其中,以下三个方面的不足最为业内关注:（1）EA的普适性仍然有待提高;（2）EA的延展性不足,其性能随着优化问题规模的增大（变量个数增多）而迅速降低;（3）EA在工程优化问题上的应用并不广泛。针对前两方面的不足,本文通过引入多方法融合的思想,提出更具鲁棒性的EA算法框架,以提升EA的延展性和普适性。同时,本文将所提出的算法应用于解决多项工程应用问题,取得了较好的成果。在算法设计方面,本文主要围绕着多方法融合（multi-method ensemble）思想展开研究。所取得的成果可以分为三个方面:1.针对此前各种分布估计算法（EDA）版本延展性不强的问题,本文通过引入多方法融合思想,设计一种自适应混合采样操作,并提出一种面向大规模优化应用的EDA -基于自适应混合分布采样的EDA（MUEDA）。MUEDA相对于传统EDA与经典的大规模优化EA的性能优势通过30 -1500维的函数优化实验得到全面验证。2.针对此前各种粒子群优化算法（PSO）版本普适性较差的问题,本文设计了一种自适应学习的算法框架,将多个PSO新解生成策略并列执行,提出自适应学习PSO（SLPSO）。SLPSO可以根据不同优化问题的特性,甚至是同一优化问题在不同优化阶段对优化算法要求的不同,将较多的计算资源分配给当前表现最好的策略。在这样的情况下,SLPSO的普适性得到了显著地提高。这一自适应方法的效果得到了函数优化实验和电力系统负载调配优化（ELD）实验结果的有力支持。3.在之前的研究中,以多方法融合为指导思想的EA均采用并列执行的框架。此类算法的普适性基本由框架对优化反馈的学习能力所决定。因此,并列框架在病态优化问题、带欺骗性优化问题以及极度多峰优化问题上表现仍然无法令人满意。为了改变这一现状,本文提出了基于两层串列结构的多方法融合框架（TSEA）。该框架的主体思想是根据具体问题的特性,将优化过程自适应地划分为相对独立的两个阶段:全局收敛阶段和深度搜索阶段。该算法框架的有效性在对多个复杂优化问题实施求解的过程中得到了充分验证。以两阶段串列结构的多方法融合算法框架为基础,本文设计了可应用于一般单目标优化、大规模单目标优化、多目标优化以及动态多目标优化问题求解的一系列具体算法实例。这些算法的性能除了在各类复杂函数优化问题上得到验证外,还在实际工程优化应用问题上展现出显著超越此前优化算法的性能表现。这些应用问题包括:1.大规模优化问题（变量个数在102数量级以上）:MUEDA和TSEA在该类问题上取得了较大的突破。这主要表现为:在常规的问题上,本文算法的效率取得了与变量个数增加呈近似线性关系的降低趋势;在较难的问题上,对比于多种新近提出的面向大规模优化算法,我们的算法无论在搜索效率和有效性方面都表现出较大的优势。在2008年和2010年IEEE计算智能大会（WCCI）所组织的大规模优化竞赛中,MUEDA和TSEA均取得综合排名第二的好成绩。2.大规模电力系统负载调配（ELD）:ELD问题是电力系统中非常重要但仍难以有效解决的优化问题。此前算法的性能随着ELD问题规模的增大衰减很快。为了改解决这一问题,本文基于TSEA算法框架、利用EDA和差分进化（DE）算法设计了一个自适应大规模ELD优化算法。对比此前最好的ELD优化算法,ED-DE以较小的代价搜索到更好的负载调配方案。特别地,ED-DE在所有已知的经典ELD问题上均刷新了最优解的记录。此外,本文也将SLPSO算法应用于大规模ELD问题求解,也取得了很好的效果3.数字IIR滤波器设计:数字IIR滤波器在数字信号处理领域有重要的作用。进化算法是求解该问题的主要算法之一。此前基于进化算法的求解方案存在两方面不足:（1）求解问题的规模（滤波器的阶数）有限;（2）取得的滤波器设计方案一般是以浮点数表示。此前算法在实际应用时会遇到两方面困难:求解问题规模的增加对算法的延展性提出了更高的要求;定点数的使用会造成求解空间的退化以及搜索信息的缺失,从而提升了对算法鲁棒性的要求。本文基于串列多方法融合框架思想,设计了新的两阶段Memetic算法（MA）TSMA,在数字IIR滤波器设计优化上取得了很好的效果。在高阶定点数数字IIR滤波器设计问题上,此前最为有效的优化算法均已失效,而TSMA仍能够获得可靠的性能表现。此外,串列多方法融合框架思想还被用于新兴的动态多目标优化问题的求解,也取得了很好的性能表现。综合本文的研究成果,基于两层串列结构的多方法融合框架在增强算法效率、有效性、鲁棒性以及普适性等各方面都表现出强大的生命力,适用于大规模复杂优化问题的求解。

论文目录

• 摘要
• ABSTRACT
• 表格
• 插图
• 主要符号对照表
• 第1章 绪论
• 1.1 优化问题简介
• 1.1.1 单目标优化问题
• 1.1.2 多目标优化问题
• 1.1.3 动态优化问题
• 1.2 优化技术概述
• 1.3 进化算法
• 1.3.1 进化算法的分类
• 1.3.2 EA 的优势分析
• 1.4 面向数值优化的EA 研究现状
• 1.4.1 特效算子的设计
• 1.4.2 多方法融合
• 1.5 本论文的主要研究内容及创新之处
• 1.6 本文组织安排
• 1.7 本章小结
• 第2章 基于自适应混合分布的单变量分布估计算法
• 2.1 引言
• 2.2 基于空间分布估计算法
• 2.3 重尾分布
• 2.3.1 重尾分布的定义
• 2.3.2 理论探讨
• 2.4 适应度形态分析
• 2.4.1 单峰问题
• 2.4.2 多峰问题
• 2.5 MUEDA 算法
• 2.6 实验验证
• 2.6.1 低维问题实验
• 2.6.2 高维问题实验
• 2.6.3 扩展分析实验
• 2.7 本章小结
• 第3章 自适应学习粒子群优化算法（SLPSO）
• 3.1 引言
• 3.2 粒子群优化算法回顾
• 3.2.1 如何调整参数设置？
• 3.2.2 如何增强PSO 的搜索广度？
• 3.2.3 如何利用外部技术辅助PSO 搜索？
• 3.3 基于自适应学习的粒子群优化算法
• 3.3.1 基于差异的速度更新机制（DbV）
• 3.3.2 基于分布估计的速度更新机制（EbV）
• 3.3.3 CLPSO 和修正CLPSO（PSO-CL-pbest）
• 3.3.4 基于自适应学习的粒子群优化算法流程
• 3.3.5 搜索区间分析
• 3.4 函数优化实验
• 3.4.1 函数优化问题
• 3.4.2 实验结果
• 3.4.3 讨论分析
• 3.4.4 全局表现评估
• 3.5 自适应学习行为分析
• 3.6 电力系统经济负载调配优化
• 3.7 本章小结
• 第4章 基于多进化算法的多方法融合思想验证
• 4.1 多方法融合思想应用的必要性讨论
• 4.2 进化算法表现多样性实验证明
• 4.2.1 不带旋转的简单单峰优化问题
• 4.2.2 不带旋转的简单多峰优化问题
• 4.2.3 不带旋转的较难单峰问题
• 4.2.4 不带旋转的较难多峰问题
• 4.2.5 旋转问题
• 4.2.6 整体对比
• 4.3 本章小结
• 第5章 基于两阶段串列结构的多方法融合算法
• 5.1 引言
• 5.2 TSEA 流程
• 5.3 TSEA 一般函数优化实验
• 5.3.1 TSEA 与其子优化器的对比
• 5.3.2 TSEA 与当前最为有效的EA 的对比
• 5.3.3 当前最为有效的MA 的对比
• 5.4 TSEA 大规模函数优化实验
• 5.5 基于两阶段串列结构的MA
• 5.5.1 实验验证高效EA 寻优算子作为局部搜索的假设
• 5.5.2 基于两阶段串列结构的MA 算法流程
• 5.6 TSMA 实验验证
• 5.6.1 TSMA 与其子优化器的对比
• 5.6.2 TSMA 与当前最为有效的DE 和PSO 的对比
• 5.6.3 当前最为有效的MA 的对比
• 5.6.4 MUEDA、SLPSO、TSEA 与TSMA 的实验对比
• 5.7 本章小结
• 第6章 多方法融合算法在电力系统负载调配中的应用
• 6.1 引言
• 6.2 ELD 优化问题数学定义
• 6.3 ELD 问题的适应度形态分析
• 6.3.1 EA 相关的ELD 优化回顾
• 6.3.2 分布估计与差分进化合成算法
• 6.3.3 ED-DE 时间复杂度分析
• 6.4 ED-DE 的ELD 优化实验验证
• 6.4.1 非光滑13 发电机组问题
• 6.4.2 非光滑40 发电机组问题
• 6.4.3 非光滑多燃料10 发电机组问题
• 6.4.4 非光滑多燃料拓展问题
• 6.4.5 函数优化验证
• 6.5 本章小结
• 第7章 基于两阶段串列结构的多方法融合算法在数字IIR 滤波器设计中的应用
• 7.1 EA 相关的数字IIR 滤波器设计回顾
• 7.1.1 数字IIR 滤波器设计的数学定义
• 7.1.2 数字IIR 滤波器设计的适应度形态分析
• 7.2 局部搜索增强型多目标进化算法
• 7.3 LS-MOEA 应用于多目标数字IIR 滤波器设计实验
• 7.3.1 LS-MOEA 与经典滤波器设计方法的对比
• 7.3.2 LS-MOEA 与基于单目标EA 设计方法的对比
• 7.3.3 LS-MOEA 与基于NSGA-II 设计方法的对比
• 7.4 TSMA 应用于数字IIR 滤波器设计讨论
• 7.5 TSMA 应用于高阶数字IIR 滤波器设计实验
• 7.5.1 第一组数字IIR 滤波器设计实验
• 7.5.2 拓展数字IIR 滤波器设计实验
• 7.6 本章小结
• 第8章 多方法融合思想在动态多目标优化的应用
• 8.1 引言
• 8.1.1 动态单目标优化
• 8.1.2 静态多目标优化
• 8.1.3 动态多目标优化
• 8.2 技术路线探讨
• 8.2.1 如何设计强鲁棒性的重初始化策略？
• 8.2.2 如何在不失多样性的前提下增强搜索效率？
• 8.3 基于多策略融合的动态多目标优化进化算法（MS-MOEA）
• 8.4 MS-MOEA 在静态多目标优化问题上的实验
• 8.5 MS-MOEA 在DMO 问题上的实验
• 8.5.1 测试问题
• 8.5.2 评估标准
• 8.5.3 在FDA 测试集上的实验对比结果
• 8.5.4 在DMZDT 测试集和WYL 问题上的实验对比结果
• 8.5.5 实验结果总体评价
• 8.6 本章小节
• 第9章 总结与展望
• 9.1 全文总结
• 9.2 未来研究展望
• 参考文献
• 致谢
• 读研期间发表的学术论文与取得的研究成果
• 已发表期刊论文
• 已发表会议论文
• 读研期间所参与的实验室研究项目
• 读研期间作为项目负责人主持完成的研究项目
• 读研期间获得的主要奖项