基于聚类的多目标进化算法重组算子研究

发布时间：2020-09-27 07:37

　　 实际工程中存在着大量的具有多约束、多变量以及高度非线性等性质的复杂多目标优化问题。由于传统的确定性优化技术不能较好地求解这一类问题,因此基于自然启发搜索的进化算法成为了解决此类问题的主流方法。由于多目标进化算法单次运行就可获得多目标优化问题Pareto解集的逼近解集,因此近年来得到了蓬勃发展。多目标进化算法有两个重要算子:个体重组算子和环境选择算子。重组算子的作用是产生新个体,而环境选择算子的作用则是挑选优良个体进入下一代。当前,大量的研究工作集中于环境选择算子,而对个体重组算子投入的关注较少,大部分的多目标进化算法直接应用单目标进化算法中的重组算子。实际上,由于m个目标的连续多目标优化问题的Pareto解集是一个m-1维的分段连续的流型,因此,在多目标进化算法重组的过程中,如果充分地将这一规则特性用于引导搜索,理应获得更高的搜索效率。近年来,机器学习和进化计算技术的同步快速发展让学者们更积极地思考二者的相互促进。由于进化算法是基于数据的科学,因此本文提出将典型的数据挖掘方法-聚类算法应用到多目标进化算法中,用以发掘多目标优化问题的Pareto解集的结构,并利用此结构设计特定的重组算子,引导算法的搜索。本文的研究工作总结概括如下:传统的单目标进化算法重组算子直接以整个种群作为交配池随机地挑选父个体产生新解,在多目标进化算法进化后期,这些算子产生的新解容易偏离Pareto解集的流型。为了解决此问题,设计了一种自适应交配限制策略AMRS,进而提出了一种基于近邻传播的多目标进化算法APMO。AMRS使用了一种近邻传播聚类方法AP发掘种群的分布结构,基于此结构,以一定的交配限制概率利用邻居个体或相互差异较大的个体构建交配池用于重组。为了适应进化过程中勘探和开采的平衡的变化,在每一代,根据两类交配池在过去一定代数的重组效用对交配限制概率进行更新。对比实验表明APMO具有优秀的求解性能。实验分析指出AMRS的设计科学合理,并且AMRS具有良好的适应性。巡航导弹航迹规划结果表明AMRS能够提高多目标进化算法解决复杂工程多目标优化问题的能力,并且基于多目标进化算法开展航迹规划合理而且必要。多目标进化算法的基于高斯模型抽样的重组算子中,通常存在所求解问题的特性考虑不够,建模时异常解处理不合理而且计算复杂度高,产生的新解多样性不足等问题。为了解决这些问题,设计了一种基于聚类的混合高斯模型抽样策略CASS,将CASS算子与差分进化算子相结合,进而提出了一种自适应增量多目标进化算法AMEA。AMEA在每一代首先运用K-means聚类算法发掘种群的结构。基于此结构,差分进化算子挑选相互差异较大的解作为父个体产生新解,CASS算子使用协方差矩阵共享策略每个解构建一个高斯模型共同逼近种群结构并抽样产生新解。为了适应进化过程中勘探和开采平衡的变化,基于两种算子先前产生新解的效用,设计了一种强度Pareto的方法自适应地控制两种算子的贡献。为了降低聚类引起的计算开销,AMEA中还引入了一种重用机制降低执行聚类过程的次数。实验分析表明AMEA对于具有多种特性的标准测试题以及实际的巡航导弹航迹规划问题求解性能优异,设计的CASS抽样策略、新解产生算子混合与自适应控制机制、种群结构重用机制均合理有效。APMO和AMEA在进化过程中需要完成多次多重迭代的聚类过程,为了进一步降低聚类带来的计算开销,通过将聚类的迭代过程与进化算法的进化过程融合,提出了一种设计聚类-进化融合的重组算子的思路。首先基于K-means聚类算法的融合实验证明了这种思路可行有效。之后利用自组织映射聚类算法SOM进行融合,开发了一种自组织多目标进化算法SMEA。在SMEA中,交替执行进化操作和SOM聚类算法的训练操作。每一代,仅利用新近保留的有效解训练SOM模型,并且SMEA仅访问每个训练解一次,然后利用当前为止发掘的结构引导个体从邻居或整个种群中挑选父个体产生新解。由于完成进化算法的进化过程仅需要实现一个多重迭代的聚类过程,因此能极大地降低聚类操作带来的计算开销。实验分析显示,SMEA能以较小的聚类计算开销对于多种不同特性的标准测试问题以及实际的复杂巡航导弹航迹规划问题均达到良好的求解效果。当前存在的基于数据挖掘方法的多目标进化算法中,其所采用的数据挖掘方法一般要求用于学习的数据满足独立同分布假设。由于进化算法产生的是非平稳数据,其并不满足这一假设。为了充分考虑进化过程的数据的特点,率先设计了一种基于对非平稳数据学习的在线凝聚聚类Add C的重组算子,进而提出了一种增量进化算法OCEA。在OCEA中,Add C的迭代过程与多目标进化算法的进化过程融合在一起。每当一个新解被保留,则算法开展一次在线聚类,更新发掘的Pareto解集的结构,基于发掘的结构,以一定的概率引导邻居个体或相互差异较大的个体重组产生新解,从而维持勘探和开采之间的平衡。由于OCEA仅对被保留下来的有效解访问一次进行聚类,因此其需要较小的聚类开销。实验分析表明OCEA不仅具有良好的求解能力还具有优秀的聚类能力,基于在线聚类的重组算子适应不同的环境选择算子。巡航导弹航迹规划结果显示OCEA对于此类复杂的工程多目标优化问题求解效果同样突出。
【学位单位】：哈尔滨工业大学
【学位级别】：博士
【学位年份】：2016
【中图分类】：TP18
【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 课题背景及研究的目的和意义
        1.1.1 课题背景
        1.1.2 课题研究的目的和意义
    1.2 多目标进化算法研究现状
        1.2.1 多目标优化问题
        1.2.2 多目标进化算法研究现状
    1.3 基于聚类的多目标进化算法研究现状
        1.3.1 聚类算法
        1.3.2 基于聚类的多目标进化算法研究现状
    1.4 结构化多目标进化算法分析
        1.4.1 元胞多目标遗传算法
        1.4.2 基于分解的多目标进化算法
        1.4.3 基于规则模型的多目标分布估计算法
    1.5 本文的主要研究内容
第2章 多目标进化算法及巡航导弹航迹规划模型
    2.1 引言
    2.2 进化计算与进化算法
    2.3 典型的多目标进化算法
        2.3.1 快速非支配排序遗传算法
        2.3.2 改进的强度Pareto进化算法
        2.3.3 S测度选择进化多目标优化算法
        2.3.4 带有差分进化算子的基于分解的多目标进化算法
        2.3.5 带有目标变换的基于分解的多目标进化算法
        2.3.6 基于规则模型的多目标分布估计算法
        2.3.7 混合元胞多目标遗传算法
        2.3.8 基于自组织映射的混合多目标进化算法
    2.4 多目标进化算法标准测试集
        2.4.1 GLT标准测试集
        2.4.2 WFG标准测试集
    2.5 多目标进化算法测度方法
    2.6 巡航导弹航迹规划模型
        2.6.1 地形和威胁表示
        2.6.2 优化目标
        2.6.3 约束条件
        2.6.4 优化变量
    2.7 本章小结
第3章 基于聚类的自适应交配限制策略
    3.1 引言
    3.2 传统单目标重组算子的不足
    3.3 基于近邻传播的自适应多目标进化算法
        3.3.1 算法框架
        3.3.2 基于近邻传播和重组效用的自适应交配限制策略
        3.3.3 新解产生
        3.3.4 环境选择
    3.4 实验研究
        3.4.1 测试实例与性能指标
        3.4.2 实验设置
        3.4.3 对比研究
    3.5 进一步讨论
        3.5.1 AMRS组件分析
        3.5.2 差分进化算子参数灵敏度分析
        3.5.3 基于超体积环境选择的APMO
        3.5.4 基于APMO-HV算法的巡航导弹航迹规划
    3.6 本章小结
第4章 基于聚类的混合高斯模型抽样策略
    4.1 引言
    4.2 相关背景
        4.2.1 多目标分布估计算法
        4.2.2 多目标分布估计算法中的高斯模型抽样
    4.3 基于聚类的自适应增量多目标进化算法
        4.3.1 算法框架
        4.3.2 K-means聚类算法
        4.3.3 新解产生
        4.3.4 环境选择
        4.3.5 重用机制
        4.3.6 重组算子的贡献控制
    4.4 实验研究
        4.4.1 测试实例与性能指标
        4.4.2 实验设置
        4.4.3 对比研究
    4.5 进一步讨论
        4.5.1 WFG测试集求解性能
        4.5.2 提出的抽样策略的有效性
        4.5.3 混合策略的有效性
        4.5.4 自适应策略分析
        4.5.5 重用机制的有效性
        4.5.6 参数灵敏度分析
        4.5.7 基于AMEA算法的巡航导弹航迹规划
    4.6 本章小结
第5章 基于聚类-进化过程融合的重组算子
    5.1 引言
    5.2 前期工作
    5.3 自组织映射及其在多目标进化算法中的应用
        5.3.1 自组织映射
        5.3.2 基于自组织映射的多目标进化算法
    5.4 自组织多目标进化算法
        5.4.1 算法框架
        5.4.2 新解产生
        5.4.3 环境选择
    5.5 实验研究
        5.5.1 测试实例与性能指标
        5.5.2 实验设置
        5.5.3 对比研究
    5.6 进一步讨论
        5.6.1 WFG测试集求解性能
        5.6.2 参数灵敏度分析
        5.6.3 基于SMEA算法的巡航导弹航迹规划
    5.7 本章小结
第6章 基于在线凝聚聚类的重组算子
    6.1 引言
    6.2 在线凝聚聚类
    6.3 基于在线聚类的进化算法
        6.3.1 算法框架
        6.3.2 新解产生
        6.3.3 环境选择和在线凝聚聚类
    6.4 实验研究
        6.4.1 测试实例与性能指标
        6.4.2 实验设置
        6.4.3 对比研究
    6.5 进一步讨论
        6.5.1 WFG测试集求解性能
        6.5.2 算法性能横向比较
        6.5.3 参数灵敏度分析
        6.5.4 聚类效果分析
        6.5.5 基于OCEA算法的巡航导弹航迹规划
        6.5.6 基于在线凝聚聚类的世代多目标进化算法
    6.6 本章小结
结论
参考文献
攻读博士学位期间发表的论文及其他成果
致谢
个人简历


本文编号：2827602