Closed-loop evolutionary multiobjective optimization

Artificial evolution has been used for more than 50 years as a method of optimization in engineering, operations research and computational intelligence. In closed-loop evolution (a term used by the statistician, George Box) or, equivalently, evolutionary experimentation (Ingo Rechenberg?s terminology), the ?phenotypes? are evaluated in the real world by conducting a physical experiment, whilst selection and breeding is simulated. Well-known early work on artificial evolution?design engineering problems in fluid dynamics, and chemical plant process optimization? was carried out in this experimental mode. More recently, the closed-loop approach has been successfully used in much evolvable hardware and evolutionary robotics research, and in some microbiology and biochemistry applications. In this article, several further new targets for closed-loop evolutionary and multiobjective optimization are considered. Four case studies from my own collaborative work are described: (i) instrument optimization in analytical biochemistry; (ii) finding effective drug combinations in vitro; (iii) onchip synthetic biomolecule design; and (iv) improving chocolate production processes. Accurate simulation in these applications is not possible due to complexity or a lack of adequate analytical models. In these and other applications discussed, optimizing experimentally brings with it several challenges: noise; nuisance factors; ephemeral resource constraints; expensive evaluations, and evaluations that must be done in (large) batches. Evolutionary algorithms (EAs) are largely equal to these vagaries, whilst modern multiobjective EAs also enable tradeoffs among conflicting optimization goals to be explored. Nevertheless, principles from other disciplines, such as statistics, Design of Experiments, machine learning and global optimization are also relevant to aspects of the closed-loop problem, and may inspire futher development of multiobjective EAs.     

一种新的分布性保持方法

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

An improved decomposition-based multiobjective evolutionary algorithm with a better balance of convergence and diversity

In decomposition-based multiobjective evolutionary algorithms (MOEAs), a good balance between convergence and diversity is very important to the performance of an algorithm. However, only the aggregation functions enough to achieve a good balance, especially in high-dimensional objective space. So we considered using the value of related acute angle between a solution and a direction vector as an other consider index. This idea is implemented to enhance the famous decomposition-based algorithm, i.e., MOEA/D. The enhanced algorithm is compared to its predecessor and other state-of-the-art algorithms on a several well-known test suites. Our experimental results show that the proposed algorithm performs better than its predecessor in keeping a better balance between the convergence and diversity, and also as effective as other state-of-the-art algorithms.     

A diversity preserving selection in multiobjective evolutionary algorithms

In this paper, an efficient diversity preserving selection (DPS) technique is presented for multiobjective evolutionary algorithms (MEAs). The main goal is to preserve diversity of nondominated solutions in problems with scaled objectives. This is achieved with the help of a mechanism that preserves certain inferior individuals over successive generations with a view to provide long term advantages. The mechanism selects a group (of individuals) that is statistically furthest from the worst group, instead of just concentrating on the best individuals, as in truncation selection. In a way, DPS judiciously combines the diversity preserving mechanism with conventional truncation selection. Experiments demonstrate that DPS significantly improves diversity of nondominated solutions in badly-scaling problems, while at the same time it exhibits acceptable proximity performance. Whilst DPS has certain advantages when it comes to scaling problems, it empirically shows no disadvantages for the problems with non-scaled objectives.     

Asymptotic convergence of metaheuristics for multiobjective optimization problems

This paper analyzes the convergence of metaheuristics used for multiobjective optimization problems in which the transition probabilities use a uniform mutation rule. We prove that these algorithms converge only if elitism is used.     

The balance between proximity and diversity in multiobjective evolutionary algorithms

Over the last decade, a variety of evolutionary algorithms (EAs) have been proposed for solving multiobjective optimization problems. Especially more recent multiobjective evolutionary algorithms (MOEAs) have been shown to be efficient and superior to earlier approaches. An important question however is whether we can expect such improvements to converge onto a specific efficient MOEA that behaves best on a large variety of problems. In this paper, we argue that the development of new MOEAs cannot converge onto a single new most efficient MOEA because the performance of MOEAs shows characteristics of multiobjective problems. While we point out the most important aspects for designing competent MOEAs in this paper, we also indicate the inherent multiobjective tradeoff in multiobjective optimization between proximity and diversity preservation. We discuss the impact of this tradeoff on the concepts and design of exploration and exploitation operators. We also present a general framework for competent MOEAs and show how current state-of-the-art MOEAs can be obtained by making choices within this framework. Furthermore, we show an example of how we can separate nondomination selection pressure from diversity preservation selection pressure and discuss the impact of changing the ratio between these components.     

A multiobjective evolutionary algorithm toolbox for computer-aidedmultiobjective optimization

This paper presents an interactive graphical user interface (GUI) based multiobjective evolutionary algorithm (MOEA) toolbox for effective computer-aided multiobjective (MO) optimization. Without the need of aggregating multiple criteria into a compromise function, it incorporates the concept of Pareto's optimality to evolve a family of nondominated solutions distributing along the tradeoffs uniformly. The toolbox is also designed with many useful features such as the goal and priority settings to provide better support for decision-making in MO optimization, dynamic population size that is computed adaptively according to the online discovered Pareto-front, soft/hard goal settings for constraint handlings, multiple goals specification for logical "AND"/"OR" operation, adaptive niching scheme for uniform population distribution, and a useful convergence representation for MO optimization. The MOEA toolbox is freely available for download at http://vlab.ee.nus.edu.sg/-kctan/moea.htm which is ready for immediate use with minimal knowledge needed in evolutionary computing. To use the toolbox, the user merely needs to provide a simple "model" file that specifies the objective function corresponding to his/her particular optimization problem. Other aspects like decision variable settings, optimization process monitoring and graphical results analysis can be performed easily through the embedded GUIs in the toolbox. The effectiveness and applications of the toolbox are illustrated via the design optimization problem of a practical ill-conditioned distillation system. Performance of the algorithm in MOEA toolbox is also compared with other well-known evolutionary MO optimization methods upon a benchmark problem.     

An evolutionary strategy for decremental multiobjective optimization problems

In this article, an evolutionary algorithm for multiobjective optimization problems in a dynamic environment is studied. In particular, we focus on decremental multiobjective optimization problems, where some objectives may be deleted during evolution—for such a process we call it objective decrement. It is shown that the Pareto‐optimal set after objective decrement is actually a subset of the Pareto‐optimal set before objective decrement. Based on this observation, the inheritance strategy is suggested. When objective decrement takes place, this strategy selects good chromosomes according to the decremented objective set from the solutions found before objective decrement, and then continues to optimize them via evolution for the decremented objective set. The experimental results showed that this strategy can help MOGAs achieve better performance than MOGAs without using the strategy, where the evolution is restarted when objective decrement occurs. More solutions with better quality are found during the same time span. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 847–866, 2007.     

Performance evaluation of evolutionary multiobjective optimization algorithms for multiobjective fuzzy genetics-based machine learning

Recently, evolutionary multiobjective optimization (EMO) algorithms have been utilized for the design of accurate and interpretable fuzzy rule-based systems. This research area is often referred to as multiobjective genetic fuzzy systems (MoGFS), where EMO algorithms are used to search for non-dominated fuzzy rule-based systems with respect to their accuracy and interpretability. In this paper, we examine the ability of EMO algorithms to efficiently search for Pareto optimal or near Pareto optimal fuzzy rule-based systems for classification problems. We use NSGA-II (elitist non-dominated sorting genetic algorithm), its variants, and MOEA/D (multiobjective evolutionary algorithm based on decomposition) in our multiobjective fuzzy genetics-based machine learning (MoFGBML) algorithm. Classification performance of obtained fuzzy rule-based systems by each EMO algorithm is evaluated for training data and test data under various settings of the available computation load and the granularity of fuzzy partitions. Experimental results in this paper suggest that reported classification performance of MoGFS in the literature can be further improved using more computation load, more efficient EMO algorithms, and/or more antecedent fuzzy sets from finer fuzzy partitions.     

A tutorial on multiobjective optimization: fundamentals and evolutionary methods

In almost no other field of computer science, the idea of using bio-inspired search paradigms has been so useful as in solving multiobjective optimization problems. The idea of using a population of search agents that collectively approximate the Pareto front resonates well with processes in natural evolution, immune systems, and swarm intelligence. Methods such as NSGA-II, SPEA2, SMS-EMOA, MOPSO, and MOEA/D became standard solvers when it comes to solving multiobjective optimization problems. This tutorial will review some of the most important fundamentals in multiobjective optimization and then introduce representative algorithms, illustrate their working principles, and discuss their application scope. In addition, the tutorial will discuss statistical performance assessment. Finally, it highlights recent important trends and closely related research fields. The tutorial is intended for readers, who want to acquire basic knowledge on the mathematical foundations of multiobjective optimization and state-of-the-art methods in evolutionary multiobjective optimization. The aim is to provide a starting point for researching in this active area, and it should also help the advanced reader to identify open research topics.     

A systems approach to evolutionary multiobjective structural optimization and beyond

Multiobjective evolutionary algorithms (MOEAs) have shown to be effective in solving a wide range of test problems. However, it is not straightforward to apply MOEAs to complex real-world problems. This paper discusses the major challenges we face in applying MOEAs to complex structural optimization, including the involvement of time-consuming and multi-disciplinary quality evaluation processes, changing environments, vagueness in formulating criteria formulation, and the involvement of multiple sub-systems. We propose that the successful tackling of all these aspects give birth to a systems approach to evolutionary design optimization characterized by considerations at four levels, namely, the system property level, temporal level, spatial level and process level. Finally, we suggest a few promising future research topics in evolutionary structural design that consist in the necessary steps towards a life-like design approach, where design principles found in biological systems such as self-organization, self-repair and scalability play a central role.     

A gene-level hybrid search framework for multiobjective evolutionary optimization

This paper proposes a general framework of gene-level hybrid search (GLHS) for multiobjective evolutionary optimization. Regarding the existing hybrid search methods, most of them usually combine different search strategies and only select one search strategy to generate child solution. This kind of hybrid search is called as a chromosome-level approach in this paper. However, in GLHS, every gene bit of the child solution can be produced using different search strategies and such operation provides the enhanced exploration capability. As an example, two different DE mutation strategies are used in this paper as the variance candidate pool to implement the proposed GLHS framework, named GLHS-DE. To validate the effectiveness of GLHS-DE, it is embedded into one state-of-the-art algorithmic framework of MOEA/D, and is compared to a basic DE operator and two competitive hybrid search operators, i.e., FRRMAB and CDE, on 80 test problems with two to fifteen objectives. The experimental results show GLHS-DE obtains a superior performance over DE, FRRMAB and CDE on about 70 out of 80 test problems, indicating the promising application of our approach for multiobjective evolutionary optimization.

     

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.     

MIJ2K Optimization using evolutionary multiobjective optimization algorithms

This paper deals with the multiobjective definition of video compression and its optimization. The optimization will be done using NSGA-II, a well-tested and highly accurate algorithm with a high convergence speed developed for solving multiobjective problems. Video compression is defined as a problem including two competing objectives. We try to find a set of optimal, so-called Pareto-optimal solutions, instead of a single optimal solution. The two competing objectives are quality and compression ratio maximization. The optimization will be achieved using a new patent pending codec, called MIJ2K, also outlined in this paper. Video will be compressed with the MIJ2K codec applied to some classical videos used for performance measurement, selected from the Xiph.org Foundation repository. The result of the optimization will be a set of near-optimal encoder parameters. We also present the convergence of NSGA-II with different encoder parameters and discuss the suitability of MOEAs as opposed to classical search-based techniques in this field.     

一种求解旅行商问题的进化多目标优化方法

为了克服传统小生境(Niching)策略中的参数设置难题,提出一种求解旅行商问题的进化多目标优化方法:建立以路径长度和平均离群距离为目标的双目标优化模型,利用改进非支配排序遗传算法(NSGAII)进行求解.为了在全局探索能力与局部开发能力之间保持平衡,算法中采用一种使路径长度相同的可行解互不占优的评价策略,并通过一种新的离散差分进化算子和简化的2-Opt策略生成候选解.与已有算法的数值试验结果比较表明,求解旅行商问题(TSP)的改进非支配排序遗传算法(NSGAII-TSP)能够更好地保持种群多样性,从而克服局部最优解的吸引并具有更鲁棒的全局探索能力.通过借助特殊的个体评价策略,所提出的算法可以更好地进行全局优化,甚至同时得到多个全局最优解.     

Mean-semivariance portfolio optimization with multiobjective evolutionary algorithms and technical analysis rules

Recent work has been devoted to study the use of multiobjective evolutionary algorithms (MOEAs) in stock portfolio optimization, within a common mean-variance framework. This article proposes the use of a more appropriate framework, mean-semivariance framework, which takes into account only adverse return variations instead of overall variations. It also proposes the use and comparison of established technical analysis (TA) indicators in pursuing better outcomes within the risk-return relation. Results show there is some difference in the performance of the two selected MOEAs – non-dominated sorting genetic algorithm II (NSGA II) and strength pareto evolutionary algorithm 2 (SPEA 2) – within portfolio optimization. In addition, when used with four TA based strategies – relative strength index (RSI), moving average convergence/divergence (MACD), contrarian bollinger bands (CBB) and bollinger bands (BB), the two selected MOEAs achieve solutions with interesting in-sample and out-of-sample outcomes for the BB strategy.     

Single- and multiobjective evolutionary optimization assisted by Gaussian random field metamodels

This paper presents and analyzes in detail an efficient search method based on evolutionary algorithms (EA) assisted by local Gaussian random field metamodels (GRFM). It is created for the use in optimization problems with one (or many) computationally expensive evaluation function(s). The role of GRFM is to predict objective function values for new candidate solutions by exploiting information recorded during previous evaluations. Moreover, GRFM are able to provide estimates of the confidence of their predictions. Predictions and their confidence intervals predicted by GRFM are used by the metamodel assisted EA. It selects the promising members in each generation and carries out exact, costly evaluations only for them. The extensive use of the uncertainty information of predictions for screening the candidate solutions makes it possible to significantly reduce the computational cost of singleand multiobjective EA. This is adequately demonstrated in this paper by means of mathematical test cases and a multipoint airfoil design in aerodynamics.     

An efficient evolutionary optimization algorithm for multiobjective distribution feeder reconfiguration

In this paper, a Multi-objective Modified Honey Bee Mating Optimization (MMHBMO) evolutionary algorithm is proposed to solve the multi-objective Distribution Feeder Reconfiguration (DFR). The real power loss, the number of the switching operations and the deviation of the voltage at each node are considered as the objective functions. Conventional algorithms for solving the multiobjective optimization problems convert the multiple objectives into a single objective using a vector of the user-predefined weights. This paper presents a new MHBMO algorithm for the DFR problem. In the proposed algorithm an external repository is utilized to save non-dominated solutions found during the search process. A fuzzy clustering technique is used to control the size of the repository within the limits because of the objective functions are not the same. The proposed algorithm is tested on a distribution test feeder.