BIOINSPIRED SEARCH IN THE COMPLETE GRAPH OF A PERFECT MATCH OF MAXIMUM POWER
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.
