An improved evolutionary algorithm for handling many-objective optimization problems

It has been shown that the multi-objective evolutionary algorithms (MOEAs) act poorly in solving many-objective optimization problems which include more than three objectives. The research emphasis, in recent years, has been put into improving the MOEAs to enable them to solve many-objective optimization problems efficiently. In this paper, we propose a new composite fitness evaluation function, in a novel way, to select quality solutions from the objective space of a many-objective optimization problem. Using this composite function, we develop a new algorithm on a well-known NSGA-II and call it FR-NSGA-II, a fast reference point based NSGA-II. The algorithm is evaluated for producing quality solutions measured in terms of proximity, diversity and computational time. The working logic of the algorithm is explained using a bi-objective linear programming problem. Then we test the algorithm using experiments with benchmark problems from DTLZ family. We also compare FR-NSGA-II with four competitive algorithms from the extant literature to show that FR-NSGA-II will produce quality solutions even if the number of objectives is as high as 20.     

A new decomposition based evolutionary algorithm with uniform designs for many-objective optimization

For many-objective optimization problems, how to get a set of solutions with good convergence and diversity is a difficult and challenging work. In this paper, a new decomposition based evolutionary algorithm with uniform designs is proposed to achieve the goal. The proposed algorithm adopts the uniform design method to set the weight vectors which are uniformly distributed over the design space, and the size of the weight vectors neither increases nonlinearly with the number of objectives nor considers a formulaic setting. A crossover operator based on the uniform design method is constructed to enhance the search capacity of the proposed algorithm. Moreover, in order to improve the convergence performance of the algorithm, a sub-population strategy is used to optimize each sub-problem. Comparing with some efficient state-of-the-art algorithms, e.g., NSGAII-CE, MOEA/D and HypE, on six benchmark functions, the proposed algorithm is able to find a set of solutions with better diversity and convergence.     

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.     

A radial space division based evolutionary algorithm for many-objective optimization

In evolutionary many-objective optimization, diversity maintenance plays an important role in pushing the population towards the Pareto optimal front. Existing many-objective evolutionary algorithms mainly focus on convergence enhancement, but pay less attention to diversity enhancement, which may fail to obtain uniformly distributed solutions or fall into local optima. This paper proposes a radial space division based evolutionary algorithm for many-objective optimization, where the solutions in high-dimensional objective space are projected into the grid divided 2-dimensional radial space for diversity maintenance and convergence enhancement. Specifically, the diversity of the population is emphasized by selecting solutions from different grids, where an adaptive penalty based approach is proposed to select a better converged solution from the grid with multiple solutions for convergence enhancement. The proposed algorithm is compared with five state-of-the-art many-objective evolutionary algorithms on a variety of benchmark test problems. Experimental results demonstrate the competitiveness of the proposed algorithm in terms of both convergence enhancement and diversity maintenance.     

MCEDA: A novel many-objective optimization approach based on model and clustering

To solve many-objective optimization problems (MaOPs) by evolutionary algorithms (EAs), the maintenance of convergence and diversity is essential and difficult. Improved multi-objective optimization evolutionary algorithms (MOEAs), usually based on the genetic algorithm (GA), have been applied to MaOPs, which use the crossover and mutation operators of GAs to generate new solutions. In this paper, a new approach, based on decomposition and the MOEA/D framework, is proposed: model and clustering based estimation of distribution algorithm (MCEDA). MOEA/D means the multi-objective evolutionary algorithm based on decomposition. The proposed MCEDA is a new estimation of distribution algorithm (EDA) framework, which is intended to extend the application of estimation of distribution algorithm to MaOPs. MCEDA was implemented by two similar algorithm, MCEDA/B (based on bits model) and MCEDA/RM (based on regular model) to deal with MaOPs. In MCEDA, the problem is decomposed into several subproblems. For each subproblem, clustering algorithm is applied to divide the population into several subgroups. On each subgroup, an estimation model is created to generate the new population. In this work, two kinds of models are adopted, the new proposed bits model and the regular model used in RM-MEDA (a regularity model based multi-objective estimation of distribution algorithm). The non-dominated selection operator is applied to improve convergence. The proposed algorithms have been tested on the benchmark test suite for evolutionary algorithms (DTLZ). The comparison with several state-of-the-art algorithms indicates that the proposed MCEDA is a competitive and promising approach.     

A novel metric based on changes in pareto domination ratio for objective reduction of many-objective optimization problems

Abstract

Although many-objective optimisation can be simplified through reduction of redundant objectives, algorithms that perform this reduction still lack a convenient method of evaluation. In this paper, we address this deficiency by proposing a new method of evaluation, on the basis of changes in the Pareto-domination ratio after a reduction has occurred. Experimental results have shown that the proposed method can perform non- redundant objective set evaluation more accurately than existing evaluation methods, and also does not need the true Pareto front beforehand.     

A bi-layer decomposition algorithm for many-objective optimization problems

Applied Intelligence - Decomposition-based evolutionary algorithms have shown great potential in solving many-objective optimization problems (MaOPs). However, manual parameters (e.g., neighbor...     

A novel two-archive strategy for evolutionary many-objective optimization algorithm based on reference points

Current evolutionary many-objective optimization algorithms face two challenges: one is to ensure population diversity for searching the entire solution space. The other is to ensure quick convergence to the optimal solution set. In this paper, we propose a novel two-archive strategy for evolutionary many-objective optimization algorithm. The uniform archive strategy, based on reference points, is used to keep population diversity in the evolutionary process, and to ensure that an evolutionary algorithm is able to search the entire solution space. The single elite archive strategy is used to ensure that individuals with the best single objective value are able to evolve into the next generation and have more opportunities to generate offspring. This strategy aims to improve the convergence rate. Then this novel two-archive strategy is applied to improving the Non-dominated Sorting Genetic Algorithm (NSGA-III). Simulation experiments are conducted on benchmark test sets and experimental results show that our proposed algorithm with the two-archive strategy has a better performance than other state-of-art algorithms.     

Binary search based boundary elimination selection in many-objective evolutionary optimization

In many-objective optimization, the balance between convergence and diversity is hard to maintain, while the dominance resistant solutions (DRSs) could further harm the balance particularly in high-dimensional objective space. Thus, this paper proposes a novel selection strategy – boundary elimination selection based on binary search (called BESBS), trying to avoid the impact of DRSs during the optimization and achieve a good balance between the convergence and diversity simultaneously. During the environmental selection, the binary search (BS) is used to adaptively adjust the ϵ value in the ϵ-dominance relationship and assist in detecting the well-distributed neighbors for the elite solutions. Then the ϵ value obtained by BS is used for serving the boundary elimination selection (BES) to guarantee the stability of the elite population. To improve the convergence, BES is mainly designed to select individuals approximating to the ideal point. By modifying the fitness of solutions and choosing solutions in terms of the shuffled sequence of objective axis, the DRSs will be eliminated during the selection. Thus, BESBS could achieve a good balance between the convergence and diversity and avoid the impact from DRSs simultaneously. From a series of experiments with 35 instances, the experimental results have shown that BESBS is competitive against 8 state-of-art many-objective evolutionary algorithms.     

Comparison of many-objective evolutionary algorithms using performance metrics ensemble

In this study, we have thoroughly researched on performance of six state-of-the-art Multiobjective Evolutionary Algorithms (MOEAs) under a number of carefully crafted many-objective optimization benchmark problems. Each MOEA apply different method to handle the difficulty of increasing objectives. Performance metrics ensemble exploits a number of performance metrics using double elimination tournament selection and provides a comprehensive measure revealing insights pertaining to specific problem characteristics that each MOEA could perform the best. Experimental results give detailed information for performance of each MOEA to solve many-objective optimization problems. More importantly, it shows that this performance depends on two distinct aspects: the ability of MOEA to address the specific characteristics of the problem and the ability of MOEA to handle high-dimensional objective space.     

Tree decomposition and discrete optimization problems: A survey

The paper considers tree decomposition methods as applied to discrete optimization and presents relevant mathematical results. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 102–118, July–August 2007.     

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.     

Measuring the convergence and diversity of CDAS Multi-Objective Particle Swarm Optimization Algorithms: A study of many-objective problems

The interest for many-objective optimization has grown due to the limitations of Pareto dominance based Multi-Objective Evolutionary Algorithms when dealing with problems of a high number of objectives. Recently, some many-objective techniques have been proposed to avoid the deterioration of these algorithms' search ability. At the same time, the interest in the use of Particle Swarm Optimization (PSO) algorithms in multi-objective problems also grew. The PSO has been found to be very efficient to solve multi-objective problems (MOPs) and several Multi-Objective Particle Swarm Optimization (MOPSO) algorithms have been proposed. This work presents a study of the behavior of MOPSO algorithms in many-objective problems. The many-objective technique named control of dominance area of solutions (CDAS) is used on two Multi-Objective Particle Swarm Optimization algorithms. An empirical analysis is performed to identify the influence of the CDAS technique on the convergence and diversity of MOPSO algorithms using three different many-objective problems. The experimental results are compared applying quality indicators and statistical tests.     

A dimensionality reduction approach for many-objective Markov Decision Processes: Application to a water reservoir operation problem

The operation of complex environmental systems usually accounts for multiple, conflicting objectives, whose presence imposes to explicitly consider the preference structure of the parties involved. Multi-objective Markov Decision Processes are a useful mathematical framework for the resolution of such sequential, decision-making problems. However, the computational requirements of the available optimization techniques limit their application to problems involving few objectives. In real-world applications it is therefore common practice to select few, representative objectives with respect to which the problem is solved. This paper proposes a dimensionality reduction approach, based on the Non-negative Principal Component Analysis (NPCA), to aggregate the original objectives into a reduced number of principal components, with respect to which the optimization problem is solved. The approach is evaluated on the daily operation of a multi-purpose water reservoir (Tono Dam, Japan) with 10 operating objectives, and compared against a 5-objectives formulation of the same problem. Results show that the NPCA-based approach provides a better representation of the Pareto front, especially in terms of consistency and solution diversity.     

基于最小距离和聚合策略的分解多目标进化算法

针对基于帕累托（Pareto）支配的多目标进化算法在解决高维问题时选择压力降低,以及基于分解的多目标进化算法在提高收敛性和分布性的同时降低了种群多样性的问题,提出了一种基于最小距离和聚合策略的分解多目标进化算法。首先,使用基于角度分解的技术将目标空间分解为指定个数的子空间来提高种群的多样性;然后,在生成新解的过程中加入基于聚合的交叉邻域方法,使生成的新解更接近于父代解;最后,分两阶段在每个子空间内基于最小距离和聚合策略来选择解以提高收敛性和分布性。为了验证所提算法的可行性,采用标准测试函数ZDT和DTLZ进行仿真实验,结果表明所提算法的总体性能均优于经典的基于分解的多目标进化算法（MOEA/D）、MOEA/D-DE、NSGA-Ⅲ和GrEA。可见,所提算法在提高多样性的同时可以有效平衡收敛性和多样性。     

A Two-Engine interaction driven many-objective evolutionary algorithm with feasibility-aware adaptation

The infeasible parts of the objective space in many-objective optimization problems make evolutionary algorithms face difficulties in obtaining proximity and maintaining diversity simultaneously. This paper proposes a Two-Engine interaction driven many-objective Evolutionary Algorithm with feasibility-aware adaptation (TEEA) that adapts the reference vectors and evolves the population towards the true Pareto Front (PF). The two interacting engines make reference vectors always approximately evenly distributed within the current PF for providing appropriate guidance for selection. The current PF is tracked by maintaining an Individual Archive (IA) of undominated individuals, and the adaptation of reference vectors is conducted with the help of a Reference Archive (RA) that contains layers of reference vectors corresponding to different density. On CEC’2018 benchmark functions with competition standards, the experimental results of the proposed TEEA have demonstrated the expected characteristics and competitive performance.     

A hybrid ant colony optimization approach for finite element mesh decomposition

This paper examines the application of the ant colony optimization algorithm to the partitioning of unstructured adaptive meshes for parallel explicit time-stepping finite element analysis. The concept of the ant colony optimization technique for finding approximate solutions to combinatorial optimization problems is described.The application of ant colony optimization for partitioning finite element meshes based on triangular elements is described.A recursive greedy algorithm optimization method is also presented as a local optimization technique to improve the quality of the solutions given by the ant colony optimization algorithm. The partitioning is based on the recursive bisection approach.The mesh decomposition is carried out using normal and predictive modes for which the predictive mode uses a trained multilayered feed-forward neural network which estimates the number of triangular elements that will be generated after finite elements mesh generation is carried out.The performance of the proposed hybrid approach for the recursive bisection of finite element meshes is examined by decomposing two mesh examples.     

Identifying good algorithm parameters in evolutionary multi- and many-objective optimisation: A visualisation approach

Evolutionary algorithms are often highly dependent on the correct setting of their parameters, and benchmarking different parametrisations allows a user to identify which parameters offer the best performance on their given problem. Visualisation offers a way of presenting the results of such benchmarking so that a non-expert user can understand how their algorithm is performing. By examining the characteristics of their algorithm, such as convergence and diversity, the user can learn how effective their chosen algorithm parametrisation is. This paper presents a technique intended to offer this insight, by presenting the relative performance of a set of EAs optimising the same multi-objective problem in a simple visualisation. The visualisation characterises the behaviour of the algorithm in terms of known performance indicators drawn from the literature, and is capable of visualising the optimisation of many-objective problems also. The method is demonstrated with benchmark test problems from the popular DTLZ and CEC 2009 problem suites, optimising them with different parametrisations of both NSGA-II and NSGA-III, and it is shown that known characteristics of optimisers solving these problems can be observed in the visualisations resulting.     

A decomposition-based many-objective artificial bee colony algorithm with reinforcement learning

When optimizing many-objective optimization problems (MaOPs), the optimization effect is normally related to the problem types. Therefore, enhancing the generalization ability is essential to the application of the algorithms. In this paper, a novel decomposition-based Artificial bee colony algorithm (ABC) for MaOP optimization, MaOABC/D-LA, is presented to enhance the generalization ability. A reinforcement learning-based searching strategy is designed in the MaOABC/D-LA, with which the algorithm adjusts its searching actions according to their performance. And a variant of the onlooker bee mechanism is proposed to balance the optimization quality. To investigate performance of the proposed algorithm, a comparison experiment is conducted. The experimental results show that the MaOABC/D-LA outperforms the peer algorithms in efficiency and solution quality for MaOPs with different types of features. This indicates the proposed method has a definite effect on improving generalization ability.