research-article

ASAGA: an adaptive surrogate-assisted genetic algorithm

Authors:

Khaled RasheedAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1049 - 1056

https://doi.org/10.1145/1389095.1389289

Published: 12 July 2008 Publication History

Abstract

Genetic algorithms (GAs) used in complex optimization domains usually need to perform a large number of fitness function evaluations in order to get near-optimal solutions. In real world application domains such as the engineering design problems, such evaluations might be extremely expensive computationally. It is therefore common to estimate or approximate the fitness using certain methods. A popular method is to construct a so called surrogate or meta-model to approximate the original fitness function, which can simulate the behavior of the original fitness function but can be evaluated much faster. It is usually difficult to determine which approximate model should be used and/or what the frequency of usage should be. The answer also varies depending on the individual problem. To solve this problem, an adaptive fitness approximation GA (ASAGA) is presented. ASAGA adaptively chooses the appropriate model type; adaptively adjusts the model complexity and the frequency of model usage according to time spent and model accuracy. ASAGA also introduces a stochastic penalty function method to handle constraints. Experiments show that ASAGA outperforms non-adaptive surrogate-assisted GAs with statistical significance.

References

[1]

K. Rasheed. GADO: A genetic algorithm for continuous design optimization. Technical Report DCS-TR-352, Department of Computer Science, Rutgers University, 1998. Ph.D. Thesis.

Digital Library

[2]

Khaled Rasheed, Haym Hirsh: Learning to be selective in genetic-algorithm-based design optimization. Artificial Intelligence in Engineering Design Analysis and Manufacturing 13(3): 157--169, 1999.

Digital Library

[3]

Y. Jin and J. Branke. Evolutionary optimization in uncertain environments: A survey. IEEE Transactions on Evolutionary Computation, 9(3):303--317, 2005.

Digital Library

[4]

Y. S. Ong, P. B. Nair, A. J. Keane, and K. W. Wong. Surrogate-Assisted Evolutionary Optimization Frameworks for High-Fidelity Engineering Design Problems. In Y. Jin, editor, Knowledge Incorporation in Evolutionary Computation, Studies in Fuzziness and Soft Computing, pages 307--332. Springer, 2004.

[5]

Eric Sandgren. The utility of nonlinear programming algorithms. Technical report, Purdue University. Ph.D. Thesis, 1977.

[6]

Y. Jin. A comprehensive survey of fitness approximation in evolutionary computation. Soft Computing Journal, 9(1):3--12, 2005.

Digital Library

[7]

R. Jin, W. Chen, and T.W. Simpson. Comparative studies of metamodeling techniques under miltiple modeling criteria. Technical report 2000-4801, AIAA, 2000.

[8]

K. Sastry, D.E. Goldberg, and M. Pelikan. Don't evaluate, inherit. In Proceedings of Genetic and Evolutionary Computation Conference, pages 551--558, 2001. Morgan Kaufmann.

[9]

N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge Press, 2000.

Digital Library

[10]

LT Bui, HA Abbass, D Essam. Fitness inheritance for noisy evolutionary multi-objective optimization. Proceedings of the 2005 conference on Genetic and evolutionary computation, pages: 779--785. 2005.

Digital Library

[11]

H.-S. Kim and S.-B. Cho. An efficient genetic algorithm with less fitness evaluation by clustering. In Proceedings of IEEE Congress on Evolutionary Computation, pages 887--894, 2001. IEEE.

[12]

K Deb. An Efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 2000, Elsevier.

[13]

Y. Jin and B. Sendhoff. Reducing fitness evaluations using clustering techniques and neural networks ensembles. In Genetic and Evolutionary Computation Conference, volume 3102 of LNCS, pages 688--699, 2004. Springer.

[14]

Z. Z. Zhou, Y. S. Ong, P. B. Nair, A. J. Keane and K. Y. Lum. Combining Global and Local Surrogate Models to Accelerate Evolutionary Optimization. IEEE Transactions on Systems, Man and Cybernetics - Part C, Vol. 37, No. 1, pp. 66--76. 2007.

Digital Library

[15]

T. Joachims. 11 in: Making large-Scale SVM Learning Practical. Advances in Kernel Methods - Support Vector Learning, B. Schölkopf and C. Burges and A. Smola (ed.), MIT Press, 1999.

Digital Library

[16]

K. Rasheed and H. Hirsh. Informed operators: Speeding up genetic-algorithm-based design optimization using reduced models. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'2000), pp. 628--635, 2000.

[17]

X Llorà, K Sastry, DE Goldberg, A Gupta, L Lakshmi. Combating User Fatigue in iGAs: Partial Ordering, Support Vector Machines, and Synthetic Fitness. In Proceedings of the 2005 conference on Genetic and evolutionary computation, pages: 1363--1370. 2005.

Digital Library

[18]

William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in C: the Art of Scientific Computing. Cambridge University Press, Cambridge {England}; New York, 2nd edition, 1992.

Digital Library

[19]

W. Carpenter and J.-F. Barthelemy. A comparison of polynomial approximation and artificial neural nets as response surface. Technical report 92-2247, AIAA, 1992.

[20]

M. Hüscken, Y. Jin, and B. Sendhoff. Structure optimization of neural networks for aerodynamic optimization. Soft Computing Journal, 9(1):21--28, 2005.

Digital Library

[21]

Khaled Rasheed, Xiao Ni, Swaroop Vattam. "Comparison of Methods for Developing Dynamic Reduced Models for Design Optimization". Soft Computing Journal, 9(1):29--37, 2005.

Digital Library

[22]

T. Simpson, T. Mauery, J. Korte, and F. Mistree. Comparison of response surface and Kriging models for multidiscilinary design optimization. Technical report 98-4755, AIAA, 1998.

[23]

Z. Zhou, Y.S. Ong, and P.B. Nair. Hierarchical surrogate-assisted evolutionary optimization framework. In Congress on Evolutionary Computation, pages 1586--1593, 2004. IEEE.

[24]

Y. Jin, M. Hüsken, M. Olhofer, and B. Sendhoff. Neural networks for fitness approximation in evolutionary optimization. In Y. Jin, editor,Knowledge Incorporation in Evolutionary Computation, pages 281--305. Springer, Berlin, 2004.

[25]

D. Bueche, N.N. Schraudolph, and P. Koumoutsakos. Accelerating evolutionary algorithms with Gaussian process fitness function models. In IEEE Trans. on Systems, Man, and Cybernetics: Part C, 35(2):183--194, 2005.

Digital Library

[26]

C.M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, 1995.

Digital Library

[27]

L. Willmes, T. Baeck, Y. Jin, and B. Sendhoff. Comparing neural networks and kriging for fitness approximation in evolutionary optimization. In Proceedings of IEEE Congress on Evolutionary Computation, pages 663--670, 2003.

Cited By

Yu XWang YZhu LFilev DYao X(2024)Engine Calibration With Surrogate-Assisted Bilevel Evolutionary AlgorithmIEEE Transactions on Cybernetics10.1109/TCYB.2023.326745454:6(3832-3845)Online publication date: Jun-2024
https://doi.org/10.1109/TCYB.2023.3267454
Nishihara KNakata M(2024)A Surrogate-Assisted Partial Optimization for Expensive Constrained Optimization ProblemsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_24(391-407)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70068-2_24
Washino TMori N(2023)A Novel AutoAugment Utilizing Surrogate Model-Based Thermodynamical Genetic Algorithm2023 15th International Congress on Advanced Applied Informatics Winter (IIAI-AAI-Winter)10.1109/IIAI-AAI-Winter61682.2023.00057(272-277)Online publication date: 11-Dec-2023
https://doi.org/10.1109/IIAI-AAI-Winter61682.2023.00057
Show More Cited By

Index Terms

ASAGA: an adaptive surrogate-assisted genetic algorithm

Recommendations

Sub-structural niching in estimation of distribution algorithms
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

We propose a sub-structural niching method that fully exploits the problem decomposition capability of linkage-learning methods such as the estimation distribution algorithms and concentrate on maintaining diversity at the sub-structural level. The ...
An application of a GA with Markov network surrogate to feature selection

Surrogate models of fitness have been presented as a way of reducing the number of fitness evaluations required by evolutionary algorithms. This is of particular interest with expensive fitness functions where the time taken for building the model is ...
An improved class of real-coded Genetic Algorithms for numerical optimization

Over the last few decades, many improved Evolutionary Algorithms (EAs) have been proposed to tackle different types of optimization problems. Genetic Algorithm (GA) among other canonical algorithms have not shown consistent performance over a range of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
304
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)4

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yu XWang YZhu LFilev DYao X(2024)Engine Calibration With Surrogate-Assisted Bilevel Evolutionary AlgorithmIEEE Transactions on Cybernetics10.1109/TCYB.2023.326745454:6(3832-3845)Online publication date: Jun-2024
https://doi.org/10.1109/TCYB.2023.3267454
Nishihara KNakata M(2024)A Surrogate-Assisted Partial Optimization for Expensive Constrained Optimization ProblemsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_24(391-407)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70068-2_24
Washino TMori N(2023)A Novel AutoAugment Utilizing Surrogate Model-Based Thermodynamical Genetic Algorithm2023 15th International Congress on Advanced Applied Informatics Winter (IIAI-AAI-Winter)10.1109/IIAI-AAI-Winter61682.2023.00057(272-277)Online publication date: 11-Dec-2023
https://doi.org/10.1109/IIAI-AAI-Winter61682.2023.00057
Yang ZQiu HGao LChen LCai X(2023)Constraint boundary pursuing-based surrogate-assisted differential evolution for expensive optimization problems with mixed constraintsStructural and Multidisciplinary Optimization10.1007/s00158-022-03473-w66:2Online publication date: 15-Feb-2023
https://doi.org/10.1007/s00158-022-03473-w
Nishihara KNakata M(2022)Surrogate-assisted Differential Evolution with Adaptation of Training Data Selection Criterion2022 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI51031.2022.10022105(1675-1682)Online publication date: 4-Dec-2022
https://doi.org/10.1109/SSCI51031.2022.10022105
Muhammad JAltun H(2022)Guiding genetic search algorithm with ANN based fitness function: a case study using structured HOG descriptors for license plate detectionMultimedia Tools and Applications10.1007/s11042-022-14195-y82:12(17979-17997)Online publication date: 21-Nov-2022
https://doi.org/10.1007/s11042-022-14195-y
Jatschka TRaidl GRodemann T(2021)A General Cooperative Optimization Approach for Distributing Service Points in Mobility ApplicationsAlgorithms10.3390/a1408023214:8(232)Online publication date: 6-Aug-2021
https://doi.org/10.3390/a14080232
Ong JTeo J(2021)Systematic Review and Open Challenges in Hyper-heuristics Usage On Expensive Optimization Problems with Limited Number of Evaluations2021 IEEE Symposium on Industrial Electronics & Applications (ISIEA)10.1109/ISIEA51897.2021.9509993(1-6)Online publication date: 10-Jul-2021
https://doi.org/10.1109/ISIEA51897.2021.9509993
Li ZTian KLi HShi YWang B(2021)A competitive variable-fidelity surrogate-assisted CMA-ES algorithm using data mining techniquesAerospace Science and Technology10.1016/j.ast.2021.107084(107084)Online publication date: Sep-2021
https://doi.org/10.1016/j.ast.2021.107084
Liu CWan ZLiu YLi XLiu D(2021)Trust-region based adaptive radial basis function algorithm for global optimization of expensive constrained black-box problemsApplied Soft Computing10.1016/j.asoc.2021.107233105:COnline publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1016/j.asoc.2021.107233
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten