论文部分内容阅读
在科学研究中经常遇到多目标优化问题(Multi-Objective Optimization Problems,MOPs)。一个多目标优化问题通常包含多个相互冲突的子目标,要找到满足所有目标的设计方案,就要解决多目标与多约束之间的冲突。多目标优化问题应用范围广泛,涉及工程优化与设计、运筹学、生物医学、数据挖掘等诸多领域。因此,本文重点研究一类决策空间数据维度高、且决策空间解集分布呈非线性的多目标优化问题,即高维多目标优化问题(High-Dimensional Multi-Objective Optimization Problems)。传统的演化多目标优化算法和模型多目标优化是求解多目标优化问题的两种有效方法,但各有其优缺点：(1)对于某一类连续多目标优化问题,其Pareto解集在决策空间的分布是一个分段连续的(m-1)维“流形”(其中m是目标个数),传统演化多目标优化算法没有利用上述Pareto解集在决策空间的分布具有“流形”结构这一特性。另一方面,在传统演化多目标优化算法中,当种群接近收敛时,盲目交叉、变异操作会使本已近似收敛的种群偏离实际的Pareto解集(Pareto Set, PS),给算法性能造成不良影响；(2)鉴于传统演化多目标优化算法的不足,学者们提出了模型多目标优化,通过统计学习的方法建立问题决策空间分布模型,然后对该模型随机采样繁殖新的子代个体,如此反复,进而实现种群收敛,但是模型多目标优化算法也有不足：算法建模采用的是线性方法,如Local PC A、 PCA等,对于高维的非线性数据,线性方法建模过程复杂且模型不准确。“流形学习”算法能挖掘高维非线性数据集中蕴含的整体几何和拓扑规律,这种规律本质上不依赖于数据集的实际观测维数,也就是说：“流形学习”算法能发现嵌入在高维数据空间的低维光滑“流形”结构。因此,本文将“流形学习”算法引入到高维多目标优化算法中,提出一种名为“流形学习多目标优化算法”的新型多目标优化算法,以克服传统演化多目标优化算法和模型多目标优化算法的不足,利用“流形学习”算法降低高维多目标优化问题决策空间的数据维度,挖掘决策空间中内蕴的“流形”结构,建立准确的决策空间模型,指导算法演化,加速收敛。全文主要工作分为五个方面：(1)针对传统演化多目标优化算法和模型多目标优化算法的缺点,提出一种能直接通过“流形学习”算法挖掘高维多目标问题决策空间非线性模型的新型优化算法——流形学习多目标优化算法,提出一种通用的基于流形学习的多目标优化算法框架,方便相关后续研究。(2)为合理的评测算法性能,全面分析常用多目标测试函数决策空间及目标空间的几何分布形状,针对性选择高维多目标测试函数,选定算法性能评价指标,用于算法评测。(3)提出两大类流形学习多目标优化算法：基于自组织映射网络的多目标优化算法和基于局部线性嵌入的多目标优化算法。①分析自组织映射网络(Self-Organizing Maps,SOM)算法特性,针对基于规则模型的多目标分布估计算法(A Regularity Model-based Mul tiobjective Estimation of Distribution Algorithm, RM-MEDA)采用Local PCA聚类建立局部线性模型的不足,提出基于自组织映射的流形学习多目标优化算法(Multi-Objective Evol utionary Algorithm via Self-Organizing Maps,SOM-MOEA), SOM-MOEA先利用SOM神经元向种群流形学习,然后采用随机噪音向量“扩展”SOM神经元的策略来繁殖下一代个体,从而建立问题决策空间的“流形”结构,指导算法演化。②在SOM-MOEA和RM-MEDA算法中,分别采用了随机噪音向量扩展SOM神经元和聚类主成分的策略来繁殖种群个体,这种“扩展”过程具有盲目性,会破坏已经建立好的种群模型,针对上述SOM-MOEA和RM-MEDA算法不足,提出一种基于局部线性嵌入的流形学习多目标优化算法(Multi-Objective Evolutionary Algorithm via Locally Linear Embedding,LLE-MOEA),对比SOM-MOEA和RM-MEDA, LLE-MOEA最大的改进在于：LLE-MOEA能在不使用“扩展”策略的前提下,利用局部线性嵌入算法直接挖掘优化问题决策空间中内蕴的“流形”,由此“流形”上的数据点集直接繁殖下一代种群个体,无需“扩展”,从而建立问题决策空间的非线性模型,指导算法快速收敛。在此基础之上,进一步利用基本局部线性嵌入算法的改进算法：监督局部线性嵌入和Hessian局部线性嵌入,又分别提出了SLLE-MOEA (Multi-Objective Evolutionary Algorithm Based on Supervised Locally Linear Embedding)和HLLE-MOEA (Multi-Objective Evol-utionary Algorithm Based on Hessian Locally Linear E mbedding,HLLE-MOEA)两种流形学习多目标优化算法。(4)通过变量无关、线性相关和非线性相关三类多目标测试函数测试算法,结论如下：①当LLE、SLLE及HLLE算法单独用于数据降维时,其邻域参数k对最终降维效果影响大,但是当LLE、SLLE及HLLE用于本文提出的流形学习多目标优化算法时,算法性能表现出对LLE邻域参数k值不敏感,实验求得本文算法中的最优k=2,过大的k值不但会增加计算量,而且还会破坏决策空间流形结构,进一步实验表明LLE-MOEA算法适合求解变量无关型多目标优化问题。②LLE-MOEA算法表现出对SLLE算法类别参数a的敏感性,盲目添加类别信息会破坏种群流形结构。由于a值代表数据集中点之间的类别信息,因此,SLLE-MOEA算法适合求解变量线性相关型多目标优化问题。③对于变量非线性相关多目标优化问题,SOM-MOEA算法更优,原因在于SOM-MOEA的神经元繁殖策略适当增加了优化问题决策空间数据点的多样性。④SOM-MOEA和LLE-MOEA算法的收敛性和多样性优于RM-MEDA和NSGA-II。(5)利用流形学习多目标优化算法求解卫星星座设计问题。经过对卫星星座设计问题特性的分析发现：卫星星座设计问题涉及多种准则和优化指标,问题目标复杂甚至没有解析表达式,是典型的高维工程多目标优化问题,流形学习多目标优化算法适合求解此类问题。较传统的几何解析法和基于仿真的方法,流形学习方法具有明显优势,主要体现在：流形学习多目标优化算法可以降低卫星星座设计问题决策空间维度,扩展卫星星座设计问题的探索空间,能快速设计出均匀或不对称的卫星星座。利用本文提出的SOM-MOEA、 LLE-MOEA、SLLE-MOEA、HLLE-MOEA四种流形学习多目标优化算法求解区域覆盖卫星星座设计问题,实验表明：流形学习多目标优化算法确实能够降低卫星星座设计问题决策空间数据维度,挖掘问题决策空间中内蕴的“流形”结构,加速算法收敛,且性能优于RM-MEDA和NSGA-Ⅱ。综上所述,本文针对传统演化多目标优化算法和模型多目标优化算法的不足,提出一类基于流形学习的多目标优化算法,算法通过挖掘优化问题决策空间中内蕴的“流形”结构来直接繁殖下一代种群个体,建立准确的决策空间模型,指导算法演化,加速种群收敛。通过测试函数及卫星星座设计应用,验证了流形学习多目标优化算法在求解卫星星座设计这一类高维多目标工程优化问题上的有效性。本文的研究不仅丰富了多目标优化算法理论,而且将为流形学习算法的应用提供新的研究方向。