MOEA/D with uniform decomposition measurement for many-objective problems

Many-objective problems (MAPs) have put forward a number of challenges to classical Pareto-dominance based multi-objective evolutionary algorithms (MOEAs) for the past few years. Recently, researchers have suggested that MOEA/D (multi-objective evolutionary algorithm based on decomposition) can work for MAPs. However, there exist two difficulties in applying MOEA/D to solve MAPs directly. One is that the number of constructed weight vectors is not arbitrary and the weight vectors are mainly distributed on the boundary of weight space for MAPs. The other is that the relationship between the optimal solution of subproblem and its weight vector is nonlinear for the Tchebycheff decomposition approach used by MOEA/D. To deal with these two difficulties, we propose an improved MOEA/D with uniform decomposition measurement and the modified Tchebycheff decomposition approach (MOEA/D-UDM) in this paper. Firstly, a novel weight vectors initialization method based on the uniform decomposition measurement is introduced to obtain uniform weight vectors in any amount, which is one of great merits to use our proposed algorithm. The modified Tchebycheff decomposition approach, instead of the Tchebycheff decomposition approach, is used in MOEA/D-UDM to alleviate the inconsistency between the weight vector of subproblem and the direction of its optimal solution in the Tchebycheff decomposition approach. The proposed MOEA/D-UDM is compared with two state-of-the-art MOEAs, namely MOEA/D and UMOEA/D on a number of MAPs. Experimental results suggest that the proposed MOEA/D-UDM outperforms or performs similarly to the other compared algorithms in terms of hypervolume and inverted generational distance metrics on different types of problems. The effects of uniform weight vector initializing method and the modified Tchebycheff decomposition are also studied separately.     

A decomposition-based multiobjective evolutionary algorithm with angle-based adaptive penalty

A multiobjective evolutionary algorithm based on decomposition (MOEA/D) decomposes a multiobjective optimization problem (MOP) into a number of scalar optimization subproblems and optimizes them in a collaborative manner. In MOEA/D, decomposition mechanisms are used to push the population to approach the Pareto optimal front (POF), while a set of uniformly distributed weight vectors are applied to maintain the diversity of the population. Penalty-based boundary intersection (PBI) is one of the approaches used frequently in decomposition. In PBI, the penalty factor plays a crucial role in balancing convergence and diversity. However, the traditional PBI approach adopts a fixed penalty value, which will significantly degrade the performance of MOEA/D on some MOPs with complicated POFs. This paper proposes an angle-based adaptive penalty (AAP) scheme for MOEA/D, called MOEA/D-AAP, which can dynamically adjust the penalty value for each weight vector during the evolutionary process. Six newly designed benchmark MOPs and an MOP in the wastewater treatment process are used to test the effectiveness of the proposed MOEA/D-AAP. Comparison experiments demonstrate that the AAP scheme can significantly improve the performance of MOEA/D.     

一种基于混合高斯模型的多目标进化算法

目前,大多数多目标进化算法采用为单目标优化所设计的重组算子.通过证明或实验分析了几个典型的单目标优化重组算子并不适合某些多目标优化问题.提出了基于分解技术和混合高斯模型的多目标优化算法（multiobjective evolutionary algorithm based on decomposition and mixture Gaussian models,简称MOEA/D-MG）.该算法首先采用一个改进的混合高斯模型对群体建模并采样产生新个体,然后利用一个贪婪策略来更新群体.针对具有复杂Pareto前沿的多目标优化问题的测试结果表明,对给定的大多数测试题,该算法具有良好的效果.     

基于幂变换的多目标进化算法MOEA?D权重设计方法

在多目标最优化问题中,如何求解一组均匀散布在前沿界面上的有效解具有重要意义.MOEA?D是最近出现的一种杰出的多目标进化算法,当前沿界面的形状是某种已知的类型时,MOEA?D使用高级分解的方法容易求出均匀散布在前沿界面上的有效解.然而,多目标优化问题的前沿界面的形状通常是未知的.为了使MOEA?D能求出一般多目标优化问题的均匀散布的有效解,利用幂函数对目标进行数学变换,使变换后的多目标优化问题的前沿界面在算法的进化过程中逐渐接近希望得到的形状,提出了一种求解一般的多目标优化问题的MOEA?D算法的权重设计方法,并且讨论了经过数学变换后前沿界面的保距性问题.采用建议的权重设计方法,MOEA?D更容易求出一般的多目标优化问题均匀散布的有效解.数值结果验证了算法的有效性.     

混合分解和强度帕累托多目标进化算法

在多目标进化优化中,使用分解策略的基于分解的多目标进化算法(MOEA/D)时间复杂度低,使用〖BP(〗强度帕累托策略的〖BP)〗强度帕累托进化算法-2(SPEA2)能得到分布均匀的解集。结合这两种策略,提出一种新的多目标进化算法用于求解具有复杂、不连续的帕累托前沿的多目标优化问题(MOP)。首先,利用分解策略快速逼近帕累托前沿;然后,利用强度帕累托策略使解集均匀分布在帕累托前沿,利用解集重置分解策略中的权重向量集,使其适配于特定的帕累托前沿;最后,利用分解策略进一步逼近帕累托前沿。使用的反向世代距离(IGD)作为度量标准,将新算法与MOEA/D、SPEA2和paλ-MOEA/D在12个基准问题上进行性能对比。实验结果表明该算法性能在7个基准问题上最优,在5个基准问题上接近于最优,且无论MOP的帕累托前沿是简单或复杂、连续或不连续的,该算法均能生成分布均匀的解集。     

MOEA/D线性插入方向向量策略研究

MOEA/D具有良好的收敛性、均匀的分布性、求解效率高等优点,普遍应用于求解多目标优化问题.然而对于Pareto前端复杂的多目标优化问题,预先设定均匀的权重向量并不能够维持Pareto最优解集的良好分布性.本文,首先分析均匀分布的权重向量、均匀分布的搜索方向二者与均匀分布的解集之间的关系,提出一种新的权重向量设置方式;其次基于进化过程中解集的分布,提出线性插入搜索方向策略,并将其转换为对应的权重向量,同时在MOEA/D中周期性应用该策略调整搜索方向,获取分布均匀的解集;最后将该算法在WFG系列测试问题上进行性能测试,并采用世代距离指标(GD)、Spacing指标(S)、超体积指标(HV)对算法收敛性和多样性进行对比分析,实验结果表明,与原始的MOEA/D、使用均匀分布的搜索方向MOEA/D、使用预处理的M OEA/D、M OEA/D-DU相比,改进的算法求出解集的多样性极大提高,收敛性明显增强,解集的整体质量显著提高.     

MOEA/D + uniform design: A new version of MOEA/D for optimization problems with many objectives

To extend multiobjective evolutionary algorithm based on decomposition (MOEA/D) in higher dimensional objective spaces, this paper proposes a new version of MOEA/D with uniform design, named the uniform design multiobjective evolutionary algorithm based on decomposition (UMOEA/D), and compares the proposed algorithm with MOEA/D and NSGA-II on some scalable test problems with three to five objectives. UMOEA/D adopts the uniform design method to set the aggregation coefficient vectors of the subproblems. Compared with MOEA/D, distribution of the coefficient vectors is more uniform over the design space, and the population size neither increases nonlinearly with the number of objectives nor considers a formulaic setting. The experimental results indicate that UMOEA/D outperforms MOEA/D and NSGA-II on almost all these many-objective test instances, especially on problems with higher dimensional objectives and complicated Pareto set shapes. Experimental results also show that UMOEA/D runs faster than NSGA-II for the problems used in this paper. In additional, the results obtained are very competitive when comparing UMOEA/D with some other algorithm on the multiobjective knapsack problems.     

Many-objective evolutionary algorithm based on adaptive weighted decomposition

Decomposition is a representative method for handling many-objective optimization problems with evolutionary algorithms. Classical decomposition scheme relies on a set of uniformly distributed reference vectors to divide the objective space into multiple subregions. This scheme often works poorly when the problem has an irregular Pareto front due to the inconsistency between the distribution of reference vectors and the shape of Pareto fronts. We propose in this paper an adaptive weighted decomposition based many-objective evolutionary algorithm to tackle complicated many-objective problems whose Pareto fronts may or may not be regular. Unlike traditional decomposition based algorithms that use a pre-defined set of reference vectors, the reference vectors in the proposed algorithm are produced from the population during the search. The experiments show that the performance of the proposed algorithm is competitive with other state-of-the-art algorithms and is less-sensitive to the irregularity of the Pareto fronts.     

基于分解的多目标花朵授粉算法

在过去几十年里，许多多目标进化算法被广泛应用于解决多目标优化问题，其中一种比较流行的多目标进化算法是基于分解的多目标进化算法(MOEA/D)。花朵授粉算法是一种启发式优化算法，但迄今为止，花朵授粉算法在基于分解的多目标进化算法领域的研究还非常少。本文在基于分解的多目标进化算法的框架下，将花朵授粉算法拓展至多目标优化领域，提出一种基于分解的多目标花朵授粉算法(MOFPA/D)。此外，为了保证非支配解的多样性，本文提出一种基于网格的目标空间分割法，该方法从找到的Pareto最优解集中筛选出一定数量且分布均匀的Pareto最优解。实验结果表明，基于分解的多目标花朵授粉算法在收敛性与多样性方面均优于基于分解的多目标进化算法。     

A novel adaptive control strategy for decomposition-based multiobjective algorithm

Recently, evolutionary algorithm based on decomposition (MOEA/D) has been found to be very effective and efficient for solving complicated multiobjective optimization problems (MOPs). However, the selected differential evolution (DE) strategies and their parameter settings impact a lot on the performance of MOEA/D when tackling various kinds of MOPs. Therefore, in this paper, a novel adaptive control strategy is designed for a recently proposed MOEA/D with stable matching model, in which multiple DE strategies coupled with the parameter settings are adaptively conducted at different evolutionary stages and thus their advantages can be combined to further enhance the performance. By exploiting the historically successful experience, an execution probability is learned for each DE strategy to perform adaptive adjustment on the candidate solutions. The proposed adaptive strategies on operator selection and parameter settings are aimed at improving both of the convergence speed and population diversity, which are validated by our numerous experiments. When compared with several variants of MOEA/D such as MOEA/D, MOEA/D-DE, MOEA/D-DE+PSO, ENS-MOEA/D, MOEA/D-FRRMAB and MOEA/D-STM, our algorithm performs better on most of test problems.     

基于在线感知Pareto前沿划分目标空间的多目标进化优化

多目标进化优化是求解多目标优化问题的可行方法.但是, 由于没有准确感知并充分利用问题的Pareto前沿, 已有方法难以高效求解复杂的多目标优化问题.本文提出一种基于在线感知Pareto前沿划分目标空间的多目标进化优化方法, 以利用感知的结果, 采用有针对性的进化优化方法求解多目标优化问题.首先, 根据个体之间的拥挤距离与给定阈值的关系感知优化问题的Pareto前沿上的间断点, 并基于此将目标空间划分为若干子空间; 然后, 在每一子空间中采用MOEA/D (Multi-objective evolutionary algorithm based on decomposition)得到一个外部保存集; 最后, 基于所有外部保存集生成问题的Pareto解集.将提出的方法应用于15个基准数值函数优化问题, 并与NSGA-Ⅱ、RPEA、MOEA/D、MOEA/DPBI、MOEA/D-STM和MOEA/D-ACD等比较.结果表明, 提出的方法能够产生收敛和分布性更优的Pareto解集, 是一种非常有竞争力的方法.     

Decomposing the user-preference in multiobjective optimization

Preference information (such as the reference point) of the decision maker (DM) is often used in multiobjective optimization; however, the location of the specified reference point has a detrimental effect on the performance of multiobjective evolutionary algorithms (MOEAs). Inspired by multiobjective evolutionary algorithm-based decomposition (MOEA/D), this paper proposes an MOEA to decompose the preference information of the reference point specified by the DM into a number of scalar optimization subproblems and deals with them simultaneously (called MOEA/D-PRE). This paper presents an approach of iterative weight to map the desired region of the DM, which makes the algorithm easily obtain the desired region. Experimental results have demonstrated that the proposed algorithm outperforms two popular preference-based approaches, g-dominance and r-dominance, on continuous multiobjective optimization problems (MOPs), especially on many-objective optimization problems. Moreover, this study develops distinct models to satisfy different needs of the DM, thus providing a new way to deal with preference-based multiobjective optimization. Additionally, in terms of the shortcoming of MOEA/D-PRE, an improved MOEA/D-PRE that dynamically adjusts the size of the preferred region is proposed and has better performance on some problems.     

基于多目标进化算法的MOEA/D权重向量产生方法

在进化多目标优化研究领域,多目标优化是指对含有2个及以上目标的多目标问题的同时优化,其在近些年来受到越来越多的关注。随着MOEA/D的提出,基于聚合的多目标进化算法得到越来越多的研究,对MOEA/D算法的改进已有较多成果,但是很少有成果研究MOEA/D中权重的产生方法。提出一种使用多目标进化算法产生任意多个均匀分布的权重向量的方法,将其应用到MOEA/D,MSOPS和NSGA-III中,对这3个经典的基于聚合的多目标进化算法进行系统的比较研究。通过该类算法在DTLZ测试集、多目标旅行商问题MOTSP上的优化结果来分别研究该类算法在连续性问题、组合优化问题上的优化能力,以及使用矩形测试问题使得多目标进化算法的优化结果在决策空间可视化。实验结果表明,没有一个算法能适用于所有特性的问题。然而,MOEA/D采用不同聚合函数的两个算法MOEA/D_Tchebycheff和MOEA/D_PBI在多数情况下的性能比MSOPS和NSGA-III更好。     

Multiobjective Optimization Problems With Complicated Pareto Sets, MOEA/D and NSGA-II

Partly due to lack of test problems, the impact of the Pareto set (PS) shapes on the performance of evolutionary algorithms has not yet attracted much attention. This paper introduces a general class of continuous multiobjective optimization test instances with arbitrary prescribed PS shapes, which could be used for studying the ability of multiobjective evolutionary algorithms for dealing with complicated PS shapes. It also proposes a new version of MOEA/D based on differential evolution (DE), i.e., MOEA/D-DE, and compares the proposed algorithm with NSGA-II with the same reproduction operators on the test instances introduced in this paper. The experimental results indicate that MOEA/D could significantly outperform NSGA-II on these test instances. It suggests that decomposition based multiobjective evolutionary algorithms are very promising in dealing with complicated PS shapes.     

On the effect of reference point in MOEA/D for multi-objective optimization

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) has continuously proven effective for multi-objective optimization. So far, the effect of weight vectors and scalarizing methods in MOEA/D has been intensively studied. However, the reference point which serves as the starting point of reference lines (determined by weight vectors) is yet to be well studied. This study aims to fill in this research gap. Ideally, the ideal point of a multi-objective problem could serve as the reference point, however, since the ideal point is often unknown beforehand, the reference point has to be estimated (or specified). In this study, the effect of the reference point specified in three representative manners, i.e., pessimistic, optimistic and dynamic (from optimistic to pessimistic), is examined on three sets of benchmark problems. Each set of the problems has different degrees of difficulty in convergence and spread. Experimental results show that (i) the reference point implicitly impacts the convergence and spread performance of MOEA/D; (ii) the pessimistic specification emphasizes more of exploiting existing regions and the optimistic specification emphasizes more of exploring new regions; (iii) the dynamic specification can strike a good balance between exploitation and exploration, exhibiting good performance for most of the test problems, and thus, is commended to use for new problems.     

A novel multi-objective immune algorithm with a decomposition-based clonal selection

In recent years, a number of multi-objective immune algorithms (MOIAs) have been proposed as inspired by the information processing in biologic immune system. Since most MOIAs encourage to search around some boundary and less-crowded areas using the clonal selection principle, they have been validated to show the effectiveness on tackling various kinds of multi-objective optimization problems (MOPs). The crowding distance metric is often used in MOIAs as a diversity metric to reflect the status of population’s diversity, which is employed to clone less-crowded individuals for evolution. However, this kind of cloning may encounter some difficulties when tackling some complicated MOPs (e.g., the UF problems with variable linkages). To alleviate the above difficulties, a novel MOIA with a decomposition-based clonal selection strategy (MOIA-DCSS) is proposed in this paper. Each individual is associated to one subproblem using the decomposition approach and then the performance enhancement on each subproblem can be easily quantified. Then, a novel decomposition-based clonal selection strategy is designed to clone the solutions with the larger improvements for the subproblems, which encourages to search around these subproblems. Moreover, differential evolution is employed in MOIA-DCSS to strength the exploration ability and also to improve the population’s diversity. To evaluate the performance of MOIA-DCSS, twenty-eight test problems are used with the complicated Pareto-optimal sets and fronts. The experimental results validate the superiority of MOIA-DCSS over four state-of-the-art multi-objective algorithms (i.e., NSLS, MOEA/D-M2M, MOEA/D-DRA and MOEA/DD) and three competitive MOIAs (i.e., NNIA, HEIA, and AIMA).     

A Survey of Evolutionary Algorithms for Multi-Objective Optimization Problems With Irregular Pareto Fronts

Evolutionary algorithms have been shown to be very successful in solving multi-objective optimization problems(MOPs).However,their performance often deteriorates when solving MOPs with irregular Pareto fronts.To remedy this issue,a large body of research has been performed in recent years and many new algorithms have been proposed.This paper provides a comprehensive survey of the research on MOPs with irregular Pareto fronts.We start with a brief introduction to the basic concepts,followed by a summary of the benchmark test problems with irregular problems,an analysis of the causes of the irregularity,and real-world optimization problems with irregular Pareto fronts.Then,a taxonomy of the existing methodologies for handling irregular problems is given and representative algorithms are reviewed with a discussion of their strengths and weaknesses.Finally,open challenges are pointed out and a few promising future directions are suggested.     

基于改进MOEA/D算法的WSN覆盖优化方法*

为了优化无线传感器网络（WSN）的覆盖方法,针对MOEA/D中缺少对本代优质个体的保存和最优解集中的个体极少的两个问题,提出了粒子群优化的基于分解的多目标进化算法（MOEA/D-PSO）。通过保留种群本代优质个体,改进本地优化解集在进化过程中的搜索方向和搜索进度,弥补了MOEA/D不足。仿真实验证明,相对于MOEA/D和非支配排序遗传算法（NSGA-II）,MOEA/D-PSO所得非支配解更接近Pareto最优曲面,解集分布的均匀性和多样性表现更佳,WSN的覆盖范围更广,能量消耗更少。     

Multi-objective node deployment in WSNs: In search of an optimal trade-off among coverage,lifetime, energy consumption,and connectivity

The increased demand of Wireless Sensor Networks (WSNs) in different areas of application have intensified studies dedicated to the deployment of sensor nodes in recent past. For deployment of sensor nodes some of the key objectives that need to be satisfied are coverage of the area to be monitored, net energy consumed by the WSN, lifetime of the network, and connectivity and number of deployed sensors. In this article the sensor node deployment task has been formulated as a constrained multi-objective optimization (MO) problem where the aim is to find a deployed sensor node arrangement to maximize the area of coverage, minimize the net energy consumption, maximize the network lifetime, and minimize the number of deployed sensor nodes while maintaining connectivity between each sensor node and the sink node for proper data transmission. We assume a tree structure between the deployed nodes and the sink node for data transmission. Our method employs a recently developed and very competitive multi-objective evolutionary algorithm (MOEA) known as MOEA/D-DE that uses a decomposition approach for converting the problem of approximation of the Pareto fronts (PF) into a number of single-objective optimization problems. This algorithm employs differential evolution (DE), one of the most powerful real parameter optimizers in current use, as its search method. The original MOEA/D has been modified by introducing a new fuzzy dominance based decomposition technique. The algorithm introduces a fuzzy Pareto dominance concept to compare two solutions and uses the scalar decomposition method only when one of the solutions fails to dominate the other in terms of a fuzzy dominance level. We have compared the performance of the resulting algorithm, called MOEA/DFD, with the original MOEA/D-DE and another very popular MOEA called Non-dominated Sorting Genetic Algorithm (NSGA-II). The best trade-off solutions from MOEA/DFD based node deployment scheme have also been compared with a few single-objective node deployment schemes based on the original DE, an adaptive DE-variant (JADE), original particle swarm optimization (PSO), and a state-of-the art variant of PSO (Comprehensive Learning PSO). In all the test instances, MOEA/DFD performs better than all other algorithms. Also the proposed multi-objective formulation of the problem adds more flexibility to the decision maker for choosing the necessary threshold of the objectives to be satisfied.     

MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition

Decomposition is a basic strategy in traditional multiobjective optimization. However, it has not yet been widely used in multiobjective evolutionary optimization. This paper proposes a multiobjective evolutionary algorithm based on decomposition (MOEA/D). It decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. Each subproblem is optimized by only using information from its several neighboring subproblems, which makes MOEA/D have lower computational complexity at each generation than MOGLS and nondominated sorting genetic algorithm II (NSGA-II). Experimental results have demonstrated that MOEA/D with simple decomposition methods outperforms or performs similarly to MOGLS and NSGA-II on multiobjective 0-1 knapsack problems and continuous multiobjective optimization problems. It has been shown that MOEA/D using objective normalization can deal with disparately-scaled objectives, and MOEA/D with an advanced decomposition method can generate a set of very evenly distributed solutions for 3-objective test instances. The ability of MOEA/D with small population, the scalability and sensitivity of MOEA/D have also been experimentally investigated in this paper.