Abstract
In this chapter we propose a surrogate-assisted framework for expensive single- and multi-objective evolutionary optimization, under a fixed budget of computationally intensive evaluations. The framework uses similarity-based surrogate models and an individual-based model management with pre-selection. Instead of existing frameworks where the surrogates are used to improve the performance of evolutionary operators or as local search tools, here we use them to allow for an augmented number of generations to evolve solutions. The introduction of the surrogates into the evolutionary cycle is controlled by a single parameter, which is related with the number of generations performed by the evolutionary algorithm.Numerical experiments are conducted in order to assess the applicability and the performance in constrained and unconstrained, single- and multi-objective optimization problems. The results show that the present framework arises as an attractive alternative to improve the final solutions with a fixed budget of expensive evaluations.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Pareto Front
- Evolutionary Computation
- Multiobjective Optimization
- Parent Population
- Multiobjective Optimization Problem
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Acar, E., Rais-Rohani, M.: Ensemble of metamodels with optimized weight factors. Struct. Multidisc. Optim. 37(3), 279–294 (2009)
Aha, D.W.: Editorial. Artif. Intell. Rev. 11(1-5), 1–6 (1997); special issue on lazy learning
Akbarzadeh-T, M.R., Davarynejad, M., Pariz, N.: Adaptive fuzzy fitness granulation for evolutionary optimization. International Journal of Approximate Reasoning 49(3), 523 (2008)
Altman, N.S.: An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician 46(3), 175–185 (1992)
Blanning, R.W.: The source and uses of sensivity information. Interfaces 4(4), 32–38 (1974)
Bui, L.T., Abbass, H.A., Essam, D.: Fitness inheritance for noisy evolutionary multi-objective optimization. In: GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, pp. 779–785. ACM, New York (2005)
Bull, L.: On model-based evolutionary computation. Soft Computing 3(2), 76–82 (1999)
Chen, J.H., Goldberg, D.E., Ho, S.Y., Sastry, K.: Fitness inheritance in multi-objective optimization. In: GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 319–326. Morgan Kaufmann Publishers Inc., San Francisco (2002)
Coello, C.A.C., Lamont, G.B., Veldhuizen, D.A.V.: Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic Publishers, Norwell (2002)
Deb, K.: An Efficient Constraint Handling Method for Genetic Algorithms. Computer Methods in Applied Mechanics and Engineering 186(2/4), 311–338 (2000)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002)
Ducheyne, E., De Baets, B., de Wulf, R.: Is fitness inheritance useful for real-world applications? In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 31–42. Springer, Heidelberg (2003)
Ducheyne, E., Baets, B.D., Wulf, R.D.: Fitness inheritance in multiple objective evolutionary algorithms: A test bench and real-world evaluation. Applied Soft Computing 8(1), 337–349 (2007)
El-Beltagy, M., Nair, P., Keane, A.: Metamodeling techniques for evolutionary optimization of computationally expensive problems: promises and limitations. In: Proceedings of Genetic and Evolutionary Conference, pp. 196–203. Morgan Kaufmann, Orlando (1999)
Emmerich, M., Giannakoglou, K., Naujoks, B.: Single- and multiobjective evolutionary optimization assisted by gaussian random field metamodels. Evolutionary Computation 10(4), 421–439 (2006)
Emmerich, M.T.M.: Single- and multi-objective evolutionary design optimization assisted by gaussian random field metamodels. PhD thesis, Technische Universitaet Dortmund (2005)
Ferrari, S., Stengel, R.F.: Smooth function approximation using neural networks. IEEE Transactions on Neural Networks 16(1), 24–38 (2005)
Forrester, A.I., Keane, A.J.: Recent advances in surrogate-based optimization. Progress in Aerospace Sciences 45, 50–79 (2009)
Giannakoglou, K.C.: Design of optimal aerodynamic shapes using stochastic optimization methods and computational intelligence. Progress in Aerospace Sciences 38(1), 43–76 (2002)
Goh, C.K., Tan, K.C.: A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization. IEEE Transactions on Evolutionary Computation 13(1), 103–127 (2009)
Goldberg, D.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Co., Reading (1989)
Grefenstette, J., Fitzpatrick, J.: Genetic search with approximate fitness evaluations. In: Proceedings of the International Conference on Genetic Algorithms and Their Applications, pp. 112–120 (1985)
Herrera, F., Lozano, M., Verdegay, J.L.: Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis. Artificial Intelligence Review 12(4), 265–319 (1998)
Jin, Y.: A comprehensive survey of fitness approximation in evolutionary computation. Soft Computing Journal 9(1), 3–12 (2005)
Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments-a survey. IEEE Transactions on Evolutionary Computation 9(3), 303–317 (2005)
Jin, Y., Olhofer, M., Sendhoff, B.: A framework for evolutionary optimization with approximate fitness functions. IEEE Transactions on Evolutionary Computation 6(5), 481–494 (2002)
Kecman, V.: Learning and soft computing: support vector machines, neural networks, and fuzzy logic models. Complex adaptive systems. MIT Press, Cambridge (2001)
Kim, H.S., Cho, S.B.: An efficient genetic algorithm with less fitness evaluation by clustering. In: Proceedings of the 2001 Congress on Evolutionary Computation, vol. 2, pp. 887–894 (2001)
Knowles, J.: Parego: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Transactions on Evolutionary Computation 10(1), 50–66 (2006)
Kybic, J., Blu, T., Unser, M.: Generalized sampling; a variational approach – Part I: Theory. IEEE Transactions on Signal Processing 50(8), 1965–1976 (2002)
Kybic, J., Blu, T., Unser, M.: Generalized sampling; a variational approach – Part II: Applications. IEEE Transactions on Signal Processing 50(8), 1977–1985 (2002)
Lim, D., Ong, Y., Jin, Y., Sendhoff, B.: A study on metamodeling techniques, ensembles, and multi-surrogates in evolutionary computation. In: Proceedings of the 9th annual conference on Genetic and evolutionary computation, pp. 1288–1295. ACM Press, New York (2007)
Lim, D., Jin, Y., Ong, Y.S., Sendhoff, B.: Generalizing surrogate-assisted evolutionary computation. IEEE Transactions on Evolutionary Computation (2008) (in press)
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd edn. Springer, Heidelberg (1996)
Mota, F., Gomide, F.: Fuzzy clustering in fitness estimation models for genetic algorithms and applications. In: IEEE International Conference on Fuzzy Systems, pp. 1388–1395 (2006) ISBN: 0-7803-9488-7
Myers, R.H., Montgomery, D.C.: Response Surface Methodology – Process and Product Optimization Using Designed Experiments. Wiley Series in Probability and Statistics. John Wiley & Sons Inc., New York (2002)
Ong, Y., Nair, P., Keane, A.: Evolutionary optimization of computationally expensive problems via surrogate modeling. AIAA Journal 41(4), 687–696 (2003)
Pilato, C., Tumeo, A., Palermo, G., Ferrandi, F., Lanzi, P.L., Sciuto, D.: Improving evolutionary exploration to area-time optimization of FPGA designs. Journal of Systems Architecture 54(11), 1046 (2008)
Praveen, C., Duvigneau, R.: Low cost PSO using metamodels and inexact pre-evaluation: Application to aerodynamic shape design. Computer Methods in Applied Mechanics and Engineering 198(9-12), 1087–1096 (2009)
Queipo, N., Arévalo, C., Pintos, S.: The integration of design of experiments, surrogate modeling, and optimization for thermoscience research. Engineering with Computers 20, 309–315 (2005)
Queipo, N.V., Haftka, R.T., Shyy, W., Goela, T., Vaidyanathana, R., Tucker, P.K.: Surrogate-based analysis and optimization. Progress in Aerospace Sciences 41(1), 1–28 (2005)
Rasheed, K., Vattam, S., Ni, X.: Comparison of methods for using reduced models to speed up design optimization. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 1180–1187. Morgan Kaufmann, New York (2002)
Rasheed, K., Ni, X., Vattam, S.: Comparison of methods for developing dynamic reduced models for design optimization. Soft Computing Journal 9, 29–37 (2005)
Regis, R.G., Shoemaker, C.A.: Local function approximation in evolutionary algorithms for the optimization of costly functions. IEEE Trans. Evolutionary Computation 8(5), 490–505 (2004)
Reyes-Sierra, M., Coello, C.A.C.: A study of fitness inheritance and approximation techniques for multi-objective particle swarm optimization. In: The 2005 IEEE Congress on Evolutionary Computation, vol. 1, pp. 65–72 (2005)
Runarsson, T.: Approximate evolution strategy using stochastic ranking. In: Yen, G.G., Wang, L., Bonissone, P., Lucas, S.M. (eds.) IEEE World Congress on Computational Intelligence, Vancouver, Canada (2006)
Runarsson, T.P.: Constrained Evolutionary Optimization by Approximate Ranking and Surrogate Models. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 401–410. Springer, Heidelberg (2004)
Runarsson, T.P., Yao, X.: Stochastic Ranking for Constrained Evolutionary Optimization. IEEE Transactions on Evolutionary Computation 4(3), 284–294 (2000)
Salami, M., Hendtlass, T.: A fast evaluation strategy for evolutionary algorithms. Applied Soft Computing 2, 156–173 (2003)
Sanchez, E., Pintos, S., Queipo, N.: Toward an optimal ensemble of kernel-based approximations with engineering applications. Structural and Multidisciplinary Optimization, 1–15 (2007)
Sastry, K., Goldberg, D.E., Pelikan, M.: Don’t evaluate, inherit. Tech. Rep. IlliGAL Report No. 2001013, Illinois Genetic Algorithms Laboratory (IlliGAL), Department of General Engineering, University of Illinois at Urbana-Champaign (2001)
Sastry, K., Pelikan, M., Goldberg, D.E.: Efficiency enhancement of genetic algorithms via building-block-wise fitness estimation. In: Congress on Evolutionary Computation, CEC 2004, pp. 720–727 (2004)
Schmidt, M., Lipson, H.: Coevolution of fitness predictors. IEEE Transactions on Evolutionary Computation 12(6), 736–749 (2008)
Shepard, D.: A two-dimensional interpolation function for irregularly-spaced data. In: Proceedings of the 1968 23rd ACM National Conference, pp. 517–524. ACM Press, New York (1968)
Sironen, S., Kangas, A., Maltamo, M., Kalliovirta, J.: Localization of growth estimates using non-parametric imputation methods. Forest Ecology and Management 256, 674–684 (2008)
Smith, R.E., Dike, B.A., Stegmann, S.A.: Fitness inheritance in genetic algorithms. In: SAC 1995: Proceedings of the 1995 ACM symposium on Applied computing, pp. 345–350. ACM Press, New York (1995)
Sokolov, A., Whitley, D., Barreto, A.M.S.: A note on the variance of rank-based selection strategies for genetic algorithms and genetic programming. Genetic Programming and Evolvable Machines 8(3), 221–237 (2007)
Srinivas, N., Deb, K.: Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation 2(3), 221–248 (1994)
Van Veldhuizen, D.A., Lamont, G.B.: Evolutionary computation and convergence to a pareto front. In: Koza, J.R. (ed.) Late Breaking Papers at the Genetic Programming 1998 Conference, Stanford University Bookstore, University of Wisconsin, Madison, Wisconsin, USA, Stanford, CA, USA (1998)
Wanner, E.F., Guimaraes, F.G., Takahashi, R.H.C., Lowther, D.A., Ramirez, J.A.: Multiobjective memetic algorithms with quadratic approximation-based local search for expensive optimization in electromagnetics. IEEE Transactions on Magnetics 44(6), 1126–1129 (2008)
Yang, D., Flockton, S.J.: Evolutionary algorithms with a coarse-to-fine function smoothing. In: IEEE International Conference on Evolutionary Computation, vol. 2, pp. 657–662 (1995)
Zhang, J., Yim, Y.S., Yang, J.: Intelligent selection of instances for prediction functions in lazy learning algorithms. Artif. Intell. Rev. 11(1-5), 175–191 (1997)
Zheng, X., Julstrom, B.A., Cheng, W.: Design of vector quantization codebooks using a genetic algorithm. In: Proceedings of 1997 IEEE International Conference on Evolutionary Computation, Piacataway, NJ, pp. 525–530 (1997)
Zhou, Z., Ong, Y.S., Nair, P.B.: Hierarchical surrogate-assisted evolutionary optimization framework. In: Congress on Evolutionary Computation, pp. 1586–1593. IEEE, Los Alamitos (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Fonseca, L.G., Barbosa, H.J.C., Lemonge, A.C.C. (2010). On Similarity-Based Surrogate Models for Expensive Single- and Multi-objective Evolutionary Optimization. In: Tenne, Y., Goh, CK. (eds) Computational Intelligence in Expensive Optimization Problems. Adaptation Learning and Optimization, vol 2. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10701-6_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-10701-6_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10700-9
Online ISBN: 978-3-642-10701-6
eBook Packages: EngineeringEngineering (R0)