New Adaptive Multi-Memetic Global Optimization Algorithm for Loosely Coupled Systems

This study introduces a new parallel adaptive multi-memetic population-based algorithm for solving global optimization problems efficiently on loosely coupled computing systems. The existent approaches to the synthesis of adaptive population-based algorithms were considered along with the parallelization techniques; distinct features of the loosely coupled computing systems were identified; those features have to be considered carefully when designing algorithms for this class of systems. The proposed algorithm is based on the two level adaptation strategies. The upper level is a static one and allows one to adjust numeric values of the basic algorithm's free parameters before the optimization process using the information about an objective function obtained by means of the landscape analysis. The lower level is a dynamic one and was implemented by means of hybridization of the basic algorithm and several local search methods (memes). The work also presents a new static load balancing method for mapping the proposed algorithm onto parallel computing nodes. The proposed load balancing method takes into consideration both the optimization algorithm's distinct features and the computing system's architecture. This results in higher efficiency of the optimization algorithm comparing to the traditional load balancing methods. A wide performance investigation of the proposed optimization algorithm and its software optimization was carried out in this work with a use of high-dimensional benchmark functions of various classes

References

[1] Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy [Modern search optimization algorithms. Algorithms, inspired by nature]. Moscow, BMSTU Publ., 2014.

[2] Sakharov M., Karpenko A. A new way of decomposing search domain in a global optimization problem. In: Abraham A., Kovalev S., Tarassov V., Snasel V., Vasileva M., Sukhanov A. (eds). Proceedings of the Second International Scientific Conference "Intelligent Information Technologies for Industry" (IITI’17). IITI 2017. Advances in Intelligent Systems and Computing, vol 679. Springer, Cham, 2017, pp. 398--407. DOI: https://doi.org/10.1007/978-3-319-68321-8_41

[3] Neri F., Cotta C., Moscato P. Handbook of memetic algorithms. Springer, 2012. DOI: 10.1007/978-3-642-23247-3

[4] Vassilev V., Fogarty T., Miller J. Smoothness, ruggedness and neutrality of fitness landscapes: from theory to application. In: Ghosh A., Tsutsui S. (eds). Advances in Evolutionary Computing. Natural Computing Series. Berlin, Heidelberg, Springer, 2003, pp. 3--44. DOI: https://doi.org/10.1007/978-3-642-18965-4_1

[5] Krasnogor N. Studies on the theory and design space of memetic algorithms. Ph.D. Thesis, University of the West of England, 2002.

[6] Moscato P. On evolution, search, optimization, genetic algorithms and martial arts. Towards memetic algorithms. Technical Report Concurrent Computation Program. California Institute of Technology, 1989.

[7] Ang J.H., Tan K.C., Mamun A.A. An evolutionary memetic algorithm for rule extraction. Expert Syst. App., 2010 vol. 37, iss. 2, pp. 1302--1315. DOI: https://doi.org/10.1016/j.eswa.2009.06.028

[8] Ong Y.S., Lim M.H., Zhu N., et al. Classification of adaptive memetic algorithms: a comparative study. IEEE Trans. Syst., Man, Cybern. B Cybern., 2006, vol. 36, iss. 1, pp. 141--152. DOI: 10.1109/TSMCB.2005.856143

[9] Kerschke P., Preuss M., Hernandez C., et al. Cell mapping techniques for exploratory landscape analysis. EVOLVE a bridge between probability, set oriented numerics, and evolutionary computation V. Advances in Intelligent Systems and Computing, vol. 288, Cham, Springer, 2014, pp. 115--131. DOI: https://doi.org/10.1007/978-3-319-07494-8_9

[10] Munoz M.A., Kirley M., Halgamuge S.K. Exploratory landscape analysis of continuous space optimization problems using information content. IEEE T. Evolut. Comput., 2015, vol. 19, iss. 1, pp. 74--87. DOI: 10.1109/TEVC.2014.2302006

[11] Karpenko A.P., Sakharov M.K. Multi-memes global optimization based on the algorithm of mind evolutionary computation. Informatsionnye tekhnologii [Information Technologies], 2014, no. 7, pp. 23--30 (in Russ.).

[12] Sakharov M.K., Karpenko A.P. Adaptive load balancing in the modified mind evolutionary computation algorithm. Supercomputing Frontiers and Innovations, 2018, vol. 5, no. 4, pp. 5--14, 2018. DOI: 10.14529/jsfi180401

[13] Sun Ch., Sun Y., Wang W. A survey of MEC: 1998-2001. IEEE SMC, 2002, vol. 6, pp. 445--453. DOI: 10.1109/ICSMC.2002.1175629

[14] Sakharov M., Karpenko A. Performance investigation of mind evolutionary computation algorithm and some of its modifications. In: Abraham A., Kovalev S., Tarassov V., Snasel V. (eds). Proceedings of the First International Scientific Conference "Intelligent Information Technologies for Industry" (IITI’16). Advances in Intelligent Systems and Computing, vol. 450. Cham, Springer, 2016, pp. 475--486. DOI: https://doi.org/10.1007/978-3-319-33609-1_43

[15] Voevodin V.V., Voevodin Vl.V. Parallelnye vychisleniya [Parallel computations]. St. Petersburg, BKhV-Peterburg Publ., 2002.

[16] Nelder J.A., Mead R. A simplex method for function minimization. Comput. J., 1965, vol. 7, iss. 4, pp. 308--313. DOI: https://doi.org/10.1093/comjnl/7.4.308

[17] Hooke R., Jeeves T.A. Direct search solution of numerical and statistical problems. JACM, 1961, vol. 8, iss. 2, pp. 212--229. DOI: 10.1145/321062.321069

[18] Karpenko A.P., Belous V.V. Metody optimizatsii (bazovyy kurs) [Optimization methods (base course)]. Moscow, BMSTU Publ., 2016.

[19] Momin J., Yang X.S. A literature survey of benchmark functions for global optimization problems. IJMMNO, 2013, vol. 4, no. 2, pp. 150--194. DOI: 10.1504/IJMMNO.2013.055204

[20] Sakharov M.K. Issledovaniye modeli kontrolya zabolevayemosti s ispolzovaniyem impulsnoy vaktsinatsii [Study on disease control method using pulse vaccination]. Naukoemkie tekhnologii i intellektualnye sistemy [High Technology and Intelligent Systems]. Moscow, BMSTU Publ., 2018, pp. 116--120 (in Russ.).