Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions

Since the suggestion of a computing procedure of multiple Pareto-optimal solutions in multi-objective optimization problems in the early Nineties, researchers have been on the look out for a procedure which is computationally fast and simultaneously capable of finding a well-converged and well-distributed set of solutions. Most multi-objective evolutionary algorithms (MOEAs) developed in the past decade are either good for achieving a well-distributed solutions at the expense of a large computational effort or computationally fast at the expense of achieving a not-so-good distribution of solutions. For example, although the Strength Pareto Evolutionary Algorithm or SPEA (Zitzler and Thiele, 1999) produces a much better distribution compared to the elitist non-dominated sorting GA or NSGA-II (Deb et al., 2002a), the computational time needed to run SPEA is much greater. In this paper, we evaluate a recently-proposed steady-state MOEA (Deb et al., 2003) which was developed based on the epsilon-dominance concept introduced earlier(Laumanns et al., 2002) and using efficient parent and archive update strategies for achieving a well-distributed and well-converged set of solutions quickly. Based on an extensive comparative study with four other state-of-the-art MOEAs on a number of two, three, and four objective test problems, it is observed that the steady-state MOEA is a good compromise in terms of convergence near to the Pareto-optimal front, diversity of solutions, and computational time. Moreover, the epsilon-MOEA is a step closer towards making MOEAs pragmatic, particularly allowing a decision-maker to control the achievable accuracy in the obtained Pareto-optimal solutions.     

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.     

The mean–variance cardinality constrained portfolio optimization problem: An experimental evaluation of five multiobjective evolutionary algorithms

This paper compares the effectiveness of five state-of-the-art multiobjective evolutionary algorithms (MOEAs) together with a steady state evolutionary algorithm on the mean–variance cardinality constrained portfolio optimization problem (MVCCPO). The main computational challenges of the model are due to the presence of a nonlinear objective function and the discrete constraints. The MOEAs considered are the Niched Pareto genetic algorithm 2 (NPGA2), non-dominated sorting genetic algorithm II (NSGA-II), Pareto envelope-based selection algorithm (PESA), strength Pareto evolutionary algorithm 2 (SPEA2), and e-multiobjective evolutionary algorithm (e-MOEA). The computational comparison was performed using formal metrics proposed by the evolutionary multiobjective optimization community on publicly available data sets which contain up to 2196 assets.     

Vehicle power train optimization using multi-objective bird swarm algorithm

In this paper, a multi-objective bird swarm algorithm (MOBSA) is proposed to cope with multi-objective optimization problems. The algorithm is explored based on BSA which is an evolutionary algorithm suitable for single objective optimization. In this paper, non-dominated sorting approach is used to distinguish optimal solutions and parallel coordinates is applied to evaluate the distribution density of non-dominated solution and further update the external archive when it is full to overflowing, which ensure faster convergence and more widespread of Pareto front. Then, the MOBSA is adopted to optimize benchmark problems. The results demonstrate that MOBSA gets better performance compared with NSGA-II and MOPSO. Since a vehicle power train problem could be treated as a typical multi-objective optimization problem with constraints, with integration of constrained non-dominated solution, MOBSA is adopted to acquire optimal gear ratios and optimize vehicle power train. The results compared with other popular algorithm prove the proposed algorithm is more suitable for constrained multi-objective optimization problem in engineering field.

     

Handling multiple objectives with biogeography-based optimization

Biogeography-based optimization (BBO) is a new evolutionary optimization method inspired by biogeography. In this paper, BBO is extended to a multi-objective optimization, and a biogeography-based multi-objective optimization (BBMO) is introduced, which uses the cluster attribute of islands to naturally decompose the problem. The proposed algorithm makes use of nondominated sorting approach to improve the convergence ability effciently. It also combines the crowding distance to guarantee the diversity of Pareto optimal solutions. We compare the BBMO with two representative state-of-the-art evolutionary multi-objective optimization methods, non-dominated sorting genetic algorithm-II (NSGA-II) and archive-based micro genetic algorithm (AMGA) in terms of three metrics. Simulation results indicate that in most cases, the proposed BBMO is able to find much better spread of solutions and converge faster to true Pareto optimal fronts than NSGA-II and AMGA do.     

A multi-objective artificial physics optimization algorithm based on ranks of individuals

This paper proposes a multi-objective artificial physics optimization algorithm based on individuals’ ranks. Using a Pareto sorting based technique and incorporating the concept of neighborhood crowding degree, evolutionary individuals in the search space are evaluated at first. Then each individual is assigned a unique serial number in terms of its performance, which affects the mass of the individual. Thereby, the population evolves towards the direction of the Pareto-optimal front. Synchronously, the presented approach has good diversity, such that the population is spread evenly on the Pareto front. Results of simulation on a number of difficult test problems show that the proposed algorithm, with less evolutionary generations, is able to find a better spread of solutions and better convergence near the true Pareto-optimal front compared to classical multi-objective evolutionary algorithms (NSGA, SPEA, MOPSO) and to simple multi-objective artificial physics optimization algorithm.     

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.     

An efficient non-dominated sorting method for evolutionary algorithms

We present a new non-dominated sorting algorithm to generate the non-dominated fronts in multi-objective optimization with evolutionary algorithms, particularly the NSGA-II. The non-dominated sorting algorithm used by NSGA-II has a time complexity of O(MN(2)) in generating non-dominated fronts in one generation (iteration) for a population size N and M objective functions. Since generating non-dominated fronts takes the majority of total computational time (excluding the cost of fitness evaluations) of NSGA-II, making this algorithm faster will significantly improve the overall efficiency of NSGA-II and other genetic algorithms using non-dominated sorting. The new non-dominated sorting algorithm proposed in this study reduces the number of redundant comparisons existing in the algorithm of NSGA-II by recording the dominance information among solutions from their first comparisons. By utilizing a new data structure called the dominance tree and the divide-and-conquer mechanism, the new algorithm is faster than NSGA-II for different numbers of objective functions. Although the number of solution comparisons by the proposed algorithm is close to that of NSGA-II when the number of objectives becomes large, the total computational time shows that the proposed algorithm still has better efficiency because of the adoption of the dominance tree structure and the divide-and-conquer mechanism.     

A surrogate-assisted evolutionary algorithm based on the genetic diversity objective

In this work, a novel surrogate-assisted memetic algorithm is proposed which is based on the preservation of genetic diversity within the population. The aim of the algorithm is to solve multi-objective optimization problems featuring computationally expensive fitness functions in an efficient manner. The main novelty is the use of an evolutionary algorithm as global searcher that treats the genetic diversity as an objective during the evolution and uses it, together with a non-dominated sorting approach, to assign the ranks. This algorithm, coupled with a gradient-based algorithm as local searcher and a back-propagation neural network as global surrogate model, demonstrates to provide a reliable and effective balance between exploration and exploitation. A detailed performance analysis has been conducted on five commonly used multi-objective problems, each one involving distinct features that can make the convergence difficult toward the Pareto-optimal front. In most cases, the proposed algorithm outperformed the other state-of-the-art evolutionary algorithms considered in the comparison, assuring higher repeatability on the final non-dominated set, deeper convergence level and higher convergence rate. It also demonstrates a clear ability to widely cover the Pareto-optimal front with larger percentage of non-dominated solutions if compared to the total number of function evaluations.     

Data Structures in Multi-Objective Evolutionary Algorithms

Data structures used for an algorithm can have a great impact on its performance,particularly for the solution of large and complex problems,such as multi-objective optimization problems(MOPs).Multi-objective evolutionary algorithms(MOEAs) are considered an attractive approach for solving MOPs,since they are able to explore several parts of the Pareto front simultaneously.The data structures for storing and updating populations and non-dominated solutions(archives) may affect the efficiency of the search process.This article describes data structures used in MOEAs for realizing populations and archives in a comparative way,emphasizing their computational requirements and general applicability reported in the original work.     

Evolutionary trajectory planning for an industrial robot

This paper presents a novel general method for computing optimal motions of an industrial robot manipulator (AdeptOne XL robot) in the presence of fixed and oscillating obstacles. The optimization model considers the nonlinear manipulator dynamics, actuator constraints, joint limits, and obstacle avoidance. The problem has 6 objective functions, 88 variables, and 21 constraints. Two evolutionary algorithms, namely, elitist non-dominated sorting genetic algorithm (NSGA-II) and multi-objective differential evolution (MODE), have been used for the optimization. Two methods (normalized weighting objective functions and average fitness factor) are used to select the best solution tradeoffs. Two multi-objective performance measures, namely solution spread measure and ratio of non-dominated individuals, are used to evaluate the Pareto optimal fronts. Two multi-objective performance measures, namely, optimizer overhead and algorithm effort, are used to find the computational effort of the optimization algorithm. The trajectories are defined by B-spline functions. The results obtained from NSGA-II and MODE are compared and analyzed.     

Memory-based adaptive partitioning (MAP) of search space for the enhancement of convergence in Pareto-based multi-objective evolutionary algorithms

A new algorithm, dubbed memory-based adaptive partitioning (MAP) of search space, which is intended to provide a better accuracy/speed ratio in the convergence of multi-objective evolutionary algorithms (MOEAs) is presented in this work. This algorithm works by performing an adaptive-probabilistic refinement of the search space, with no aggregation in objective space. This work investigated the integration of MAP within the state-of-the-art fast and elitist non-dominated sorting genetic algorithm (NSGAII). Considerable improvements in convergence were achieved, in terms of both speed and accuracy. Results are provided for several commonly used constrained and unconstrained benchmark problems, and comparisons are made with standalone NSGAII and hybrid NSGAII-efficient local search (eLS).     

Multi-objective optimal path selection in electric vehicles

This work proposes a memory-efficient multi-objective optimization algorithm to perform optimal path selection (OPS) in electric vehicles (EVs). The proposed algorithm requires less computational time and executes efficiently on fast-processor-based embedded systems. It is a population-based simulated evolution algorithm that incorporates innovative functions for calculating the goodness of particles and performing the allocation operation. The goodness and allocation operations ensure the exploration of new paths and the preservation of Pareto-optimal solutions. We executed our algorithm on an Intel Celeron processor, which is also used in embedded systems and compared its performance with that of the non-dominated sorting genetic algorithm-II (NSGA-II). Our experiments used real road networks. The comparison shows that on an average, our algorithm found 5.5 % more Pareto-optimal solutions than NSGA-II. Therefore, our proposed algorithm is suitable for performing OPS in EVs.     

Optimal driving during electric vehicle acceleration using evolutionary algorithms

Due to the limited amount of stored battery energy it is necessary to optimally accelerate electric vehicles (EVs), especially in urban driving cycles. Moreover, a quick speed change is also important to minimize the trip time. Conversely, for comfortable driving, the jerk experienced during speed changing must be minimum. This study focuses on finding a comfortable driving strategy for EVs during speed changes by solving a multi-objective optimization problem (MOOP) with various conflicting objectives. Variants of two different competing evolutionary algorithms (EAs), NSGA-II (a non-dominated sorting multi-objective genetic algorithm) and SPEA 2 (strength Pareto evolutionary algorithm), are adopted to solve the problem. The design parameters include the acceleration value(s) with the associated duration(s) and the controller gains. The Pareto-optimal front is obtained by solving the corresponding MOOP. Suitable multi-criterion decision-making techniques are employed to select a preferred solution for practical implementation. After an extensive analysis of EA performance and keeping online implementation in mind, it was observed that NSGA-II with the crowding distance approach was the most suitable. A recently proposed innovization procedure was used to reveal salient properties associated with the obtained trade-off solutions. These solutions were analyzed to study the effectiveness of various parameters influencing comfortable driving.     

一种基于膜系统理论的多目标演化算法

提出一种用于求解多目标优化问题的基于膜系统理论的演化算法. 受膜系统理论的功能和处理化合物方式的启发,设计了求解多目标优化问题的演化操作. 此外,在表层膜中,引入了非支配排序和拥挤距离两种机制改善算法的搜索效率. 采用ZDT（Zitzler-Deb-Thiele）和DTLZ（Deb-Thiele-Laumanns-Zitzler）多目标问题对所提算法进行测试,所提算法求得的候选解既能较好地逼近真实Pareto前沿,又能满足非支配解集多样性的要求. 仿真结果表明,所提方法求解多目标优化问题是可行和有效的.     

Evolutionary multi-criteria trajectory modeling of industrial robots in the presence of obstacles

Optimal trajectory planning for robot manipulators is always a hot spot in research fields of robotics. This paper presents two new novel general methods for computing optimal motions of an industrial robot manipulator (STANFORD robot) in presence of obstacles. The problem has a multi-criterion character in which three objective functions, a maximum of 72 variables and 103 constraints are considered. The objective functions for optimal trajectory planning are minimum traveling time, minimum mechanical energy of the actuators and minimum penalty for obstacle avoidance. By far, there has been no planning algorithm designed to treat the objective functions simultaneously. When existing optimization algorithms of trajectory planning tackle the complex instances (obstacles environment), they have some notable drawbacks viz.: (1) they may fail to find the optimal path (or spend much time and memory storage to find one) and (2) they have limited capabilities when handling constraints. In order to overcome the above drawbacks, two evolutionary algorithms (Elitist non-dominated sorting genetic algorithm (NSGA-II) and multi-objective differential evolution (MODE) algorithm) are used for the optimization. Two methods (normalized weighting objective functions method and average fitness factor method) are combinedly used to select best optimal solution from Pareto optimal front. Two multi-objective performance measures (solution spread measure and ratio of non-dominated individuals) are used to evaluate strength of the Pareto optimal fronts. Two more multi-objective performance measures namely optimizer overhead and algorithm effort are used to find computational effort of NSGA-II and MODE algorithms. The Pareto optimal fronts and results obtained from various techniques are compared and analyzed.     

多目标进化算法测试问题的设计与分析

为了有效检测多目标优化进化算法的性能,从3个方面进行多目标优化测试问题的设计,即约束条件、最优解分布的均匀性、算法逼近Pareto最优前沿的难度,采用NSGA-Ⅱ算法对这些测试问题进行仿真实验,并将算法求得的最优解可视化。结果显示,测试问题能够有效检测算法在上述3方面的性能。     

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

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

Multi-objective optimization of machining and micro-machining processes using non-dominated sorting teaching–learning-based optimization algorithm

Selection of optimum machining parameters is vital to the machining processes in order to ensure the quality of the product, reduce the machining cost, increasing the productivity and conserve resources for sustainability. Hence, in this work a posteriori multi-objective optimization algorithm named as Non-dominated Sorting Teaching–Learning-Based Optimization (NSTLBO) is applied to solve the multi-objective optimization problems of three machining processes namely, turning, wire-electric-discharge machining and laser cutting process and two micro-machining processes namely, focused ion beam micro-milling and micro wire-electric-discharge machining. The NSTLBO algorithm is incorporated with non-dominated sorting approach and crowding distance computation mechanism to maintain a diverse set of solutions in order to provide a Pareto-optimal set of solutions in a single simulation run. The results of the NSTLBO algorithm are compared with the results obtained using GA, NSGA-II, PSO, iterative search method and MOTLBO and are found to be competitive. The Pareto-optimal set of solutions for each optimization problem is obtained and reported. These Pareto-optimal set of solutions will help the decision maker in volatile scenarios and are useful for real production systems.     

An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times

Due to its simplicity yet powerful search ability, iterated local search (ILS) has been widely used to tackle a variety of single-objective combinatorial optimization problems. However, applying ILS to solve multi-objective combinatorial optimization problems is scanty. In this paper we design a multi-objective ILS (MOILS) to solve the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times to minimize the makespan and total weighted tardiness of all jobs. In the MOILS, we design a Pareto-based variable depth search in the multi-objective local search phase. The search depth is dynamically adjusted during the search process of the MOILS to strike a balance between exploration and exploitation. We incorporate an external archive into the MOILS to store the non-dominated solutions and provide initial search points for the MOILS to escape from local optima traps. We compare the MOILS with several multi-objective evolutionary algorithms (MOEAs) shown to be effective for treating the multi-objective permutation flowshop scheduling problem in the literature. The computational results show that the proposed MOILS outperforms the MOEAs.