Штучний інтелект

Анотація: У роботі розглядається задача розміщення куль у багатовимірному евклідовому просторі в кулі мінімального радіуса. Такі задачі виникають у геометричній оптимізації, аналізі високовимірних структур і застосовуються, зокрема, під час побудови багатовимірних кодових конфігурацій у задачах передавання й захисту інформації. Формально задача зводиться до пошуку конфігурації непретинних куль, що мінімізує радіус області, яка їх містить. Ця оптимізаційна задача належить до класу NP-складних, а її точний розв’язок у просторі високої розмірності потребує значних обчислювальних ресурсів. Для отримання швидких наближених рішень запропоновано жадібний алгоритм послідовного додавання куль. На кожному кроці нова куля розміщується якомога ближче до початку координат за умови дотримання геометричних обмежень, водночас уже розміщені елементи залишаються фіксованими. Такий підхід забезпечує низьку обчислювальну складність і дає змогу конструювати допустимі конфігурації у просторах великої розмірності. Проведені обчислювальні експерименти для різних розмірностей демонструють ефективність розробленого алгоритму та дають змогу оцінити щільність отриманих конфігурацій. Запропонований метод може використовуватися як стартовий етап перед застосуванням більш складних локальних або глобальних оптимізаційних алгоритмів.

Ключові слова: багатовимірна куля, математичне моделювання, обчислювальна геометрія, жадібний алгоритм, нелінійне програмування

Посилання:

1. J. H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer New York, NY (1999). doi: 10.1007/978-1-4757-6568-7.
2. S. Li, A. Mirani, M. Karlsson, E. Agrell, Low-Complexity Voronoi Shaping for the Gaussian Channel. IEEE Transactions on Communications 70(2) (2022) 865–873. doi: 10.1109/TCOMM.2021.3130286.
3. M. S. Viazovska, The sphere packing problem in dimension 8. Annals of Mathematics 185(3) (2017) 991–1015. doi: 10.1007/s12652-021-03612-z.
4. H. Cohn, N. Elkies, New upper bounds on sphere packings I. Annals of Mathematics 157(2) (2003) 689–714. doi: 10.4007/annals.2003.157.689.
5. S. Torquato, O. U. Uche, F. H. Stillinger, Random sequential addition of hard spheres in high Euclidean dimensions. Phys. Rev. E 74(6) (2006) 061308. doi: 10.1103/PhysRevE.74.061308.
6. W. S. Jodrey, E. M. Tory, Computer simulation of close random packing of equal spheres. Phys. Rev. A 32(4), (1985) 2347–2351. doi: 10.1103/PhysRevA.32.2347.
7. A. R. Kansal, S. Torquato, F. H. Stillinger, Computer generation of dense polydisperse sphere packings. Journal of Chemical Physics 117 (2002) 8212–8218. doi: 10.1063/1.1511510.
8. G. Yaskov, A. Chugay, Packing equal spheres by means of the block coordinate descent method. CEUR Workshop Proceedings 2608 (2020) 150–160. doi: org/10.32782/cmis/2608-13.
9. M. Skoge, A. Donev, F. H. Stillinger, S. Torquato, Packing hyperspheres in high-dimensional Euclidean spaces Phys. Rev. E 74(4) (2006) 041127. doi: 10.1103/PhysRevE.74.041127.
10. K. He, W. Huang, An efficient placement heuristic for three-dimensional rectangular packing. Computers & Operations Research 38(1) (2011) 227 – 233. doi: 10.1016/j.cor.2010.04.015.
11. D. P. Bertsecal, Nonlinear Programming (1999) ISBN 1-886529-00-0.
12. A. Wächter, L. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106 (2006) 25–57. doi: 10.1007/s10107-004-0559-y.