Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70201510.17587/it.31.619-629Modeling and optimizationМоделирование и оптимизацияResearch ArticleCovering a multitude using the adaptive chromosome swarm method in an affine solution spaceОбобщенная задача покрытия множества методом роя адаптивных хромосом в аффинном пространстве решенийLebedevB. K.ЛебедевБ. К.
Russian Federation

Dr. of Tech. Sc., Professor

д-р техн. наук, проф.

lebedev.b.k@gmail.comLebedevO. B.ЛебедевО. Б.
Russian Federation

Dr. of Tech. Sc., Professor

д-р техн. наук, доц.

lebedev.ob@mail.ruShmelevaA. G.ШмелеваА. Г.
Russian Federation

Сand. of Phys.-Math. Sc., Associate Professor

канд. физ.-мат. наук, доц.

ann_shmeleva@mail.ruBeskhmelnovM. I.БесхмельновМ. И.
Russian Federation

PhD Student

аспирант

m_beskhmelnov@mail.ruMIREA — Russian University of TechnologyМИРЭА — Российский технологический университет1512202531126196293101202631012026Copyright ©; 2025, Informacionnye TehnologiiCopyright ©; 2025, Информационные технологии2025Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/702015

The paper describes a method for solving the problem of coverage based on the hybridization of heuristics, and mechanisms of collective adaptation and swarm intelligence. А modernized agent swarm metaheuristics is proposed, characterized in that adaptive chromosomes serve as agents, and the search process is organized in an affine solution space. An algorithm has been developed for the random formation of an initial population of solutions in the form of a set of legal matrices of boundary requirements. А comparison with known algorithms has shown that with a shorter operating time, the solutions obtained using the developed algorithm have a deviation of the objective function from the optimal value by an average of 6 % less.

Излагается метод решения обобщенной задачи покрытия множества на основе гибридизации эвристик и механизмов коллективной адаптации и роевого интеллекта. Предложена модернизированная метаэвристика роя агентов, в которой в качестве агентов служат адаптивные хромосомы, а поисковый процесс организован в аффинном пространстве решений. Разработан алгоритм случайного формирования исходной популяции решений в виде набора легальных матриц граничных требований.

set coverageswarm of chromosomesaffine spaceoptimizationautomatic adaptationпокрытие множестварой хромосомаффинное пространствооптимизацияавтомат адаптацииKureichik V. M., Lebedev B. K., Lebedev O. B. Solving the problem of coverage based on evolutionary modeling, News of the Russian Academy of Sciences. Theory and control systems, 2009, no. 1, pp. 101—117 (in Russian).Курейчик В. М., Лебедев Б. К., Лебедев О. Б. Решение задачи покрытия на основе эволюционного моделирования // Известия РАН. Теория и системы управления. 2009. № 1. С. 101—117.Kureichik V. M., Lebedev B. K., Lebedev O. B. Simulation evolutionary solution of the coating problem, International Journal of Computer and System Sciences, 2009, vol. 48, no. 1, pp. 95—109 (in Russian).Kurejchik V. M., Lebedev B. K., Lebedev O. B. А Simulated Evolution-Based Solution of the Cover Problem // Journal of Computer and Systems Sciences International. 2009. Vol. 48, N. 1. P. 95—109.Shervani N. A. Algorithms for automation of VLSI physical design, Kluwer Academic Publisher, USA, 2013, 572 p.Sherwani N. A. Algorithms for VLSI Physical Design Automation. Kluwer Academic Publisher, 2013. 572 p.Gorelik V. A. Operations research and optimization methods, Moscow, Academia, 2018, 384 p. (in Russian).Горелик В. А. Исследование операций и методы оптимизации. М.: Academia, 2018. 384 c.Esipov B. A., Muravyev V. V. Investigation of algorithms for solving a generalized minimum coverage problem, Proceedings of the Samara Scientific Center of the Russian Academy of Sciences, 2014, vol. 16, no. 4 2), pp. 137—159 (in Russian).Есипов Б. А., Муравьев В. В. Исследование алгоритмов решения обобщенной задачи о минимальном покрытии // Известия Самарского научного центра Российской академии наук. 2014. Т. 16, № 4 (2). С. 137—159.Konovalov I. S. Comparative analysis of the greedy Grabala algorithm and the modified Goldberg model in solving the weighted problem of finding the minimum coverage of sets, Proceedings of the NCF MTUCI, 2015, pp. 366—370 (in Russian).Коновалов И. С. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при решении взвешенной задачи нахождения минимального покрытия множеств // Труды СКФ МТУСИ. 2015. С. 366—370.Konovalov I. S., Fathi V. A., Kobak V. G. Application of a genetic algorithm to solve the problem of covering sets, Bulletin of the Don State Technical University, 2016, no. 3 (86), pp. 125—132 (in Russian).Коновалов И. С., Фатхи В. А., Кобак В. Г. Применение генетического алгоритма для решения задачи покрытия множеств // Вестник Донского государственного технического университета 2016. № 3 (86). С. 125—132.Prolubnikov А. V. The problem of covering a set with interval weights of subsets and a greedy algorithm for its solution, Computing technologies, 2015, pp. 70—84 (in Russian).Пролубников А. В. Задача о покрытии множества с интервальными весами подмножеств и жадный алгоритм ее решения // Вычислительные технологии. 2015. С. 70—84.Zabinyako G. I. Implementation of algorithms for solving the problem of covering sets and analysis of their effectiveness, Computing technologies, 2007, vol. 12, no. 6, pp. 50—58 (in Russian).Забиняко Г. И. Реализация алгоритмов решения задачи о покрытии множеств и анализ их эффективности // Вычислительные технологии. 2007. Т. 12, № 6. C. 50—58.Karpenko А. P. Modern search engine optimization algorithms. Algorithms inspired by nature: a study guide, Moscow, Publishing House of the Bauman Moscow State Technical University, 2021, 446 p. (in Russian).Карпенко А. П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: Учеб. пособ. М: Издательство МГТУ им. Н. Э. Баумана. 2021. 446 с.Lebedev O. B. Coating by the ant colony method, The twelfth National Conference on Artificial Intelligence with international participation, Fizmatlit, 2010, pp. 423—431 (in Russian).Лебедев О. Б. Покрытие методом муравьиной колонии // Двенадцатая национальная конференция по искусственному интеллекту с международным участием КИИ- 2010. М.: Физматлит, 2010. С. 423—431.Lebedev В. K. Lebedev O. B. Coating based on swarm intelligence methods, Problems of developing promising micro- and nanoelectronic systems. Collection of works under the general editorship, Academician of the Russian Academy of Sciences А. L. Stemp- kovsky, Moscow, IPPM RAS, 2016, Part I, pp. 187—193 (in Russian).Лебедев Б. К. Лебедев О. Б. Покрытие на основе методов роевого интеллекта // Проблемы разработки перспективных микро- и наноэлектронных систем. Сб. трудов под общ. ред. академика РАН А. Л. Стемпковского. М.: ИППМ РАН, 2016. Часть I. С. 187—193.Eremeev A. V., Zaozerskaya L. A., Kolokolov А. A. The problem of covering a set: complexity, algorithms, experimental research, Discretion. analysis and research. Operations, Ser. 2, 2000, vol. 7, no. 2, pp. 22—46 (in Russian).Еремеев А. В., Заозерская Л. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискрет. анализ и исслед. операций. Сер. 2. 2000. Т. 7, № 2. С. 22—46.Lebedev B. K., Lebedev V. В. Coating based on the particle swarm method, Collection of scientific papers of the XIII All-Russian Scientific and Technical Conference "NEUROINFORMATICS-2011", Part 2, Moscow, Fizmatlit Publishing House, 2011, pp. 93—103 (in Russian).Лебедев Б. К., Лебедев В. Б. Покрытие на основе метода роя частиц // Сб. науч. тр. XIII Всеросс. науч.-техн. конф. "НЕЙРОИНФОРМАТИКА-2011". Ч. 2. М.: Изд-во Физматлит, 2011. C. 93—103.Lebedev B. K., Lebedev О. B., Ganzhur М. A. Optimization by swarm of transforming chromosomes, Proceedings of the XXI-th National Conference on Artificial Intelligence with international participation, Smolensk, Publishing House, MEI Branch, 2023, pp. 247—258 (in Russian).Лебедев Б. К., Лебедев О. Б., Ганжур М. А. Оптимизация методом роя трансформирующихся хромосом // Тр. XXI Нац. конф. по искусственному интеллекту с международным участием КИИ-2023. Смоленск: Филиал МЭИ, 2023. С. 247—258.Kureichik V. M., Lebedev B. K., Lebedev O. B. Search adaptation. Theory and practice, Moscow, Publishing house of Fizmatlit, 2006, 272 p. (in Russian).Курейчик В. М., Лебедев Б. К., Лебедев О. Б. Поисковая адаптация. Теория и практика. М.: Физматлит, 2006, 272 с.Kureichik V. M., Lebedev B. K., Lebedev V. B. Adaptation in topology design problems, Problems of developing promising micro- and nanoelectronic systems, Collection of scientific papers edited by А. L. Stempkovsky, Moscow, IPPM RAS, 2010, pp. 170—177 (in Russian).Курейчик В. М., Лебедев Б. К., Лебедев В. Б. Адаптация в задачах проектирования топологии // Проблемы разработки перспективных микро- и наноэлектронных систем — 2010 // Сб. трудов под общ. ред. академика РАН А. Л. Стемпковского. М.: ИППМ РАН, 2010. С. 170—177.Zubkova D. A., Gintsyak A. M., Burlutskaya Zh. V., Red- ko S. G. Modern optimization methods and features of their application, Russian technological journal, 2025, vol. 13, no. 4, pp. 78—94, DOI: 10.32362/2500-316X-2025-13-4-78-94 (in Russian).Зубкова Д. А., Гинцяк А. М., Бурлуцкая Ж. В., Редько С. Г. Современные методы оптимизации и особенности их применения // Российский технологический журнал. 2025. Т.13, № 4. С. 78—94. DOI: 10.32362/2500-316X-2025-13-4-78-94.Kong J., Romesis M., Xie M. А study of optimality, scalability, and stability of partitioning and placement algorithms, Proceedings of the International Symposium on Physical Engineering, Monterey, California, 2003, pp. 88—94.Cong J., Romesis M., Xie M. Optimality, Scalability and Stability Study of Partitioning and Placement Algorithms // Proc. of the International Symposium on Physical Design. Monterey, 2003. P. 88—94.