论文摘要
多目标优化是优化问题的主要研究领域之一,现实中的优化问题大多具备多目标的特征,并且这些目标往往是相互冲突的。不同于单目标优化问题有唯一的最优解,多目标优化问题的最优解为一组折中解集,即Pareto最优解集。进化算法是一类模拟生物自然选择与自然进化的随机搜索算法,以其擅长于求解高度复杂的非线性问题而得到了广泛的应用,并且由于一次运行可以得到一组非支配解集,从而非常适合于求解多目标优化问题。近年来,研究者们针对不同的应用问题,提出了自己的多目标进化算法,比较有代表性算法有:NSGA-II,SPEA2,PESA-II等。评价多目标进化算法的优劣主要分为三个指标:解集收敛程度,解集分布度以及时间开销。其中解集的分布度是指与问题真实Pareto面的相似程度和分布的广泛程度,良好的分布度能够为决策者们提供最适合问题的解,具有重要的理论意义和应用价值。本文针对多目标进化算法中解集的分布性展开研究,主要工作包括以下三个方面:第一,针对多目标进化算法中种群维护方法和运行时间之间的矛盾,提出了一种基于最小生成树的分布度保持方法。该方法为整个种群构造一棵生成树,定义了一个个体密度估计指标——树聚集距离（STCD）,并结合个体在树中的度数信息对种群进行维护。实验结果表明该方法在得到良好分布性解集的同时,拥有较好的时间效率。第二,提出一种动态邻域分布度评价方法。不同于大多数分布度评价方法把空间划分为若干个固定区域,评价其固定区域内的分布情况,动态邻域分布度评价方法通过相邻个体之间的关系,构造随着个体的密集程度而变化的动态的邻域。通过实验和分析发现,该方法不仅能对均匀问题的分布情况进行精确的评价,而且能对全局非均匀,局部均匀问题的分布情况进行准确的评价。部分解决了现有方法不能对非均匀分布的测试函数评价的问题。第三,由于分布规律性的难以确定以及非均匀分布的解集对搜索存在一定阻碍作用,现存的方法很难维持非均匀问题的真实分布。在此,我们提出一种解决非均匀问题的多目标进化算法。该方法定义一个反映种群分布规则程度的指标——杂乱度,根据杂乱度和度数信息发掘个体之间潜在的规律性,从而剔除那些造成种群不规则的个体。实验结果表明该算法能有效的解决非均匀问题,得到与问题真实分布类似的解集,为决策者提供了更有实用价值的方案。