A comprehensive survey of fitness approximation in evolutionary computation
Soft ComputingPublished 13 October 2003
Yaochu Jin
Citations1,225
SJR quartileQ2
SJR score0.67
SNIP1.04
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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 and open questions and interesting issues in the field are discussed.
Abstract
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.
Keywords
Computer Science
An Introduction to the Bootstrap
39,744 Citations1994Bradley Efron, Robert Tibshirani
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
IIE TransactionsResponse Surface Methodology
3,842 Citations1996Raymond H. Myers, Douglas C. Montgomery
Using a practical approach, this book discusses two-level factorial and fractional factorial designs, several aspects of empirical modeling with regression techniques, focusing on response surface methodology, mixture experiments and robust design techniques.
Evolution and Optimum Seeking
2,200 Citations1995Hans–Paul Schwefel
Problems and Methods of Optimization Hill Climbing Strategies Random Strategies Evolution Strategies for Numerical Optimization Comparison of Direct Search Strategies for Parameter Optimization.
Computational fluid dynamics : the basics with applications
1,891 Citations1995J. D. Anderson
Information and ComputationBoosting a Weak Learning Algorithm by Majority
1,686 Citations1995Yoav Freund
An algorithm for improving the accuracy of algorithms for learning binary concepts by combining a large number of hypotheses, each of which is generated by training the given learning algorithm on a different set of examples, is presented.
Neural ComputationInformation-Based Objective Functions for Active Data Selection
1,250 Citations1992David Mackay
Within a Bayesian learning framework, objective functions are discussed that measure the expected informativeness of candidate measurements that depend on the assumption that the hypothesis space is correct.
Structural and Multidisciplinary OptimizationA rigorous framework for optimization of expensive functions by surrogates
967 Citations1999Andrew Booker, J. E. Dennis +4 more
The goal of the research reported here is to develop rigorous optimization algorithms to apply to some engineering design problems for which direct application of traditional optimization approaches is not practical.
IEEE Transactions on Evolutionary ComputationA framework for evolutionary optimization with approximate fitness functions
660 Citations2002Yaochu Jin, Markus Olhofer +1 more
A framework for managing approximate models in generation-based evolution control is proposed, 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.
AIAA JournalEvolutionary Optimization of Computationally Expensive Problems via Surrogate Modeling
558 Citations2003Yew-Soon Ong, Prasanth B. Nair +1 more
The essential backbone of the framework is an evolutionary algorithm coupled with a feasible sequential quadratic programming solver in the spirit of Lamarckian learning that leverages surrogate models for solving computationally expensive design problems with general constraints on a limited computational budget.
7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and OptimizationComparison of response surface and kriging models for multidisciplinary design optimization
484 Citations1998Timothy W. Simpson, Farrokh Mistree +2 more
The second-order response surface models and kriging models—using a constant underlying global model and a Gaussian correlation function—yield comparable results.
GenJam: A Genetic Algorithm for Generating Jazz Solos
454 Citations1994John A. Biles
GenJam is a genetic algorithm-based model of a novice jazz musician learning to improvise that maintains hierarchically related populations of melodic ideas that are mapped to specific notes through scales suggested by the chord progression being played.
7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and OptimizationA comparison of approximation modeling techniques - Polynomial versus interpolating models
396 Citations1998Anthony Giunta, Layne T. Watson
Two methods of creating approximation models are compared through the calculation of the modeling accuracy on test problems involving one, five, and ten independent variables to provide an initial exploration of the accuracy and modeling capabilities of these two approximation methods.
Machine LearningGenetic algorithms in noisy environments
333 Citations1988J. Michael Fitzpatrick, John J. Grefenstette
This work explores in detail the tradeoffs between the amount of effort spent on evaluating each structure and the number of structures evaluated during a given iteration of the genetic algorithm.
Computer Methods in Applied Mechanics and EngineeringStructural optimization using evolution strategies and neural networks
219 Citations1998Manolis Papadrakakis, Nikos D. Lagaros +1 more
The objective of this paper is to investigate the efficiency of combinatorial optimization methods, in particular algorithms based on evolution strategies (ES) when incorporated into the solution of large-scale, continuous or discrete, structural optimization problems.
Lecture notes in computer scienceMetamodel—Assisted Evolution Strategies
215 Citations2002Michael Emmerich, Alexios P. Giotis +3 more
This paper presents various Metamodel-Assisted Evolution Strategies which reduce the computational cost of optimisation problems involving time-consuming function evaluations.
Lecture notes in computer scienceCreating robust solutions by means of evolutionary algorithms
208 Citations1998Jürgen Branke
For real world problems it is often not sufficient to find solutions of high quality, but the solutions should also be robust, which means that the quality of the solution does not falter completely when a slight change of the environment occurs.
Fitness inheritance in genetic algorithms
175 Citations1995Robert E. Smith, B. A. Dike +1 more
An application to a GA-easy problem shows that greater efficiency can be obtained by evaluating only a small portion of the population, and a real-world search problem confirms these results.
SIAM ReviewMolecular Modeling of Proteins and Mathematical Prediction of Protein Structure
170 Citations1997Arnold Neumaier
The various mathematical problems arising, some deficiencies of the current models and algorithms, and possible (past and future) attacks to arrive at solutions to the protein-folding problem are discussed.
ViewOn evolutionary optimization with approximate fitness functions
160 Citations2000Yaochu Jin, Markus Olhofer +1 more
It is found that the evolutionary algorithm will converge incorrectly if the approximate model has false optima, so two strategies to control the evolution process are introduced and methods to eliminate false minima in neural network training are proposed.
IEEE Transactions on Neural NetworksSelecting concise training sets from clean data
143 Citations1993Mark Plutowski, Hannah J. White
Experimental results indicate that training upon exemplars selected in this fashion can save computation in general purpose use as well, and its use during network training is demonstrated.
Lecture notes in computer scienceAccelerating the convergence of evolutionary algorithms by fitness landscape approximation
143 Citations1998Alain Ratle
Numerical results presented for a test case show that the reconstruction algorithm can effectively reduces the number of fitness function calls for simple problems as well as for difficult multidimensional ones.
An efficient genetic algorithm with less fitness evaluation by clustering
136 Citations2002Hee-Su Kim, Sung-Bae Cho
This work proposes a hybrid GA based on clustering, which considerably reduces the evaluation number without any loss of performance, and divides the whole population into several clusters, and evaluates only one representative for each cluster.
Structural and Multidisciplinary OptimizationOptimal sizing, geometrical and topological design using a genetic algorithm
130 Citations1993D. E. Grierson, Wooguil Pak
Soft ComputingStructure optimization of neural networks for evolutionary design optimization
124 Citations2003M. H�sken, Yaochu Jin +1 more
Simulation results from turbine blade optimizations using the structurally optimized neural network models are presented to show that the performance of the models can be improved significantly through structure optimization.
Journal of AircraftParallel genetic algorithm implementation in multidisciplinary rotor blade design
118 Citations1996Jongsoo Lee, Prabhat Hajela
An adaptation of genetic algorithms in the design of large-scale multidisciplinary optimization problems is described, with the use of artificial neural networks for identifying a topology for problem decomposition and for generating global function approximations for use in optimization.
Metamodeling techniques for evolutionary optimization of computationally expensive problems: promises and limitations
112 Citations1999Mohammed El-Beltagy, Prasanth B. Nair +1 more
This work presents a general framework for coupling metamodeling techniques with evolutionary algorithms to reduce the computational burden of solving this class of optimization problems.
Applied Mechanics ReviewsOptimization and Experiments: A Survey
111 Citations1998Raphael T. Haftka, Elaine P. Scott +1 more
Lecture notes in computer scienceA Hierarchical Genetic Algorithm Using Multiple Models for Optimization
110 Citations2000M. Sefrioui, Jacques Périaux
The overall results are that a Hierarchical Genetic Algorithm using multiple models can achieve the same quality of results as that of a classic GA using only a complex model, but up to three times faster.
Efficient fitness estimation in noisy environments
101 Citations2001Jürgen Branke, Christian Schmidt +1 more
This paper suggests to use local regression for estimation, taking the fitness of neighboring individuals into account, and obtains information on the gradient of the fitness landscape, which may then additionally be used to perform local hill-climbing.
IEEE Transactions on Neural NetworksStatistical active learning in multilayer perceptrons
97 Citations2000Kenji Fukumizu
Two probabilistic active learning methods, which utilize the statistical variance of locations, are proposed to solve the problem of optimum input locations sometimes distributing densely around the same point and cause local minima in backpropagation training.
Don't evaluate, inherit
92 Citations2001Kumara Sastry, David E. Goldberg +1 more
Study of fitness inheritance as an efficiency enhancement technique for genetic and evolutionary algorithms indicates that for a fixed population size, the number of function evaluations can be reduced by 70% using a simple fitness inheritance technique.
Managing approximate models in evolutionary aerodynamic design optimization
81 Citations2002Yaochu Jin, Markus Olhofer +1 more
A framework for managing approximate models in generation-based evolution control is proposed and it is shown that this framework is well suited for parallel evolutionary optimization in which evaluation of the fitness function is time-consuming.
Structural and Multidisciplinary OptimizationA comparison of polynomial approximations and artificial neural nets as response surfaces
77 Citations1993William C. Carpenter, Jean‐François Barthélémy
A rule of thumb is developed for determining the number of nodes to be used on a hidden layer of an artificial neural net and thenumber of designs needed to train an approximation is discussed.
Proceedings of the National Academy of SciencesPeptide design by artificial neural networks and computer-based evolutionary search
76 Citations1998Gisbert Schneider, Wieland Schrödl +6 more
This strategy was successfully applied to the identification of novel peptides that fully prevent the positive chronotropic effect of anti-beta1-adrenoreceptor autoantibodies from the serum of patients with dilated cardiomyopathy.
Optimal sampling strategies for learning a fitness model
69 Citations2003Alain Ratle
The paper investigates the use of kriging interpolation and estimation as a function approximation tool for the optimization of computationally complex functions.
Journal of Computing in Civil EngineeringCommon Misconceptions about Neural Networks as Approximators
68 Citations1994William C. Carpenter, Jean‐François Barthélémy
The paper examines the computational efficiency of neural‐network approximations compared to polynomial approximation, examines the effect of using underdetermined neural‐ network approxIMations, and examines the computing time required to train neural networks compared to the time to develop polyn coefficients.
Structural OptimizationA rigorous framework for optimization of expensive functions by surrogates
65 Citations1999Andrew Booker, J. E. Dennis +4 more
Fitness inheritance in multi-objective optimization
63 Citations2002Jian-Hung Chen, David E. Goldberg +2 more
Fitness inheritance is investigated as a way to speed up multi-objective genetic and evolutionary algorithms and the number of function evaluations can be reduced with the use of fitness inheritance.
Genetic and Evolutionary Computation ConferenceInformed operators: speeding up genetic-algorithm-based design optimization using reduced models
61 Citations2000Khaled Rasheed, Haym Hirsh
There is little evidence on the use of simulation technology for the instruction of urgent medical complications to physical medicine and rehabilitation residents.
Engineering OptimizationAcceleration of the convergence speed of evolutionary algorithms using multi-layer neural networks
58 Citations2003Young-Seok Hong, Hungu Lee +1 more
The proposed acceleration method implements an online multi-layer neural network approximating the fitness calculation, which greatly decreases the computation time because the time-consuming fitness calculation can be replaced by the simple network output.
Soft ComputingOn Model-Based Evolutionary Computation
58 Citations1999Lawrence A. Bull
It is shown that in this paper the performance of the model-based architecture is greatly improved on more rugged/complex landscapes without a large increase in the amount of training data required.
Evaluation of Injection Island GA Performance on Flywheel Design Optimisation
58 Citations1998David Eby, Ronald C. Averill +2 more
The paper treats a greatly simplified case — one for which all two million possible solutions were enumerated, yielding a known global optimum, and results are compared for a hybrid iiGA to a parallel GA that uses a topological “ring” structure.
International Journal of Space StructuresOptimization of Large-Scale 3-D Trusses Using Evolution Strategies and Neural Networks
56 Citations1999Manolis Papadrakakis, Nikos D. Lagaros +1 more
The structural analysis phase is replaced by a neural network prediction for the computation of the necessary data for the evolution strategies (ES) optimization procedure, to investigate the efficiency of optimization algorithms for the solution of large-scale structural optimization problems.
Computers and Electronics in AgricultureAn intelligent approach for optimal control of fruit-storage process using neural networks and genetic algorithms
55 Citations1997Takeshi Morimoto, Josse De Baerdemaeker +1 more
This study presents a new intelligent control technique, including neural networks and genetic algorithms, for realizing the optimal control of the fruit-storage process, and suggests that the storage process should be treated as a dynamic process.
A neural network based generalized response surface multiobjective evolutionary algorithm
51 Citations2003Mirko Farina
An extension of single-objective NN-based generalized response surfaces (GRS) methods to POF approximation is proposed, which is not at all straightforward due to the complex relation between the POF and Pareto optimal set.
Neural NetworksNeural networks are useful tools for drug design
49 Citations2000Gisbert Schneider
A profound understanding of molecular recognition processes and the underlying molecular interaction patterns is a prerequisite for future progress and success in rational drug design.
Lecture notes in computer scienceOptimization of Noisy Fitness Functions by Means of Genetic Algorithms Using History of Search
49 Citations2000Yasuhito Sano, Hajime Kita
Combining landscape approximation and local search in global optimization
48 Citations2003Ko-Hsin Liang, Xin Yao +1 more
This work proposes an algorithm combining landscape approximation and local search (LALS) which is designed to tackle those difficult multimodal problems and demonstrates that LALS can solve problems with very rough landscapes and also that it has very good global reliability.
AIAA JournalComposite sandwich structure optimization with application to satellite components
47 Citations1996Srinivas Kodiyalam, Nagendra Somanath +1 more
Computer applications in the biosciencesArtificial neural networks and simulated molecular evolution are potential tools for sequence-oriented protein design
44 Citations1994Gisbert Schneider, Johannes Schuchhardt +1 more
It turns out that gradient search is well suited for optimization in smooth fitness landscapes without local minima, whereas evolution strategy seems to be a method of choice for optimized in a high-dimensional multimodal search space.
Design of vector quantization codebooks using a genetic algorithm
40 Citations2002Yiaowei Zheng, Bryant A. Julstrom +1 more
This paper describes a genetic algorithm for the problem of codebook design, which uses fitness inheritance to assign fitness values to most new chromosomes, rather than evaluating them.
Lecture notes in computer scienceApplication of evolutionary algorithms to protein folding prediction
36 Citations1998Antonio Piccolboni, Giancarlo Mauri
A new evolutionary algorithm is described, based on the notion of distance matrix representation, together with a software package that implements it that shows how evolutionary algorithms can be applied to protein folding prediction.
Comparison of methods for using reduced models to speed up design optimization
35 Citations2002Khaled Rasheed, Swaroop Vattam +1 more
Two methods for forming reduced models to speed up genetic-algorithm-based optimization by genetically engineering some individuals instead of using the regular Darwinian evolution approach are compared.
Genetic crossover strategy using an approximation concept
34 Citations2003K.S. Anderson, YuHong Hsu
A crossover strategy which utilizes an approximation concept to steer the locations of progeny in genetic algorithm and could greatly accelerate the speed of obtaining optimal solutions.
IEEE Transactions on Neural NetworksTraining data development with the D-optimality criterion
29 Citations1999M.H. Choueiki, Clark A. Mount‐Campbell
It is demonstrated that an optimality criterion borrowed from another field; namely the D-optimality criterion used in OED, can be used to enhance the training value of a small training data set.
Neural Processing LettersKnowledge Incorporation into Neural Networks From Fuzzy Rules
26 Citations1999Yaochu Jin, Bernhard Sendhoff
In the first approach, information from the derivative of the fuzzy system is used to regularize the neural network learning, whereas in the second approach the fuzzy rules are used as a catalyst to increase the learning speed.
Evolutionary algorithms with a coarse-to-fine function smoothing
23 Citations2002Dekun Yang, S.J. Flockton
Simulations show that the coarse-to-fine function smoothing method can improve traditional evolutionary algorithms in locating the global optimum of a given function.
AIAA JournalCalculation of compressible turbulent boundary layers on straight-tapered swept wings
22 Citations1976P. Bradshaw, G. A. Mizner +1 more
Genetic and Evolutionary Computation ConferenceMulti-objective optimisation of rolling rod product design using meta-modelling approach
22 Citations2002Victor Oduguwa, Rajkumar Roy
An engineering optimisation approach designed to bridge the gap between traditional solution methods in the industry and state-of-the-art techniques from the research community is reported on.
The Aeronautical JournalA case for multi-level optimisation in aeronautical design
21 Citations1999G. M. Robinson, Andy J. Keane
It is argued that this situation will continue until optimisation algorithms are developed which utilise the range of available analysis methods in a manner more like human designers, and a case made for their adoption as the way forward.
Journal of Optimization Theory and ApplicationsActuator placement based on reachable set optimization for expected disturbance
15 Citations1996James M. Redmond, Gordon G. Parker
Optimisation for Multilevel Problems: A Comparison of Various Algorithms
13 Citations1998Mohamed A. El-Beltagy, Andy J. Keane
This paper compares various optimization methods with genetic algorithms using three different strategies of multilevel optimization, and a sequential mixing strategy applied to a Genetic Algorithm with niche forming is shown to give best results.