Covering a multitude using the adaptive chromosome swarm method in an affine solution space

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

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.

About the authors

B. K. Lebedev

MIREA — Russian University of Technology

Author for correspondence.
Email: lebedev.b.k@gmail.com

Dr. of Tech. Sc., Professor

Russian Federation, Moscow

O. B. Lebedev

MIREA — Russian University of Technology

Email: lebedev.ob@mail.ru

Dr. of Tech. Sc., Professor

Russian Federation, Moscow

A. G. Shmeleva

MIREA — Russian University of Technology

Email: ann_shmeleva@mail.ru

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

Russian Federation, Moscow

M. I. Beskhmelnov

MIREA — Russian University of Technology

Email: m_beskhmelnov@mail.ru

PhD Student

Russian Federation, Moscow

References

  1. 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).
  2. 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).
  3. Shervani N. A. Algorithms for automation of VLSI physical design, Kluwer Academic Publisher, USA, 2013, 572 p.
  4. Gorelik V. A. Operations research and optimization methods, Moscow, Academia, 2018, 384 p. (in Russian).
  5. 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).
  6. 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).
  7. 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).
  8. 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).
  9. 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).
  10. 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).
  11. 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).
  12. 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).
  13. 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).
  14. 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).
  15. 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).
  16. Kureichik V. M., Lebedev B. K., Lebedev O. B. Search adaptation. Theory and practice, Moscow, Publishing house of Fizmatlit, 2006, 272 p. (in Russian).
  17. 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).
  18. 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).
  19. 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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Informacionnye Tehnologii


СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ПИ № 77 - 15565 от 02 июня 2003 г.