New Adaptive Multi-Memetic Global Optimization Agorithm

This paper deals with the Simple MEC (SMEC) algorithm which belongs to a class of MEC algorithms. The algorithm was selected for investigation due to the following reasons: nowadays this algorithm and its modifications are successfully used for solving various optimization problems; the algorithm is highly suitable for parallel computations, especially for loosely coupled systems; the algorithm is not sufficiently studied --- there are relatively few modifications of SMEC (while, for instance, tens of various modifications are known for particle swarm optimization). Authors proposed an adaptive multi-memetic modification of SMEC algorithm, which includes a stage of landscape analysis for composing a set of basic adaptation strategies; software implementation of the algorithm is also presented. Performance investigation was carried out with a use of multi-dimensional benchmark functions of different classes. It was demonstrated that the concept of multi-population along with the incorporated landscape analysis procedure allows making a rough static adaptation of the algorithm to the objective function at the very beginning of evolution process at the cost of small computational expenses. Utilization of memes, in turn, helps the algorithm to correct possible errors of static adaptation during the evolution due to a closer investigation of search sub-domains

This work was supported by the Russian Foundation for Basic Research (RFBR project no. 16-07-00287)

References

[1] Weise T. Global optimization algorithms - theory and application. University of Kassel, 2008.

[2] Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy [Modern algorithms of search optimization. Nature-inspired algorithms]. Moscow, BMSTU Publ., 2014.

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

[4] Neri F., Cotta C., Moscato P. Handbook of memetic algorithms. Springer, 2011.

[5] Dawkins R. The Selfish Gene. Oxford Univ. Press, 1976.

[6] Sakharov M.K., Karpenko A.P. Multimemetic mind evolutionary computation algorithm for loosely coupled systems of desktop computers. Nauka i obrazovanie: nauchnoe izdanie MGTU im. N.E. Baumana [Science and Education: Scientific Publication], 2015, no. 10 (in Russ.). DOI: 10.7463/1015.0814435

[7] Sakharov M., Karpenko A. New parallel multi-memetic MEC-based algorithm for loosely coupled systems. Proc. VII Int. Conf. Optimization Methods and Application Optimization and applications OPTIMA--2016, 2016, pp. 124−126.

[8] Mersmann O., Bischl B., Trautmann H., et al. Exploratory landscape analysis. GECCO11, ACM, 2011, pp. 829--836. DOI: 10.1145/2001576.2001690

[9] Vassilev V.K., Fogarty T.C., Miller J.F. 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

[10] Bischl B., Mersmann O., Trautmann H., et al. Algorithm selection based on exploratory landscape analysis and cost-sensitive learning. GECCO14, ACM, 2012, pp. 313--320.

[11] Kerschke P., Preuss M., Hernandezet C., et al. Cell mapping techniques for exploratory landscape analysis. In: Tantar AA., et al. (eds). 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.

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

[13] Sun Ch., Sun Y., Wang W. A survey of MEC: 1998--2001. IEEE SMC 2002 Int. Conf., 2002, p. 9. DOI: 10.1109/ICSMC.2002.1175629

[14] Jie J., Zeng J., Ren Y. Improved mind evolutionary computation for optimizations. Proc. 5th World Congress Intell. Contr. Automat., 2004, pp. 2200--2204. DOI: 10.1109/WCICA.2004.1341978

[15] Jie J., Zeng J., Han C. An extended mind evolutionary computation model for optimizations. Appl. Math. Comput., 2007, vol. 185, iss. 2, pp. 1038--1049. DOI: 10.1016/j.amc.2006.07.037

[16] 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). Proc. 1st Int. Sci. Conf. IITI16. Proceedings of the First International Scientific Conference Intelligent Information Technologies for Industry (IITI16). 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

[17] Sobol I.M. On the distribution of points in a cube and the approximate evaluation of integrals. USSR Comput. Maths. Phys., 1967, vol. 7, iss. 4, pp. 86--112. DOI: 10.1016/0041-5553(67)90144-9

[18] 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 (IITI17). Advances in Intelligent Systems and Computing, vol. 679. Cham, Springer, 2017, pp. 398−407. DOI: https://doi.org/10.1007/978-3-319-68321-8_41

[19] Floudas A.A., Pardalos P.M., Adjiman C., et al. Handbook of test problems in local and global optimization. Boston, MA, Springer, 1999.

[20] Liang J.J., Qu B.Y., Suganthan P.N. Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization. Technical Report. Zhengzhou Univ., Nanyang Technological Univ., 2013.

[21] Nguyen Q.H., Ong Y.S., Krasnogor N. A study on the design issues of memetic algorithm. IEEE Congress on Evolutionary Computation, 2007, pp. 2390--2397. DOI: 10.1109/CEC.2007.4424770

[22] Hart W., Krasnogor N., Smith J.E., Memetic evolutionary algorithms. In: Hart W.E., Smith J.E., Krasnogor N. (eds). Recent Advances in Memetic Algorithms. Studies in Fuzziness and Soft Computing, vol. 166. Berlin, Heidelberg, Springer, 2005, pp. 3--27. DOI: https://doi.org/10.1007/3-540-32363-5_1

[23] Krasnogor N., Blackburne B., Burke E.K., et al. Multimeme algorithms for protein structure prediction. In: Guervos J.J.M., Adamidis P., Beyer H.G., Schwefel H.P., Fernandez-Villacanas J.L. (eds). Parallel Problem Solving from Nature --- PPSN VII. PPSN 2002. Lecture Notes in Computer Science, vol. 2439. Berlin, Heidelberg, Springer, pp. 769--778. DOI: https://doi.org/10.1007/3-540-45712-7_74

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

[25] 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.).

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

[27] Solis F.J., Wets R. J.-B. Minimization by random search techniques. Math. Oper. Res., 1981, vol. 6, no. 1, pp. 19--30. DOI: 10.1287/moor.6.1.19