Search academic texts

Registration Number

0823U101575, PhD dissertation

Title

Methods and algorithms for constructing fuzzy Voronoi diagrams based on the theory of optimal set partitioning

Author

Vadim H. Padalko, Доктор філософії

popup.head Olena M. Kiseleva
popup.opponent Sergiy V. Yakovlev
popup.opponent Oleg B. Blyuss
popup.review Liudmyla L. Нart
popup.review Valentyna A. Turchyna

Status

Доктор філософії, 113, Прикладна математика

Date

17-06-2022

Description

Дисертаційна робота присвячена розробці та обґрунтуванню методів і алгоритмів побудови нечітких діаграм Вороного із застосуванням теорії оптимального розбиття множин із -вимірного евклідового простору на підмножини. Математична теорія оптимального розбиття множин (ОРМ) на сьогодні є потужним інструментом для розв’язання багатьох теоретичних і практично важливих задач, що зводяться в математичній постановці до неперервних задач оптимального розбиття множини з евклідового простору (лінійних або нелінійних, статичних або динамічних, детермінованих або стохастичних, в умовах визначеності або нечітких). Розв’язок ряду модельних задач зі згаданих класів часто призводить до математичних об'єктів, які мають назву діаграми Вороного або розбиття Діріхле. Діаграми Вороного в двох і тривимірних просторах використовуються в самих різних областях прикладних наук: кристалографії, фізики, астрономії, хімії, мікробіології, комп'ютерній графіці, при вирішенні проблем штучного інтелекту, розпізнавання образів та ін. Для побудови діаграм Вороного розроблено багато різних алгоритмів, однак всі ці алгоритми досить складні. Математичним апаратом побудови діаграм Вороного, який має ряд переваг у порівнянні з відомими підходами, описаними в науковій літературі, є теорія оптимального розбиття множин, яка розроблена О.М. Кісельовою. Для розв’язання неперервних задач ОРМ запропонований єдиний підхід, в основі якого лежить наступна ідея. Вихідні задачі ОРМ, які математично сформульовані як нескінченновимірні задачі оптимізації, зводяться певним чином (наприклад, через функціонал Лагранжа) до допоміжних скінченновимірних негладких задач максимізації або негладких задач максиміна, для чисельного розв’язання яких застосовуються сучасні ефективні методи недиференційовної оптимізації, а саме, різні модифікації r -алгоритму Н.З. Шора. Переважна більшість задач теорії ОРМ досліджувалась в умовах визначеності. Однак реальні ситуації, для яких створюються моделі оптимального розбиття множин, найчастіше характеризуються деяким ступенем невизначеності: в початкових даних, в умовах і цілях. У цих випадках якість прийнятих рішень в оптимізаційних моделях розбиття множин знаходиться в прямій залежності від повноти урахування всіх невизначених факторів, істотних для наслідків від прийнятих рішень. Природним представляється узагальнення моделей розбиття в умовах визначеності на випадок моделей в умовах невизначеності. Для розкриття невизначеності в таких задачах (тобто для формалізації невизначеної інформації) застосовується апарат теорії нечітких множин, який базується на понятті нечіткої множини, введеного Л. А. Заде, а також апарат нечіткої логіки. Метою роботи є розробка та обґрунтування методів і алгоритмів побудови нечітких діаграм Вороного із застосуванням теорії оптимального розбиття множин із n -вимірного евклідового простору n E на підмножини. За аналогією з класифікацією нечітких задач ОРМ виділено два основних типи нечітких діаграм Вороного: діаграми Вороного з нечіткими параметрами і діаграми Вороного, в яких множина точок, що утворюють комірки Вороного, є нечіткими множинами (нечіткі комірки). А розв’язок нечітких задач ОРМ, як і для детермінованих задач ОРМ, призводить до побудови нечітких діаграм Вороного двох основних типів: діаграми Вороного з нечіткими параметрами і діаграми з нечіткими комірками Вороного. Показана можливість застосування математичної теорії оптимального розбиття множин до побудови діаграми Вороного і різних її узагальнень. Математичний та алгоритмічний апарат побудови різних варіантів діаграми Вороного заснований на формулюванні неперервних задач оптимального розбиття множин з критеріями якості розбиття, що забезпечують відповідні види діаграми Вороного.