基于集合的高维多目标优化问题的进化算法

由于高维多目标优化问题包含的目标很多,已有的方法往往难以解决该问题.本文提出一种有效解决该问题的基于集合的进化算法,该方法以超体积、分布度,以及延展度为新的目标,将原优化问题转化为3目标优化问题;定义基于集合的Pareto占优关系,设计体现用户偏好的适应度函数;此外,还提出集合进化策略.将所提方法应用于4个基准高维多目标优化问题,并与其他2种方法比较,实验结果表明了所提方法的优越性.     

高维多目标优化中基于稀疏特征选择的目标降维方法

目标降维算法通过去除冗余的目标达到简化问题规模的目的,为求解高维多目标优化问题提供了一种新的思路和方法.近似解集的几何结构特征和Pareto占优关系从不同侧面反映了多目标优化问题的内在结构特性,而现有算法仅利用其中一种特征分析目标之间的关系,具有较大局限性.本文提出基于稀疏特征选择的目标降维方法,该方法利用近似解集的几何结构特征构建稀疏回归模型,求解高维目标空间映射为低维目标子空间的稀疏投影矩阵,依据此矩阵度量目标的重要性,并利用Pareto占优关系改变程度选择满足误差阈值的目标子集,实现目标降维.通过与其他已有目标降维算法比较,实验结果表明本文提出的降维算法具有较高的准确性,并且受近似解集质量的影响较小.     

一种基于角度惩罚距离的高维多目标进化算法

为了使多目标进化算法在收敛性和分布性之间保持平衡,该文提出一种基于角度惩罚距离的高维多目标进化算法(Many-Objective Evolutionary Algorithm based on Angle Penalized Distance, MaOEA-APD)。首先,综合考虑收敛性和分布性在进化不同阶段的重要性,构造一种角度惩罚距离,使两者随进化进程动态平衡;其次,开发基于删除劣质个体的环境选择策略,在提高种群分布性的同时提高收敛性;最后,根据环境选择的原理,设计与之相协调且互补的匹配选择过程,提高算法的整体进化效率。将所提算法与目前国内外性能优异的3种高维多目标进化算法进行对比,实验结果表明在WFG标准测试函数集上,该文算法相对于其他算法,综合性能有了较大的提升。     

基于自适应支配准则的高维多目标进化算法

基于松弛支配的高维多目标进化算法（Many-objective Evolutionary Algorithms,MaOEAs）由于能够有效地提高区分解的能力,受到广泛关注,但该类大多数算法处理不同目标的优化问题时普适性较差.针对这个问题,本文提出一种基于自适应支配准则的高维多目标进化算法（Adaptive Dominance Criterion Based Evolutionary Algorithm for Many-objective Optimization,ADCEA）.首先,自适应准则（Adaptive Dominance Criterion,ADC）根据目标空间中相邻解间的角度信息和目标数目,设计一种自适应小生境方法,并结合收敛性指标信息,实现对候选解的非支配排序.然后,为了进一步增强种群的多样性,在环境选择中引入参考向量分割种群技术;最后,构建合理的适应度函数,并根据适应度值大小选取收敛性和多样性较好的非支配解集.实验证明,本文所提的方法在处理不同目标的优化问题时普适性提高,并在平衡种群的收敛性和多样性上取得显著效果.     

利用冲突信息降维的进化高维目标优化算法

进化多目标优化算法求解高维目标优化问题面临收敛能力、计算复杂度、决策以及Pareto前沿的可视化等困难，其根本原因是目标空间维数高。目标降维通过丢弃冗余目标，为缓解高维目标优化求解困难提供一种新思路。本文提出利用冲突信息降维的分解进化高维目标优化算法（CIOR-MOEA/D）。该方法通过衡量目标在近似解集上体现的冲突性，构造问题的冲突信息矩阵，对该矩阵进行特征分析，确定目标的重要性程度，实现维数约简，并利用分解进化多目标优化算法（MOEA/D）对重要子目标集合进行分解进化,从而得到问题的近似解集。实验结果表明,本文提出的目标降维算法在降维的准确性与鲁棒性上均表现突出，能够有效地处理冗余高维目标优化问题。      

基于模糊支配的高维多目标进化算法MFEA

为提高高维复杂多目标优化算法的收敛性和解集分布性,提出一种基于模糊支配的高维多目标进化算法MFEA.在第二代Pareto支配类高维多目标进化算法模型基础上,利用模糊理论对模型中的环境选择进行改进,提出基于模糊隶属度的支配关系,并结合Harmonic、k邻域法和小生境技术对其中的拥挤密度估计方法进行改进,最后根据高维多目标的特点并结合模糊理论α-截集的思想提出了新的环境选择策略.将该算法与目前性能最好的5种多目标进化算法在标准测试函数集上进行对比试验,结果表明本文算法与其他算法相比具有明显的优势,不仅提高了算法的收敛性能,而且保证了Pareto最优解的均匀分布性.     

关于如何用角度信息引入决策者偏好的研究

在实际的多目标优化中,决策者通常只对少部分的Pareto最优解感兴趣。然而,传统多目标优化算法关注整个Pareto最优面上的解集,这不仅需要花费大量计算时间在无用解的搜索上,同时决策者也很难从众多解中选出符合自己偏好的解（特别是问题目标个数大于3时）。为此,本文提出了一种利用个体间的角度关系的偏好多目标进化算法。该方法通过重新定义个体间的支配关系和聚集距离使那些离决策者偏好区域越近的个体优先被保留下来,从而引导种群趋近于决策者的偏好区域。     

一种基于角度信息的约束高维多目标进化算法

目前约束高维多目标进化算法大多注重提高收敛精度,而收敛速度相对较慢.为提高算法的收敛速度,提出一种基于角度信息的约束高维多目标进化算法.该算法提出基于角度违反度函数的选择操作,依据动态的收敛性和分布性直接选择较优个体,提高收敛速度;此外,提出了基于差分进化算法的交叉操作,在不同的进化阶段选用不可行解参与交叉操作,补偿收敛精度.在标准测试函数集C-DTLZ上进行仿真实验,并与当前国内外性能优异的4种约束高维多目标进化算法进行对比,证明了本文算法收敛精度保持良好,而收敛速度得到了提升,且目标维数越高提升效果越明显.     

基于类圆映射的高维多目标可视化方法

可视化技术有利于对高维多目标优化问题求解所得的解集进行评价与分析,但是现有的高维多目标可视化方法无法有效保持解集的Pareto支配关系、前沿密度分布及形状。针对以上问题,本文提出类圆映射可视化方法.首先将多目标按相关性均匀排列在单位圆圆弧上,根据适应度函数值将解集映射为类圆空间内的一个多边形,并通过多边形的几何中心和面积对解集进行3维可视化.在此基础上对类圆支配与均衡性进行了定义,并对类圆映射下的支配关系、映射遮挡等进行了理论分析与证明.与平行坐标系、主成分分析方法和径向可视化方法相比表明,本文方法能保持解集Pareto支配关系,并能反映解集在原始空间的密度分布和形状。此外,还能有效避免解集映射点遮档.其有利于决策者进行可视化评价和选择高维多目标解集.     

基于分解和超平面拟合的进化超多目标优化降维算法

目标降维是研究超多目标优化问题的一个重要方向,它通过恰当的算法设计,能够剔除一些对求解优化问题冗余的目标,达到极大简化优化问题的效果。在超多目标优化降维问题中,前沿界面呈现非线性的情形是最普遍也是最难处理的降维问题。该文提出一种基于分解和超平面拟合的算法(DHA)来处理这类目标降维问题,通过对进化过程中种群的有效分解,使得在几何上非线性分布的非劣解集近似分解为多个近似线性分布的子集,再用系数是稀疏的超平面结合一些扰动项去拟合这些非劣解子集,最后根据该超平面提取出原问题的本质目标集,达到去除冗余目标的效果。为了检验提出算法的有效性,采用DTLZ5(I, m), WFG3(I, m)和MAOP(I, m)作为测试问题集,与代表当今水平的著名算法进行比较。计算机仿真结果表明该文提出的算法无论前沿界面是线性或非线性的情形都具有优异的性能。     

融入偏好的武器装备体系多目标规划决策方法

武器装备体系规划是装备体系建设的重要环节,对装备论证工作具有重要指导意义.首先对武器装备体系规划问题进行了定性分析和公式化描述;然后提出基于超网络的体系建模方法,构建能力指标定量计算模型;接着采用NSGA-II算法范式,分析了决策者偏好表示方法,将决策者偏好融入优化过程,将原优化问题转化为以超体积、未知度、决策者满意度...     

基于双向搜索差分进化的多目标优化算法

针对差分进化算法求解多目标优化问题时易陷入局部最优的问题,设计了双向搜索机制以增强DE(Differential Evolution,DE)算法的局部搜索能力。一方面降低了算法陷入局部最优的风险,另一方面可增强Pareto解集的多样性,使Pareto前沿面的解集分布更为均匀。实验结果表明,相比于NSGA-II等同类算法,提出的方法在搜索Pareto最优解时效率更高,并且Pareto最优解集的精度及分布程度比前者更好。     

动态多目标优化的进化算法及其收敛性分析

给出了动态多目标优化问题的一种新解法.首先对时间变量进行了等区间离散化,在得到的子区间(称为环境)上定义了种群的静态序值方差和静态密度方差.然后把动态多目标优化问题近似地转化成了若干个两个目标的静态优化问题.在给出的一种能自动检测环境变化的应答算子下,提出了一种动态多目标进化算法,同时证明了算法的收敛性.计算机仿真表明新算法对动态多目标优化问题是有效的.     

多目标问题的游戏模型并行共同进化算法

游戏理论的主要成就是进化稳定战略,由MaynardSmith在1982年提出。使用基于游戏模型的共同进化算法寻找ESS作为多目标问题(MOPs)的解,该算法是一种基于粗粒度并行模型的进化算法。首先,研究游戏模型的共同进化方法解决MOPs的有效性。且说明进化游戏如何由共同进化算法来具体实现,证实它是否能达到MOP的最佳均衡点。其次,通过在几个多目标问题上的严格的实验,与其它一些方法比较,评估该方法的性能。     

基于权值向量的偏好多目标优化方法

偏好多目标优化方法是多目标优化领域的一个重要分支,其主要目的是仅搜索Pareto前沿面上部分区域内决策者感兴趣的解.基于MOEA/D算法根据预先设定的均匀分布的权值向量搜索Pareto最优前沿面的思想,本文提出了一种基于权值向量的偏好多目标优化方法,该方法通过引入具有偏好信息的权值向量,使算法仅搜索偏好点附近的解.仿真实验结果表明,与现有偏好多目标优化算法相比,本文方法具有支持多偏好点、偏好区域大小可控、偏好点位置无特别要求及偏好解具有更好收敛性的优势.     

基于进化机制的动态多目标优化方法

动态多目标优化是进化计算领域一个新兴的研究方向.文中给出了定义在离散时间空间上、决策变量的维数随时间(环境)可发生变化的一类动态多目标优化问题(DMOP)的新方法.该方法首先把DMOP转化成了一系列同类静态约束优化问题,然后在一种环境变化判断规则下提出了解DMOP的一种新动态多目标进化算法(DMEA).数值实验表明新算法对DMOP最优解具有较好的跟踪能力,并且能有效的获得DMOP在不同环境下数量较多、质量较好且分布均匀的Pareto最优解.     

基于均匀设计的多目标进化算法

现实生活中的很多决策问题都要考虑同时优化若干个目标,多目标优化算法就是要从所有可能的方案中找到最合理、最可靠的解决方案。如何在Pareto界面稀疏区域求得更多非劣解,则使所求出的解的分布更加均匀。如何求出距Pareto界面更近的非劣解以使所求出的解的质量更高。论文基于加权平均法和均匀设计方法设计了一种解决多目标优化问题的新算法。首先,为了找到在Pareto界面上尽可能多、且均匀分布的点,利用均匀设计方法设计了一个交叉算子,该算子让稀疏部分的相邻点进行均匀交叉,以使算法在稀疏部分能找到更多的非劣解,从而使其所求解分布更加均匀。其次,为了克服加权平均法不能找到Pareto界面非凸部分解的缺点,考虑到非劣解界面上相邻距离较远的一对点之间有可能是非劣解界面上非凸部分之一的情况,分别将此两点与距其最近的非劣解集外的点进行交叉,以期在该两点之间找到新的非劣解,这样可能在非劣解界面的非凸部分找到更多的解。最后对两个测试问题进行了数值试验,并和著名的NSGA-Ⅱ算法用算法性能评价的三种度量进行了比较,结果表明了本文算法是有效的。     

求解约束优化的一种新的进化算法

罚函数法是解决约束优化最常用的方法,但如何确定罚因子是其难以克服与回避的问题.该文提出的求解约束优化问题的新的进化算法克服了这一困难,其基本思想是对种群中的个体按可行和不可行分别采取两种评价方案,对可行解按其目标函数值的大小加以评价,对不可行解按其违反约束的程度进行评价.作为评价个体优劣的适应度函数将可行点映射到(-1,1),将不可行点映射到(1,2),这样有效地区分了可行点与不可行点.数据实验与比较结果表明了该算法的有效性.     

结合偏好处理的虚拟机放置问题研究

虚拟机的调度（放置）问题（Virtual Machine Placement, VMP）是云计算中的一个重要研究课题。它指的是使用特定的调度算法,将虚拟机放置到合适的主机上的过程,是一个典型的NP问题。目前的研究大量的使用了启发式的多目标优化算法,这类方法考虑了调度的目标与限制。针对满足目标和限制的条件下依旧会有多种解决方案的情况,引入了用户偏好表达的调度策略。具体的做法,首先,使用CP-nets定性地描述用户对虚拟机调度的偏好;其次,处理了多个用户偏好以及他们之间的冲突问题,最后,将元启发式算法得出的Pareto解进行偏好处理,返回满足用户偏好的最佳调度方案。实例分析和实验的结果表明,考虑用户偏好的虚拟机调度方案极大的提升了用户的满意程度。