大规模多目标演化算法及其应用研究
发布时间：2020-08-15 11:58
【摘要】：多目标优化问题是在科学研究和生产应用中广泛存在的一类具有挑战性的优化问题。其难点在于问题的多个目标之间往往存在冲突,导致通常不存在一个可以满足所有优化目标的解,因此现有的解析方法难以对其进行精确求解。演化算法因其基于种群的多点搜索机制,及对问题性质不做特别假设,天然地符合多目标优化寻找一组在多个目标之间进行折衷的最优解集的逼近集合的需求。因此,多目标演化算法已成为求解这类问题的主流技术手段之一。随着多目标演化算法的发展,其扩放性逐渐受到了研究者的关注。相比于多目标演化算法在目标维度的扩放性受到的广泛关注,目前研究其在决策变量维度的扩放性的工作较少。然而,这一点是与实际需求是相悖的。其一,大规模多目标优化问题的求解是有其应用需求的,如深度神经网络权值优化问题、大规模多目标社交网络分析、多目标车辆路径规划问题等;其二,现有多目标演化算法的性能随变量数增大而急剧下降,难以有效求解大规模多目标问题。基于此,本文针对大规模多目标演化优化进行研究,通过分析连续和离散多目标优化问题的特性,设计高效求解大规模多目标优化问题的多目标演化算法。本文的主要研究工作与创新之处包括以下几个方面:1.面向大规模多目标连续优化问题的分析和演化算法研究。由于多个优化目标之间存在冲突,人们通常希望寻求一组称之为Pareto最优解集,来寻求多个目标之间的折衷。针对这类问题,研究者们已经提出了许多多目标演化算法。但这些算法的性能随规模增大显著降低。因此,本文首先通过几个典型的测试问题集,深入分析制约现有多目标演化算法可扩放性的关键瓶颈,并将这些测试问题依据规模因素所带来的影响划分为三类,即聚焦收敛性的问题、聚焦多样性且无收敛-多样相关性的问题、聚焦多样性且有收敛-多样相关性的问题。对于第一类问题,现有的大规模单目标优化的研究成果天然地可以借鉴进来。对于第二类问题,由于收敛-多样之间无相关性,算法对于收敛性和多样性的需求可以相对独立地得到满足。实验结果表明,现有的大规模算法可以很好地对这类问题进行求解。对于第三类问题,与前两类问题的优异性能相比,现有的大规模算法不能对其进行很好地求解,甚至表现出比传统多目标演化算法还要差的性能。因此,对于这类问题的求解,亟待研究。基于此,本文提出了一个带多样性导向机制的大规模多目标演化算法。它以经典的SMS-EMOA为基本框架,引入一个基于外部集的新解生成器以加强多样性。该新解生成器的基本思想是,强迫外部集中的个体搜索Pareto前沿的不同区域,以产生目标空间中多样的新生个体。我们提出了一个双重局部搜索机制以实现其搜索。实验结果表明,该算法可以比现有算法在第三类问题上得到更好的解,并且实现更好的收敛性和多样性之间的平衡。2.针对一种复杂的现实大规模多目标连续优化问题,即ROC凸包最大化问题,进行研究。基于ROC凸包的分类问题旨在寻找一组在TPR和FPR之间进行权衡的分类器。其本质上是一个多目标优化问题。随着数据维度、分类器超参数目等变量的数目规模急剧增大,这类问题展现出大规模多目标优化问题的特性。然而,不同于一般性的多目标优化问题,它的求解目标是寻求一组称之为凸包解集的最优解集。因此,研究者们已经提出了一些基于凸包的多目标演化算法。然而,在求解大规模问题时,现有算法表现出多样性不足的现象。因此,本文在现有算法的基础上,提出了一个改进版的基于凸包的多目标演化算法,以加强其多样性。具体地,该算法采用一个基于个体最小值凸包的多目标排序策略和基于凸包面积最大化的选择机制实现对种群的选择。在多个高维不平衡数据集上的实验结果表明,通过优化一组神经网络的权值,该算法可比现有算法得到的分类性能更好。3.针对一种复杂的现实大规模多目标离散优化问题,即社交网络上的影响力最大化问题,进行研究。社交网络上的影响力最大化问题是近年来得到广泛关注的一个组合优化问题。在竞争环境下,该问题的研究旨在从众多网络节点中,找出在其他参与者的竞争下影响力仍能超过指定阈值的、始发数最少的一组节点。然而,随着社交网络规模的增大,现有的研究方法难以在可接受的时间内给出一个质量可接受的解。基于此,本文首先将竞争环境中的影响力最大化问题建模成一个多目标优化问题,并设计了一个可扩放的多目标演化算法对其进行求解。具体地,一个变可行域搜索的机制被提出以加速算法的搜索速率,以提升多样性和收敛性之间平衡。在多个大规模的社交网络上的实验结果表明,该算法相对于现有方法,可以在问题求解的性能和时间开销之间给出一个比较好的平衡。
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TP18
【图文】：
逡逑１．５本文的组织结构逡逑本文的组织结构如图１．１所示。第１章介绍了大规模多目标优化的背景知识、逡逑当前研究中存在的一些问题，以及本文的主要工作。第２章对大规模多目标演化逡逑算法的研究进展进行了全面的综述。逡逑第１章：绪论逡逑第２章：大规模多目逡逑标优化的研宄现状逡逑／邋一逡逑！邋｜第３章：大规模逦｜第４章：基于大规逦｜第５章：基于多目标逡逑多目标演化算逦模多目标演化的逦演化的大规模社交网逡逑！逦＾逦｜邋ＲＯＣ凸包最大化逦｜邋络影响力最大化逡逑Ｖ—逦逦逦逦逦逦—．．．．．．逦逦—．．．．．．逦逦Ｊ逡逑第６章：总结和展望逡逑图１．１本文组织结构图逡逑９逡逑
间相互冲突，多目标演化算法通常会对其进行权衡，c\索一组称为Ｐａｒｅｔｏ最优逡逑解的解集。所有Ｐａｒｅｔｏ最优解的集合在目标空间中的图像称为Ｐａｒｅｔｏ前沿ｔ１４＇逡逑然而，Ｐａｒｅｔｏ前沿与ＲＯＣ凸包不完全相同，如图４．１所示。点Ａ和Ｄ位于逡逑ＲＯＣ凸包上，而点Ｂ，Ｃ和Ｅ不在。尽管在Ｐａｒｅｔｏ最优的概念中所有五个分类逡逑器被认为是同等最优的，但是对应于点Ｂ，Ｃ和Ｅ的分类器在ＲＯＣ图中表现出逡逑更差的性能。当且仅：１：彳某个分类器的性能在ＲＯＣ凸包N、该分类器才被认为是逡逑最佳的。由于在ＲＯＣ图中，任何虚拟分类器都可以通过混合两个真实分类器来逡逑构造，其性能可以由这两个真实分类器对应的点的连接线上的点表示［％。因此，逡逑可以通过ＲＯＣ凸包来改进与Ｐａｒｅｔｏ前沿相对应的一组分类器。考虑到ＲＯＣ凸逡逑包的这种特性，传统的基于Ｐａｒｅｔｏ的多Q儽暄莼惴ǹ赡芪薹ù锏搅己玫男阅堋ｅ义弦虼耍鱿至斯赜诮徊窖芯客拱蕴岣撸遥希眯阅艿墓ぷ鳎蓿保矗梗荨ｅ义希矗峰义
本文编号：2794079
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TP18
【图文】：
逡逑１．５本文的组织结构逡逑本文的组织结构如图１．１所示。第１章介绍了大规模多目标优化的背景知识、逡逑当前研究中存在的一些问题，以及本文的主要工作。第２章对大规模多目标演化逡逑算法的研究进展进行了全面的综述。逡逑第１章：绪论逡逑第２章：大规模多目逡逑标优化的研宄现状逡逑／邋一逡逑！邋｜第３章：大规模逦｜第４章：基于大规逦｜第５章：基于多目标逡逑多目标演化算逦模多目标演化的逦演化的大规模社交网逡逑！逦＾逦｜邋ＲＯＣ凸包最大化逦｜邋络影响力最大化逡逑Ｖ—逦逦逦逦逦逦—．．．．．．逦逦—．．．．．．逦逦Ｊ逡逑第６章：总结和展望逡逑图１．１本文组织结构图逡逑９逡逑
间相互冲突，多目标演化算法通常会对其进行权衡，c\索一组称为Ｐａｒｅｔｏ最优逡逑解的解集。所有Ｐａｒｅｔｏ最优解的集合在目标空间中的图像称为Ｐａｒｅｔｏ前沿ｔ１４＇逡逑然而，Ｐａｒｅｔｏ前沿与ＲＯＣ凸包不完全相同，如图４．１所示。点Ａ和Ｄ位于逡逑ＲＯＣ凸包上，而点Ｂ，Ｃ和Ｅ不在。尽管在Ｐａｒｅｔｏ最优的概念中所有五个分类逡逑器被认为是同等最优的，但是对应于点Ｂ，Ｃ和Ｅ的分类器在ＲＯＣ图中表现出逡逑更差的性能。当且仅：１：彳某个分类器的性能在ＲＯＣ凸包N、该分类器才被认为是逡逑最佳的。由于在ＲＯＣ图中，任何虚拟分类器都可以通过混合两个真实分类器来逡逑构造，其性能可以由这两个真实分类器对应的点的连接线上的点表示［％。因此，逡逑可以通过ＲＯＣ凸包来改进与Ｐａｒｅｔｏ前沿相对应的一组分类器。考虑到ＲＯＣ凸逡逑包的这种特性，传统的基于Ｐａｒｅｔｏ的多Q儽暄莼惴ǹ赡芪薹ù锏搅己玫男阅堋ｅ义弦虼耍鱿至斯赜诮徊窖芯客拱蕴岣撸遥希眯阅艿墓ぷ鳎蓿保矗梗荨ｅ义希矗峰义
本文编号：2794079
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2794079.html
