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

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

融合指标分组的高维混合多目标进化优化

高维混合多目标优化问题因包含多个不同类型指标,目前尚缺乏有效求解该问题的进化优化方法。提出一种基于目标分组的高维混合多目标并行进化优化方法。采用深度学习神经网络预测种群隐式性能指标;基于指标相关性,将高维混合多目标优化问题分解为若干子优化问题;采用多种群并行进化算法,求解分解后的每一子优化问题,并基于各子种群的非被占优解构建外部保存集;采用聚合函数对外部保存集个体进一步优化,得到Pareto最优解集。在室内布局优化问题中验证所提方法,实验结果表明,所提方法的Pareto最优解在收敛性、分布性以及延展性等方面均优于对比方法。     

Development of Pareto-based evolutionary model integrated with dynamic goal programming and successive linear objective reduction

This study investigates the coupling effects of objective-reduction and preference-ordering schemes on the search efficiency in the evolutionary process of multi-objective optimization. The difficulty in solving a many-objective problem increases with the number of conflicting objectives. Degenerated objective space can enhance the multi-directional search toward the multi-dimensional Pareto-optimal front by eliminating redundant objectives, but it is difficult to capture the true Pareto-relation among objectives in the non-optimal solution domain. Successive linear objective-reduction for the dimensionality-reduction and dynamic goal programming for preference-ordering are developed individually and combined with a multi-objective genetic algorithm in order to reflect the aspiration levels for the essential objectives adaptively during optimization. The performance of the proposed framework is demonstrated in redundant and non-redundant benchmark test problems. The preference-ordering approach induces the non-dominated solutions near the front despite enduring a small loss in diversity of the solutions. The induced solutions facilitate a degeneration of the Pareto-optimal front using successive linear objective-reduction, which updates the set of essential objectives by excluding non-conflicting objectives from the set of total objectives based on a principal component analysis. Salient issues related to real-world problems are discussed based on the results of an oil-field application.     

基于估值不确定度排序顺序均值采样的昂贵高维多目标进化算法

模型管理,特别是训练样本的选择和填充采样准则,是影响昂贵多目标优化算法求解性能的重要因素.为此,选择样本库中具有较好目标函数值的若干个体作为样本训练目标函数的代理模型,使用基于参考向量的进化算法搜索模型的最优解集,并提出一种基于个体目标函数估值不确定度排序顺序均值的采样策略,从该最优解集中选择两个个体进行真实的目标函数评价.为了验证算法的有效性,将所提出算法在DTLZ和WFG多目标优化测试问题和两个实际工程优化问题上进行测试,并与其他5种优秀的同类型算法进行结果对比.实验结果表明,所提出算法在求解昂贵高维多目标优化问题上是有效的.     

改进聚合树的高维多目标降维优化算法

对于高维多目标优化问题,降维优化算法通过去除或融合冗余目标的方法解决算法耗时过多的问题,但同时也会导致算法分布性能下降。聚合树算法定义非参数秩冲突从而可以快速计算出各目标间冲突度,但聚合树算法鲁棒性有待提高,且需要用户自行决策去除冗余目标。针对这些问题,提出数组叠加机制并定义冲突趋势和冲突度误差,以提高算法鲁棒性;通过合并冲突度较低的冗余目标的方法来进行目标降维,并定义降维截止冲突度;与NSGA-III算法结合,以达到对高维多目标问题进行完整降维优化的目的。为检验该算法性能,与其他经典高维算法进行对DTLZ测试函数集的优化对比,实验结果表明,该算法在耗时更少的同时,也具有较为优秀的分布性能和收敛性能。     

A preference multi-objective optimization based on adaptive rank clone and differential evolution

Evolutionary multi-objective optimization (EMO) algorithms have been used in various real-world applications. However, most of the Pareto domination based multi-objective optimization evolutionary algorithms are not suitable for many-objective optimization. Recently, EMO algorithm incorporated decision maker’s preferences became a new trend for solving many-objective problems and showed a good performance. In this paper, we first use a new selection scheme and an adaptive rank based clone scheme to exploit the dynamic information of the online antibody population. Moreover, a special differential evolution (DE) scheme is combined with directional information by selecting parents for the DE calculation according to the ranks of individuals within a population. So the dominated solutions can learn the information of the non-dominated ones by using directional information. The proposed method has been extensively compared with two-archive algorithm, light beam search non-dominated sorting genetic algorithm II and preference rank immune memory clone selection algorithm over several benchmark multi-objective optimization problems with from two to ten objectives. The experimental results indicate that the proposed algorithm achieves competitive results.     

采用放松支配关系的高维多目标微分进化算法

为了提高进化算法在求解高维多目标优化问题时的收敛性和多样性,提出了采用放松支配关系的高维多目标微分进化算法。该算法采用放松的Pareto支配关系,以增加个体的选择压力;采用群体和外部存储器协同进化的方案,并通过混合微分变异算子,生成子代群体;采用基于指标的方法计算个体的适应度并对群体进行更新;采用基于Lp范数（0相似文献   

An angle based evolutionary algorithm with infeasibility information for constrained many-objective optimization

Recently, angle-based approaches have shown promising for unconstrained many-objective optimization problems (MaOPs), but few of them are extended to solve constrained MaOPs (CMaOPs). Moreover, due to the difficulty in searching for feasible solutions in high-dimensional objective space, the use of infeasible solutions comes to be more important in solving CMaOPs. In this paper, an angle based evolutionary algorithm with infeasibility information is proposed for constrained many-objective optimization, where different kinds of infeasible solutions are utilized in environmental selection and mating selection. To be specific, an angle-based constrained dominance relation is proposed for non-dominated sorting, which gives infeasible solutions with good diversity the same priority to feasible solutions for escaping from the locally feasible regions. As for diversity maintenance, an angle-based density estimation is developed to give the infeasible solutions with good convergence a chance to survive for next generation, which is helpful to get across the large infeasible barrier. In addition, in order to utilize the potential of infeasible solutions in creating high-quality offspring, a modified mating selection is designed by considering the convergence, diversity and feasibility of solutions simultaneously. Experimental results on two constrained many-objective optimization test suites demonstrate the competitiveness of the proposed algorithm in comparison with five existing constrained many-objective evolutionary algorithms for CMaOPs. Moreover, the effectiveness of the proposed algorithm on a real-world problem is showcased.     

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

代理模型能够辅助进化算法在计算资源有限的情况下加快找到问题的最优解集,因此建立高效的代理模型辅助多目标进化搜索逐渐受到了重视.然而随着目标数量的增加,对每个目标分别建立高斯过程模型时个体整体估值的不确定度会随之增加.因此通过对模型最优解集的搜索探索原问题潜在的非支配解集,并基于个体的收敛性,种群的多样性和估值的不确定度...     

A clustering-ranking method for many-objective optimization

In evolutionary multi-objective optimization, balancing convergence and diversity remains a challenge and especially for many-objective (three or more objectives) optimization problems (MaOPs). To improve convergence and diversity for MaOPs, we propose a new approach: clustering-ranking evolutionary algorithm (crEA), where the two procedures (clustering and ranking) are implemented sequentially. Clustering incorporates the recently proposed non-dominated sorting genetic algorithm III (NSGA-III), using a series of reference lines as the cluster centroid. The solutions are ranked according to the fitness value, which is considered to be the degree of closeness to the true Pareto front. An environmental selection operation is performed on every cluster to promote both convergence and diversity. The proposed algorithm has been tested extensively on nine widely used benchmark problems from the walking fish group (WFG) as well as combinatorial travelling salesman problem (TSP). An extensive comparison with six state-of-the-art algorithms indicates that the proposed crEA is capable of finding a better approximated and distributed solution set.     

基于参考点的高维多目标粒子群算法

高维多目标优化问题一般指目标个数为4个 或以上时的多目标优化问题.由于种群中非支配解数量随着目标数量的增加而急剧增多,导致进化算法的进化压力严重降低,求解效率低.针对该问题,提出一种基于粒子群的高维多目标问题求解方法,在目标空间中引入一系列的参考点,根据参考点筛选出能兼顾多样性和收敛性的非支配解作为粒子的全局最优,以增大选择压力.同时,提出了基于参考点的外部档案维护策略,以保持最后所得解集的多样性.在标准测试函数DTLZ2上的仿真结果表明,所提方法在求解高维多目标问题时能够得到收敛性和分布性都较好的解集.     

基于R2指标和参考向量的高维多目标进化算法

在高维多目标优化中, 不同的优化问题存在不同形状的Pareto前沿(PF), 而研究表明大多数多目标进化算法(Multi-objective evolutionary algorithms, MOEAs) 在处理不同的优化问题时普适性较差. 为了解决这个问题, 本文提出了一个基于R2指标和参考向量的高维多目标进化算法(An R2 indicator and reference vector based many-objective optimization evolutionary algorithm, R2-RVEA). R2-RVEA基于Pareto支配选取非支配解来指导种群进化, 仅当非支配解的数量超过种群规模时, 算法进一步采用种群分解策略和R2指标选择策略进行多样性管理. 通过大量的实验证明, 本文提出的算法在处理不同形状的PF时具有良好的性能.     

Using objective reduction and interactive procedure to handle many-objective optimization problems

A number of practical optimization problems are posed as many-objective (more than three objectives) problems. Most of the existing evolutionary multi-objective optimization algorithms, which target the entire Pareto-front are not equipped to handle many-objective problems. Though there have been copious efforts to overcome the challenges posed by such problems, there does not exist a generic procedure to effectively handle them. This paper presents a simplify and solve framework for handling many-objective optimization problems. In that, a given problem is simplified by identification and elimination of the redundant objectives, before interactively engaging the decision maker to converge to the most preferred solution on the Pareto-optimal front. The merit of performing objective reduction before interacting with the decision maker is two fold. Firstly, the revelation that certain objectives are redundant, significantly reduces the complexity of the optimization problem, implying lower computational cost and higher search efficiency. Secondly, it is well known that human beings are not efficient in handling several factors (objectives in the current context) at a time. Hence, simplifying the problem a priori addresses the fundamental issue of cognitive overload for the decision maker, which may help avoid inconsistent preferences during the different stages of interactive engagement. The implementation of the proposed framework is first demonstrated on a three-objective problem, followed by its application on two real-world engineering problems.     

融合张角拥挤控制策略的高维多目标优化

对于高维多目标优化问题,随着目标维数的增加,种群中非被支配解的比例剧增, 严重降低了种群的进化压力.为了对数量众多的非被支配解进行有效的拥挤控制并提升种群的多样性, 本文在提出张角概念的基础上设计了一种新的拥挤控制策略(Congestion control strategy based on open angle, CCSOA),它的时间复杂度并不会随着目标维数的增加而增大. 与目前优秀的进化多目标优化(Evolutionary multiobjective optimization, EMO)算法IBEA (Indicator-based evolutionary algorithm)、NSGAIII (Nondominated sorting genetic algorithm III)和GrEA (Grid-based evolutionary algorithm)的比较结果表明, 融合了CCSOA的高维多目标优化算法在收敛效果和解集分布的均匀性两个方面均有较大的优势.     

Indicator-based set evolution particle swarm optimization for many-objective problems

Multi-objective particle swarm optimization (MOPSO) has been well studied in recent years. However, existing MOPSO methods are not powerful enough when tackling optimization problems with more than three objectives, termed as many-objective optimization problems (MaOPs). In this study, an improved set evolution multi-objective particle swarm optimization (S-MOPSO, for short) is proposed for solving many-objective problems. According to the proposed framework of set evolution MOPSO (S-MOPSO), including quality indicators-based objective transformation, the Pareto dominance on sets, and the particle swarm operators for set evolution, an enhanced S-MOPSO method is developed by updating particles hierarchically, i.e., a set of solutions is first regarded as a particle to be updated and then the solutions in a selected set are further evolved by a modified PSO. In the set evolutionary stage, the strategy for efficiently updating the set particle is proposed. When further evolving a single solution in the initial decision space of the optimized MaOP, the global and local best particles are dynamically determined based on those ideal reference points. The performance of the proposed algorithm is empirically demonstrated by applying it to several scalable benchmark many-objective problems.     

A Line Complex-Based Evolutionary Algorithm for Many-Objective Optimization

In solving many-objective optimization problems (MaOPs), existing nondominated sorting-based multi-objective evolutionary algorithms suffer from the fast loss of selection pressure. Most candidate solutions become nondominated during the evolutionary process, thus leading to the failure of producing offspring toward Pareto-optimal front with diversity. Can we find a more effective way to select nondominated solutions and resolve this issue? To answer this critical question, this work proposes to evolve solutions through line complex rather than solution points in Euclidean space. First, Plücker coordinates are used to project solution points to line complex composed of position vectors and momentum ones. Besides position vectors of the solution points, momentum vectors are used to extend the comparability of nondominated solutions and enhance selection pressure. Then, a new distance function designed for high-dimensional space is proposed to replace Euclidean distance as a more effective distance-based estimator. Based on them, a novel many-objective evolutionary algorithm (MaOEA) is proposed by integrating a line complex-based environmental selection strategy into the NSGA-III framework. The proposed algorithm is compared with the state of the art on widely used benchmark problems with up to 15 objectives. Experimental results demonstrate its superior competitiveness in solving MaOPs.      

Preference representation using Gaussian functions on a hyperplane in evolutionary multi-objective optimization

Many-objective optimization has attracted much attention in evolutionary multi-objective optimization (EMO). This is because EMO algorithms developed so far often degrade their search ability for optimization problems with four or more objectives, which are frequently referred to as many-objective problems. One of promising approaches to handle many objectives is to incorporate the preference of a decision maker (DM) into EMO algorithms. With the preference, EMO algorithms can focus the search on regions preferred by the DM, resulting in solutions close to the Pareto front around the preferred regions. Although a number of preference-based EMO algorithms have been proposed, it is not trivial for the DM to reflect his/her actual preference in the search. We previously proposed to represent the preference of the DM using Gaussian functions on a hyperplane. The DM specifies the center and spread vectors of the Gaussian functions so as to represent his/her preference. The preference handling is integrated into the framework of NSGA-II. This paper extends our previous work so that obtained solutions follow the distribution of Gaussian functions specified. The performance of our proposed method is demonstrated mainly for benchmark problems and real-world applications with a few objectives in this paper. We also show the applicability of our method to many-objective problems.     

On decomposition methods in interactive user-preference based optimization

Evolutionary multi-objective optimization (EMO) methodologies have been widely applied to find a well-distributed trade-off solutions approximating to the Pareto-optimal front in the past decades. However, integrating the user-preference into the optimization to find the region of interest (ROI) [1] or preferred Pareto-optimal solutions could be more efficient and effective for the decision maker (DM) straightforwardly. In this paper, we propose several methods by combining preference-based strategy (like the reference points) with the decomposition-based multi-objective evolutionary algorithm (MOEA/D) [2], and demonstrate how preferred sets or ROIs near the different reference points specified by the DM can be found simultaneously and interactively. The study is based on the experiments conducted on a set of test problems with objectives ranging from two to fifteen objectives. Experiments have proved that the proposed approaches are more efficient and effective especially on many-objective problems to provide a set of solutions to the DM's preference, so that a better and a more reliable decision can be made.     

A many-objective evolutionary algorithm based on a projection-assisted intra-family election

In recent years, many researchers have put emphasis on the study of how to keep a good balance between convergence and diversity in many-objective optimization. This paper proposes a new many-objective evolutionary algorithm based on a projection-assisted intra-family election. In the proposed algorithm, basic evolution directions are adaptively generated according to the current population and potential evolution directions are excavated in each individual's family. Based on these evolution directions, a strategy of intra-family election is performed in every family and elite individuals are elected as representatives of the specific family to join the next stage, which can enhance the convergence of the algorithm. Moreover, a selection procedure based on angles is used to maintain the diversity. The performance of the proposed algorithm is verified and compared with several state-of-the-art many-objective evolutionary algorithms on a variety of well-known benchmark problems ranging from 5 to 20 objectives. Empirical results demonstrate that the proposed algorithm outperforms other peer algorithms in terms of both the diversity and the convergence of the final solutions set on most of the test instances. In particular, our proposed algorithm shows obvious superiority when handling the problems with larger number of objectives.     

基于分解的高维多目标改进进化算法

针对基于参考向量的高维多目标进化算法中随机选择父代个体会降低算法的收敛速度,以及部分参考向量分配个体的缺失会减弱种群多样性的问题,提出了一种基于分解的高维多目标改进优化算法（IMaOEA/D）。首先,在分解策略框架下,当一个参考向量至少分配了2个个体时,对该参考向量分配的个体根据其到理想点的距离选择父代个体来繁殖子代,从而提高搜索速度。然后,针对未能分配到至少2个个体的参考向量,则从所有个体中选择沿该参考向量和理想点距离最小的点,使得该参考向量至少有2个个体与其相关。同时,确保环境选择后每个参考向量有一个个体与其相关,从而保证种群的多样性。在10个和15个目标的MaF测试问题集上将所提算法与其他4个基于分解的高维多目标优化算法进行了测试对比,实验结果表明所提算法对于高维多目标优化问题具有较好的寻优能力,且该算法在30个测试问题中的14个测试问题上得到的优化结果均优于其他4个对比算法,特别是对于退化问题具有一定的寻优优势。