FEMOEA: a fast and efficient multi-objective evolutionary algorithm

A multi-objective evolutionary algorithm which can be applied to many nonlinear multi-objective optimization problems is proposed. Its aim is to quickly obtain a fixed size Pareto-front approximation. It adapts ideas from different multi-objective evolutionary algorithms, but also incorporates new devices. In particular, the search in the feasible region is carried out on promising areas (hyperspheres) determined by a radius value, which decreases as the optimization procedure evolves. This mechanism helps to maintain a balance between exploration and exploitation of the search space. Additionally, a new local search method which accelerates the convergence of the population towards the Pareto-front, has been incorporated. It is an extension of the local optimizer SASS and improves a given solution along a search direction (no gradient information is used). Finally, a termination criterion has also been proposed, which stops the algorithm if the distances between the Pareto-front approximations provided by the algorithm in three consecutive iterations are smaller than a given tolerance. To know how far two of those sets are from each other, a modification of the well-known Hausdorff distance is proposed. In order to analyze the algorithm performance, it has been compared to the reference algorithms NSGA-II and SPEA2 and the state-of-the-art algorithms MOEA/D and SMS-EMOA. Several quality indicators have been considered, namely, hypervolume, average distance, additive epsilon indicator, spread and spacing. According to the computational tests performed, the new algorithm, named FEMOEA, outperforms the other algorithms.     

Multi-objective simulation-based evolutionary algorithm for an aircraft spare parts allocation problem

Simulation optimization has received considerable attention from both simulation researchers and practitioners. In this study, we develop a solution framework which integrates multi-objective evolutionary algorithm (MOEA) with multi-objective computing budget allocation (MOCBA) method for the multi-objective simulation optimization problem. We apply it on a multi-objective aircraft spare parts allocation problem to find a set of non-dominated solutions. The problem has three features: huge search space, multi-objective, and high variability. To address these difficulties, the solution framework employs simulation to estimate the performance, MOEA to search for the more promising designs, and MOCBA algorithm to identify the non-dominated designs and efficiently allocate the simulation budget. Some computational experiments are carried out to test the effectiveness and performance of the proposed solution framework.     

A new orthogonal evolutionary algorithm based on decomposition for multi-objective optimization

The diversity of solutions is very important for multi-objective evolutionary algorithms to deal with multi-objective optimization problems (MOPs). In order to achieve the goal, a new orthogonal evolutionary algorithm based on objective space decomposition (OEA/D) is proposed in this paper. To be specific, the objective space of an MOP is firstly decomposed into a set of sub-regions via a set of direction vectors, and OEA/D maintains the diversity of solutions by making each sub-region have a solution to the maximum extent. Also, the quantization orthogonal crossover (QOX) is used to enhance the search ability of OEA/D. Experimental studies have been conducted to compare this proposed algorithm with classic MOEA/D, NSGAII, NICA and D2MOPSO. Simulation results on six multi-objective benchmark functions show that the proposed algorithm is able to obtain better diversity and more evenly distributed Pareto fronts than other four algorithms.     

Hybrid immune algorithm with Lamarckian local search for multi-objective optimization

Lamarckian learning has been introduced into evolutionary computation as local search mechanism. The relevant research topic, memetic computation, has received significant amount of interests. In this study, a novel Lamarckian learning strategy is designed for improving the Nondominated Neighbor Immune Algorithm, a novel hybrid multi-objective optimization algorithm, Multi-objective Lamarckian Immune Algorithm (MLIA), is proposed. The Lamarckian learning performs a greedy search which proceeds towards the goal along the direction obtained by Tchebycheff approach and generates the improved progenies or improved decision vectors, so single individual will be optimized locally and the newcomers yield an enhanced exploitation around the nondominated individuals in less-crowded regions of the current trade-off front. Simulation results based on twelve benchmark problems show that MLIA outperforms the original immune algorithm and NSGA-II in approximating Pareto-optimal front in most of the test problems. When compared with the state of the art algorithm MOEA/D, MLIA shows better performance in terms of the coverage of two sets metric, although it is laggard in the hypervolume metric.     

A novel multi-objective memetic algorithm based on opposition-based self-adaptive differential evolution

Under the framework of evolutionary paradigms, many evolutionary algorithms have been designed for handling multi-objective optimization problems. Each of the different algorithms may display exceptionally good performance in certain optimization problems, but none of them can be completely superior over one another. As such, different evolutionary algorithms are being synthesized to complement each other in view of their strengths and the limitations inherent in them. In this study, the novel memetic algorithm known as the Opposition-based Self-adaptive Hybridized Differential Evolution algorithm (OSADE) is being comprehensively investigated through a comparative study with some state-of-the-art algorithms, such as NSGA-II, non-dominated sorting Differential Evolution (NSDE), MOEA/D-SBX, MOEA/D-DE and the Multi-objective Evolutionary Gradient Search (MO-EGS) by using a suite of different benchmark problems. Through the experimental results that are presented by employing the Inverted Generational Distance (IGD) and the Hausdorff Distance performance indicators, it is seen that OSADE is able to achieve competitive, if not better, performance when compared to the other algorithms in this study.     

A fast Pareto genetic algorithm approach for solving expensive multiobjective optimization problems

We present a new multiobjective evolutionary algorithm (MOEA), called fast Pareto genetic algorithm (FastPGA), for the simultaneous optimization of multiple objectives where each solution evaluation is computationally- and/or financially-expensive. This is often the case when there are time or resource constraints involved in finding a solution. FastPGA utilizes a new ranking strategy that utilizes more information about Pareto dominance among solutions and niching relations. New genetic operators are employed to enhance the proposed algorithm’s performance in terms of convergence behavior and computational effort as rapid convergence is of utmost concern and highly desired when solving expensive multiobjective optimization problems (MOPs). Computational results for a number of test problems indicate that FastPGA is a promising approach. FastPGA yields similar performance to that of the improved nondominated sorting genetic algorithm (NSGA-II), a widely-accepted benchmark in the MOEA research community. However, FastPGA outperforms NSGA-II when only a small number of solution evaluations are permitted, as would be the case when solving expensive MOPs.     

Evolutionary multiobjective optimization in noisy problem environments

This paper presents a multiobjective evolutionary algorithm (MOEA) capable of handling stochastic objective functions. We extend a previously developed approach to solve multiple objective optimization problems in deterministic environments by incorporating a stochastic nondomination-based solution ranking procedure. In this study, concepts of stochastic dominance and significant dominance are introduced in order to better discriminate among competing solutions. The MOEA is applied to a number of published test problems to assess its robustness and to evaluate its performance relative to NSGA-II. Moreover, a new stopping criterion is proposed, which is based on the convergence velocity of any MOEA to the true Pareto optimal front, even if the exact location of the true front is unknown. This stopping criterion is especially useful in real-world problems, where finding an appropriate point to terminate the search is crucial.     

HMOAM: hybrid multi-objective genetic optimization for facial analysis by appearance model

Successful hybridization of single-objective evolutionary algorithm with gradient based methods has shown promising results. However, studies of hybridized Multi-Objective Evolutionary Algorithm are limited, especially in the domain of image analysis. This paper presents a novel methodology of hybridization of multi-objective genetic algorithm for the real world optimization problem of facial analysis of multiple camera images by 2.5D Appearance Model. Facial large lateral movements make acquisition and analysis of facial images by single camera inefficient. Moreover, non-convex multi-dimensional search space formed by the face search by appearance model requires an efficient optimization methodology. Currently, with wide availability of inexpensive cameras, a multi-view system is as practical as a single-view system. To manage these multiple informations, multi-objective genetic algorithm is employed to optimize the face search. To efficiently tackle the problem of non-convexity of the search space, hybridization of NSGA-II (Non-dominated Sorting Genetic Algorithm) with Gradient Descent is proposed in this paper. For this hybridization, we propose a gradient operator in NSGA-II, which computes gradients of the solutions in conjunction with the existing operator of mutation. Thus, it does not increase the computational cost of the system. Another proposition includes a unique method of calculating the relevant information of each camera in a multiple camera system which makes the hybridization procedure efficient and robust. Our proposed algorithm is applied on different facial poses of CMU-PIE database, webcam face images and synthetic face images, and the results are compared with a single view system and a non-hybrid multiple camera system. Simulation results validate the efficiency, accuracy and robustness achieved.     

Multi-objective and prioritized berth allocation in container ports

This paper considers a berth allocation problem (BAP) which requires the determination of exact berthing times and positions of incoming ships in a container port. The problem is solved by optimizing the berth schedule so as to minimize concurrently the three objectives of makespan, waiting time, and degree of deviation from a predetermined priority schedule. These objectives represent the interests of both port and ship operators. Unlike most existing approaches in the literature which are single-objective-based, a multi-objective evolutionary algorithm (MOEA) that incorporates the concept of Pareto optimality is proposed for solving the multi-objective BAP. The MOEA is equipped with three primary features which are specifically designed to target the optimization of the three objectives. The features include a local search heuristic, a hybrid solution decoding scheme, and an optimal berth insertion procedure. The effects that each of these features has on the quality of berth schedules are studied.     

Approximating the irregularly shaped Pareto front of multi-objective reservoir flood control operation problem

Decomposition based multi-objective evolutionary algorithm (MOEA/D) has been proved to be effective on multi-objective optimization problems. However, it fails to achieve satisfactory coverage and uniformity on problems with irregularly shaped Pareto fronts, like the reservoir flood control operation (RFCO) problem. To enhance the performance of MOEA/D on the real-world RFCO problem, a Pareto front relevant (PFR) decomposition method is developed in this paper. Different front the decomposition method in the original MOEA/D which is based on a unique reference point (i.e. the estimated ideal point), the PFR decomposition method uses a set of reference points which are uniformly sampled from the fitting model of the obtained Pareto front. As a result, the PFR decomposition method can provide more flexible adaptation to the Pareto front shapes of the target problems. Experimental studies on benchmark problems and typical RFCO problems at Ankang reservoir have illustrated that the proposed PFR decomposition method significantly improves the adaptivity of MOEA/D to the complex Pareto front shape of the RFCO problem and performs better both in terms of coverage and uniformity.     

New simulation-based frameworks for multi-objective reliability-based design optimization of structures

In the present study, two new simulation-based frameworks are proposed for multi-objective reliability-based design optimization (MORBDO). The first is based on hybrid non-dominated sorting weighted simulation method (NSWSM) in conjunction with iterative local searches that is efficient for continuous MORBDO problems. According to NSWSM, uniform samples are generated within the design space and, then, the set of feasible samples are separated. Thereafter, the non-dominated sorting operator is employed to extract the approximated Pareto front. The iterative local sample generation is then performed in order to enhance the accuracy, diversity, and increase the extent of non-dominated solutions. In the second framework, a pseudo-double loop algorithm is presented based on hybrid weighted simulation method (WSM) and the Non-dominated Sorting Genetic Algorithm II (NSGA-II) that is efficient for problems including both discrete and continuous variables. According to hybrid WSM-NSGA-II, proper non-dominated solutions are produced in each generation of NSGA-II and, subsequently, WSM evaluates the reliability level of each candidate solution until the algorithm converges to the true Pareto solutions. The valuable characteristic of presented approaches is that only one simulation run is required for WSM during entire optimization process, even if solutions for different levels of reliability be desired. Illustrative examples indicate that NSWSM with the proposed local search strategy is more efficient for small dimension continuous problems. However, WSM-NSGA-II outperforms NSWSM in terms of solutions quality and computational efficiency, specifically for discrete MORBDOs. Employing global optimizer in WSM-NSGA-II provided more accurate results with lower samples than NSWSM.     

A hybrid multi-objective evolutionary algorithm based on NSGA-II for practical scheduling with release times in steel plants

The hot metal is produced from the blast furnaces in the iron plant and should be processed as soon as possible in the subsequent steel plant for energy saving. Therefore, the release times of hot metal have an influence on the scheduling of a steel plant. In this paper, the scheduling problem with release times for steel plants is studied. The production objectives and constraints related to the release times are clarified, and a new multi-objective scheduling model is built. For the solving of the multi-objective optimization, a hybrid multi-objective evolutionary algorithm based on non-dominated sorting genetic algorithm-II (NSGA-II) is proposed. In the hybrid multi-objective algorithm, an efficient decoding heuristic (DH) and a non-dominated solution construction method (NSCM) are proposed based on the problem-specific characteristics. During the evolutionary process, individuals with different solutions may have a same chromosome because the NSCM constructs non-dominated solutions just based on the solution found by DH. Therefore, three operations in the original NSGA-II process are modified to avoid identical chromosomes in the evolutionary operations. Computational tests show that the proposed hybrid algorithm based on NSGA-II is feasible and effective for the multi-objective scheduling with release times.     

A fast steady-state <Emphasis Type="Italic">ε</Emphasis>-dominance multi-objective evolutionary algorithm

Multi-objective evolutionary algorithms (MOEAs) have become an increasingly popular tool for design and optimization tasks in real-world applications. Most of the popular baseline algorithms are pivoted on the use of Pareto-ranking (that is empirically inefficient) to improve the convergence to the Pareto front of a multi-objective optimization problem. This paper proposes a new ε-dominance MOEA (EDMOEA) which adopts pair-comparison selection and steady-state replacement instead of the Pareto-ranking. The proposed algorithm is an elitist algorithm with a new preservation technique of population diversity based on the ε-dominance relation. It is demonstrated that superior results could be obtained by the EDMOEA compared with other algorithms: NSGA-II, SPEA2, IBEA, ε-MOEA, PESA and PESA-II on test problems. The EDMOEA is able to converge to the Pareto optimal set much faster especially on the ZDT test functions with a large number of decision variables.     

基于网格化管理视角下灾后应急物流决策模型与算法研究

灾害发生后,应急资源的需求预测与应急配送中心的合理选址是实现高效救援的关键。本文通过在网格化管理视角下的信息更新将应急救援过程划分为多个阶段,在开展救援的过程中实现救援信息收集和救援预测的同步开展,建立一种多阶段带时间约束的应急救援物资配送响应-时效性的选址模型。借助遗传算法(NSGA-II),实现了基于编码结构独立、路径相互关联基础上的多目标规划求解。本研究的决策模型及算法有着较好的搜索与寻优能力,对实际救援开展具有指导意义。     

Robustness in multi-objective optimization using evolutionary algorithms

This work discusses robustness assessment during multi-objective optimization with a Multi-Objective Evolutionary Algorithm (MOEA) using a combination of two types of robustness measures. Expectation quantifies simultaneously fitness and robustness, while variance assesses the deviation of the original fitness in the neighborhood of the solution. Possible equations for each type are assessed via application to several benchmark problems and the selection of the most adequate is carried out. Diverse combinations of expectation and variance measures are then linked to a specific MOEA proposed by the authors, their selection being done on the basis of the results produced for various multi-objective benchmark problems. Finally, the combination preferred plus the same MOEA are used successfully to obtain the fittest and most robust Pareto optimal frontiers for a few more complex multi-criteria optimization problems.     

Improving the non-dominated sorting genetic algorithm using a gene-therapy method for multi-objective optimization

The non-dominate sorting genetic algorithmic-II (NSGA-II) is an effective algorithm for finding Pareto-optimal front for multi-objective optimization problems. To further enhance the advantage of the NSGA-II, this study proposes an evaluative-NSGA-II (E-NSGA-II) in which a novel gene-therapy method incorporates into the crossover operation to retain superior schema patterns in evolutionary population and enhance its solution capability. The merit of each select gene in a crossover chromosome is estimated by exchanging the therapeutic genes in both mating chromosomes and observing their fitness differentiation. Hence, the evaluative crossover operation can generate effective genomes based on the gene merit without explicitly analyzing the solution space. Experiments for nine unconstrained multi-objective benchmarks and four constrained problems show that E-NSGA-II can find Pareto-optimal solutions in all test cases with better convergence and diversity qualities than several existing algorithms.     

A new multi-objective self-organizing optimization algorithm (MOSOA) for spatial optimization problems

Spatial planning is an important and complex activity. It includes land use planning and resource allocation as basic components. An abundance of papers can be found in the literature related to each one of these two aspects separately. On the contrary, a much smaller number of research reports deal with both aspects simultaneously. This paper presents an innovative evolutionary algorithm for treating combined land use planning and resource allocation problems. The new algorithm performs optimization on a cellular automaton domain, applying suitable transition rules on the individual neighbourhoods. The optimization process is multi-objective, based on non-domination criteria and self-organizing. It produces a Pareto front thus offering an advantage to the decision maker, in comparison to methods based on weighted-sum objective functions. Moreover, the present multi-objective self-organizing algorithm (MOSOA) can handle both local and global spatial constraints. A combined land use and water allocation problem is treated, in order to illustrate the cellular automaton optimization approach. Water is allocated after pumping from an aquifer, thus contributing a nonlinearity to the objective function. The problem is bi-objective aiming at (a) the minimization of soil and groundwater pollution and (b) the maximization of economic profit. An ecological and a socioeconomic constraint are imposed: (a) Groundwater levels at selected places are kept above prescribed thresholds. (b) Land use quota is predefined. MOSOA is compared to a standard multi-objective genetic algorithm and is shown to yield better results both with respect to the Pareto front and to the degree of compactness. The latter is a highly desirable feature of a land use pattern. In the land use literature, compactness is part of the objective function or of the constraints. In contrast, the present approach renders compactness as an emergent result.     

基于拟态物理学的约束多目标共轭梯度混合算法

在拟态物理学优化算法APO的基础上,将一种基于序值的无约束多目标算法RMOAPO的思想引入到约束多目标优化领域中.提出一种基于拟态物理学的约束多目标共轭梯度混合算法CGRMOAPA.算法采取外点罚函数法作为约束问题处理技术,并借鉴聚集函数法的思想,将约束多目标优化问题转化为单目标无约束优化问题,最终利用共轭梯度法进行求解.通过与CRMOAPO、MOGA、NSGA-II的实验对比,表明了算法CGRMOAPA具有较好的分布性能,也为约束多目标优化问题的求解提供了一种新的思路.     

An efficient evolutionary multi-objective framework for MEMS design optimisation: validation, comparison and analysis

The application of multi objective evolutionary algorithms (MOEA) in the design optimisation of microelectromechanical systems (MEMS) is of particular interest in this research. MOEA is a class of soft computing techniques of biologically inspired stochastic algorithms, which have proved to outperform their conventional counterparts in many design optimisation tasks. MEMS designers can utilise a variety of multi-disciplinary design tools that explore a complex design search space, however, still follow the traditional trial and error approaches. The paper proposes a novel framework, which couples both modelling and analysis tools to the most referenced MOEAs (NSGA-II and MOGA-II). The framework is validated and evaluated through a number of case studies of increasing complexity. The research presented in this paper unprecedentedly attempts to compare the performances of the mentioned algorithms in the application domain. The comparative study shows significant insights into the behaviour of both of the algorithms in the design optimisation of MEMS. The paper provides extended discussions and analysis of the results showing, overall, that MOGA-II outperforms NSGA-II, for the selected case studies.     

A new memetic algorithm based on cellular learning automata for solving the vertex coloring problem

Vertex coloring problem is a combinatorial optimization problem in graph theory in which a color is assigned to each vertex of graph such that no two adjacent vertices have the same color. In this paper a new hybrid algorithm which is obtained from combination of cellular learning automata (CLA) and memetic algorithm (MA) is proposed for solving the vertex coloring problem. CLA is an effective probabilistic learning model combining cellular automata and learning automaton (LA). Irregular CLA (ICLA) is a generalization of CLA in which the restriction of rectangular grid structure in CLA is removed. The proposed algorithm is based on the irregular open CLA (IOCLA) that is an extension of ICLA in which the evolution of CLA is influenced by both local and global environments. Similar to other IOCLA-based algorithms, in the proposed algorithm, local environment is constituted by neighboring LAs of any cell and the global environment consists of a pool of memes in which each meme corresponds to a certain local search method. Each meme is represented by a set of LAs from which the history of the corresponding local search method can be extracted. To show the superiority of the proposed algorithm over some well-known algorithms, several computer experiments have been conducted. The results show that the proposed algorithm performs better than other methods in terms of running time of algorithm and the required number of colors.