Метод барьерных функций, использующий модель близости, в задаче оптимального размещения кругов

( 1 Vote ) 
Категория: ИКТМ 2015 Просмотров: 655

УДК 519.85

МЕТОД БАРЬЕРНЫХ ФУНКЦИЙ, ИСПОЛЬЗУЮЩИЙ МОДЕЛЬ БЛИЗОСТИ,
В ЗАДАЧЕ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ КРУГОВ
И.А. Кобец, студент гр. 355AM
Национальный аэрокосмический университет им. Н.Е. Жуковского «ХАИ»

Интерес к множеству задач размещения вызван их сложностью и нетривиальностью математических моделей, необходимых для адекватного описания, а так же широким спектром практических приложений. Задачи упаковки кругов возникают в различных отраслях промышленности, например, в легкой, автомобильной, авиационно- космической, химической промышленности. Эти задачи заключаются в упаковке кругов в различные контейнеры. Одной из таких задач является задача оптимального размещения кругов в двумерном пространстве.
В данной работе математическая модель рассматриваемой задачи представляет собой задачу нелинейного программирования с большим количеством локальных экстремумов. Наиболее распространенным подходом к её решению является направленный или случайный перебор локальных экстремумов, поэтому актуальным является разработка построения эффективного алгоритма, находящего локальный минимум. Разработанный метод основан на барьерном методе в сочетании с методом наискорейшего спуска. Модифицированный метод барьерных функций использует модель близости [1], благодаря чему общее количество операций на каждом шаге существенно уменьшается.
Было проведено тестирование модифицированного метода, которое показало его эффективность, а также было проведено сравнение с обычным методом барьерных функций, и оказалось, что модификация метода работает в несколько раз быстрее.
Метод барьерных функций выгодно применять при решении задач достаточно большой размерности — размещении сотен объектов. Также перспективной является идея в дальнейшем применить другой метод безусловной оптимизации вместе с методом барьерных функций, для более быстрого достижения локального минимума, и, следовательно, более быстрого выполнения поставленной задачи.
Список использованных источников
1. Kartashov, A.V. Using triangulation to search for a local minimum for a circle placing problem [Text] / A.V. Kartashov, RA. Pudlo, AV. Babkina // Abstracts of 8th ESICUP Meeting, Copenhagen, Denmark, May 19-21,2011,
p. 26.