进化高维多目标优化研究综述

高维多目标优化问题(many-objective optimization problems, MaOPs)已经普遍存在于工业和科学领域中,这类问题的目标数一般超过3个且目标之间存在冲突性。进化算法作为一种基于种群的元启发式搜索方法已经被证实能够有效求解MaOPs。近二十年来,高维多目标进化算法(many-objective evolutionary algorithms, MaOEAs)研究已取得了长足发展。现对进化高维多目标优化(evolutionary many-objective optimization, EMaO)的研究进展进行全面的综述,具体包括：(1)描述了EMaO的相关理论背景;(2)分析了EMaO面临的挑战;(3)详细讨论了Ma OEAs的发展概况;(4)归纳了Ma OPs以及性能指标;(5)介绍了面对高维目标空间的可视化工具;(6)总结了Ma OEAs在一些领域的应用;(7)剖析了进化算法在解决MaOPs时所面临的问题和挑战,并给出未来研究方向的建议。     

进化高维多目标优化研究进展

高维多目标优化问题是目标个数多于3的多目标优化问题.尽管进化优化方法在多目标优化问题求解中显示了卓越的性能,但是,对于高维多目标优化问题,已有方法存在目标维数难以扩展、Pareto占优关系无法区分进化个体,以及多样性维护策略失效等困难.因此,高维多目标优化问题的高效求解引起进化优化界的高度关注.本文将分别从新型占优关系、多样性维护策略、目标缩减、目标聚合、基于性能指标的选择、融入偏好、集合进化、变化算子、可视化技术,以及应用等10个方面分类总结近年来进化高维多目标优化的研究成果,通过分析已有研究存在的问题,指出今后可能的研究方向.     

融入偏好的区间高维多目标集合进化优化方法

尽管区间参数高维多目标优化问题普遍存在且非常重要, 但是, 目前求解该问题的方法却很少. 本文提出一种有效解决该问题的集合进化优化方法, 通过在进化过程中融入决策者的偏好, 以得到符合决策者偏好的Pareto解集. 该方法将原优化问题转化为以超体积、不确定度、决策者满意度为新目标的确定型3目标优化问题; 为了求解转化后的优化问题, 采用集合Pareto占优关系比较个体, 并设计融入决策者偏好的延展性测度, 以进一步区分具有相同序值的个体; 此外, 还提出集合变异与重组策略, 以生成高性能的子代种群. 采用4个基准高维多目标优化问题和1个汽车驾驶室设计问题测试所提方法的性能, 并将其与另外3种方法进行对比. 实验结果验证, 该方法能得到收敛性、延展性、不确定度, 以及决策者满意度均衡的Pareto解集.     

基于目标迁移和条件替代的高维多目标进化算法

尽管许多高维多目标进化算法已被提出,但大多仍无法有效处理具有不规则Pareto前沿的高维多目标优化问题.鉴于此,提出基于目标迁移和条件替代的高维多目标进化算法(MaOEA-OTCR),在环境选择过程中利用目标迁移策略和条件替代准则协作逐一选择收敛性和多样性好的个体进入下一代.前者首先选择位于Pareto前沿边界的极值解进入下一代,以确定Pareto前沿的范围,同时选择收敛性最好的若干个体进入下一代,以加速种群收敛;然后迁移已选解集且利用迁移解集和未迁移解集的最大距离来选择收敛性和多样性好的个体进入下一代.后者利用基于角度和收敛性评估的条件取代准则来防止前者过度强调多样性.此外,提出一个多标准决策的匹配选择策略,旨在增加具有良好收敛性和多样性种群个体结合的概率,进一步提升算法的搜索效率.为了验证MaOEA-OTCR的有效性,在3个测试集上与8个先进的高维多目标进化算法进行对比实验.实验结果表明, MaOEA-OTCR在处理高维多目标优化问题时不仅能够获得较强的竞争性能,而且有能力处理具有不规则Pareto前沿的高维多目标优化问题.     

区间参数高维多目标集合进化优化方法

区间参数高维多目标优化问题是现实生活中常见的一类优化问题,但其有效的求解方法并不是很多.对此,利用集合的概念,提出一种求解此类问题的新方法.首先,利用衡量解集收敛性、分布性、多样性的3种性能指标将原优化问题降为3目标优化问题;其次,采用集合Pareto占优关系和不确定测度来区分转化后优化问题解的优劣;再次,设计自适应变化的交叉、变异概率以提高种群的全局和局部搜索能力;最后,利用4种基准函数优化问题,对所提出方法和对比方法进行测试.测试结果显示,除了收敛性,所提出方法得到的Pareto解集的不确定性、多样性、分布性均优于对比方法.     

一种基于信息分离的高维多目标进化算法

高维多目标优化是指对目标维数大于三维的多目标问题(multi-objective optimization problem,简称MOP)进行优化.大多数传统的多目标进化算法采用Pareto支配关系指导搜索,很难在高维多目标优化问题上得到较为理想的结果.为此,提出了一种基于信息分离的高维多目标进化算法(multi-objective evolutionary algorithm based on information separation,简称ISEA).该算法在目标空间中将原坐标系进行旋转,使第1条坐标轴与向量(1,1,…,1)^T平行.ISEA定义转换坐标的第1个坐标值为收敛信息(convergence information,简称CI),剩余的坐标代表个体分布信息(diversity information,简称DI).同时,采用一种基于分层选择的邻域惩罚机制,利用一种由两个超圆锥组成的邻域形状保持种群的分布性,当个体被选入归档集后,其邻域内的个体将被惩罚进入下一层选择,防止邻近的个体同时被选入归档集.邻域形状的第1部分利用分布信息覆盖邻近的个体,第2部分覆盖边界上的差个体.与NNIA,e-MOEA, MSOPS,AR+DMO以及IBEA这5种经典算法进行了比较.实验结果表明,ISEA在处理高维多目标优化问题时具有良好的收敛性和分布性.     

基于目标分解的高维多目标并行进化优化方法

高维多目标优化问题普遍存在且难以解决, 到目前为止, 尚缺乏有效解决该问题的进化优化方法. 本文提出一种基于目标分解的高维多目标并行进化优化方法, 首先, 将高维多目标优化问题分解为若干子优化问题, 每一子优化问题除了包含原优化问题的少数目标函数之外, 还具有由其他目标函数聚合成的一个目标函数, 以降低问题求解的难度; 其次, 采用多种群并行进化算法, 求解分解后的每一子优化问题, 并在求解过程中, 充分利用其他子种群的信息, 以提高Pareto非被占优解的选择压力; 最后, 基于各子种群的非被占优解形成外部保存集, 从而得到高维多目标优化问题的Pareto 最优解集. 性能分析表明, 本文提出的方法具有较小的计算复杂度. 将所提方法应用于多个基准优化问题, 并与NSGA-II、PPD-MOEA、ε-MOEA、HypE和MSOPS等方法比较, 实验结果表明, 所提方法能够产生收敛性、分布性, 以及延展性优越的Pareto最优解集.     

MaOEA/d2:一种基于双距离构造的高维多目标进化算法

传统的基于Pareto支配关系的多目标进化算法(MOEA)难以有效求解高维多目标优化问题(MaOP). 提出一种利用PBI效用函数的双距离构造的支配关系, 且无需引入额外的参数. 其次, 利用双距离定义了一种多样性保持方法, 该方法不仅考虑了解个体的双距离, 而且还可以根据优化问题的目标数目自适应地调整多样性占比, 以较好地平衡高维目标解群的收敛性和多样性. 最后, 将基于双距离构造的支配关系和多样性保持方法嵌入到NSGA-II算法框架中, 设计了一种基于双距离的高维多目标进化算法MaOEA/d². 该算法与其他5种代表性的高维多目标进化算法一同在5-、10-、15-和20-目标的DTLZ和WFG基准测试问题上进行了IGD和HV性能测试, 结果表明, MaOEA/d²算法具有较好的收敛性和多样性. 由此表明, MaOEA/d²算法是一种颇具前景的高维多目标进化算法.     

一种基于分解和协同的高维多目标进化算法

现实中大量存在的高维多目标优化问题对以往高效的多目标进化算法提出了严峻的挑战.通过将分解策略和协同策略相结合提出一种高维多目标进化算法MaOEA/DCE.该算法利用混合水平正交实验方法在聚合系数空间产生一组均匀分布的权重向量以改善初始种群的分布性;其次,算法将差分进化算子和自适应SBX算子进行协同进化,以产生高质量的子代个体,并改善算法的收敛性.该算法与另外5种高性能的多目标进化算法在基准测试函数集DTLZ{1,2,4,5}上进行对比实验,利用改进的反转世代距离指标IGD+评估各算法的性能.实验结果表明,Ma OEA/DCE算法与其他对比算法相比,在总体上具有较为显著的收敛性和分布性优势.     

基于IGD+S指标的高维多目标进化算法

如何有效评价个体是处理高维多目标优化问题的关键.文中提出改进的反世代距离(IGD⁺S)指标,以反世代距离(IGD)指标为原型,融合修改的反世代距离(IGD⁺)指标的弱支配性,增加无贡献个体概念,可综合评价解集收敛性和多样性.将IGD⁺S指标嵌入进化算法框架中,提出基于IGD⁺S指标的高维多目标进化算法.在环境选择过程中,根据IGD⁺S选择优良个体.实验表明,文中算法在处理DTLZ问题和WFG问题上具有良好的竞争力.     

网络拥塞控制中的智能优化算法

计算机网络的飞速发展带来了日益严重的网络拥塞问题,采用适当的方法进行拥塞控制已成为当前研究的热点。文章在对网络拥塞及拥塞控制分析的基础上,详细介绍遗传算法、人工神经网络、模糊逻辑等智能优化算法在网络拥塞控制中的应用,并分析了各种算法的优缺点。     

基于鲸鱼优化算法的无人机通信网络链路拥塞控制研究

为了提高无人机通信网络的安全性,解决由于链路拥塞而导致的通信数据误码与丢失问题,提出基于鲸鱼优化算法的无人机通信网络链路拥塞控制方法。采用NetFlow技术获取无人机通信链路实时运行数据,度量链路利用率等指标,识别当前网络链路的拥塞状态。模拟无人机通信与链路拥塞过程,综合考虑无人机通信直视径、反射径和散射径三个分量,构建网络链路模型。在无人机通信网络链路拥塞控制协议的约束下,均衡调度无人机通信数据,利用鲸鱼优化算法选择通信链路的最优解,完成通信链路切换工作,实现无人机通信网络链路的拥塞控制任务。实验结果表明:在设计方法控制下,无人机通信网络链路的时延减小了61s,吞吐率提升135kbit/s,证明优化方法能够有效缓解链路的拥塞程度,通过对通信网络误码率和溢出丢包率的分析,证明优化控制方法不会对网络的通信任务产生明显影响。     

模型辅助的计算费时进化高维多目标优化

代理模型能够辅助进化算法在计算资源有限的情况下加快找到问题的最优解集, 因此建立高效的代理模型辅助多目标进化搜索逐渐受到了重视. 然而随着目标数量的增加, 对每个目标分别建立高斯过程模型时个体整体估值的不确定度会随之增加. 因此通过对模型最优解集的搜索探索原问题潜在的非支配解集, 并基于个体的收敛性, 种群的多样性和估值的不确定度, 提出了一种新的期望提高计算方法, 用于辅助从潜在的非支配解集中选择使用真实目标函数计算的个体, 从而更新代理模型, 能够在有限的计算资源下更有效地辅助优化算法找到好的非支配解集. 在7个DTLZ 基准测试问题上的实验对比结果表明, 该算法在求解计算费时高维多目标优化问题上是有效的, 且具有较强的竞争力.     

基于禁忌遗传优化的网络拥塞控制算法

为解决网络拥塞问题,提出一种基于禁忌遗传优化的网络拥塞控制算法TSGA。该算法将禁忌搜索和遗传算法相结合,以网络资源消耗最小化和网络负载均衡分布为目标,建立多约束QoS路由优化数学模型。仿真实验结果证明,该算法可实现网络拥塞控制,有效提高网络性能。     

基于拥挤度的改进蚁群算法

针对蚁群算法在求解旅行商问题时收敛时间长,且易陷入局部最优状态的缺陷,提出一种基于拥挤度的动态信息素蚁群优化策略。该算法引入静态拥挤度和动态拥挤度算子,主动提前预防停滞现象。将拥挤度与状态转移规则相结合,使蚁群状态实时跟随路径搜索情况而改变,提高蚁群自适应能力。针对蚁群路径搜索情况,加入邻域搜索优化规则,缩小搜索区域,结合2-opt局部优化策略,加快蚁群收敛速度。仿真结果表明,本算法既有较高的搜索效率又有较强的全局搜索能力。对比其他优化算法,无论是求解质量、稳定性还是收敛速度都能达到令人满意的效果。     

带拥塞控制的多种群二元蚁群算法

二元蚁群算法在函数优化中有着良好的表现, 但仍存在易陷入局部最优和在多峰函数求解中无法同时得到多个解的缺陷. 使用拥塞控制策略改善算法的全局寻优能力, 同时引入多种群的思想, 提出了带拥塞控制多种群二元蚁群算法. 通过对几个不同函数(包括单峰与多峰)的测试, 实验结果表明该改进算法在保证较好的全局搜索能力的基础上, 拥有很好的多目标求解能力.     

一种基于博弈的拥塞控制改进算法G-Vegas

随着互联网的发展,网络拥塞问题越来越严重,如何改进现有的拥塞控制算法成为一个重要课题。为了解决网络拥塞问题,目前已有很多拥塞控制算法,大体可分为端到端的拥塞控制和基于网络的拥塞控制,本文主要关注基于端到端的拥塞控制。在众多的TCP拥塞控制算法中,Vegas算法以其主动避免拥塞的思想,具有较好的效果。但是,Vegas与目前主流的Reno算法兼容性差,存在带宽被挤占的问题。本文分析了拥塞问题的多重原因,并从博弈的角度分析了Vegas的缺点,提出了一种改进的拥塞控制算法G-Vegas。通过在NS2平台仿真,验证了算法的有效性。     

一种面向视频业务的拥塞控制策略

近年来,因特网上的视频业务得到了广泛的发展。如何在异构的IP网上为用户提供满足QoS要求的视频服务,一直是人们研究的热点。本文提出了一种新的拥塞控制策略--基于分层重要性的队列管理和基于丢包检测的速率控制。仿真结果表明,该方法可以在网络拥塞情况下,为视频业务提供较好的QoS保证。     

基于拥塞控制的AQM算法研究

在对网络拥塞控制进行分析的基础上,介绍了AQM(Active Queue Management)算法的特点及网络流量特征对AQM算法的影响。根据AQM算法的发展概况,将AQM算法中的DropTail算法、RED(Random Early Detection)算法、Adaptive RED算法、PI算法、REM(Random Early Marking)算法和AVQ(Adaptive Virtual Queue)算法进行了比较评价。并对AQM算法的反馈方式及AQM算法的控制理论进行了较为详细的分析与探讨。     

拥塞控制算法的仿真研究

本文介绍了传输控制协议（TCP）的拥塞控制技术,分析了三种典型TCP控制算法,即TCP Reno、TCPVegas和Fast TCP,并在ns仿真环境下对这三种TCP控制算法进行了仿真,并分析总结了三种算法的优缺点。