Evolutionary optimization techniques for complex engineering design challenges
Evolutionary Algorithms (EA) as a family of computational models inspired by the natural process of evolution, have been applied with a great degree of success to complex design optimization problems. Potential solutions are encoded into a simple chromosome-like data structure, and recombination and/or mutation operators are repeatedly applied to a population of such potential solutions until a certain termination condition is reached. Their popularity lies in their ease of implementation and the ability to locate designs close to the global optimum.
However, thousands of calls to the analysis or simulation codes are often required to locate a near optimal solution in most conventional EA. Optimization problems in which the evaluation of solutions is expensive arise in a variety of contexts. The reasons for the high cost of evaluation and their effect on how many evaluations/generations can be afforded differ widely from one problem to another, as the following three examples may illustrate:
To circumvent the abovementioned problems, two common practices have been investigated in this project: 1) the use of approximation models in lieu of the exact analysis code, and 2) parallelization of the analysis code evaluations. Approximation models are used to replace calls to the computationally expensive codes as often as possible in the evolutionary search process. These approximation models are commonly known as surrogate models or metamodels.
Using approximation models, the computational burden can be greatly reduced since the efforts involved in building the surrogate model and optimization using it is much lower than the standard approach of directly coupling the simulation codes with the optimizer. Nevertheless, this approach does not always perform well when the approximation models are not managed properly. Inaccuracy of the models constructed is one of the many problems faced by most engineers and designers due to lack of data or curse of dimensionality. Hence, there is a need for methodologies to efficiently and effectively use approximation methods in evolutionary optimization in the presence of such problems.
One of the well-known strengths of EA is also in the ability to partition the population of individuals among multiple computing nodes. Doing so allows sub-linear speedup in computation and even super-linear speedup if possible algorithmic speed-up is also considered. When applied to small scale dedicated and homogeneous computing nodes, this seems to be a very formidable solution.
In real-life situations, there are many cases where heterogeneity exists, e.g. in a Grid computing environment, which emphasizes on the seamless sharing of computing resources across laboratories and even geographical boundaries, heterogeneity of the resources in the sharing pool is inevitable. In addition to that, function evaluation time can vary in many cases, for instance, in the case where the objective function is a variable-fidelity function. In such situation a conventional parallelization without taking into account the heterogeneity of computing resources, might lead the EA to be ineffective. Hence, a suitable parallel optimization framework that fits in a heterogeneous computing environment while maintaining (or improving) the good search property of evolutionary optimization is developed.
A Generic Surrogate-Assisted Memetic Search package is provided here for free download.
For enquiry relating to the software package, please contact: asysong@ntu.edu.sg
J. P. Luo, A. Gupta, PDF file.
and Z. K. Wang, "Evolutionary Optimization of Expensive Multi-objective Problems with Co-sub-Pareto Front Gaussian Process Surrogates", IEEE Transactions on Cybernetics, vol. 49, No. 5, 2019.W. M. Tan, R. Sagarna, A. Gupta, PDF file.
and C. K. Goh, "Knowledge Transfer through Machine Learning in Aircraft Design", IEEE Computational Intelligence Magazine, In Press, 2017.D. Lim, PDF file.
, A. Gupta, C. K. Goh and P. S. Dutta, "Towards a new Praxis in Optinformatics targeting knowledge re-use in evolutionary computation: simultaneous problem learning and optimization", Evolutionary Intelligence, Vol. 9, No. 4, pps. 203-220, 2016.A. Kattan, A. Agapitos,
, A. A. Alghamedi and M. O'Neill, "GP Made Faster with Semantic Surrogate Modelling", Information Sciences, Vol. 355-356, pps. 169-185, 2016.J. H. Zhong,
and W. T. Cai, "Self-Learning Gene Expression Programming", IEEE Transactions on Evolutionary Computation, Vol. 20, No. 1, pp. 65-80, 2016.A. Kattan and
, "Surrogate Genetic Programming: A Semantic Aware Evolutionary Search", Information Science, Vol. 296, pps. 345-359, 2015.M. Ellabaan, PDF file.
, Q. C. Nguyen and J.-L. Kuo, "Evolutionary Discovery of Transition States in Water Clusters", Journal of Theoretical and Computational Chemistry, Vol. 11, No. 05, Oct 2012.M. N. Le,
, S. Menzel, Y. Jin and B. Sendhoff, "Evolution by Adapting Surrogates", Evolutionary Computation Journal, Accepted and In Press 2012.S. D. Handoko, C. K. Kwoh and PDF file.
, "Feasibility Structure Modeling: An Effective Chaperon for Constrained Memetic Algorithms", IEEE Transactions on Evolutionary Computation, Accepted August 2009 and In Press.H. Soh, PDF file.
, Q. C. Nguyen, Q. H. Nguyen, M. S. Habibullah, T. Hung and J.-L. Kuo, "Discovering Unique, Low-Energy Pure Water Isomers: Memetic Exploration, Optimization and Landscape Analysis", IEEE Transactions on Evolutionary Computation, Vol. 14, No. 3, pp. 419-437, Jun 2010.D. Lim, Y. Jin, PDF file.
and B. Sendhoff, "Generalizing Surrogate-assisted Evolutionary Computation", IEEE Transactions on Evolutionary Computation, Vol. 14, No. 3, pp. 329-355, Jun 2010.Q. C. Nguyen,
, H. Soh and J.-L. Kuo, "Multiscale Approach to Explore the Potential Energy Surface of Water Clusters (H2O)₈ n≤8", Journal of Phys. Chem. A, Vol. 112, No. 28, pp. 6257-6261, 2008.D. Lim, PDF file.
, Y. Jin and B. Sendhoff, "A Study on Metamodeling Techniques, Ensembles, and Multi-Surrogates in Evolutionary Computation", Genetic and Evolutionary Computation Conference, London, UK, pp. 1288-1295, 2007, ACM Press.Z. Z. Zhou, PDF file.
, M. H. Lim and B. S. Lim, "Memetic Algorithm using Multi-Surrogates for Computationally Expensive Optimization Problems", Soft Computing Journal, Vol. 11, No. 10, pp. 957-971, August 2007.H. Soh, PDF file.
, M. Salahuddin, T. Hung and B. S. Lee, "Playing in the Objective Space: Coupled Approximators for Multi-Objective Optimization", IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making, Apr 2007.Z. Z. Zhou, PDF file.
, 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, Jan. 2007, pp. 66-76.D. Lim, PDF file.
, Y. Jin and B. Sendhoff, "Trusted Evolutionary Algorithm", IEEE Congress on Evolutionary Computation, July 16-21, CEC 2006, Sheraton Vancouver Wall Centre, Vancouver, BC, Canada.Z. Z. Zhou, PDF file.
, M. H. Nguyen and D. Lim, "A Study on Polynomial Regression and Gaussian Process Global Surrogate Model in Hierarchical Surrogate-Assisted Evolutionary Algorithm", Special Session on Evolutionary Computation in Dynamic and Uncertain Environments (ECiDUE'05), IEEE Congress on Evolutionary Computation, Edinburgh, United Kingdom, September 2-5, 2005.D. Lim, PDF file.
and B. S. Lee, "Inverse Multi-Objective Robust Evolutionary Design Optimization in the Presence of Uncertainty", GECCO 2005, Washington D.C. USA, June 25-29, 2005.Z. Z. Zhou, PDF file.
and P. B. Nair, "Hierarchical Surrogate-Assisted Evolutionary Optimization Framework", IEEE Congress on Evolutionary Computation, Special Session on Learning and Approximation in Design Optimization, Portland, USA, June 20-23, 2004.and A.J. Keane, "An Automated Optimization System for Aircraft Wing Design", Seventh International Conference on Artificial Intelligence in Design, Cambridge, UK, July 2002.