Radial Basis Surrogate Model Integrated to Evolutionary Algorithm for Solving Computation Intensive Black-Box Problems

Authors: Abdulbaset Saad, Adel Younis, Zuomin Dong

Abstract:

For design optimization with high-dimensional expensive problems, an effective and efficient optimization methodology is desired. This work proposes a series of modification to the Differential Evolution (DE) algorithm for solving computation Intensive Black-Box Problems. The proposed methodology is called Radial Basis Meta-Model Algorithm Assisted Differential Evolutionary (RBF-DE), which is a global optimization algorithm based on the meta-modeling techniques. A meta-modeling assisted DE is proposed to solve computationally expensive optimization problems. The Radial Basis Function (RBF) model is used as a surrogate model to approximate the expensive objective function, while DE employs a mechanism to dynamically select the best performing combination of parameters such as differential rate, cross over probability, and population size. The proposed algorithm is tested on benchmark functions and real life practical applications and problems. The test results demonstrate that the proposed algorithm is promising and performs well compared to other optimization algorithms. The proposed algorithm is capable of converging to acceptable and good solutions in terms of accuracy, number of evaluations, and time needed to converge.

Keywords: Differential evolution, engineering design, expensive computations, meta-modeling, radial basis function, optimization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1128937

References:

[1] S. Ong, P. B. Nair, and A. J. Keane, “Evolutionary optimization of computationally expensive problems via surrogate modeling,” AIAA Journal, vol. 41, no.4, pp. 687–696, 2003.
[2] Y. Jin, “Surrogate-assisted evolutionary computation: Recent advances and future challenges, Swarm and Evolutionary Computation,” vol. 1, pp. 61–70, 2011.
[3] Cressie, N. (1990), “The Origins of Kriging,” Mathematical Geology, vol. 22, pp. 239–252.
[4] Myers RH, Montgomery DC. Response Surface Methodology. New York: John Wiley & Sons, 1995.
[5] Beatson, R, Cherrie, J and Mouat, C, “Fast fitting of radial basis functions: methods based on preconditioned GMRES iteration Advances in Computational Mathematics,” vol. 11, pp. 253–270, 1998.
[6] Giunta A., and Watson, L., “A Comparison Of Approximation Modeling Techniques: Polynomial Versus Interpolating Models,” American Institute of Aeronautics and Astronautics, 1998.
[7] Forrester, A., and Keane, A., "Recent Advances in Surrogate- Based Optimization," Progress in Aerospace Sciences, vol. 45, pp. 50–79, 2009.
[8] Rikards, R., Abramovich, H., Auzins,J., Korjakins, A., Ozolinsh, O., Kalnins, K. and Green,T., "Surrogate Models for Optimum Design of Stiffened Composite Shells," Composite Structures, vol. 63, pp. 243–251, 2004.
[9] Queipo,N., Haftka,R. , Shyy, W., Goel, T., R. and Vaidyanathan and Tucker,P., "Surrogate-Based Analysis and Optimization," Progress in Aerospace Sciences, vol. 41, pp. 1-28, 2005.
[10] Kaymaz, I., and McMathon, C., "A Response Surface Method Based on Weighted Regression For Structural Reliability Analysis," Probabilistic Engineering Mechanics, 20, pp. 11-17, 2005.
[11] Schonlau, M., Welch, W., and Jones, D., "Global Versus Local Search in Constrained Optimization of Computer Models," New Development and Applications in Experimental Design, Institute of Mathematical Statistics, Haywood, CA, pp. 11–25, 1998.
[12] Sasena, M., Papalambros, P. and Goovaerts. P., "Global Optimization of Problems with Disconnected Feasible Regions Via Surrogate Modeling," in Proc. Proceedings 9th AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, AIAA, Atlanta, GA, 2002.
[13] Osio, I., and Amon, C., "An Engineering Design Methodology with Multistage Bayesian Surrogates and Optimal Sampling," Research in Engineering Design, vol. 8, no. 4, pp. 189-206, 1996.
[14] Cuevas, E., Zaldivar, D., Pérez-Cisneros, M., Ramírez-Ortegón, M, “Circle detection using discrete differential evolution optimization,” Pattern Analysis and Applications,vol. 14, no. 1, pp. 93-107, 2011.
[15] O. Kettani, F. Ramdani, B. Tadili, “A Quantum Differential Evolutionary Algorithm for the Independent Set Problem,” International Journal of Computer Applications, vol. 58, no. 14, 2012.
[16] Dattatray G. Regulwar, S. A. Choudhari, P. A. Raj “Differential Evolution Algorithm with Application to Optimal Operation of Multipurpose Reservoir,” J. Water Resource and Protection, vol. 2, pp. 560-568, 2010.
[17] Storn R. Price K., “Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces,” Journal of Global Optimization, vol. 11, pp. 341–359. 1997.
[18] Storn R., “On the usage of differential evolution for function optimization,” Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS), pp. 519–523, 1996.
[19] Rocca, P, Oliveri, G, Massa, A., “Differential Evolution as Applied to Electromagnetics,” IEEE Antennas and Propagation Magazine, vol. 53, no. 1, pp. 38-49, 2011.
[20] Ilonen, J, Kamarainen, J. K., and Lampinen, J., “Differential Evolution Training Algorithm for Feed Forward Neural Networks,” Neurol. Proc. Lett. vol. 17, 2003, pp. 93-105.
[21] Plagianakos, V. P. and Vrahatis, M. N. “Parallel Evolutionary Training Algorithms for Hardware-Friendly Neural Networks,” Natural Comp. vol. 1, 2002, pp. 307-322.
[22] Younis A., Space Exploration and Region Elimination Global Optimization Algorithms for Multidisciplinary Design Optimization, PhD Thesis, University of Victoria, 2010.
[23] R. Hardy, “Multiquadric Equations of Topography and Other Irregular Surfaces,” Journal of Geophysical Research, vol. 76, pp. 1905-1915, 1971.
[24] N. Dyn, D. Levin, and S. Rippa, “Numerical Procedures for Surface Fitting of Scattered Data By Radial Functions,” SIAM Journal of Scientific and Statistical Computing, vol. 7, no. 2, pp. 639-659, 1986.
[25] M. Powell, Radial Basis Functions for Multivariable Interpolation: A Review, Clarendon Press, Oxford, 1987.
[26] Y. Jin, “A comprehensive survey of fitness approximation in evolutionary computation,” Soft Computing, vol. 9, pp. 3-12, 2005.
[27] Charles Darwin, On the Origin of Species by Means of Natural Selection, or the Preservation of Favored Races in the Struggle for Life, p. 162, 1859.