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

Анотація

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

Аналіз загальної моделі покриття заданих областей свідчить про те, що дана задача відноситься до класу задач комбінаторної оптимізації, тобто для одержання її розв’язку необхідно здійснити перебір припустимих варіантів покриття, причому розв’язком буде той варіант, який забезпечує мінімум цільової функції.

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

Ключові слова: обмеження спеціального виду, загальна модель, метод Монте-Карло, дерево рішень.