БИОИНСПИРИРОВАННЫЙ ПОИСК В ПОЛНОМ ГРАФЕ СОВЕРШЕННОГО ПАРОСОЧЕТАНИЯ МАКСИМАЛЬНОЙ МОЩНОСТИ
Аннотация
Разработана реконфигурируемая архитектура гибридной многоагентной системы поиска решений, базирующиеся на парадигмах роевых алгоритмов. Реконфигурируемая архитектура пу- тем настройки позволяет реализовать следующие методы гибридизации: высокоуровневую и низ- коуровневую гибридизацию вложением, типа препроцессор/постпроцессор, ко-алгоритмическую на базе одного или нескольких типов алгоритмов. Предложена методология синтеза совершенного паросочетания минимального веса в полном графе, основанная на базовых принципах гибридизации поисковых. эволюционных процедур. В работе агентами роя являются трансформирующиеся хро- мосомы, являющиеся генотипами решения. В качестве кода решения используется упорядоченный список множества вершин графа. Разработана структура упорядоченного кода паросочетания главное достоинство которого заключается в том, что одному решению (паросочетанию) соот- ветствует один код и наоборот. Определены свойства упорядоченного кода и разработаны алго- ритмы кодирования и декодирования. Работа гибридной системы начинается с генерации роем пчел случайным образом произвольного множества отличающихся друг от друга решений в виде исходного множества хромосом. Ключевой операцией пчелиного алгоритма является исследование перспективных решений и их окрестностей в пространстве поиска. Разработан метод формиро- вания окрестностей решений с регулируемой степенью подобия и близости между ними. На по- следующих этапах работы многоагентной системы выполняется поиск решений процедурами, построенными на основе гибридизации роевого и муравьиного алгоритмов. Отличительной осо- бенностью гибридизации является сохранение автономии гибридизируемых алгоритмов. Отме- тим, что для представления решений в алгоритмах используется единая структура данных, что упрощает стыковку разработанных процедур. Предлагается подход к построению модифициро- ванной парадигмы роя трансформирующихся хромосом. Поиск решений выполняющая в аффинном пространстве. В процессе поиска осуществляется перманентные трансформации (переход) хро- мосом в состояния с лучшим значением целевой функции решения (градиентная стратегия). Про- цесс поиска решений итерационный. На каждой итерации осуществляется трансформация (пере- ход) хромосом в состояния с лучшими значениями целевой функции решения. Целью трансформа- ции хромосомы, тяготеющей к лучшей хромосоме, в новое состояние является минимизация сте- пени различия, путем изменения взаимного расположения элементов в упорядоченном списке, что соответствует увеличению веса аффинной связи. Обновленные после трансформации хромосомы являются, в свою очередь, базовыми точками в последующих трансформациях. В результате экс- периментов было установлено, что показатели качества разработанных алгоритмов имеют бо- лее высокие значения чем в работах, представленных в литературе
Список литературы
1. Андерсон Д. Дискретная математика и комбинаторика. – М.: Вильямс, 2003.
2. Кормен К., Лейзерсон Ч., Ривест Р. Алгоритмы построение и анализ. – М.: МЦМНО, 2000.
3. Асанов М., Баранский В., Расин В. Дискретная математика: Графы, матроиды, алгоритмы.
– СПб.: Изд-во «Лань», 2010.
4. Blum C., Roli A. Metaheuristics in combinatorial optimization: overview and conceptual comparison //
ACM computing surveys. – 2003. – No. 35. – P. 268-308.
5. MAXimal. Алгоритм Куна нахождения наибольшего паросочетания.
6. Bast H., Mehlhorn K., Schafer G. et al. Matching Algoritms Are Fast in Sparse Random Graphs //
Theory Comput Syst. – 2006. – P. 3-14.
7. Ding J., Ma Z., Wu Y. et. al. Efficient random graph matching via degree profiles // Probab. Theory
Relat. Fields. – 2021. – P. 29-115.
8. Blum N. A new approach to maximal matchings in general graphs // International Colloquium on Automata,
Languages, and Programming. – 2017. – P. 586-597.
9. Лебедев Б.К., Лебедев О.Б. Эволюционный алгоритм нахождения максимального паросочета-
ния // 3-й Международный НТС «Интегрированные модели и мягкие вычисления в искусствен-
ном интеллекте». – М.: Изд-во Физматлит, 2005. – С. 274-280.
10. Курейчик В.В., Курейчик В.М. Генетический алгоритм определения паросочетаний графа // Тр.
10 международной конференции «Knowledge-dialogue-solution». – 2003. – С. 246-251.
11. Карпенко А.П., Кузьмина И.А. Исследование эффективности структурно-параметрического
синтеза одного класса популяционных алгоритмов глобальной оптимизации // Математические
методы в технологиях и технике. – 2024. – № 4. – С. 82-89.
12. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные
природой: учеб. пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2021. – 448 с.
13. Пантелеев А.В., Метлицкая Д.В., Алешина Е.А. Методы глобальной оптимизации: Метаэври-
стические стратегии и алгоритмы. – М.: Вузовская книга, 2013. – 44 с.
14. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Решение задачи покрытия на основе эволюционного
моделирования // Известия РАН. Теория и системы управления. – 2009. – С. 101-117.
15. Лебедев Б.К., Лебедев В.Б., Лебедев О.Б. Гибридизация роевого интеллекта и генетической эволю-
ции на примере размещения // Программные продукты, системы и алгоритмы. – 2017. – № 4.
16. Лебедев Б.К., Лебедев О.Б. Распределение ресурсов на основе гибридных моделей роевого ин-
теллекта // Научно-технический вестник информационных технологий, механики и оптики.
– 2017. – № 6. – С. 1063-1073.
17. Карпенко А.П. Типовые структуры популяционных алгоритмов глобальной оптимизации // Ин-
формационные и математические технологии в науке и управлении. – 2022. – № 1 (25). – С. 48-57.
18. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования.
– Таганрог: Изд-во ЮФУ, 2013. – 199 с.
19. Raidl G.R. A Unified view on hybrid Metaheuristics // Lecture Notes In Computer Science. – Springer,
2006. – P. 1-12.
20. Cong J., Romesis M., Xie M. Optimality, scalability and stability study of partitioning and placement
algorithms // Proc. of the International Symposium on Physical Design. – 2003. – P. 88-94.
