МОДИФИЦИРОВАННЫЙ МЕТОД МОНТЕ-КАРЛО ДЛЯ ПОКРЫТИЯ ЗАДАННОЙ ОБЛАСТИ НЕВЫПУКЛЫМИ МНОГОУГОЛЬНИКАМИ С УЧЕТОМ ОГРАНИЧЕНИЙ СПЕЦИАЛЬНОГО ВИДА

Аннотация

В данной работе была рассмотрена математическая модель покрытия заданной области невыпуклыми многоугольниками с переменными метрическими характеристиками с учетом следующих ограничений: минимум площади взаимного пересечения объектов покрытия; минимум площади пересечения объектов покрытия и дополнения заданной области до двумерного пространства; параметры размещения объектов покрытия должны принадлежать точкам в заданной подобласти с учетом приоритетных подобластей; максимальное покрытие заданных подобластей соответствующими объектами; принадлежность заданных подобластей объектам покрытия; принадлежность приоритетных подобластей областям пересечения заданного количества объектов покрытия; ограничения специального вида, влияющие на метрические характеристики объектов покрытия.

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

В статье для получения оптимального решения задачи предложен модифицированный метод Монте-Карло. Разработанный метод позволяет найти локальный экстремум целевой функции. Для реализации модифицированного метода Монте-Карло необходимо задать количество оптимизационных серий. Затем необходимо построить первый уровень дерева решений. На уровне дерева решений случайным образом выбираются точки, в которых размещается начало локальной системы координат объекта покрытия. Осуществляется проверка выполнения ограничений задачи. Если данные ограничения полностью не выполнены, то проводится построение следующего уровня дерева, в котором уже не учитывается точка, которая выбрана на предыдущем уровне. Таким образом, процесс построения уровней деревьев решений и случайного выбора элементов на данных уровнях повторяется до тех пор, пока не будут выполнены все ограничения задачи. Для каждой серии повторяется процесс построения деревьев решений и получения вариантов покрытия. После проведения всех оптимизационных серий из множества выбирается тот вариант покрытия, для которого значение целевой функции является наименьшим

Ключевые слова: ограничения специального вида, общая модель, метод Монте-Карло, дерево решений.