Search academic texts

Registration Number

0821U102141, PhD dissertation

Title

Fragmentary models in optimal classification problems

Author

Selyutin Yevhen K.,

popup.head Kozin Igor Viktorovich
popup.opponent Turchyna Valentina Andreevna
popup.opponent Novozhilova Marina Vladimirovna
popup.review Choporov Sergey Viktorovich
popup.review Ermolayev Vadim Anatolievich

Status

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

Date

29-06-2021

Description

Дисертаційна робота присвячена узагальненню і розробці теоретичних основ математичного апарату для побудови та дослідження фрагментарних моделей та метаевристичних методів для розв’язку задачі класифікації. Розглянуті в дисертації моделі та методи можуть використовуватися під час пошуку розв’язків у багатьох наукових та практичних задачах, в тому числі, задачі розміщення виробництва. У вступі обґрунтовано актуальність теми дисертаційної роботи, сформульовано мету та основні задачі дослідження, показано їх зв’язок з науковими програмами. Визначено методи дослідження, наукову новизну та практичне значення отриманих результатів. У розділі 1 проведено огляд результатів за тематикою дисертаційної роботи. Обґрунтовано вибір напрямків подальших досліджень, пов’язаних з розв’язком задачі оптимальної класифікації. Розглянуто та проаналізовано існуючі задачі оптимальної класифікації та методів пошуку їх розв’язків. Досліджено обчислювальну складність існуючих задач класифікації. Виявлено, що постановка задачі пошуку оптимальної класифікації дозволяє віднести цю задачу до багатокритеріальних. Виявлено, що більшість задач оптимальної класифікації є важкорозв’язуваними (складними в обчислювальному сенсі), оскільки до них поліноміально зводиться хоча б одна NP-повна задача. Для таких задач на сьогодні невідомі алгоритми пошуку точного розв'язку простіших, ніж повний перебір всіх допустимих розв'язків задачі. Тому є сенс шукати прості наближені алгоритми, які хоч і не дають точного розв'язку, але мають високу швидкодію. Серед таких алгоритмів виділяється клас «жадібних» алгоритмів. Виділено невирішені задачі класифікації. У розділі 2 наведено ряд основних понять та результатів, які використовуються в роботі та стосуються комбінаторного об’єкту «фрагментарна структура». Вивчено особливості та властивості фрагментарних структур, встановлено зв’язок з категорією «опуклість» та задачею покриття графів. Досліджено поняття метаевристики та проаналізовано метаевристичні методи пошуку оптимальних рішень у задачі класифікації. Встановлено зв’язок між задачею оптимальної перестановки та класифікації. Виявлено, що експериментальні дослідження розподілу локальних оптимумів свідчать про високу концентрацію їх в безпосередній близькості від глобального оптимуму. Показано, що проблема пошуку початкових популяцій для реалізації еволюційно-фрагментарної моделі зводиться до задачі покриття (або розбиття) простору перестановок опуклими множинами. У розділі 3 розглянуто фрагментарний алгоритм покриття графу зірками. Проаналізовано найпростіші варіанти задачі розміщення виробництва з точки зору задачі класифікації, а також наведено метаевристичні алгоритми пошуку оптимальних рішень складних задач розміщення виробництва. Сформульована задача покриття. Побудовано фрагментарну модель задачі. Визначено умову приєднання елементарного фрагменту. Розглянуто задачі розміщення виробництва. Визначена доцільність використання методу рою часток та фрагментарної моделі, а також їх модифікацій. У розділі 4 запропоновано програмні реалізації генерації випадкових графів та розв’язку задачі класифікації за допомогою метаевристичних алгоритмів. Було проведено порівняння ефективності роботи алгоритмів. Розглянуто реалізацію створення випадкових ребер. Проведено оцінку якості метаевристичних алгоритмів розв’язку задачі класифікації. Для оцінки ефективності метаевристик на фрагментарних структурах було розроблено програму оцінки ефективності. Були реалізовані універсальні алгоритми ряду метаевристик. Реалізовані метод випадкового пошуку, метод ітеративного локального пошуку, метод імітації відпалу, еволюційно-фрагментарний алгоритм, метод перемішаних стрибаючих жаб. У програмі реалізовані генератор випадкових завдань і програма порівняння ефективності алгоритмів. Для задачі покриття графа зірками проведено чисельний експеримент на базі 53 випадково згенерованих завдань. Розглядалися зв'язкові графи з числом вершин від 20 до 50 і з щільністю ребер 0,5-0,8. Для кожної з задач було побудовано фрагментарну модель і застосовувалася група алгоритмів (випадковий пошук, еволюційно-фрагментарний алгоритм, метод імітації відпалу тощо). Параметри алгоритмів підбиралися таким чином, щоб трудомісткість обчислень була приблизно однаковою. Результати порівняння різних алгоритмів показують, що жоден з них не володіє явною перевагою перед іншими. Це побічно підтверджує відому теорему «про відсутність безкоштовних обідів» для метаевристик. Таким чином, в умовах реальної експлуатації розумно застосовувати не одну, а кілька метаевристик і вибирати найкращий результат. Розглянутий в дисертаційній роботі метод використання фрагментарних моделей для пошуку субоптимальних рішень задач класифікації, дозволяє порівняно просто побудувати універсальну комп'ютерну систему для таких завдань. Причому універсальними будуть програми реалізації метаевристик, а індивідуальними методи побудови фрагментарних моделей і алгоритми розрахунку значень критеріїв.