Поиск экстремальных конфигураций в геометрических задачах при помощи библиотеки PyTorch
Постановка задачи Задачи упаковки — это класс задач оптимизации в математике, в которых пытаются упаковать объекты в контейнеры. Цель упаковки — либо упаковать отдельный контейнер как можно плотнее, либо упаковать все объекты, использовав как можно меньше контейнеров, либо нахождение конфигурации, которая упаковывает один контейнер с максимальной плотностью. При этом объекты не должны пересекаться и объекты не должны пересекать стены контейнера. Работа программы Создается квадратная область, в нее помещаются случайным образом сгенерированные n точек. Далее программа увеличивает их радиусы, при этом ищет лучшее расположение.
Все вычисления происходят посредством нейронной сети, которая обучается градиентным спуском.
*Градиентный спуск — это эвристический алгоритм, который выбирает случайную точку, рассчитывает направление скорейшего убывания/возрастания функции (пользуясь градиентом функции в данной точке), а затем пошагово рассчитывает новые значения функции, двигаясь в выбранную сторону. Если убывание/возрастаение значения функции становится слишком медленным, алгоритм останавливается и говорит, что нашел минимум.