论文部分内容阅读
科学研究、经济领域和工程实践中的优化问题大多是多目标问题。多目标问题的最优解是一个集合,而多目标演化算法一次进化过程可以得到多个可行解,近年来演化算法逐渐成为求解多目标问题的主流方法。卫星星座是由多颗卫星组成一个卫星网来协同工作,以满足特定空间任务所需的对地覆盖要求。卫星凭借其独特的空间位置优势,在通信、导航定位系统、防御间谍卫星、对地观测、气象预测及地质勘探等领域中都有着广泛的应用。如何设计高效、合理的卫星星座配置方案,是星座优化的关键问题。星座优化问题往往涉及多个特征点和多项优化指标,是一个复杂的高维、动态、多目标优化问题,鉴于传统演化算法忽略了Pareto解集分布规则对解集搜索的指导性且大多存在求解效率不高,算法收敛性不强等不足,随着科技的不断发展,研究和应用的不断深入,实际要优化的问题将越来越复杂,这必然会对算法用到的技术和性能提出新的挑战。分布估计算法由Thierens、Bosman等人于2001年引入多目标优化领域,张清富、周爱民等人将被传统算法忽略的“某一类连续的多目标问题的Pareto解集的分布呈现一定的规则性”这一重要特性运用进了该算法,并在解决高维多目标优化的问题上取得了很好的效果。分布估计算法(EDA)与遗传算法最大的不同就是它没有传统演化算法的交叉、变异操作,而是运用统计学,在每一代建立描述当前种群分布的概率模型,并从中以一定概率随机取样来产生新的子代。2007年,张清富、周爱民等人提出了基于规则模型的多目标评估分布算法(RM-MEDA),给出规则:m个目标的连续多目标优化问题的Pareto解集在决策空间的分布是一个分段连续的m-1维流形,并对符合这一规则的多目标优化问题进行求解,求得解集的多样性和收敛性比PCX-NSGA-Ⅱ、GDE3(Generalized Differential Evolution)、MIEDA等算法的要更好。然而基于规则模型的多目标分布估计算法也存在一定的不足。基于模型的算法的聚类分析、概率建模的过程更复杂,算法运行较耗时。在某些测试问题上,在算法初期就采用概率模型产生新个体往往会使搜索方向与实际目标搜索方向相差甚远,如基于规则模型的分布估计多目标算法RM-MEDA在ZDT4、ZDT6、DTLZ1及DTLZ3上就是发散的,从而在一定程度上造成了算法的不稳定性。本文首先对课题的研究背景、意义和国内外研究现状进行综述,深入探讨了多目标优化问题,分析了传统演化算法和分布估计算法各自的优势及不足,着重研究了基于模型原理的多目标优化算法,引入并阐述了当前存在的两类多目标优化问题:第一类连续多目标优化问题,PS和PF都是m-1维的流形;第二类连续多目标问题,PF是m-1维流形,而PS是更高维的连续流形(大于m-1维)。然后,本文针对两类多目标优化问题分别改进、设计算法,包括了:1)流形初始化种群策略,在正交基础上建立一个理想Pareto前沿,并从样本点中选取离理想Pareto前沿最近的一定量个体作为初始种群个体,从而使种群个体尽可能均匀地逼近Pareto前沿;2)在前人用GA+EDA来产生子代的工作基础上,对第一类问题快速收敛准则中的ε参数进行修正,通过不同的ε值进行试验从而选取恰当的参数值,在保证甚至提高结果质量的前提下大大提升算法采用概率建模生成子代的比例;3)第二类问题中潜在维数的确定和快速收敛准则的设计,当种群各个聚类的潜在维数相差不大时,就断定种群的分布呈现了一定规律,此时第二类问题就可以使用概率建模产生子代了。同时,本文对当前常用的测试函数集的概念、构造及特性做了一个简要的阐述,在回顾当前使用得较多测试集的同时,着重讲述WFG测试集的构造及特性,并在原有测试函数ZDT及DTLZ系列的基础上,新构造了三个PS要复杂得多的测试函数ZDT2.3、DTLZ2.3及DTLZ2.4(前一个的PS为多峰曲线,后两个的PS为多峰曲面)。本文还在当前常用的度量指标收敛性Υ及多样性△的基础上引入了IGD度量指标,IGD度量在评估收敛性的同时兼顾了种群的均匀分布性评估,更好地补充了算法对三目标问题的性能评价。本文将该改进后的算法n-RM-MEDA与NSGA-Ⅱ、m-NSGA-Ⅱ(加入流形初始化的NSGA-Ⅱ、基本的基于规则模型的算法RM-MEDA及基于正交的模型算法IORM-MEDA分别进行比较,通过对结果的统计和分析,发现当问题Pareto解集分布规则的复杂度很低时(如ZDT1-6),会弱化基于模型建模算法的优势,此时m-NSGA-Ⅱ优势显著;但在问题的PS分布规则变复杂之后,概率建模算法逐渐显露优势,NSGA-Ⅱ和m-NSGA-Ⅱ则显得力不从心,不仅在多样性上大失水准,连收敛性能都有所下降,这时在算法一开始运行就采用概率建模产生子代并不利于算法在整个空间的搜索,而一味采用遗传算法产生子代(如NSGA-Ⅱ和m-NSGA-Ⅱ)一样得不到好的结果,相比之下改进后的算法融合遗传算法与概率建模两种方法来产生子代则是个不错的选择,也验证了改进后的算法在收敛性和均匀分布上的有效性。在第五章中,本文先对星座优化设计中的相关物理模型和航天方面的背景基本知识进行了简要介绍,用改进后的算法来解决低轨星座优化问题,并将改进后的算法与m-NSGA-Ⅱ、RM-MEDA、IORM-MEDA及文献结果分别进行了比较,从结果可以看到算法优化后的覆盖性能,能较好满足特定点持续覆盖的要求,对卫星星座设计的决策者来说有一定的参考价值。