高维多目标进化优化及降维评价的方法研究

进化算法是一种模拟生物进化、基于群体搜索的全局优化算法,已经在单目标和多目标优化领域成功应用[4][7][8],并已经逐渐形成了优化领域的一个前沿研究方向—进化多目标优化。近年来,多目标进化优化前沿领域的研究呈现出新的特点,由于现实世界中的许多优化问题的复杂性,当形式化一个优化问题时,设计者和决策者往往倾向于将与问题相关的每一个指标作为一个目标,这就产生了许多目标。Farina和Amato[23]将4个及4个以上目标优化问题称为高维多目标优化问题(many-objective optimization problems)。现实世界中,大多数优化问题都是多目标优化问题。大家熟悉的Time Table问题,属于NP困难问题,也是一类高维目标优化问题[24],国内外许多学者都在研究,但目前仍没有从理论和技术上解决这类问题。目前国内外对高维多目标进化的研究尚处于起步阶段,主要研究成果集中在对已有EMO算法的改进。无论是松弛Pareto支配关系、非Pareto支配排序方法还是高维降维的处理都存在参数确定、超高维无法收敛、分布性能差、时间复杂度高、边界个体无法保留等问题,而且在理论和技术上均没有建立解决高维目标优化问题的一般方法。本文在充分分析了国内外高维多目标进化算法研究的现状,综合存在的优缺点的基础上,为了提高高维多目标进化优化的性能提出了两种高维多目标进化算法及一种高维多目标非冗余目标评价方法,并将提出的高维多目标进化算法应用在文本特征值提取方面。本文提出一种利用在超平面上进行聚类技术来解决高维多目标优化问题的无参数算法(ClusterISEA)。该算法利用聚类技术将临界层的个体进行在分布超平面进行聚类选择。算法在整个优化过程中未引入任何参数,使得算法具有更强的适应问题的能力。与其它七个算法在测试函数DTLZ系列上进行测试分析,验证算法的有效性。本文提出一种利用旋转网格技术来解决高维多目标优化问题的算法(RGridEA)。该算法利用旋转网格规划目标空间,一方面借助了网格的分布性保持策略,另一方面利用旋转机制将收敛性和分布性分开来考虑,而且也融入了方向引导的策略,从而达到高维空间个体收敛和分布均匀的目的。与其它八个算法在测试函数DTLZ系列上进行测试分析,验证算法的有效性。本文从拟合的思路入手,从非冗余目标与冗余目标在空间的分布相似程度来衡量非冗余目标集的优劣提出了一种高维多目标非冗余目标评价标准(OSDSR),由于它同时考虑了非冗余目标集和冗余目标集的信息,将空间中的目标采用分段拟合机制,根据目标拟合的程度计算目标的相似程度,并根据所计算的相似度来评价目标,它的评价结果更准确。在三个测试问题Dtlz5, Dtlz2BZ和Dtlz2进行测试,通过和传统的IGD对比,表明,OSDSR能够在不知道真实Pareto面的情况下评价出冗余目标,而评价效果与IGD相当。最后本文将提出的高维多目标进化算法应用在文本特征值提取方面,实验验证提出的算法能有效降低特征值的维数并提高文本分类的性能。