高维多目标进化算法及其软件平台研究

发布时间：2020-10-18 00:58

　　 现实世界中存在大量的多目标优化问题(multi-objective optimization problems,MOPs),它们具有多个需要同时优化且相互冲突的目标。与单目标优化不同,多目标进化算法(multi-objective optimization evolutionary algorithms,MOEAs)需要提供一组Pareto最优解集供决策者挑选,因此算法不仅需要保持收敛性,还要提高解集的分布广泛性与分布均匀性,以更好地刻画优化问题的性质,为决策者提供更多的选择。在现实工程应用中,多目标优化问题往往是非线性、高度复杂的。经典的确定性优化方法通常需要满足一些先决条件才能使用,因此限制了其应用的范围。而基于群体搜索的进化算法没有这样的限制条件,且能在这类问题上取得良好的效果。因此研究用进化算法求解多目标优化问题具有很高的现实意义。Pareto支配关系的引入为多目标优化的研究带来了重大的变革。但此类算法通常只能有效求解2–3个目标的优化问题,而在高维多目标优化问题(目标数超过3个)上的效果往往迅速下降,主要原因是Pareto支配关系的支配区域随着目标空间维数的增长呈指数下降导致的。在这种情况下,种群中非支配个体的比率会迅速上升,导致选择机制无法判断个体之间的好坏,从而导致算法无法收敛。现实世界中存在很多高维多目标优化问题,因此高维多目标优化的研究在国内外受到了越来越多的关注。为了提高算法在高维多目标优化问题上的性能,本文提出了一种基于?支配与边界惩罚选择(boundary punishment selection,BPS)的高维多目标进化算法(many-objective evolutionary algorithm based on?-dominance and BPS,?-BPS)。为了确保收敛性与分布广泛性,BPS依次选取靠近不同边界(坐标轴)的精英个体进入下一代。同时,为了保证分布均匀性,BPS将惩罚每个精英个体的邻居(靠近精英的其它个体),使对这些个体的选择延迟至下一轮(BPS可以执行多轮选择)。其次,采用?支配来惩罚精英个体的邻居,在保持分布性的同时有效去除支配抵抗解(dominance resistant solutions,DRSs)。与6种最具代表性的高维多目标进化算法在3–10目标DTLZ系列测试函数上的对比实验结果验证了?-BPS的竞争力。为了降低算法参数设置的难度,本文提出了一种基于边界淘汰选择(boundary elimination selection,BES)与二分查找的高维多目标进化算法(many-objective evolutionary algorithm based on BES and binary search,BESBS)。与BPS类似,BES依次选取靠近不同边界的精英个体进入下一代,并采用?支配来淘汰精英个体的邻居。然而,与BPS不同的是,BES只进行一轮选择,邻近精英个体的其它个体将被直接淘汰,不再有机会被选入下一代。针对?参数难以确定的问题,利用二分查找方法在实数空间内确定合适的?参数。与6种最具代表性的高维多目标进化算法的对比实验结果表明BESBS具有良好的收敛性与分布性。软件框架的设计是进化多目标优化(evolutionary multi-objective optimization,EMO)研究的重要基础。本文提出一种基于C++和Python混合编程的软件框架。由优化模板库(optimization template library,OTL)、PyOTL和PyOptimization三个工程构成。首先,C++工程OTL实现了所有的优化问题、算子、优化算法和评价指标,采用面向对象技术为不同模块构建了统一的接口。OTL采用了C++模板和泛型编程,不仅增加了系统的灵活性,也提高了代码重用率,保证了运行效率。然而相比C++,Python更适合用于构建实验平台。因此PyOTL用于将OTL中的C++代码转换成Python可调用的模块,并完成单元测试,以确保所有模块的正确性。最后,实验平台PyOptimization负责调用这些Python模块开展科学实验,它提供诸如自动批量实验、完整保存实验数据、分布式计算和数据可视化等功能,为多目标优化的研究提供方便。
【学位单位】：湘潭大学
【学位级别】：博士
【学位年份】：2015
【中图分类】：TP301.6
【文章目录】：
摘要
Abstract
术语表
第一章 绪论
    1.1 进化多目标优化概述
    1.2 进化多目标优化中的经典方法
        1.2.1 多目标优化问题
            1.2.1.1 DTLZ系列测试函数
            1.2.1.2 旅行商问题
        1.2.2 算子
            1.2.2.1 模拟二进制交叉
            1.2.2.2 多项式变异
        1.2.3 多目标进化算法
            1.2.3.1 第二代非支配排序遗传算法
            1.2.3.2 第二代强度Pareto进化算法
        1.2.4 评价指标
            1.2.4.1 世代距离
            1.2.4.2 反向世代距离
            1.2.4.3 超体积
            1.2.4.4 多样性度量
    1.3 高维多目标进化优化概述
    1.4 现有的高维多目标进化算法
        1.4.1 基于Pareto支配关系的算法
        1.4.2 基于聚合的算法
        1.4.3 基于排列的算法
        1.4.4 基于评价指标的算法
        1.4.5 基于密度估计的算法
    1.5 论文的组织结构
第二章 基于?支配与边界惩罚选择的高维多目标进化算法
    2.1 引言
    2.2 算法框架
        2.2.1 边界惩罚选择
        2.2.2 聚合函数
        2.2.3 邻域设置
    2.3 时间复杂度分析
    2.4 对比实验
        2.4.1 统计分析
        2.4.2 实验设置
        2.4.3 实验结果
    2.5 本章小结
第三章 基于边界淘汰选择和二分查找的高维多目标进化算法
    3.1 引言
    3.2 算法框架
        3.2.1 二分查找
        3.2.2 边界淘汰选择
    3.3 时间复杂度分析
    3.4 对比实验
        3.4.1 统计分析
        3.4.2 实验设置
        3.4.3 实验结果
    3.5 本章小结
第四章 多目标优化软件框架
    4.1 引言
    4.2 动机
    4.3 OTL
        4.3.1 OTL的架构
        4.3.2 C++ 模板与泛型编程
    4.4 基于Python的实验平台
        4.4.1 PyOTL
        4.4.2 PyOptimization
    4.5 对比实验
        4.5.1 统计分析
        4.5.2 实验设置
        4.5.3 实验结果
    4.6 本章小结
第五章 总结与展望
参考文献
致谢
附录A

【共引文献】

相关期刊论文 前10条

1 许小健;张金轮;;微进化算法[J];安徽工程科技学院学报(自然科学版);2010年04期

2 ;Multi-swingby optimization of mission to Saturn using global optimization algorithms[J];Acta Mechanica Sinica;2009年06期

3 ;A Preliminary Application of the Differential Evolution Algorithm to Calculate the CNOP[J];Atmospheric and Oceanic Science Letters;2009年06期

4 许小健;干洪;张金轮;;差分进化算法及其在固结系数计算中的应用[J];地下空间与工程学报;2010年05期

5 傅阳光;周成平;胡汉平;;无人飞行器海上航迹规划差分进化算法研究[J];兵工学报;2012年03期

6 彭志红;孙琳;陈杰;;基于改进差分进化算法的无人机在线低空突防航迹规划[J];北京科技大学学报;2012年01期

7 苏国韶;张小飞;符兴义;陈光强;;爆炸荷载作用下岩体振动特性的DE-FLAC~(3D)数值模拟方法[J];北京理工大学学报;2009年06期

8 尚海滨;崔平远;乔栋;;基于微分进化的行星际小推力轨道全局优化方法[J];北京理工大学学报;2010年11期

9 梅跃松;于剑桥;周亮;孟宏志;张伟;;基于微分进化算法的导弹起飞质量优化设计[J];北京理工大学学报;2011年11期

10 彭智;谢玲;;混合优化算法的全局收敛性分析[J];北京理工大学学报;2012年04期

相关博士学位论文 前10条

1 樊建聪;分布估计学习算法研究[D];山东科技大学;2010年

2 徐悦竹;机会发现算法及其应用研究[D];哈尔滨工程大学;2010年

3 吴德烽;计算智能在三维表面扫描机器人系统中的应用研究[D];大连海事大学;2010年

4 王正家;ACA互连的多因素作用分析与性能优化[D];华中科技大学;2010年

5 朱少敏;多媒体数字水印若干关键算法研究[D];中国电力科学研究院;2010年

6 许伟;基于进化算法的复杂化工过程智能建模方法及其应用[D];华东理工大学;2011年

7 杨国鹏;基于机器学习方法的高光谱影像分类研究[D];解放军信息工程大学;2010年

8 张明明;面向量子可逆逻辑自动综合的多目标进化算法研究[D];东华大学;2010年

9 齐峰;人工神经树网络模型的优化研究与应用[D];山东师范大学;2011年

10 董旭初;Bayesian网的最优树分解研究[D];吉林大学;2011年

相关硕士学位论文 前10条

1 龚正;多目标进化算法改进策略的研究[D];湘潭大学;2010年

2 刘子文;改进的粒子群算法在停车场中的应用[D];湘潭大学;2010年

3 范勤勤;基于协进化策略的改进差分进化算法及应用[D];华东理工大学;2011年

4 李飞;改进的AEA算法及其在过程建模中的应用[D];华东理工大学;2011年

5 夏宇庆;人工鱼群与差分进化混合优化算法在水质模拟预测中的应用[D];浙江大学;2011年

6 梁峰;基于BPSO和变邻域差分进化算法的配电网重构[D];东北电力大学;2011年

7 孟显;基于改进差分进化算法的含风电场的电力系统无功优化[D];河北农业大学;2011年

8 高攀;解多目标优化问题的改进差分进化算法研究[D];西安电子科技大学;2010年

9 余永红;代谢过程控制与优化的智能算法研究—参数估计[D];江南大学;2011年

10 赵霞;基于智能优化算法的期权定价模型参数估计[D];江南大学;2011年

本文编号：2845553