高维优化问题进化求解中增强收敛性的进化算子研究

摘要

在实际的生产与生活过程中常遇到需进行优化的问题，且优化的目标往往不止一个，目标间又互相冲突，这类问题称为多目标优化问题(Multi-obj ective Optimization Problems，MOPs)，当优化目标超过3个时，则称为高维目标优化问题。由于现实生活遇到的问题往往不仅是高维目标，同时也可能是高维决策，因此开展对高维特性下的MOPs研究具重要的意义。进化算法(Evolutionary Algorithms, EA)是处理MOPs的主要算法之一，拥有较强全局搜索能力，但当求解问题扩展至高维时，由于优化难度上升、支配关系丧失等，大部分进化算法已无法确保求解高维优化问题时的收敛性。而进化算子是进化算法的动力来源，以不同程度和速度引导种群进化，影响着种群的收敛性能。针对高维优化问题中进化算子的收敛性能，提出了两个新型进化算子，分别用于增强高维决策空间与高维目标空间下MOPs的收敛性能。两个新型进化算子的具体工作如下: 1.针对高维决策空间下的MOPs，提出了一种基于高维决策空间的收敛增强型进化算子。在新型进化算子中，设计两种策略分别针对高维决策空间中收敛速度较慢与精度不足的问题;在基于可控支配域（Controlling Dominance Area of Solutions，CDAS）排序的收敛速度增强策略中，通过基于CDAS的非支配排序，对种群或邻域进行排序，根据排序结果生成与不同进化时期相匹配的向量差;而在基于高维决策信息挖掘的动态缩放因子策略中，借助主成分分析对高维决策空间进行分析，动态调整差分进化(DifferentialEvolution，DE)缩放因子，最后将策略生成的向量差与缩放因子结合生成变异个体。实验证明提出的收敛增强型进化算子在具有高维决策空间的MOPs中可以有效地增强算法的收敛性能。 2.针对高维目标空间下的MOPs，提出了一种基于高维目标空间收敛性策略的进化算子。在新型进化算子中，综合局部线性嵌入(Locally Linear Embedding，LLE)与差分进化对高维目标空间的收敛性进行提高。借助LLE算法在降维时仍保持局部特征的特性，对高维目标空间进行降维处理以增强选择压力，再利用快速非支配排序进行分层，根据分层信息进行差分进化操作，进而提高种群收敛速度。实验结果表明新型进化算子在保证多样性的同时具有更好的进化选择压力与收敛速度。 3.为检验两种新型进化算子在同时具有高维决策与高维目标下MOPs的求解性能以及实际应用问题中的有效性，设计了在高维情况下多目标0-1背包问题的仿真实验，进一步验证新型进化算子在高维条件下实际应用问题中的求解性能。

目录

声明

摘要

第一章 绪论

1．1问题提出

1．2国内外研究现状

1．3研究内容

1．4本文组织结构

第二章高维优化问题的相关工作基础

2．1基本概念和相关术语

2．1．1多目标优化问题

2．1．2收敛性定义

2．1．3快速非支配排序

2．1．4 CDAS支配域

2．2基于分解的多目标进化算法(MOEA／D)

2．3进化算子

2．3．1模拟二进制进化算子

2．3．2多重父代进化算子

2．3．3基于差分进化的进化算子

2．4测试函数集

2．5本章小结

第三章基于高维决策空间的收敛增强型进化算子

3．1基于CDAS排序的收敛速度增强策略

3．1．1基于CDAS的非支配排序

3．1．2自适应向量差生成策略

3．2基于高维决策信息挖掘的动态缩放因子策略

3．2．1基于主成分的动态缩放因子设计

3．2．2基于种群稳态判定机制的启动策略

3．3进化算子流程及分析

3．4实验设计

3．4．1测试问题及对比算法

3．4．2实验参数设置

3．4．3性能指标

3．5实验结果与分析

3．6本章小结

第四章基于高维目标空间收敛性策略的进化算子

4．1基于高维目标空间的LLE降维策略

4．1．1局部线性嵌入算法

4．1．2基于LLE算法的分层策略

4．1．3策略可行性验证

4．2基于个体收敛差别的差分进化策略

4．2．1种群进化阶段归类策略

4．2．2差分进化策略

4．3进化算子流程及分析

4．4实验设计

4．4．1测试问题及对比算法

4．4．2实验参数设置

4．4．3性能指标

4．5实验结果与分析

4．6本章小结

第五章多目标0-1背包问题求解应用

5．1多目标0-1背包问题

5．2实验设计

5．2．1约束处理

5．2．2决策变量编码

5．2．3实验设置

5．3实验结果与分析

第六章总结与展望

6．1总结

6．2下一步工作与展望

致谢

参考文献

作者简介

附录