Evolutionary multiobjective optimization using an outranking-based dominance generalization

One aspect that is often disregarded in the current research on evolutionary multiobjective optimization is the fact that the solution of a multiobjective optimization problem involves not only the search itself, but also a decision making process. Most current approaches concentrate on adapting an evolutionary algorithm to generate the Pareto frontier. In this work, we present a new idea to incorporate preferences into a multi-objective evolutionary algorithm (MOEA). We introduce a binary fuzzy preference relation that expresses the degree of truth of the predicate “x is at least as good as y”. On this basis, a strict preference relation with a reasonably high degree of credibility can be established on any population. An alternative x is not strictly outranked if and only if there does not exist an alternative y which is strictly preferred to x. It is easy to prove that the best solution is not strictly outranked. For validating our proposed approach, we used the non-dominated sorting genetic algorithm II (NSGA-II), but replacing Pareto dominance by the above non-outranked concept. So, we search for the non-strictly outranked frontier that is a subset of the Pareto frontier. In several instances of a nine-objective knapsack problem our proposal clearly outperforms the standard NSGA-II, achieving non-outranked solutions which are in an obviously privileged zone of the Pareto frontier.     

A parallel double-level multiobjective evolutionary algorithm for robust optimization

Robust optimization is a popular method to tackle uncertain optimization problems. However, traditional robust optimization can only find a single solution in one run which is not flexible enough for decision-makers to select a satisfying solution according to their preferences. Besides, traditional robust optimization often takes a large number of Monte Carlo simulations to get a numeric solution, which is quite time-consuming. To address these problems, this paper proposes a parallel double-level multiobjective evolutionary algorithm (PDL-MOEA). In PDL-MOEA, a single-objective uncertain optimization problem is translated into a bi-objective one by conserving the expectation and the variance as two objectives, so that the algorithm can provide decision-makers with a group of solutions with different stabilities. Further, a parallel evolutionary mechanism based on message passing interface (MPI) is proposed to parallel the algorithm. The parallel mechanism adopts a double-level design, i.e., global level and sub-problem level. The global level acts as a master, which maintains the global population information. At the sub-problem level, the optimization problem is decomposed into a set of sub-problems which can be solved in parallel, thus reducing the computation time. Experimental results show that PDL-MOEA generally outperforms several state-of-the-art serial/parallel MOEAs in terms of accuracy, efficiency, and scalability.     

Integrated multiobjective optimization and a priori preferences using genetic algorithms

One of the tasks of decision-making support systems is to develop methods that help the designer select a solution among a set of actions, e.g. by constructing a function expressing his/her preferences over a set of potential solutions. In this paper, a new method to solve multiobjective optimization (MOO) problems is developed in which the user’s information about his/her preferences is taken into account within the search process. Preference functions are built that reflect the decision-maker’s (DM) interests and use meaningful parameters for each objective. The preference functions convert these objective preferences into numbers. Next, a single objective is automatically built and no weight selection is performed. Problems found due to the multimodality nature of a generated single cost index are managed with Genetic Algorithms (GAs). Three examples are given to illustrate the effectiveness of the method.     

A credit ranking model for a parafinancial company based on the ELECTRE-III method and a multiobjective evolutionary algorithm

Credit rating is an assessment performed by lenders or financial institutions to determine a person’s creditworthiness based on the proposed terms of the loan. Frequently, these institutions use rating models to obtain estimates for the probabilities of default for their clients (companies, organizations, government, and individuals) and to assess the risk of credit portfolios. Numerous statistical and data mining methods are used to develop such models. In this paper, the potential of a multicriteria decision-aiding approach is studied. As a first step, the proposed methodology models the problem as a multicriteria evaluation process with multiple and in some cases, conflicting dimensions, which are integrated to derive sound recommendation for DMs. The second step of the methodology involves building a multicriteria outranking model based on ELECTRE III method. An evolutionary algorithm is used to exploit the outranking model. The methodology is applied to a small-scale financial institution operating in the agricultural sector. We compare loan applications based on their attributes and the credit profile of the customer or credit applicant. Our methodology offers the flexibility of combining heterogeneous information together with the preferences of decision makers (DMs), generating both relative and fixed rules for selecting the best loan applications among new and existing customers, which is an improvement over traditional methods The results reveal that outranking models are well suited to credit rating, providing good ranking results and suitable understanding on the relative importance of the evaluation criteria.     

多目标遗传算法求解认知无线电性能优化问题

认知无线电的性能优化是一个动态多目标优化问题。现有的Bio-CR模型基于遗传算法优化认知无线电的性能,它使用线性加权方法将此多目标优化问题简化为了一个单目标优化问题。针对Bio-CR很难确定每个适应度函数的权值和容易漏掉一些最优解的问题,提出了基于多目标遗传算法的认知无线电性能优化算法CREA。CREA能够根据信道条件和用户服务需求的变化动态地调整传输参数以优化性能,不仅克服了Bio-CR的两个缺点,而且通过保存计算结果进一步减少了遗传算法的运行次数。CREA首先根据信道条件的变化动态确定一组适应度函数,然后运行多目标遗传算法获得一个Pareto-optimal set,最后根据用户服务需求从中选出一个最满意解,并通知认知无线电更新自己的传输参数。Matlab仿真实验证明了CREA的正确性和有效性。     

An evolutionary method for complex-process optimization

In this paper we present a new evolutionary method for complex-process optimization. It is partially based on the principles of the scatter search methodology, but it makes use of innovative strategies to be more effective in the context of complex-process optimization using a small number of tuning parameters. In particular, we introduce a new combination method based on path relinking, which considers a broader area around the population members than previous combination methods. We also use a population-update method which improves the balance between intensification and diversification. New strategies to intensify the search and to escape from suboptimal solutions are also presented. The application of the proposed evolutionary algorithm to different sets of both state-of-the-art continuous global optimization and complex-process optimization problems reveals that it is robust and efficient for the type of problems intended to solve, outperforming the results obtained with other methods found in the literature.     

A self-adaptive linear evolutionary algorithm for solving constrained optimization problems

In many real-world applications of evolutionary algorithms, the fitness of an individual requires a quantitative measure. This paper proposes a self-adaptive linear evolutionary algorithm (ALEA) in which we introduce a novel strategy for evaluating individual’s relative strengths and weaknesses. Based on this strategy, searching space of constrained optimization problems with high dimensions for design variables is compressed into two-dimensional performance space in which it is possible to quickly identify ‘good’ individuals of the performance for a multiobjective optimization application, regardless of original space complexity. This is considered as our main contribution. In addition, the proposed new evolutionary algorithm combines two basic operators with modification in reproduction phase, namely, crossover and mutation. Simulation results over a comprehensive set of benchmark functions show that the proposed strategy is feasible and effective, and provides good performance in terms of uniformity and diversity of solutions.     

Ant colony approaches for multiobjective structural optimization problems with a cardinality constraint

Two Ant Colony Optimization algorithms are proposed to tackle multiobjective structural optimization problems with an additional constraint. A cardinality constraint is introduced in order to limit the number of distinct values of the design variables appearing in any candidate solution. Such constraint is directly enforced when an ant builds a candidate solution, while the other mechanical constraints are handled by means of an adaptive penalty method (APM). The test-problems are composed by structural optimization problems with discrete design variables, and the objectives are to minimize both the structure’s weight and its maximum nodal displacement. The Pareto sets generated in the computational experiments are evaluated by means of performance metrics, and the obtained designs are also compared with solutions available from single-objective studies in the literature.     

A solution process for simulation-based multiobjective design optimization with an application in the paper industry

In this paper, we address some computational challenges arising in complex simulation-based design optimization problems. High computational cost, black-box formulation and stochasticity are some of the challenges related to optimization of design problems involving the simulation of complex mathematical models. Solving becomes even more challenging in case of multiple conflicting objectives that must be optimized simultaneously. In such cases, application of multiobjective optimization methods is necessary in order to gain an understanding of which design offers the best possible trade-off. We apply a three-stage solution process to meet the challenges mentioned above. As our case study, we consider the integrated design and control problem in paper mill design where the aim is to decrease the investment cost and enhance the quality of paper on the design level and, at the same time, guarantee the smooth performance of the production system on the operational level. In the first stage of the three-stage solution process, a set of solutions involving different trade-offs is generated with a method suited for computationally expensive multiobjective optimization problems using parallel computing. Then, based on the generated solutions an approximation method is applied to create a computationally inexpensive surrogate problem for the design problem and the surrogate problem is solved in the second stage with an interactive multiobjective optimization method. This stage involves a decision maker and her/his preferences to find the most preferred solution to the surrogate problem. In the third stage, the solution best corresponding that of stage two is found for the original problem.     

Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory

When attempting to solve multiobjective optimization problems (MOPs) using evolutionary algorithms, the Pareto genetic algorithm (GA) has now become a standard of sorts. After its introduction, this approach was further developed and led to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to keep diversity. On the other hand, the scheme for solving MOPs presented by Nash introduced the notion of Nash equilibrium and aimed at solving MOPs that originated from evolutionary game theory and economics. Since the concept of Nash Equilibrium was introduced, game theorists have attempted to formalize aspects of the evolutionary equilibrium. Nash genetic algorithm (Nash GA) is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash equilibrium through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method by which agents can play optimal strategies in the absence of rationality. Through the process of Darwinian selection, a population of agents can evolve to an evolutionary stable strategy (ESS). In this article, we find the ESS as a solution of MOPs using a coevolutionary algorithm based on evolutionary game theory. By applying newly designed coevolutionary algorithms to several MOPs, we can confirm that evolutionary game theory can be embodied by the coevolutionary algorithm and this coevolutionary algorithm can find optimal equilibrium points as solutions for an MOP. We also show the optimization performance of the co-evolutionary algorithm based on evolutionary game theory by applying this model to several MOPs and comparing the solutions with those of previous evolutionary optimization models. This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003.     

Large-scale parallelization of the Borg multiobjective evolutionary algorithm to enhance the management of complex environmental systems

The Borg MOEA is a self-adaptive multiobjective evolutionary algorithm capable of solving complex, many-objective environmental systems problems efficiently and reliably. Water and environmental resources problems pose significant computational challenges due to their potential for large Pareto optimal sets, the presence of disjoint Pareto-optimal regions that arise from discrete choices, multi-modal suboptimal regions, and expensive objective function calculations. This work develops two large-scale parallel implementations of the Borg MOEA, the master–slave and multi-master Borg MOEA, and applies them to a highly challenging risk-based water supply portfolio planning problem. The performance and scalability of both implementations are compared on up to 16384 processors. The multi-master Borg MOEA is shown to scale efficiently on tens of thousands of cores while dramatically improving the reliability of attaining high-quality solutions. Our results dramatically expand the scale and scope of complex environmental systems that can be addressed using many-objective evolutionary optimization.     

Improving the design of sequences for DNA computing: A multiobjective evolutionary approach

Designing oligonucleotide strands that selectively hybridize to reduce undesired reactions is a critical step for successful DNA computing. To accomplish this, DNA molecules must be restricted to a wide window of thermodynamical and logical conditions, which in turn facilitate and control the algorithmic processes implemented by chemical reactions. In this paper, we propose a multiobjective evolutionary algorithm for DNA sequence design that, unlike preceding evolutionary approaches, uses a matrix-based chromosome as encoding strategy. Computational results show that a matrix-based GA along with its specific genetic operators may improve the performance for DNA sequence optimization compared to previous methods.     

Distributed evolutionary algorithms and their models: A survey of the state-of-the-art

The increasing complexity of real-world optimization problems raises new challenges to evolutionary computation. Responding to these challenges, distributed evolutionary computation has received considerable attention over the past decade. This article provides a comprehensive survey of the state-of-the-art distributed evolutionary algorithms and models, which have been classified into two groups according to their task division mechanism. Population-distributed models are presented with master-slave, island, cellular, hierarchical, and pool architectures, which parallelize an evolution task at population, individual, or operation levels. Dimension-distributed models include coevolution and multi-agent models, which focus on dimension reduction. Insights into the models, such as synchronization, homogeneity, communication, topology, speedup, advantages and disadvantages are also presented and discussed. The study of these models helps guide future development of different and/or improved algorithms. Also highlighted are recent hotspots in this area, including the cloud and MapReduce-based implementations, GPU and CUDA-based implementations, distributed evolutionary multiobjective optimization, and real-world applications. Further, a number of future research directions have been discussed, with a conclusion that the development of distributed evolutionary computation will continue to flourish.     

Incorporation of implicit decision-maker preferences in multi-objective evolutionary optimization using a multi-criteria classification method

Nowadays, most Multi-Objective Evolutionary Algorithms (MOEA) concentrate mainly on searching for an approximation of the Pareto frontier to solve a multi-objective optimization problem. However, finding this set does not completely solve the problem. The decision-maker (DM) still has to choose the best compromise solution from that set. But as the number of criteria increases, several important difficulties arise in performing this task. Identifying the Region of Interest (ROI), according to the DM’s preferences, is a promising alternative that would facilitate the selection process. This paper approaches the incorporation of preferences into a MOEA in order to characterize the ROI by a multi-criteria classification method. This approach is called Hybrid Multi-Criteria Sorting Genetic Algorithm and is composed of two phases. First, a metaheuristic is used to generate a small set of solutions that are classified in ordered categories by the DM. Thus, the DM’s preferences will be reflected indirectly in this set. In the second phase, a multi-criteria sorting method is combined with an evolutionary algorithm. The first one is used to classify new solutions. Those classified as ‘satisfactory’ are used for creating a selective pressure towards the ROI. The effectiveness of our method was proved in nine instances of a public project portfolio problem. The obtained results indicate that our approach achieves a good characterization of the ROI, and outperforms the standard NSGA-II in simple and complex problems. Also, these results confirm that our approach is able to deal with many-objective problems.     

一种新的分布性保持方法

分布性保持是多目标进化算法主要目标之一. 然而通常维护方法的性能与运行时间存在矛盾. 提出一种基于最小生成树的分布性维护方法. 利用最小生成树中的度数和边长对个体密度进行估计, 使低度数的边界个体和长边长的低密度个体得到了保留. 另外, 一次性选择个体进入下代种群, 避免了每移出一个个体就需要对个体密度进行调整的操作. 通过5个测试问题和4个方面的测试标准, 与3个著名的算法进行比较实验, 结果表明该方法在以较快速度对种群进行维护的同时, 拥有良好的分布性.     

Illustration of fairness in evolutionary multi-objective optimization

It is widely assumed that evolutionary algorithms for multi-objective optimization problems should use certain mechanisms to achieve a good spread over the Pareto front. In this paper, we examine such mechanisms from a theoretical point of view and analyze simple algorithms incorporating the concept of fairness. This mechanism tries to balance the number of offspring of all individuals in the current population. We rigorously analyze the runtime behavior of different fairness mechanisms and present illustrative examples to point out situations, where the right mechanism can speed up the optimization process significantly. We also indicate drawbacks for the use of fairness by presenting instances, where the optimization process is slowed down drastically.     

A new Probe Guided Mutation operator and its application for solving the cardinality constrained portfolio optimization problem

This paper revisits the classical Polynomial Mutation (PLM) operator and proposes a new probe guided version of the PLM operator designed to be used in conjunction with Multiobjective Evolutionary Algorithms (MOEAs). The proposed Probe Guided Mutation (PGM) operator is validated by using data sets from six different stock markets. The performance of the proposed PGM operator is assessed in comparison with the one of the classical PLM with the assistance of the Non-dominated Sorting Genetic Algorithm II (NSGAII) and the Strength Pareto Evolutionary Algorithm 2 (SPEA2). The evaluation of the performance is based on three performance metrics, namely Hypervolume, Spread and Epsilon indicator. The experimental results reveal that the proposed PGM operator outperforms with confidence the performance of the classical PLM operator for all performance metrics when applied to the solution of the cardinality constrained portfolio optimization problem (CCPOP). We also calculate the True Efficient Frontier (TEF) of the CCPOP by formulating the CCPOP as a Mixed Integer Quadratic Program (MIQP) and we compare the relevant results with the approximate efficient frontiers that are generated by the proposed PGM operator. The results confirm that the PGM operator generates near optimal solutions that lie very close or in certain cases overlap with the TEF.     

Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation

This paper presents an adaptive weighted sum (AWS) method for multiobjective optimization problems. The method extends the previously developed biobjective AWS method to problems with more than two objective functions. In the first phase, the usual weighted sum method is performed to approximate the Pareto surface quickly, and a mesh of Pareto front patches is identified. Each Pareto front patch is then refined by imposing additional equality constraints that connect the pseudonadir point and the expected Pareto optimal solutions on a piecewise planar hypersurface in the -dimensional objective space. It is demonstrated that the method produces a well-distributed Pareto front mesh for effective visualization, and that it finds solutions in nonconvex regions. Two numerical examples and a simple structural optimization problem are solved as case studies. Presented as paper AIAA-2004-4322 at the 10th AIAA-ISSMO Multidisciplinary Analysis and Optimization Conference, Albany, New York, August 30–September 1, 2004     

Time Complexity of Evolutionary Algorithms for Combinatorial Optimization： A Decade of Results

Computational time complexity analyzes of evolutionary algorithms (EAs) have been performed since the mid-nineties. The first results were related to very simple algorithms,such as the (1 1)-EA,on toy problems.These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems.In fact,in recent years,it has been possible to analyze the (1 1)-EA on combinatorial optimization problems with practical applications and more realistic population-baeed EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines.The most common mathematical techniques are introduced,the basic ideas behind them are discussed and their elective applications are highlighted.Solved problems that were still open are enumerated as are those still awaiting for a solution.New questions and problems arisen in the meantime are also considered.     

The two-stage recombination operator and its application to the multiobjective 0/1 knapsack problem: A comparative study

In this paper, we first propose a new recombination operator called the two-stage recombination and then we test its performance in the context of the multiobjective 0/1 knapsack problem (MOKP). The proposed recombination operator generates only one offspring solution from a selected pair of parents according to the following two stages. In the first stage, called genetic shared-information stage or similarity-preserving stage, the generated offspring inherits all parent similar genes (i.e., genes or decision variables having the same positions and the same values in both parents). In the second stage, called problem fitness-information stage, the parent non-similar genes (i.e., genes or decision variables having the same positions but different values regarding the two parents) are selected from one of the two parents using some fitness information. Initially, we propose two different approaches for the second stage: the general version and the restricted version. However, the application of the restricted version to the MOKP leads to an improved version which is more specific to this problem. The general and the MOKP-specific versions of the two-stage recombination are compared against three traditional crossovers using two well-known multiobjective evolutionary algorithms. Promising results are obtained. We also provide a comparison between the general version and the MOKP-specific version.