Новый адаптивный метод мультимеметической глобальной оптимизации для слабосвязанных вычислительных систем

Предложен новый параллельный адаптивный мультимеметический популяционный метод для эффективного решения задач глобальной оптимизации на слабосвязанных вычислительных системах. Рассмотрены существующие подходы к синтезу адаптивных популяционных алгоритмов и методы их распараллеливания; выделены особенности класса слабосвязанных параллельных вычислительных систем, которые необходимо учитывать при разработке алгоритмов для данных систем. Предложенный алгоритм основан на двухуровневой схеме адаптации. Верхний уровень является статическим и позволяет провести настройку свободных параметров базового алгоритма до начала оптимизации на основе информации о целевой функции, полученной методами ландшафтного анализа. Нижний уровень адаптации динамический и реализован за счет гибридизации базового алгоритма с алгоритмами локальной оптимизации (мемами). Предложена новая статическая схема балансировки загрузки для отображения алгоритма на параллельные вычислительные узлы слабосвязанных вычислительных систем. Предложенная схема балансировки учитывает как особенности алгоритма, так и архитектуру используемой вычислительной системы, что позволяет повысить эффективность решения задачи оптимизации по сравнению с традиционными схемами балансировки. Проведено подробное исследование эффективности предложенного алгоритма и его программной реализации с использованием многомерных тестовых функций различных классов

Литература

[1] Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М., Изд-во МГТУ им. Н.Э. Баумана, 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] Карпенко А.П., Сахаров М.К. Мультимемеевая глобальная оптимизация на основе алгоритма эволюции разума. Информационные технологии, 2014, № 7, с. 23--30.

[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] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб., БХВ-Петербург, 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] Карпенко А.П., Белоус В.В. Методы оптимизации (базовый курс). М., Изд-во МГТУ им. Н.Э. Баумана, 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] Сахаров М.К. Исследование модели контроля заболеваемости с использованием импульсной вакцинации. Наукоемкие технологии и интеллектуальные системы. М., МГТУ им. Н.Э. Баумана, 2018, с. 116--120.