A comprehensive survey of fitness approximation in evolutionary computation

Evolutionary algorithms (EAs) have received increasing interests both in the academy and industry. One main difficulty in applying EAs to real-world applications is that EAs usually need a large number of fitness evaluations before a satisfying result can be obtained. However, fitness evaluations are not always straightforward in many real-world applications. Either an explicit fitness function does not exist, or the evaluation of the fitness is computationally very expensive. In both cases, it is necessary to estimate the fitness function by constructing an approximate model. In this paper, a comprehensive survey of the research on fitness approximation in evolutionary computation is presented. Main issues like approximation levels, approximate model management schemes, model construction techniques are reviewed. To conclude, open questions and interesting issues in the field are discussed.     

Algorithmic analysis of a basic evolutionary algorithm for continuous optimization

In practical optimization, applying evolutionary algorithms has nearly become a matter of course. Their theoretical analysis, however, is far behind practice. So far, theorems on the runtime are limited to discrete search spaces; results for continuous search spaces are limited to convergence theory or even rely on validation by experiments, which is unsatisfactory from a theoretical point of view.     

IDCOS: optimization strategy for parallel complex expression computation on big data

The Journal of Supercomputing - Complex expressions are the basis of data analytics. To process complex expressions on big data efficiently, we developed a novel optimization strategy for parallel...     

Cricket behaviour-based evolutionary computation technique in solving engineering optimization problems

Meta-heuristicalgorithms are widely used in various areas such as engineering, statistics, industrial, image processing, artificial intelligence etc. In this study, the Cricket algorithm which is a novel nature-inspired meta-heuristic algorithm approach which can be used for the solution of some global engineering optimization problems was introduced. This novel approach is a meta-heuristic method that arose from the inspiration of the behaviour of crickets in the nature. It has a structure for the use in the solution of various problems. In the development stage of the algorithm, the good aspects of the Bat, Particle Swarm Optimization and Firefly were experimented for being applied to this algorithm. In addition to this, because of the fact that these insects intercommunicate through sound, the physical principles of sound propagation in the nature were practiced in the algorithm. Thanks to this, the compliance of the algorithm to real life tried to be provided. This new developed approach was applied on the familiar global engineering problems and the obtained results were compared with the results of the algorithm applied to these problems.     

A graphical model for evolutionary optimization

We present a statistical model of empirical optimization that admits the creation of algorithms with explicit and intuitively defined desiderata. Because No Free Lunch theorems dictate that no optimization algorithm can be considered more efficient than any other when considering all possible functions, the desired function class plays a prominent role in the model. In particular, this provides a direct way to answer the traditionally difficult question of what algorithm is best matched to a particular class of functions. Among the benefits of the model are the ability to specify the function class in a straightforward manner, a natural way to specify noisy or dynamic functions, and a new source of insight into No Free Lunch theorems for optimization.     

A survey on approaches for reliability-based optimization

Reliability-based Optimization is a most appropriate and advantageous methodology for structural design. Its main feature is that it allows determining the best design solution (with respect to prescribed criteria) while explicitly considering the unavoidable effects of uncertainty. In general, the application of this methodology is numerically involved, as it implies the simultaneous solution of an optimization problem and also the use of specialized algorithms for quantifying the effects of uncertainties. In view of this fact, several approaches have been developed in the literature for applying this methodology in problems of practical interest. This contribution provides a survey on approaches for performing Reliability-based Optimization, with emphasis on the theoretical foundations and the main assumptions involved. Early approaches as well as the most recently developed methods are covered. In addition, a qualitative comparison is performed in order to provide some general guidelines on the range of applicability on the different approaches discussed in this contribution.     

Multiobjective evolutionary computation for supersonic wing-shapeoptimization

This paper discusses the design optimization of a wing for supersonic transport (SST) using a multiple-objective genetic algorithm (MOGA). Three objective functions are used to minimize the drag for supersonic cruise, the drag for transonic cruise, and the bending moment at the wing root for supersonic cruise. The wing shape is defined by 66 design variables. A Euler flow code is used to evaluate supersonic performance, and a potential flow code is used to evaluate transonic performance. To reduce the total computational time, flow calculations are parallelized on an NEC SX-4 computer using 32 processing elements. The detailed analysis of the resulting Pareto front suggests a renewed interest in the arrow wing planform for the supersonic wing     

A filter-based evolutionary algorithm for constrained optimization

We introduce a filter-based evolutionary algorithm (FEA) for constrained optimization. The filter used by an FEA explicitly imposes the concept of dominance on a partially ordered solution set. We show that the algorithm is provably robust for both linear and nonlinear problems and constraints. FEAs use a finite pattern of mutation offsets, and our analysis is closely related to recent convergence results for pattern search methods. We discuss how properties of this pattern impact the ability of an FEA to converge to a constrained local optimum.     

Editorial scalability of evolutionary algorithms and other metaheuristics for large-scale continuous optimization problems

This editorial note presents the motivations, objectives, and structure of the special issue on scalability of evolutionary algorithms and other metaheuristics for large-scale continuous optimization problems. In addition, it provides the link to an associated Website where complementary material to the special issue is available.     

A survey on metaheuristics for stochastic combinatorial optimization

Metaheuristics are general algorithmic frameworks, often nature-inspired, designed to solve complex optimization problems, and they are a growing research area since a few decades. In recent years, metaheuristics are emerging as successful alternatives to more classical approaches also for solving optimization problems that include in their mathematical formulation uncertain, stochastic, and dynamic information. In this paper metaheuristics such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others are introduced, and their applications to the class of Stochastic Combinatorial Optimization Problems (SCOPs) is thoroughly reviewed. Issues common to all metaheuristics, open problems, and possible directions of research are proposed and discussed. In this survey, the reader familiar to metaheuristics finds also pointers to classical algorithmic approaches to optimization under uncertainty, and useful informations to start working on this problem domain, while the reader new to metaheuristics should find a good tutorial in those metaheuristics that are currently being applied to optimization under uncertainty, and motivations for interest in this field.

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.     

A computationally efficient evolutionary algorithm for real-parameter optimization

Due to increasing interest in solving real-world optimization problems using evolutionary algorithms (EAs), researchers have recently developed a number of real-parameter genetic algorithms (GAs). In these studies, the main research effort is spent on developing an efficient recombination operator. Such recombination operators use probability distributions around the parent solutions to create an offspring. Some operators emphasize solutions at the center of mass of parents and some around the parents. In this paper, we propose a generic parent-centric recombination operator (PCX) and a steady-state, elite-preserving, scalable, and computationally fast population-alteration model (we call the G3 model). The performance of the G3 model with the PCX operator is investigated on three commonly used test problems and is compared with a number of evolutionary and classical optimization algorithms including other real-parameter GAs with the unimodal normal distribution crossover (UNDX) and the simplex crossover (SPX) operators, the correlated self-adaptive evolution strategy, the covariance matrix adaptation evolution strategy (CMA-ES), the differential evolution technique, and the quasi-Newton method. The proposed approach is found to consistently and reliably perform better than all other methods used in the study. A scale-up study with problem sizes up to 500 variables shows a polynomial computational complexity of the proposed approach. This extensive study clearly demonstrates the power of the proposed technique in tackling real-parameter optimization problems.     

A framework for evolutionary optimization with approximate fitnessfunctions

It is not unusual that an approximate model is needed for fitness evaluation in evolutionary computation. In this case, the convergence properties of the evolutionary algorithm are unclear due to the approximation error of the model. In this paper, extensive empirical studies are carried out to investigate the convergence properties of an evolution strategy using an approximate fitness function on two benchmark problems. It is found that incorrect convergence will occur if the approximate model has false optima. To address this problem, individual- and generation-based evolution control are introduced and the resulting effects on the convergence properties are presented. A framework for managing approximate models in generation-based evolution control is proposed. This framework is well suited for parallel evolutionary optimization, which is able to guarantee the correct convergence of the evolutionary algorithm, as well as to reduce the computation cost as much as possible. Control of the evolution and updating of the approximate models are based on the estimated fidelity of the approximate model. Numerical results are presented for three test problems and for an aerodynamic design example     

Parallelizing evolutionary computation: A mobile agent-based approach

Parallel computation models have been widely used to enhance the performance of traditional evolutionary algorithms, and they have been implemented on parallel computers to speed up the computation. Instead of using expensive parallel computing facilities, we propose to implement parallel evolutionary computation models on easily available networked PCs, and present a multi-agent framework to support parallelism. With the unique characteristics of agent autonomy and mobility, mobile agents can carry the EC-code and migrate from machine to machine to complete the computation dynamically. To evaluate the proposed approach we have developed a prototype system on a middleware platform JADE to solve a time-consuming task. Different kinds of experiments have been conducted to assess the developed system and the preliminary results show the promise and efficiency of our mobile agent-based approach.     

A general framework for statistical performance comparison of evolutionary computation algorithms

This paper proposes a statistical methodology for comparing the performance of evolutionary computation algorithms. A twofold sampling scheme for collecting performance data is introduced, and these data are analyzed using bootstrap-based multiple hypothesis testing procedures. The proposed method is sufficiently flexible to allow the researcher to choose how performance is measured, does not rely upon distributional assumptions, and can be extended to analyze many other randomized numeric optimization routines. As a result, this approach offers a convenient, flexible, and reliable technique for comparing algorithms in a wide variety of applications.     

An evolutionary decoding method for HMM-based continuous speech recognition systems using particle swarm optimization

The main recognition procedure in modern HMM-based continuous speech recognition systems is Viterbi algorithm. Viterbi algorithm finds out the best acoustic sequence according to input speech in the search space using dynamic programming. In this paper, dynamic programming is replaced by a search method which is based on particle swarm optimization. The major idea is focused on generating initial population of particles as the speech segmentation vectors. The particles try to achieve the best segmentation by an updating method during iterations. In this paper, a new method of particles representation and recognition process is introduced which is consistent with the nature of continuous speech recognition. The idea was tested on bi-phone recognition and continuous speech recognition workbenches and the results show that the proposed search method reaches the performance of the Viterbi segmentation algorithm ; however, there is a slight degradation in the accuracy rate.     

A study on scalable representations for evolutionary optimization of ground structures

This paper presents a comparative study of two indirect solution representations, a generative and an ontogenic one, on a set of well-known 2D truss design problems. The generative representation encodes the parameters of a trusses design as a mapping from a 2D space. The ontogenic representation encodes truss design parameters as a local truss transformation iterated several times, starting from a trivial initial truss. Both representations are tested with a naive evolution strategy based optimization scheme, as well as the state of the art HyperNEAT approach. We focus both on the best objective value obtained and the computational cost to reach a given level of optimality. The study shows that the two solution representations behave very differently. For experimental settings with equal complexity, with the same optimization scheme and settings, the generative representation provides results which are far from optimal, whereas the ontogenic representation delivers near-optimal solutions. The ontogenic representation is also much less computationally expensive than a direct representation until very close to the global optimum. The study questions the scalability of the generative representations, while the results for the ontogenic representation display much better scalability.     

Redundant representations in evolutionary computation

This paper discusses how the use of redundant representations influences the performance of genetic and evolutionary algorithms. Representations are redundant if the number of genotypes exceeds the number of phenotypes. A distinction is made between synonymously and non-synonymously redundant representations. Representations are synonymously redundant if the genotypes that represent the same phenotype are very similar to each other. Non-synonymously redundant representations do not allow genetic operators to work properly and result in a lower performance of evolutionary search. When using synonymously redundant representations, the performance of selectorecombinative genetic algorithms (GAs) depends on the modification of the initial supply. We have developed theoretical models for synonymously redundant representations that show the necessary population size to solve a problem and the number of generations goes with O(2(kr)/r), where kr is the order of redundancy and r is the number of genotypic building blocks (BB) that represent the optimal phenotypic BB. As a result, uniformly redundant representations do not change the behavior of GAs. Only by increasing r, which means overrepresenting the optimal solution, does GA performance increase. Therefore, non-uniformly redundant representations can only be used advantageously if a-priori information exists regarding the optimal solution. The validity of the proposed theoretical concepts is illustrated for the binary trivial voting mapping and the real-valued link-biased encoding. Our empirical investigations show that the developed population sizing and time to convergence models allow an accurate prediction of the empirical results.