基于极值动力学的优化方法及其应用研究

论文摘要

近年来,对NP难的组合优化问题寻求高效的解决方法已成为优化领域的一个极具挑战性的研究课题。除了传统的运筹学方法,现代启发式方法正在得到越来越多的研究人员的关注和重视,已经广泛地应用于基础研究和实际工程领域。现有的大多数启发式方法,如进化算法、人工生命、模拟退火算法和禁忌算法等,都是从生物进化、统计物理和人工智能等领域发展而来。极值动力学优化算法（Extremal Optimization,EO）是近年来出现的一种新颖的、通用的、基于局部搜索的启发式方法,该方法是从统计物理学发展而来。众所周知,模拟退火算法（Simulated An-nealing,SA）是模拟系统处于平衡态的一种优化方法,与SA不同的是,EO算法的理论基础建筑在Bak-Sneppen生物进化模型之上,该模型模拟处于远离平衡态的系统,具备自组织临界性（Self-Organized Criti-cality,SOC）。SOC是指不管系统处于何种初始状态,不需要调整任何参数,整个系统就可以演化到一个自组织临界状态,在该状态下,系统呈现出幂律分布（Power-law）。遗传算法通过对交配池中的所有可能解实施选择、杂交和变异等遗传操作来达到寻优的目的,而EO算法总是不断地变异近似解的最差组成部分（即所谓的极值动力学机制）来达到寻优的目的。正是这种内在的极值动力学机制,使得EO具备很强的爬山能力,尤其在求解带有相变点（Phase transitions）的组合优化问题时EO更是展现出强大的优势。EO算法的特点是收敛速度快,局部搜索能力强,只有变异算子,无可调参数（对于基本EO算法）或只有一个可调参数τ（对于τ-EO算法）。目前EO算法已经被成功地应用于求解一些NP难的组合优化问题,如二分图,旅行商问题,图着色,旋转玻璃和动态组合优化问题。但是,国外对于EO算法在数值优化和多目标优化问题方面的研究并不多,国内学者对EO算法的研究更少之甚少。本文主要研究求解无约束或带约束数值优化问题的EO算法,并将求解单目标优化问题的EO算法扩展到多目标优化领域。本文的主要工作包括:（1）本文从分析EO算法的机理入手,提出了一种求解约束连续优化问题的新算法――带自适应Le′vy变异的基于种群的EO算法（PEO）,通过求解6个经典的约束连续优化问题,实验结果证实了PEO能与3种流行的优化算法相匹敌,不失为一种求解数值约束优化问题的有效方法。（2）为了弥补标准粒子群算法容易陷入局部极值点的不足,本文提出了一种新颖的混合粒子群-极值动力学优化算法（PSO-EO）,该算法有效地结合了PSO的全局搜索能力和EO的局部搜索能力,使得标准PSO算法可以跳出局部极值点,从而弥补了标准PSO算法的不足。迄今为止,还没有文献提出将EO和PSO结合起来的优化算法。通过求解6个经典的复杂单峰/多峰函数,PSO-EO算法被证实了具有避免早熟收敛的特点,是一种求解复杂数值优化问题的有效算法。（3）由于EO算法只有变异操作,因此,变异算子对EO算法的性能好坏起到了重要作用。本文将高斯变异和柯西变异有效地结合起来,提出了一种新颖的适合于求解数值优化问题的变异算子――混合高斯-柯西变异,该算子将“粗调”和“微调”很好地结合起来,并且省去了决定何时在不同变异之间进行切换的麻烦。（4）本文将基于Pareto支配概念的适应度评价方法引入到EO,提出了一种新颖的多目标极值动力学优化方法（Multiobjective Extremal Op-timization,MOEO）,使EO算法成功地扩展到多目标优化领域。接着,用MOEO算法解决了多目标连续优化问题（包括无约束问题和带约束问题）,实验结果表明MOEO非常适合于求解多目标连续优化问题,能够与3种经典的多目标进化算法（即NSGA-II,SPEA2和PAES）相匹敌。最后,提出了一种适合于求解多目标0/1背包问题的MOEO算法。实验结果表明MOEO算法具有快速的收敛能力和良好的多样化性能,具有与3种经典的多目标进化算法（即NSGA,SPEA和NPGA）相竞争的优势。（5）本文利用MOEO算法解决了4个经典的机械组件设计问题。实验结果表明:MOEO算法找到的非劣解集在收敛性和多样性方面有着良好的性能,能够与3种经典的多目标进化算法（NSGA-II,SPEA2和PAES）相匹敌。因此,MOEO算法是一个能解决实际工程优化问题的行之有效的方法。（6）本文将MOEO算法应用于求解5个经典的股票投资组合优化问题。实验结果表明:MOEO找到的近似Pareto前沿具有良好的收敛性能和多样化性能,能够与算法NSGA-II和SPEA2相匹敌,比PAES更优。因此,MOEO算法是一个能解决实际管理决策优化问题的有效方法。

论文目录

• 摘要
• ABSTRACT（英文摘要）
• 第一章 绪论
• 1.1 极值动力学优化算法的研究现状
• 1.2 多目标优化方法概述及其研究现状
• 1.2.1 多目标优化的基本概念
• 1.2.2 传统的多目标优化方法及其局限性
• 1.2.3 多目标进化算法的研究现状
• 1.3 极值动力学优化算法在多目标优化中的研究现状及存在问题
• 1.4 本文主要研究内容
• 第二章 极值动力学优化算法
• 2.1 自组织临界性
• 2.2 Bak-Sneppen生物演化模型
• 2.3 从自组织临界性到自组织优化算法的构造
• 2.4 极值动力学优化算法的机理
• 2.5 带自适应L′evy变异的基于种群的极值动力学优化算法（PEO）
• 2.5.1 约束连续优化问题建模
• 2.5.2 基于种群的极值动力学优化算法
• 2.5.3 自适应L′evy变异算子
• 2.5.4 实验仿真和结果
• 2.5.4.1 测试函数
• 2.5.4.2 参数设置
• 2.5.4.3 实验仿真和结果分析
• 2.5.5 带自适应L′evy变异的PEO算法的特色
• 2.5.6 实验结论
• 2.6 本章小结
• 第三章 混合的粒子群――极值动力学优化算法
• 3.1 粒子群优化算法（PSO）
• 3.1.1 PSO算法的思想
• 3.1.2 PSO算法的研究热点
• 3.1.3 PSO算法的应用及发展前景
• 3.2 混合粒子群-极值动力学优化算法（PSO-EO）
• 3.2.1 混合PSO-EO算法的思想
• 3.2.2 混合PSO-EO算法的流程
• 3.2.3 混合高斯-柯西变异算子
• 3.2.4 实验仿真和结果
• 3.2.4.1 测试函数
• 3.2.4.2 参数设置
• 3.2.4.3 实验仿真和结果分析
• 3.2.5 实验结论
• 3.3 本章小结
• 第四章 基于极值动力学的多目标优化方法
• 4.1 多目标进化算法及其策略分析
• 4.1.1 多目标进化算法概述
• 4.1.2 典型多目标进化算法的策略分析
• 4.1.2.1 适应度评价方法
• 4.1.2.2 种群多样性保持机制
• 4.1.2.3 选择算子
• 4.1.2.4 精英策略
• 4.2 求解多目标连续优化问题的多目标极值动力学优化算法（MOEO）
• 4.2.1 算法流程
• 4.2.2 适应度评价
• 4.2.3 多样性保持机制
• 4.2.4 外部存档
• 4.2.5 约束处理方法
• 4.2.6 计算效率分析
• 4.2.7 MOEO算法求解无约束多目标优化问题
• 4.2.7.1 测试函数
• 4.2.7.2 性能指标
• 4.2.7.3 参数设置
• 4.2.7.4 实验仿真和结果分析
• 4.2.7.5 MOEO算法的特色
• 4.2.7.6 实验结论
• 4.2.8 MOEO算法求解带约束多目标优化问题
• 4.2.8.1 测试函数
• 4.2.8.2 性能指标
• 4.2.8.3 参数设置
• 4.2.8.4 实验仿真和结果分析
• 4.2.8.5 实验结论
• 4.3 求解多目标0
• 4.3.1 多目标0
• 4.3.2 算法流程
• 4.3.3 测试实例
• 4.3.4 参数设置
• 4.3.5 实验仿真和结果分析
• 4.3.6 实验结论
• 4.4 本章小结
• 第五章 多目标极值动力学优化算法在工程优化和管理决策中的应用
• 5.1 用多目标极值动力学优化算法求解多目标机械组件设计问题
• 5.1.1 多目标机械组件设计问题
• 5.1.2 设计实例
• 5.1.3 参数设置
• 5.1.4 实验仿真和结果分析
• 5.1.5 实验结论
• 5.2 用多目标极值动力学优化算法求解投资组合优化问题
• 5.2.1 Markowitz的均值－方差投资组合模型
• 5.2.2 投资组合的多目标优化模型
• 5.2.3 算法流程
• 5.2.4 测试实例
• 5.2.5 参数设置
• 5.2.6 实验仿真和结果分析
• 5.2.7 实验结论
• 5.3 本章小结
• 第六章 结束语
• 6.1 总结
• 6.2 本文主要的研究成果与创新点
• 6.3 研究展望
• 参考文献
• 致谢
• 攻读博士学位期间发表、录用或完成的学术论文