论文部分内容阅读
最优化问题是一类最常遇到的问题,因为最优化问题的解决通常是某个问题得到解决之前的最后也是最关键的步骤。近些年来,随着科学技术的发展和工程应用的不断的增多,很多问题通过数学模型的建立最终都可以归结于最优化问题。最优化问题可以根据同时需要优化的问题数目的不同分为单目标优化问题和多目标优化问题。随着在现实世界中遇到的问题越来越复杂,更多的问题被建模为多目标优化问题。这也促使多目标优化问题成为当下得到研究比较多的一类问题,它的求解对于问题最终的解决具有非常重要的意义。但是实际中遇到的多目标优化问题通常表现出一定的复杂性,并且不具有数学意义上求解的特性,而且通常是非线性的。多目标优化问题的这些特性决定了传统的方法并不能很好的解决这一大类问题。目前解决这类问题最常使用的一类算法是多目标进化算法(MOEA)。衡量MOEA的性能的指标通常包含两个方面:1.算法求解得到的解集与真正的问题最优解的解集的逼近程度;2.算法求解得到的解集相对于整个问题的解集的分布程度,包括分布广度和分布的均匀性。作为MOEA中优秀的框架意义上被提出和使用较多的并且具有代表性的两大类算法是NSGA-II和MOEA/D。前者代表了一类基于非支配排序的MOEA,而后者则代表了一类基于分解的MOEA。这两种具有代表性的MOEA在算法迭代过程中对于维持解集的多样性都使用到了密度度量这个指标。其中,NSGA-II定义了自己的拥挤距离(crowding distance),而MOEA/D中则使用了传统的欧氏距离(Euclidian distance)来度量,这两种距离度量在某种程度上都仅仅考虑了点之间单纯的距离关系。但是在三维空间或者更高维度空间里,点与另一个点之间的关系还包括其相对位置关系,也就是方向的问题。所以,本文引入了三角剖分这个工具,综合考虑距离与邻域关系的基础上来提高进化算法解集的分布度。根据我们的实验结果数据,可以说明在维持解集多样性上本文中提出的改进方法具有显著的作用。本文的主要工作如下:1.针对NSGA-II算法的具体改进。我们知道NSGA-II算法是基于非支配排序的,其中的核心思想在于进化群体中一个偏序关系的构造。对于进化群体中的个体进行边界集的构造和边界集上个体拥挤距离的计算。拥有较小的边界集号的个体会被算法优先选择进入下一次迭代,而在最后一层边界集的选择时则选择拥挤距离大的个体。从这种偏序关系上我们可以看出,非支配排序的目的在于使算法尽快收敛,而拥挤距离的计算在于选择个体使解集的分布度更高。本文的具体工作就在于在计算拥挤距离的时候用三角剖分的方式更精确的确立个体的拥挤距离。2.针对MOEA/D算法的具体改进。根据我们对MOEA/D中权向量和解集之间对应关系的分析,我们可以根据目标空间中个体的目标值计算出其应该对应的权向量空间中具体的权向量值。这样我们就可以在目标空间中调整解集中的个体使其尽量均匀分布,并计算相应的权向量加入到种群中,使该个体最终收敛到合适的位置。在衡量个体间的均匀性的时候,本文也是采用三角剖分的方式精确的确立种群中的稀疏区域与拥挤区域。从而向稀疏区域加入个体,从密集区域删除个体,从而最终提高解集的分布度。