УДК 519.85
РАЗРАБОТКА МЕТОДА ПОИСКА ЛОКАЛЬНОГО МИНИМУМА
С ИСПОЛЬЗОВАНИЕМ МОДЕЛИ БЛИЗОСТИ ДЛЯ ЗАДАЧИ
ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ МНОГОУГОЛЬНИКОВ
В.С. Скачко, студент гр. 355БМ
Национальный аэрокосмический университет им. Н.Е.Жуковского «ХАИ»
Одним из важных классов задач, направленных на снижение расходов сырья, материалов и других видов ресурсов, является класс задач геометрического проектирования. Задачи эти заключаются в поиске оптимального размещения некоторых геометрических объектов в заданных областях при наличии различных ограничений и некоторых критериев качества размещения.
В работе рассматривается задача размещения невыпуклых многоугольников внутри прямоугольной области. При размещении они не должны попарно пересекаться, при этом длина полосы должна быть минимальной. К многоугольникам может быть применена операция трансляции без поворотов. Математическая модель задачи имеет линейную функцию цели. Область допустимых решений представляет собой в многомерном пространстве невыпуклую область с кусочнолинейной границей. Задача является многоэкстремальной с большим количеством локальных минимумов. Наиболее распространенным подходом к её решению является направленный или случайный перебор локальных экстремумов, поэтому актуальным является разработка построения эффективного алгоритма, находящего локальный минимум. Разработанный метод основан на барьерном методе[1] в сочетании с методом сопряженных градиентов. Модифицированный метод барьерных функций использует модель близости, благодаря чему общее количество операций на каждом шаге существенно уменьшается.
В дальнейшем можно улучшить задачу для более сложных граничных ограничений, большего количества фигур или с дополнительными ограничениями. В перспективе планируется работа по модификации метода барьерных функций, использовании его в комбинации с другими быстрыми методами локального поиска оптимума, улучшению быстродействия программы и работы алгоритма.
Список использованных источников: 1. Карташов, А .В. Методы условной оптимизации [Текст] / А.В. Карташов, А.В. Бабкина, Р.А. Пудло // Комп’ютерні системи та інформаційні технології: сб. науч. тр. Нац. аэрокосм, ун-та им. HJE. Жуковского «ХАИ». - С. 37 - 94.
Нет похожих статей