Задача геометрического покрытия является частным случаем задачи оптимального проектирования и принадлежит к классу задач «раскроя и упаковки». Задача заключается в том, что требуется расположить некоторые геометрические объекты на покрываемой поверхности таким образом, чтобы вся поверхность была покрыта целиком. Сложность рассматриваемых задач обусловлена их принадлежностью к классу NP-трудных задач, что исключает возможность их решения точными методами и требует построения приближенных оптимизационных методов и алгоритмов. В данной статье рассматривается задача геометрического покрытия области кругами из заданного набора радиусов. Для решения задачи геометрического покрытия используется метод покрытия гексагональной сеткой с оптимизацией метаэвристическим алгоритмом. В качестве такого алгоритма выступает вороний алгоритм поиска, который является относительно новым метаэвристическим алгоритмом, основанным на интеллектуальном поведении ворон в стае. Вороний алгоритм поиска включает в себя два регулирующих параметра: вероятность осведомленности и длина полета. Для исследования метода решения и проверки эффективности была смоделирована задача на основе реального проекта систем автоматического полива, а также приведены результаты экспериментов с различными значениями регулирующих параметров.
Тырин Григорий Николаевич
Фроловский Владимир Дмитриевич
Тырин Г.Н., Фроловский В.Д. Исследование и применение вороньего алгоритма поиска для задач оптимизации геометрического покрытия // Доклады АН ВШ РФ. – 2021. – № 1 (50). – C. 54–61 – doi: 10.17212/1727-2769-2021-1-54-61
Tyrin G.N., Frolovsky V.D. Issledovanie i primenenie voron'ego algoritma poiska dlya zadach optimizatsii geometricheskogo pokrytiya [Research and application of the crow search algorithm for geometric covering optimization problems]. Doklady Akademii nauk vysshei shkoly Rossiiskoi Federatsii = Proceedings of the Russian higher school Academy of sciences, 2021, no. 1 (50), pp. 54–61. DOI: 10.17212/1727-2769-2021-1-54-61.
