МУЛЬТИ-МЕМЕТИЧЕСКИЙ МУРАВЬИНЫЙ АЛГОРИТМ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

  • Б. K. Лебедев Южный Федеральный Университет
  • О. Б. Лебедев Южный Федеральный Университет
  • Е.О. Лебедева Южный Федеральный Университет
Ключевые слова: Муравьиный алгоритм, мем, меметический алгоритм, мульти-меметическая гибридизация, адаптация, рой частиц, оптимизация

Аннотация

Рассматривается задача конструирования мульти-меметического муравьиного ал-
горитма (МА), включающая разработку 5 мемов и выбор целесообразной стратегии ис-
пользования того или иного мема из роя доступных мемов. Работа МА дискретной опти-
мизации иллюстрируется на примере задачи разбиения графа на подграфы, широко приме-
няющейся при решении таких задач, как кластеризация, раскраска, выделения клик, паро-
сочетания, разбиения СБИС и т.д. Задан граф G(X, U), где Х – множество вершин, |X| = n, U
– множество ребер. Необходимо разбить множество X на подмножества X1 и X2, X1X2=X,
X1X2=, Xi. Для поиска решения задачи используется полный граф поиска решений
(ГПР) R(X,E). В отличие от канонической парадигмы МА агентом на ГПР R(X,E) строится
не маршрут, а формируется подграф. На первом этапе каждой итерации МА конструк-
тивным алгоритмом (мемом) каждый из агентов формирует множествo X1k. Во всех ме-
мах формирование множества X1k осуществляется последовательно (пошагово). На каж-
дом шаге t агент применяет вероятностное правило выбора следующей вершины для вклю-
чения ее в формируемое множество X1k(t). В первом меме поиск решений осуществляется
на ГПР R(X,E), а феромон откладывается на множестве ребер E. Основное отличие вто-
рого мема от первого заключается в том, что из процесса поиска агентом решения исклю-
чается полный граф поиска R(X,E). Феромон откладывается только на вершинах графа
G(X,U). Это приводит к резкому сокращению числа феромонных точек и, следовательно,
памяти, так как число ребер графа R(X,E) значительно больше числа вершин. Особенность
третьего мема М3 заключается в том, что на вершине xi графа G(X,U) формируются два
показателя φi1k и φi2k: φi1k – суммарный уровень феромона, отложенного на xi, только в тех
случаях, когда xi,была в составе X1k(t); φi2k –суммарный уровень феромона, отложенного на
xi, только в тех случаях, когда xi, не входила в состав X1k(t). Показатель φ1i характеризует
для вершины xi предпочтительность узла X1k(t). Четвертый мем отличается от третьего
тем, что агентом формируются параллельно два множества X1k(t) и X2k(t). В пятом меме
для уменьшения общей трудоемкости поисковой процедуры используется подход, основан-
ный на декомпозиции структуры данных в процессах формирования множества вершин
X1kX и отложения феромона. В модифицированном подходе отложение феромона осуще-
ствляется на графе R(X,E), а формирование подмножества вершин X1kX осуществляется
на ориентированном графе B(X,V). Предложены два подхода к построению адаптивного
мульти-меметического алгоритма, использующего рой мемов. Мульти-меметическая гиб-
ридизация приводит к алгоритму, обладающему свойствами самоадаптации, поскольку в
процессе поиска мемы конкурируют между собой, и победивший на данном этапе поиска
мем используется на последующих итерациях. За счет повышения эффективности поиска,
гибридный алгоритм дает возможность уменьшить число агентов в системе и повысить
тем самым его быстродействие.

Литература

1. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохнов-
ленные природой: учеб. пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 448 с.
2. Cotta C., Moscato P.B. Handbook of memetic algorithms. – Springer, 2012. – 368 p.
3. Moscato P., Corne D., Glover F., Dorigo M. Memetic algorithms: A short introduction // In
book: New Ideas in Optimization. – McGraw-Hill, 1999. – P. 219-234.
4. Krasnogor N. Studies on the theory and design space of memetic algorithms. Doct. diss.
– Bristol: Univ. of the West of England, 2002. – 412 р.
5. Neri F., Cotta C. Memetic algorithms and memetic computing optimization: A literature review
// Swarm and Evolutionary Computation. – 2012. – P. 1-14.
6. Карпенко А.П., Сахаров М.К. Мультимемеевая глобальная оптимизация на основе алго-
ритма эволюции разума // Информационные технологии. – 2014. – № 7. – С. 23-30.
7. Карпенко А.П., Чернобривченко К.А. Мультимемеевая модификация гибридного му-
равьиного алгоритма непрерывной оптимизации HCIAC // Электронный научно-
технический журнал. Эл. №ФС7748211, 2012.
8. Лебедев Б.К., Лебедев О.Б. Меметический алгоритм разбиения // Вестник Ростовского
государственного университета путей сообщения. – 2017. – № 2 (62). – С. 136-145.
9. Лебедев Б.К., Лебедев О.Б. Гибридный биоинспирированный алгоритм на основе инте-
грации метода ветвей и границ и метода муравьиной колонии // Вестник Ростовского
государственного университета путей сообщения. – 2018. – № 2 (70). – С. 77-88.
10. Yew-Soon Ong, Meng-Hiot Lim, Ning Zhu, Kok-Wai Wong. Classification of adaptive memetic
algorithms: A comparative study // IEEE Trans. on Systems, Man, and Cybernetics. – 2006.
– Vol. 36, Issue 1. – P. 141-152.
11. Dorigo M. and Stützle T. Ant Colony Optimization. – MIT Press, Cambridge, MA, 2004. – 345 р.
12. Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Распределение ресурсов на основе гибридных
моделей роевого интеллекта // Научно-технический вестник информационных техноло-
гий, механики и оптики. – 2017. – Т. 17, № 6. – С. 1063-1073.
13. Cong J., Romesis M., and Xie M. Optimality, Scalability and Stability Study of Partitioning
and Placement Algorithms // Proc. of the International Symposium on Physical Design, Monterey,
CA, 2003. – P. 88-94.
14. Воробьева Е.Ю., Карпенко А.П., Селиверстов Е.Ю. Ко-гибридизация алгоритмов роя частиц
// Наука и образование. МГТУ им. Н.Э. Баумана. Электронный журнал. – 2012. – № 4.
15. Лебедев Б.К., Лебедев О.Б., Лебедев В.Б. Гибридизация роевого интеллекта и генетиче-
ской эволюции на примере размещения // Программные продукты, системы и алгорит-
мы. – DOI: 10.15827/2311-6749.25.280. – http://swsys-web.ru/hybridization-of-swarmintelligence-
and-genetic-evolution.html.
16. Cheng Yu., Sha D.Y. A hybrid particle swarm optimization for job shop scheduling problem //
Computers & Industrial Engineering. – 2006. – P. 791-808.
17. Агасиев Т.А., Карпенко А.П. Современные техники глобальной оптимизации // Инфор-
мационные технологии. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2018. – № 6. – С. 370-386.
18. Clerc M. Particle Swarm Optimization. – ISTE, London, UK, 2006. – 248 р.
19. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Разбиение на основе моделирования адап-
тивного поведения биологических систем // Нейрокомпьютеры: разработка, примене-
ние. – 2010. – № 2. – С. 28-33.
20. Ong Y.S., Keane A.J. Meta-Lamarckian learning in memetic algorithms // IEEE Transactions
on Evolutionary Computation. – 2004. – Vol. 8 (2). – P. 99-110.
Опубликован
2019-11-12
Выпуск
Раздел
Раздел I. Искусственный интеллект и нечеткие системы