ASAGA: an adaptive surrogate-assisted genetic algorithm

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.
• 2: Khaled Rasheed , Haym Hirsh, Learning to be selective in genetic-algorithm-based design optimization, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.13 n.3, p.157-169, June 1999 [doi>10.1017/S0890060499133043]
• 3: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 2001
• 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 - A Fusion of Foundations, Methodologies and Applications, v.9 n.1, p.3-12, January 2005 [doi>10.1007/s00500-003-0328-5]
• 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: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 10: Lam T. Bui , Hussein A. Abbass , Daryl Essam, Fitness inheritance for noisy evolutionary multi-objective optimization, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068141]
• 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.
• 15: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 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: Xavier Llorà , Kumara Sastry , David E. Goldberg , Abhimanyu Gupta , Lalitha Lakshmi, Combating user fatigue in iGAs: partial ordering, support vector machines, and synthetic fitness, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068228]
• 18: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, New York, NY, 1992
• 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üsken , Y. Jin , B. Sendhoff, Structure optimization of neural networks for evolutionary design optimization, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.9 n.1, p.21-28, January 2005 [doi>10.1007/s00500-003-0330-y]
• 21: K. Rasheed , X. Ni , S. Vattam, Comparison of methods for developing dynamic reduced models for design optimization, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.9 n.1, p.29-37, January 2005 [doi>10.1007/s00500-003-0331-x]
• 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.
• 26: Christopher M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, Inc., New York, NY, 1995
• 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.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Experimentation, Performance

Keywords:
adaptive meta-modeling, fitness approximation, genetic algorithms, surrogate-assisted evolution