Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Мультимемеевый алгоритм эволюции разума для слабосвязанных систем на основе персональных компьютеров

# 10, октябрь 2015
DOI: 10.7463/1015.0814435
Файл статьи: SE-BMSTU...o452.pdf (812.58Кб)
авторы: Сахаров М. К.1,*, профессор, д.ф.-м.н. Карпенко А. П.1, Велисевич Я. И.1

УДК 519.6

1 МГТУ им. Н.Э. Баумана, Москва, Россия

Решение современных задач оптимизации проектных решений, зачастую, сопряжено с большими затратами вычислительных ресурсов. В настоящее время одним из наиболее перспективных методов повышения эффективности работы алгоритмов для решения подобных задач являются распределенные параллельные вычисления.
В тоже время, простого увеличения вычислительных мощностей недостаточно для решения практически значимых задач. Необходима разработка специализированных алгоритмов, ориентированных на конкретную параллельную систему, что позволило бы повысить эффективность метода, благодаря использованию особенностей архитектуры вычислительной системы.
В данной работе предложен параллельный гибридный алгоритм эволюции разума HMEC, который относится к классу меметических алгоритмов глобальной оптимизации. Отличительной особенностью алгоритма является использование ряда различных мемов, позволяющих алгоритму адаптироваться к разного рода целевым функциям. Под мемом понимают какой-либо алгоритм локальной оптимизации, уточняющий текущее решение исходной задачи оптимизации на определенных шагах выполнения основного алгоритма. В широком смысле, меметические алгоритмы представляют собой гибридизацию одного из популяционных алгоритмов глобального поиска и одного или нескольких алгоритмов локальной оптимизации.
Алгоритм ориентирован на использование в слабосвязанных вычислительных системах, состоящих из персональных компьютеров.
В рамках работы выполнена программная реализация данного алгоритма с использованием декомпозиции области поиска на стадии первичной инициализации популяции. В качестве инструментов реализации использовались язык программирования Python и интерфейс обмена сообщениями MPI, как один из наиболее распространенных и ориентированных на слабосвязанные системы интерфейсов.
Широкое исследование эффективности алгоритма проведено на наборе тестовых модифицированных функций Розенброка, Вейерштрасса, Гриванка и Швефеля. Эффективность алгоритма оценена с помощью таких показателей, как оценка вероятности локализации глобального экстремума, среднее число итераций и среднее число испытаний. Также определено и проанализировано число побед мемов в ходе локальных состязаний в процессе мультистарта для каждой тестовой функции. Результаты исследований показывают, что параллельный меметический алгоритм HMEC позволяет во многих случаях с высокой вероятностью и точностью локализовать глобальный экстремум для заданной целевой функции чем последовательная версия алгоритма.
Результаты исследования показывают перспективность дальнейших модификаций и развития параллельных мультимемеевых алгоритмов глобальной оптимизации.

Список литературы
  1. Karpenko A., Posypkin M., Rubtsov A., Sakharov M. Multi-memetic Global Optimization based on the Mind Evolutionary Computation // Proceedings of the IV International Conference on Optimization Methods and Application “Optimization and Applications” (OPTIMA-2013). Moscow: Dorodnicyn Computing Centre of RAS, 2013. P. 83-84.
  2. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446.
  3. Карпенко А.П., Сахаров М.К. Мультимемеевая глобальная оптимизация на основе алгоритма эволюции разума // Информационные технологии. 2014. № 7. С . 23-30.
  4. Weise T. Global Optimization Algorithms. Theory and Application. University of Kassel, 2008. 758 p.
  5. Talbi E. A Taxonomy of Hybrid Metaheuristics // Journal of Heuristics. 2002. Vol. 8, iss. 5. P. 541-564. DOI:10.1023/A:1016540724870
  6. Dawkins R. The Selfish Gene. Oxford University Press, 1976. 384 p.
  7. Nguyen Q.H., Ong Y.S., Krasnogor N. A Study on the Design Issues of Memetic Algorithm // IEEE Congress on Evolutionary Computation (CEC 2007). IEEE Publ., 2007. P. 2390-2397. DOI: 10.1109/CEC.2007.4424770
  8. Ong Y.S., Lim M.H., Zhu N., Wong K.W. Classification of adaptive memetic algorithms: A comparative study // IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. 2006. Vol. 36, iss. 1. P. 141-152. DOI: 10.1109/TSMCB.2005.856143
  9. Chengyi S., Yan S., Wanzhen W. A Survey of MEC: 1998-2001 // 2002 IEEE International Conference on Systems, Man and Cybernetics. Vol. 6. IEEE Publ., 2002. P. 445-453. DOI: 10.1109/ICSMC.2002.1175629
  10. Jie J., Zeng J. Improved Mind Evolutionary Computation for Optimizations // Proceedings of 5th World Congress on Intelligent Control and Automation. Vol. 3. IEEE Publ., 2004. P. 2200-2204. DOI: 10.1109/WCICA.2004.1341978
  11. Floudas A.A., Pardalos P.M., Adjiman C., Esposito W.R., Gümüs Z.H., Harding S.T., Klepeis J.L., Meyer C.A., Schweiger C.A. Handbook of Test Problems in Local and Global Optimization. Kluwer, Dordrecht, 1999. 441 p.
  12. Nelder J.A., Meade R. A Simplex Method for Function Minimization // Computer Journal. 1965. Vol. 7, iss. 4. P. 308-313. DOI: 10.1093/comjnl/7.4.308
  13. 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 201311. Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China; Technical Report. Nanyang Technological University, Singapore, 2013. 32 p.
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2024 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)