An orthogonal multi-objective evolutionary algorithm for multi-objective optimization problems with constraints

In this paper, an orthogonal multi-objective evolutionary algorithm (OMOEA) is proposed for multi-objective optimization problems (MOPs) with constraints. Firstly, these constraints are taken into account when determining Pareto dominance. As a result, a strict partial-ordered relation is obtained, and feasibility is not considered later in the selection process. Then, the orthogonal design and the statistical optimal method are generalized to MOPs, and a new type of multi-objective evolutionary algorithm (MOEA) is constructed. In this framework, an original niche evolves first, and splits into a group of sub-niches. Then every sub-niche repeats the above process. Due to the uniformity of the search, the optimality of the statistics, and the exponential increase of the splitting frequency of the niches, OMOEA uses a deterministic search without blindness or stochasticity. It can soon yield a large set of solutions which converges to the Pareto-optimal set with high precision and uniform distribution. We take six test problems designed by Deb, Zitzler et al., and an engineering problem (W) with constraints provided by Ray et al. to test the new technique. The numerical experiments show that our algorithm is superior to other MOGAS and MOEAs, such as FFGA, NSGAII, SPEA2, and so on, in terms of the precision, quantity and distribution of solutions. Notably, for the engineering problem W, it finds the Pareto-optimal set, which was previously unknown.     

基于正交设计的多目标演化算法

提出一种基于正交设计的多目标演化算法以求解多目标优化问题(MOPs)．它的特点在于：(1)用基于正交数组的均匀搜索代替经典EA的随机性搜索,既保证了解分布的均匀性,又保证了收敛的快速性;(2)用统计优化方法繁殖后代,不仅提高了解的精度,而且加快了收敛速度;(3)实验结果表明,对于双目标的MOPs,新算法在解集分布的均匀性、多样性与解精确性及算法收敛速度等方面均优于SPEA;(4)用于求解一个带约束多目标优化工程设计问题,它得到了最好的结果——Pareto最优解,在此之前,此问题的Pareto最优解是未知的．     

A dominance tree and its application in evolutionary multi-objective optimization

Most contemporary multi-objective evolutionary algorithms (MOEAs) store and handle a population with a linear list, and this may impose high computational complexities on the comparisons of solutions and the fitness assignment processes. This paper presents a data structure for storing the whole population and their dominating information in MOEAs. This structure, called a Dominance Tree (DT), is a binary tree that can effectively and efficiently store three-valued relations (namely dominating, dominated or non-dominated) among vector values. This paper further demonstrates DT’s potential applications in evolutionary multi-objective optimization with two cases. The first case utilizes the DT to improve NSGA-II as a fitness assignment strategy. The second case demonstrates a DT-based MOEA (called a DTEA), which is designed by leveraging the favorable properties of the DT. The simulation results show that the DT-improved NSGA-II is significantly faster than NSGA-II. Meanwhile, DTEA is much faster than SPEA2, NSGA-II and an improved version of NSGA-II. On the other hand, in regard to converging to the Pareto optimal front and maintaining the diversity of solutions, DT-improved NSGA-II and DTEA are found to be competitive with NSGA-II and SPEA2.     

A fast and elitist multiobjective genetic algorithm: NSGA-II

Multi-objective evolutionary algorithms (MOEAs) that use non-dominated sorting and sharing have been criticized mainly for: (1) their O(MN³) computational complexity (where M is the number of objectives and N is the population size); (2) their non-elitism approach; and (3) the need to specify a sharing parameter. In this paper, we suggest a non-dominated sorting-based MOEA, called NSGA-II (Non-dominated Sorting Genetic Algorithm II), which alleviates all of the above three difficulties. Specifically, a fast non-dominated sorting approach with O(MN²) computational complexity is presented. Also, a selection operator is presented that creates a mating pool by combining the parent and offspring populations and selecting the best N solutions (with respect to fitness and spread). Simulation results on difficult test problems show that NSGA-II is able, for most problems, to find a much better spread of solutions and better convergence near the true Pareto-optimal front compared to the Pareto-archived evolution strategy and the strength-Pareto evolutionary algorithm - two other elitist MOEAs that pay special attention to creating a diverse Pareto-optimal front. Moreover, we modify the definition of dominance in order to solve constrained multi-objective problems efficiently. Simulation results of the constrained NSGA-II on a number of test problems, including a five-objective, seven-constraint nonlinear problem, are compared with another constrained multi-objective optimizer, and the much better performance of NSGA-II is observed     

基于邻域竞赛的多目标优化算法

传统多目标优化算法（Multi-objective evolution algorithms,MOEAs）的基本框架大致分为两部分:首先是收敛性保持,采用Pareto支配方法将种群分成若干非支配层;其次是分布性保持,在临界层中,采用分布性保持机制维持种群的分布性.然而在处理高维优化问题（Many-objective optimization problems,MOPs）（目标维数大于3）时,随着目标维数的增加,种群的收敛性和分布性的冲突加剧,Pareto支配关系比较个体优劣的能力也迅速下降,此时传统的MOEA已不再适用于高维优化问题.鉴于此,本文提出了一种基于邻域竞赛的多目标优化算法（Evolutionary algorithm based on neighborhood competition for multi-objective optimization,NCEA）.NCEA首先将个体的各个目标之和作为个体的收敛性估计;然后,计算当前个体向量与收敛性最好的个体向量之间的夹角,并将其作为当前个体的邻域估计;最后,通过邻域竞赛方法将问题划分为若干个相互关联的子问题并逐步优化.为了验证NCEA的有效性,本文选取5个优秀的算法与NCEA进行对比实验.通过对比实验验证,NCEA具有较强的竞争力,能同时保持良好的收敛性和分布性.     

基于多目标进化算法的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更好。     

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

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

Comparison of multi-objective evolutionary algorithms in hybrid Kansei engineering system for product form design

Understanding the affective needs of customers is crucial to the success of product design. Hybrid Kansei engineering system (HKES) is an expert system capable of generating products in accordance with the affective responses. HKES consists of two subsystems: forward Kansei engineering system (FKES) and backward Kansei engineering system (BKES). In previous studies, HKES was based primarily on single-objective optimization, such that only one optimal design was obtained in a given simulation run. The use of multi-objective evolutionary algorithm (MOEA) in HKES was only attempted using the non-dominated sorting genetic algorithm-II (NSGA-II), such that very little work has been conducted to compare different MOEAs. In this paper, we propose an approach to HKES combining the methodologies of support vector regression (SVR) and MOEAs. In BKES, we constructed predictive models using SVR. In FKES, optimal design alternatives were generated using MOEAs. Representative designs were obtained using fuzzy c-means algorithm for clustering the Pareto front into groups. To enable comparison, we employed three typical MOEAs: NSGA-II, the Pareto envelope-based selection algorithm-II (PESA-II), and the strength Pareto evolutionary algorithm-2 (SPEA2). A case study of vase form design was provided to demonstrate the proposed approach. Our results suggest that NSGA-II has good convergence performance and hybrid performance; in contrast, SPEA2 provides the strong diversity required by designers. The proposed HKES is applicable to a wide variety of product design problems, while providing creative design ideas through the exploration of numerous Pareto optimal solutions.     

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.     

一个SPEA改进算法及其收敛性分析

SPEA是一种多目标优化算法。与其它多目标进化算法相比,SPEA算法具有设置参数少、解在空间分布均匀等优点。本文引入多点交叉和Cauchy变异对SPEA算法的收敛速度进行了改进,并对其收敛性进行了分析,文中给出的仿真算例证实了改进方法的有效性。     

A polar-based guided multi-objective evolutionary algorithm to search for optimal solutions interested by decision-makers in a logistics network design problem

In practical multi-objective optimization problems, respective decision-makers might be interested in some optimal solutions that have objective values closer to their specified values. Guided multi-objective evolutionary algorithms (guided MOEAs) have been significantly used to guide their evolutionary search direction toward these optimal solutions using by decision makers. However, most guided MOEAs need to be iteratively and interactively evaluated and then guided by decision-makers through re-formulating or re-weighting objectives, and it might negatively affect the algorithms performance. In this paper, a novel guided MOEA that uses a dynamic polar-based region around a particular point in objective space is proposed. Based on the region, new selection operations are designed such that the algorithm can guide the evolutionary search toward optimal solutions that are close to the particular point in objective space without the iterative and interactive efforts. The proposed guided MOEA is tested on the multi-criteria decision-making problem of flexible logistics network design with different desired points. Experimental results show that the proposed guided MOEA outperforms two most effective guided and non-guided MOEAs, R-NSGA-II and NSGA-II.     

DOPGA: a new fitness assignment scheme for multi-objective evolutionary algorithms

In this article, a new fitness assignment scheme to evaluate the Pareto-optimal solutions for multi-objective evolutionary algorithms is proposed. The proposed DOmination Power of an individual Genetic Algorithm (DOPGA) method can order the individuals in a form in which each individual (the so-called solution) could have a unique rank. With this new method, a multi-objective problem can be treated as if it were a single-objective problem without drastically deviating from the Pareto definition. In DOPGA, relative position of a solution is embedded into the fitness assignment procedures. We compare the performance of the algorithm with two benchmark evolutionary algorithms (Strength Pareto Evolutionary Algorithm (SPEA) and Strength Pareto Evolutionary Algorithm 2 (SPEA2)) on 12 unconstrained bi-objective and one tri-objective test problems. DOPGA significantly outperforms SPEA on all test problems. DOPGA performs better than SPEA2 in terms of convergence metric on all test problems. Also, Pareto-optimal solutions found by DOPGA spread better than SPEA2 on eight of 13 test problems.     

An adaptive evolutionary multi-objective approach based on simulated annealing

A multi-objective optimization problem can be solved by decomposing it into one or more single objective subproblems in some multi-objective metaheuristic algorithms. Each subproblem corresponds to one weighted aggregation function. For example, MOEA/D is an evolutionary multi-objective optimization (EMO) algorithm that attempts to optimize multiple subproblems simultaneously by evolving a population of solutions. However, the performance of MOEA/D highly depends on the initial setting and diversity of the weight vectors. In this paper, we present an improved version of MOEA/D, called EMOSA, which incorporates an advanced local search technique (simulated annealing) and adapts the search directions (weight vectors) corresponding to various subproblems. In EMOSA, the weight vector of each subproblem is adaptively modified at the lowest temperature in order to diversify the search toward the unexplored parts of the Pareto-optimal front. Our computational results show that EMOSA outperforms six other well established multi-objective metaheuristic algorithms on both the (constrained) multi-objective knapsack problem and the (unconstrained) multi-objective traveling salesman problem. Moreover, the effects of the main algorithmic components and parameter sensitivities on the search performance of EMOSA are experimentally investigated.     

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

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

Approximating the Pareto-front of a planar bi-objective competitive facility location and design problem

A bi-objective competitive facility location and design problem is considered. The problem of obtaining a complete representation of the efficient set and its corresponding Pareto-front has been previously tackled through exact general methods, but they require high computational effort. In this work, we propose a new evolutionary multi-objective optimization algorithm, named FEMOEA, which deals with the problem at hand in a fast and efficient way. It combines ideas from different multi-objective and single-objective optimization evolutionary algorithms, although it also incorporates new devices which help to reduce the computational requirements, and also to improve the quality of the provided solutions. The performance of the algorithm is analyzed by comparing it to other (meta)heuristics previously proposed in the literature. In particular, the reference algorithms MOEA/D, SPEA2 and NSGA-II have been considered. A comprehensive computational study shows that the new heuristic method outperforms, on average, the three heuristic algorithms. Additionally, it reduces, on average, the computing time of the exact methods by approximately 99%, and this offering high-quality discrete approximations of the true Pareto-front.     

Multiobjective evolutionary algorithms for electric power dispatch problem

The potential and effectiveness of the newly developed Pareto-based multiobjective evolutionary algorithms (MOEA) for solving a real-world power system multiobjective nonlinear optimization problem are comprehensively discussed and evaluated in this paper. Specifically, nondominated sorting genetic algorithm, niched Pareto genetic algorithm, and strength Pareto evolutionary algorithm (SPEA) have been developed and successfully applied to an environmental/economic electric power dispatch problem. A new procedure for quality measure is proposed in this paper in order to evaluate different techniques. A feasibility check procedure has been developed and superimposed on MOEA to restrict the search to the feasible region of the problem space. A hierarchical clustering algorithm is also imposed to provide the power system operator with a representative and manageable Pareto-optimal set. Moreover, an approach based on fuzzy set theory is developed to extract one of the Pareto-optimal solutions as the best compromise one. These multiobjective evolutionary algorithms have been individually examined and applied to the standard IEEE 30-bus six-generator test system. Several optimization runs have been carried out on different cases of problem complexity. The results of MOEA have been compared to those reported in the literature. The results confirm the potential and effectiveness of MOEA compared to the traditional multiobjective optimization techniques. In addition, the results demonstrate the superiority of the SPEA as a promising multiobjective evolutionary algorithm to solve different power system multiobjective optimization problems.     

Diagnostic assessment of search controls and failure modes in many-objective evolutionary optimization

The growing popularity of multiobjective evolutionary algorithms (MOEAs) for solving many-objective problems warrants the careful investigation of their search controls and failure modes. This study contributes a new diagnostic assessment framework for rigorously evaluating the effectiveness, reliability, efficiency, and controllability of MOEAs as well as identifying their search controls and failure modes. The framework is demonstrated using the recently introduced Borg MOEA, [Formula: see text]-NSGA-II, [Formula: see text]-MOEA, IBEA, OMOPSO, GDE3, MOEA/D, SPEA2, and NSGA-II on 33 instances of 18 test problems from the DTLZ, WFG, and CEC 2009 test suites. The diagnostic framework exploits Sobol's variance decomposition to provide guidance on the algorithms' non-separable, multi-parameter controls when performing a many-objective search. This study represents one of the most comprehensive empirical assessments of MOEAs ever completed.     

针对非均匀问题的多目标进化算法

文章针对解集分布非均匀的问题,提出了一种新的多目标进化算法,称之为GNEA(带小生境的网格进化算法)。在算法中,针对分均匀问题的特点,采用了小生境技术来保持解集的局部非均匀分布,以及网格技术来保证整个解集的分布度。为了让GNEA运行效率更高,提出了用庄家法构造非支配集的方法。最后通过与其他算法进行比较,验证了算法具有较好的运行效率,且在解决非均匀问题上是一种有效的多目标进化算法。     

A hybrid multi-objective evolutionary algorithm with feedback mechanism

Exploration and exploitation are two cornerstones for multi-objective evolutionary algorithms (MOEAs). To balance exploration and exploitation, we propose an efficient hybrid MOEA (i.e., MOHGD) by integrating multiple techniques and feedback mechanism. Multiple techniques include harmony search, genetic operator and differential evolution, which can improve the search diversity. Whereas hybrid selection mechanism contributes to the search efficiency by integrating the advantages of the static and adaptive selection scheme. Therefore, multiple techniques based on the hybrid selection strategy can effectively enhance the exploration ability of the MOHGD. Besides, we propose a feedback strategy to transfer some non-dominated solutions from the external archive to the parent population. This feedback strategy can strengthen convergence toward Pareto optimal solutions and improve the exploitation ability of the MOHGD. The proposed MOHGD has been evaluated on benchmarks against other state of the art MOEAs in terms of convergence, spread, coverage, and convergence speed. Computational results show that the proposed MOHGD is competitive or superior to other MOEAs considered in this paper.     

一种改进的基于差分进化的多目标进化算法

近年来运用进化算法（EAs）解决多目标优化问题（Multi-objective Optimization Problems MOPs）引起了各国学者们的关注。作为一种基于种群的优化方法,EAs提供了一种在一次运行后得到一组优化的解的方法。差分进化（DE）算法是EA的一个分支,最开始是用来解决连续函数空间的问题。提出了一种改进的基于差分进化的多目标进化算法（CDE）,并且将它与另外两个经典的多目标进化算法（MOEAs）NSGA-II和SPEA2进行了对比实验。