BIOINSPIRED SEARCH IN THE COMPLETE GRAPH OF A PERFECT MATCH OF MAXIMUM POWER
Keywords:
Поисковая оптимизация, методология, декомпозиция, роевой интеллект, муравьиная и пчелиная колонии, трансформирующиеся хромосомы, адаптивное поведение, гибридизацияAbstract
A reconfigurable architecture of a hybrid multi-agent decision-making system based on swarm algorithm
paradigms has been developed. The reconfigurable architecture allows implementing the following
hybridization methods by tuning: high-level and low-level hybridization by nesting, preprocessor/
postprocessor type, co-algorithmic based on one or several types of algorithms. A methodology for
synthesizing a perfect matching of minimum weight in a complete graph based on the basic principles of
hybridization of search. evolutionary procedures has been proposed. In this paper, the swarm agents are
transforming chromosomes, which are the genotypes of the solution. An ordered list of the set of graph
vertices is used as the solution code. A structure of an ordered matching code has been developed, the
main advantage of which is that one solution (matching) corresponds to one code and vice versa. The
properties of the ordered code have been determined and encoding and decoding algorithms have been
developed. The hybrid system operation starts with the random generation by a swarm of bees of an arbitrary
set of solutions differing from each other in the form of an initial set of chromosomes. The key operation
of the bee algorithm is the study of promising solutions and their neighborhoods in the search space.
A method for forming neighborhoods of solutions with an adjustable degree of similarity and closeness
between them has been developed. At subsequent stages of the multi-agent system operation, solutions are
searched for by procedures built on the basis of hybridization of the swarm and ant algorithms. A distinctive
feature of hybridization is the preservation of the autonomy of the hybridized algorithms. Note that a
single data structure is used to represent solutions in the algorithms, which simplifies the docking of the
developed procedures. An approach to constructing a modified paradigm of a swarm of transforming
chromosomes is proposed. The search for solutions is performed in an affine space. In the process of
searching, permanent transformations (transitions) of chromosomes into states with the best value of the
objective function of the solution (gradient strategy) are carried out. The process of finding solutions is
iterative. At each iteration, the chromosomes are transformed (transitioned) into states with better values
of the objective function of the solution. The purpose of transforming a chromosome that tends to be the
best chromosome into a new state is to minimize the degree of difference by changing the mutual arrangement
of elements in an ordered list, which corresponds to an increase in the weight of the affine
connection. The chromosomes updated after the transformation are, in turn, the base points in subsequent
transformations. As a result of the experiments, it was found that the quality indicators of the developed
algorithms have higher values than in the works presented in the literature.
References
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.
