ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 12. Vol. 31. 2025

DOI: 10.17587/it.31.619-629

B. K. Lebedev, Dr. of Tech. Sc., Professor, O. B. Lebedev, Dr. of Tech. Sc., Professor, A. G. Shmeleva, Ñand. of Phys.-Math. Sc., Associate Professor, M. I. Beskhmelnov, PhD Student,
MIREA — Russian University of Technology, Moscow, Russian Federation

Covering a Multitude using the Adaptive Chromosome Swarm Method in an Affine Solution Space

Received on 30.03.2025
Accepted on 18.04.2025

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.
Keywords: set coverage, swarm of chromosomes, affine space, optimization, automatic adaptation

P. 619-629

Full text on eLIBRARY

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 Gra-bala 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. Stempkovsky, 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.

To the contents