Reduction of function evaluation in differential evolution using nearest neighbor comparison
Tóm tắt
Approximation models have recently been introduced to differential evolution (DE) to reduce expensive fitness evaluation in function optimization. These models basically require additional control parameters and/or external storage for the learning process. Depending on the choice of the additional parameters, the strategies may have different levels of efficiency. The present paper introduces an alternative way for reducing function evaluations in differential evolution, which does not require additional control parameter and external archive. The algorithm uses a nearest neighbor in the search population to judge whether a new point is worth evaluating, so that unnecessary evaluations can be avoided. The performance of this new scheme of differential evolution, known as differential evolution with nearest neighbor comparison (DE-NNC), is demonstrated and compared with that of standard DE as well as approximation models including differential evolution using k-nearest neighbor predictor (DE-kNN), differential evolution using speeded-up k-nearest neighbor estimator (DE-EkNN) and DE with estimated comparison method through some test functions. The results show that DE-NNC can produce considerable reduction of actual function calls compared to DE and is competitive to DE-kNN, DE-EkNN and DE with estimated comparison.
Tài liệu tham khảo
Storn, R., Price, K.: Differential Evolution–A Simple and Efficient Adaptive Scheme for Global Optimization Over Continuous Spaces. International Computer Science Institute, Berkeley (1995)
Das, S., Suganthan, P.N.: Differential evolution: a survey of the state-of-the-art. IEEE Trans. Evol. Comput. 15(1), 4–31 (2011)
Jin, Y.: A comprehensive survey of fitness approximation in evolutionary computation. Soft Comput. 9(1), 3–12 (2005)
Khu, S.T., Liu, Y., Savic, D.A.: A fast calibration technique using a hybrid genetic algorithm—neural network approach: application to rainfall-runoff models. In The sixth international conference of hydroinformatics (HIC2004), Singapore (2004)
Liu, Y., Khu, S. T.: Automatic calibration of numerical models using fast optimization by fitness approximation. In 2007 International joint conference on neural networks (IJCNN), Orlando, Florida, pp 1073–1078 (2007)
Yan, S., Minsker, B.S.: A dynamic meta-model approach to genetic algorithm solution of a risk-based groundwater remediation design model. In American Society of Civil Engineers (ASCE) Environmental and Water Resources Institute (EWRI) world water and environmental resources congress 2003 and related symposia, Philadelphia, PA (2003)
Giunta, A.A., Watson, L.T., Koehler, J.: A comparison of approximation modeling techniques: polynomial versus interpolating models. In Proceedings of the 7th IAA/USAF/NASA/ISSMO symposium on multidisciplinary analysis and design, pp 392–404 (1998)
Simpson, T.W., Mauery, T.M., Korte, J.J., Mistree, F.: Comparison of response surface and kriging models for multidisciplinary design optimization. Am. Inst. Aeronaut. Astronaut. 98(7), 1–16 (1998)
Shyy, W., Tucker, P.K., Vaidyanathan, R.: Response surface and neural network techniques for rocket engine injector optimization. J. Propuls. Power 17(2), 391–401 (2001)
Guimaraes, F.G., Wanner, E.F., Campelo, F., Takahashi, R.H., Igarashi, H., Lowther, D.A., Ramirez, J.A.: Local learning and search in memetic algorithms. In: Proceedings of the 2006 IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada, pp. 9841–9848 (2006)
Jin, Y., Sendhoff, B.. Reducing fitness evaluations using clustering techniques and neural network ensembles. In Genetic and Evolutionary Computation-GECCO 2004, Springer, Berlin Heidelberg, pp 688–699 (2004)
Jin, Y., Olhofer, M., Sendhoff, B. (2000). On evolutionary optimization with approximate fitness functions. In GECCO, pp 786–793
Jin, Y., Olhofer, M., Sendhoff, B.: A framework for evolutionary optimization with approximate fitness functions. IEEE Trans Evolution Comput 6(5), 481–494 (2002)
Liu, Y., Sun, F.: A fast differential evolution algorithm using k-Nearest Neighbour predictor. Expert Syst Appl 38(4), 4254–4258 (2011)
Park, S.Y., Lee, J.J.: An efficient differential evolution using speeded-up k-nearest neighbor estimator. Soft Comput. 18(1), 35–49 (2014)
Takahama, T., Sakai, S.: Reducing function evaluations in differential evolution using rough approximation-based comparison. In IEEE congress on evolutionary computation (CEC) 2008, pp 2307–2314 (2008)
Takahama, T., Sakai, S.: A comparative study on kernel smoothers in differential evolution with estimated comparison method for reducing function evaluations. In IEEE congress on evolutionary computation (CEC) 2009, pp 1367–1374 (2009)
Takahama, T., Sakai, S.: Reducing function evaluations using adaptively controlled differential evolution with rough approximation model. In computational intelligence in expensive optimization problems, pp 111–129, Springer, Berlin Heidelberg (2010)
Takahama, T., Sakai, S.: Efficient constrained optimization by the \(\varepsilon \) constrained differential evolution with rough approximation using kernel regression. In IEEE congress on evolutionary computation (CEC) 2013, pp 1334–1341 (2013)
Neri, F., Tirronen, V.: Recent advances in differential evolution: a survey and experimental analysis. Artif. Intel. Rev. 33(1–2), 61–106 (2010)