复杂优化问题的新型多自主体动态进化算法

摘要

在当今全球经济竞争日趋激烈，资源能源日益紧张，环保与节约意识越发强烈的社会经济环境下，工业制造，农业生产以及国防、交通、金融等众多行业追求高产出、高收益、高效益、低排放、保安全，从而面临着需要解决多峰分布、非凸约束、局部极值环境等更为复杂的优化难题。本文从启发式优化算法求解复杂优化问题存在的局限性出发，首先深入研究了避免寻优代理陷入局部最优的问题，发现了导致该问题的重要隐含因素，并提出雨林算法(RFA);其次为提高雨林算法的可扩展能力，设计了一种新型多自主体，以构建移植性更好、程序实现更容易的动态多样进化算法(DDEA);最后针对不同类型的优化问题，进行基于启发式多层代理进化算法的研究，提出面向实际应用中解决复杂非凸约束优化和奇异非凸约束优化的两类新型多自主体动态进化算法。本文的主要内容与成果如下:
　　(1)以启发式寻优算法在复杂多峰优化问题中的广泛应用为背景，以避免算法过早收敛并陷入局部极值为目标，对群体智能优化算法的运行机理进行了深入分析，发现“虚拟碰撞”现象作为一种隐性过早收敛的表象将直接影响算法的准确性与快速性，进一步探索发现采样过程的无约束性与样本分布信息的缺失是导致“虚拟碰撞”的根本原因。为解决上述问题，提出了针对非凸优化的雨林优化算法(RFA):通过仿照植物生长模式，利用规模可变种群代替规模限定种群进行分区分级寻优采样，来协调历代样本间的分布关系，并制定均匀与非均匀采样原则来权衡优化算法的探索与挖掘。通过六类复杂标称函数的性能测试，并与粒子群算法(PSO)和遗传算法(GA)相比，RFA在多次实验中均能率先捕获全局最优结果，而采样累计分布图像也同时显示RFA对样本疏密控制的张弛有度。这表明该算法能有效减少“虚拟碰撞”的发生，进而在提高寻优效率的同时，获得精准性和稳定性较高的全局最优解。
　　(2)为进一步提高雨林算法的通用能力与可移植性，简化该算法的程序实现方式以拓展其应用，并改善采样分布中探索与挖掘的主要矛盾，本文提出一种新型多自主体，并以此构建结构更为灵活的动态多样进化算法(DDEA)。本文从雨林算法的优良特征中抽象出一种更为灵活的新型代理模式，其中包括新颖的特征属性、多模态的自组织方式、特有的信息动态反馈与共享等，并首次提出用于多自主体分布式管理的三层协议模型(TLPM)，从而成功构建新型的多自主体进化机制。DDEA结合该多自主体系统中多层代理的灵活与自组织特点，不但有利于算法的程序实现，便于程序扩展与移植，而且还进一步实现了探索与探索的快速切换，有效解决了采样分布决策中的主要矛盾。通过六组不同形态标称函数的性能测试，并与目前常用PSO和GA进行速度、准确度对比，结果表明DDEA能够根据适应度高低较为合理地分布不同疏密程度的代理个体，进而更加快速地锁定全局最优区域，并以较少的采样获取相对精度和稳定度较高的最优结果，充分体现了该新型多自主体系统具备突出的自适应能力与进化效率。
　　(3)针对一般进化算法求解复杂非凸约束优化问题所遇到的寻优不确定性与误收敛问题，分别提出了双向动态多样进化算法(BDDEA)和迭代动态多样进化算法(IDDEA)。首先，针对复杂非凸约束优化问题进行了深入分析，发现其全局最优可行解的边界分布特征，往往给一般进化算法带来可行域内部大量采样的耗时，而罚函数的引入不但会引起新的选参难题，而且还会造成目标函数的复杂变化，从而导致寻优不确定性;其次，针对实际工程中难以有效解决的奇异非凸约束优化问题，发现其全局最优点附近的奇异环境，往往会导致一般进化算法在后期挖掘过程中出现误收敛现象;然后，本文结合这两类约束优化问题的不同特点，分别针对复杂约束和奇异约束（近邻局部最优问题）提出双向动态多样进化算法(BDDEA)和迭代动态多样进化算法(IDDEA)。由于BDDEA算法可以在可行域内外分别采用目标适应度与惩罚适应度来双向估计相对占优区域的方位，以此来避免由罚函数带来的选参难、函数畸变的难题，并最大化提高向复杂约束内的最优区域的收敛速度和准确度;IDDEA采用了子区域划分手段，充分利用DDEA的探索优势，将寻优区域逐步缩小，进而相对放大近邻局部最优区域与全局最优区域的对比度，有效避免误收敛现象的发生。为验证所提方法的有效性，开展了多类标称函数的性能测试以及与常用算法的对比，并引用实际工程中三组复杂的结构优化设计难题，对IDDEA进行应用测试并与以往优化算法比较。结果表明，BDDEA在非凸约束边界上，尤其是最优解所在的边界两边，汇聚有更多采样点，从而有效推进了算法对目标分布特征的突显过程，并以最快速度找到全局最优可行解;IDDEA在多个工程优化问题中，成功克服了奇异环境对非凸约束优化的困扰，并最终能够获取更加优越的设计参数，满足高性能设计要求。

目录

声明

摘要

主要符号表

1 绪论

1．1 研究背景与意义

1．2 国内外相关工作研究进展

1．2．1 群体智能优化算法的研究历程

1．2．2 群体智能优化算法存在的问题

1．3 本文主要研究思路

2 虚拟碰撞

2．1 关键域与虚拟碰撞

2．2 虚拟碰撞的不可避免性

2．3 虚拟碰撞的负面影响

2．4 减少虚拟碰撞的策略

2．4．1 在未知区域的均匀采样

2．4．2 根据已知采样信息的非均匀采样

2．5 本章小结

3 基于新型多自主体的雨林算法

3．1 林木的生长进化特点

3．2 采样信息熵

3．2．1 采样价值

3．2．2 信息熵与信息价值

3．3 算法规则与流程

3．3．1 算法规则

3．3．2 算法流程

3．4 实验结果测评

3．4．1 寻优速度对比

3．4．2 寻优准确度对比

3．4．3 算法的泛化能力

3．5 本章小结

4 动态多自主体进化算法

4．1 DDEA的策略分析与新型多自主体

4．1．1 探索与挖掘之间的快速切换

4．1．2 多自主体的动态分区管理

4．2 DDEA的信息处理

4．2．1 绝对占优

4．2．2 相对占优

4．2．3 可信度分析

4．3 DDEA的核心设计

4．3．1 范围划分协议

4．3．2 规模设置协议

4．3．3 生存竞争协议

4．4 DDEA的性能评估

4．4．1 速度测评

4．4．2 精准度测评

4．4．3 泛化能力测评

4．5 本章小结

5 BDDEA与约束优化问题的求解

5．1 双向动态多自主体进化架构

5．1．1 双向信息处理

5．1．2 动态多自主体进化

5．1．3 BDDEA算法流程

5．2 标称问题评估

5．2．1 速度测评

5．2．2 精准度测评

5．2．3 采样分布

5．3 本章小结

6 IDDEA与奇异非凸约束优化问题的求解

6．1 子区域的划分

6．1．1 最优估计与多自体的进化

6．1．2 子区间创建

6．2 子区间引导的多自主体收敛迭代

6．3 下确界惩罚与IDDEA流程

6．4 标称问题测试

6．4．1 Himmelblau问题

6．4．2 弹簧拉伸／压缩权重的最小化问题

6．4．3 压力容器设计问题

6．4．4 焊接梁设计问题

6．5 本章小结

7 结论与展望

7．1 结论

7．2 创新点

7．3 展望

参考文献

攻读博士学位期间科研项目及科研成果

致谢

作者简介