超多目标演化算法及其应用研究

发布时间：2018-01-09 18:16

本文关键词：超多目标演化算法及其应用研究　出处：《中国科学技术大学》2017年博士论文　论文类型：学位论文

【摘要】：在现实世界中,我们经常面对具有多个目标的优化问题,这类问题被称为多目标优化问题(Multi-objective Optimization Problem)。其中,至少有四个目标的多目标优化问题通常被非正式地称为超多目标优化问题(Many-objective Opti-mization Problem)。作为一类重要的优化问题,超多目标优化问题广泛出现在各种现实世界的应用中,如工程设计、空中交通控制、护士排班、汽车控制器优化、供水组合规划等等。演化算法(Evolutionary Algorithm)作为一类基于种群的黑盒搜索/优化方法,不需要对问题的连续性和可微性做假设。这类算法非常适合处理具有多个目标的复杂优化问题。在过去的几十年里,研究人员提出一系列的多目标演化算法。但是,有研究表明,基于传统的帕累托支配的方法在超多目标优化问题(目标数大于3的多目标优化问题)上会发生比较严重的性能退化。发生这种现象的主要原因在于随着目标空间维度的增加,随机种群中的非支配解的比例急剧增加。这就导致基于支配定义的主要的选择标准失去效果,而基于多样性的次要选择标准在环境选择阶段起主导作用。次要选择标准会导致种群发散地分布在目标空间,并远离帕累托前沿。因此这类算法在处理超多目标优化问题时,收敛性会急剧降低,整个种群与帕累托最优前沿相去甚远。为了处理超多目标优化问题,研究者们提出了一系列的超多目标演化算法。基于算法的核心思想,我们将超多目标演化方法分为以下几类:基于松弛的支配定义的方法、基于多样性的方法、基于聚集的方法、基于评价指标的方法、基于参照点集的方法、基于偏好的方法和降维的方法。作为一种基于参照点集合的方法,两档案算法(Two Archive Algorithm,TAA)在环境选择中使用了两个档案(解集合)来处理非支配解。具体来说,在每一代中,非支配解被分到两个档案中:收敛性档案(Convergence Archive,CA)和多样性档案(Diversity Archive,DA)。这两个档案分别针对收敛性和多样性。但是,随着目标个数的增加,收敛性档案的大小会急剧增加,从而使得剩余给多样性档案的空间很小,严重影响了二者的平衡。同时,收敛性档案的更新率很低,使得算法的收敛速度很慢。另外,多样性档案的更新策略导致算法偏向于远离收敛性档案的收敛性很差的解,也会对算法的性能造成影响。在第二章中,作者针对两档案算法的主要缺陷,提出了改进版的两档案算法(Improved Two Archive Algorithm,ITAA)。在改进版算法中,基于惩罚的边界交叉方法被用来作为CA的截断选择策略。PBI方法为CA中的解提供了排序标准,使得算法可以在CA超过一定大小时对CA进行截断。此外,改进版算法使用基于平移的密度估计对DA进行排序,以避免多样性档案严重滞后于整个种群的收敛。在基准测试集上的实验结果显示,在大部分测试样例上,改进版的算法在收敛性和多样性上都优于原版算法。由于最终的解集合是根据评估指标进行评价的,所以一个处理超多目标优化问题的很直观的方法是利用解集合的指标值来引导搜索方向。但是,单个指标函数很有可能具有偏向性,将搜索方向引导至帕累托前沿的某个子区域。以一个基于Iε+指标的算法IBEA为例,在处理超多目标优化问题时,它很难保持种群的多样性。这种现象说明,I￡+指标相对多样性而言更加偏好收敛性。其他指标(如拥塞距离、平移密度估计等等.)很可能偏好多样性更好的解。由于不同的指标可能具有不同的偏向性并且可能相互补充,因此,在环境选择阶段使用多个指标而非单个指标可能会得到一个更好的算法。由这一思想驱动,作者在第三章中提出了一个多指标优化算法来处理超多目标优化问题。特别地,设计这样一个算法的关键问题在于如何基于很有可能并不一致的多个指标来进行环境选择。有研究表明,随机排序在处理约束优化中的适应度和约束违反量之间的冲突方面表现突出。因此,作者采用了随机排序技术来处理多指标的平衡这一难点。实验结果表明,提出的基于随机排序的多指标算法(Stochastic Ranking based multi-indicator Algorithm,SRA),在一系列的基准测试问题上都显示出很好的性能。最近几年,爆炸式的数据已经远远超出了用户抽取有用信息的能力。电子商务平台(如亚马逊、阿里巴巴)以及内容提供商(如Netflix,lastfm,和豆瓣)试图推荐巨量的商品来满足每个用户的特定的兴趣。为了处理这一问题,很多推荐系统应运而生,成为科研界的研究热点。推荐系统可以被分为以下两类:基于内容的方法和基于协同过滤的方法。基于内容的方法利用自然信息建立用户档案或者物品档案并进行个性化推荐;协同过滤的方法则基于用户的行为历史进行推荐。这里,一个用户的行为可以是他的点击、评分、购买记录以及对于商品或者服务的评论。显然,仅仅考虑推荐系统的准确性对于推荐系统的评价是不够全面的。其他性能指标,例如多样性、新颖性、覆盖率、偶然性也应该被考虑在内。这些看起来冲突的不同的性能指标使得推荐任务变为一个多目标优化问题。尽管在多目标推荐系统中已经有很多研究工作,但是,尚无工作考虑基于超多目标优化的个性化推荐(超多三个目标的)。在本文的第四章中,作者将前N项个性化推荐建模成了超多目标优化问题,并使用随机排序多指标算法来处理这一问题。在Movielens数据集上的实验结果显示,与其他三个超多目标演化算法相比,提出的算法在收敛性和多样性上都表现较好。
[Abstract]:In the real world , we often face optimization problems with multiple objectives called Multi - objective Optimization Problem . Among them , the multi - objective optimization problem with at least four objectives is often referred to informally as hypermultiple objective optimization problems . As a kind of important optimization problem , hyper - multi - objective optimization has been widely used in various real world applications , such as engineering design , air traffic control , nurse shift , car controller optimization , water supply combination planning , etc . However , with the increase of the number of objects , the size of the convergence file can be increased sharply , so that the space remaining to the diversity file is very small , which seriously affects the balance of the two . In the second chapter , the author proposes an improved Two Archive Algorithm ( ITAA ) for the main defects of the two - file algorithm . In the improved algorithm , the boundary crossing method based on penalty is used as a truncated selection strategy for CA . The PBI method provides ordering criteria for the solution in CA , so that the algorithm can intercept the CA more than a certain hour . In order to deal with this problem , the author puts forward a multi - index optimization algorithm to deal with the problem of multi - target optimization . In the fourth chapter , the author puts forward a multi - index optimization algorithm based on content - based method to deal with the problem of multi - target optimization .

【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】