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

  Скачати повний текст

Дисертаційна робота присвячена узагальненню і розробці теоретичних основ математичного апарату для побудови та дослідження фрагментарних моделей та метаевристичних методів для розв'язку задачі класифікації. Розглянуті в дисертації моделі та методи можуть використовуватися під час пошуку розв'язків у багатьох наукових та практичних задачах, в тому числі, задачі розміщення виробництва.У вступі обґрунтовано актуальність теми дисертаційної роботи, сформульовано мету та основні задачі дослідження, показано їх зв'язок з науковими програмами. Визначено методи дослідження, наукову новизну та практичне значення отриманих результатів.У розділі 1 проведено огляд результатів за тематикою дисертаційної роботи. Обґрунтовано вибір напрямків подальших досліджень, пов'язаних з розв'язком задачі оптимальної класифікації. Розглянуто та проаналізовано існуючі задачі оптимальної класифікації та методів пошуку їх розв'язків. Досліджено обчислювальну складність існуючих задач класифікації. Виявлено, що постановка задачі пошуку оптимальної класифікації дозволяє віднести цю задачу до багатокритеріальних. Виявлено, що більшість задач оптимальної класифікації є важкорозв'язуваними (складними в обчислювальному сенсі), оскільки до них поліноміально зводиться хоча б одна NP-повна задача. Для таких задач на сьогодні невідомі алгоритми пошуку точного розв'язку простіших, ніж повний перебір всіх допустимих розв'язків задачі. Тому є сенс шукати прості наближені алгоритми, які хоч і не дають точного розв'язку, але мають високу швидкодію. Серед таких алгоритмів виділяється клас «жадібних» алгоритмів.Виділено невирішені задачі класифікації.У розділі 2 наведено ряд основних понять та результатів, які використовуються в роботі та стосуються комбінаторного об'єкту «фрагментарна структура». Вивчено особливості та властивості фрагментарних структур, встановлено зв'язок з категорією «опуклість» та задачею покриття графів. Досліджено поняття метаевристики та проаналізовано метаевристичні методи пошуку оптимальних рішень у задачі класифікації. Встановлено зв'язок між задачею оптимальної перестановки та класифікації.Виявлено, що експериментальні дослідження розподілу локальних оптимумів свідчать про високу концентрацію їх в безпосередній близькості від глобального оптимуму.Показано, що проблема пошуку початкових популяцій для реалізації еволюційно-фрагментарної моделі зводиться до задачі покриття (або розбиття) простору перестановок опуклими множинами.У розділі 3 розглянуто фрагментарний алгоритм покриття графу зірками. Проаналізовано найпростіші варіанти задачі розміщення виробництва з точки зору задачі класифікації, а також наведено метаевристичні алгоритми пошуку оптимальних рішень складних задач розміщення виробництва.Сформульована задача покриття. Побудовано фрагментарну модель задачі.Визначено умову приєднання елементарного фрагменту.Розглянуто задачі розміщення виробництва. Визначена доцільність використання методу рою часток та фрагментарної моделі, а також їх модифікацій.У розділі 4 запропоновано програмні реалізації генерації випадкових графів та розв'язку задачі класифікації за допомогою метаевристичних алгоритмів. Було проведено порівняння ефективності роботи алгоритмів. Розглянуто реалізацію створення випадкових ребер. Проведено оцінку якості метаевристичних алгоритмів розв'язку задачі класифікації.Для оцінки ефективності метаевристик на фрагментарних структурах було розроблено програму оцінки ефективності. Були реалізовані універсальні алгоритми ряду метаевристик. Реалізовані метод випадкового пошуку, метод ітеративного локального пошуку, метод імітації відпалу, еволюційно-фрагментарний алгоритм, метод перемішаних стрибаючих жаб. У програмі реалізовані генератор випадкових завдань і програма порівняння ефективності алгоритмів.Для задачі покриття графа зірками проведено чисельний експеримент на базі 53 випадково згенерованих завдань. Розглядалися зв'язкові графи з числом вершин від 20 до 50 і з щільністю ребер 0,5-0,8. Для кожної з задач було побудовано фрагментарну модель і застосовувалася група алгоритмів (випадковий пошук, еволюційно-фрагментарний алгоритм, метод імітації відпалу тощо). Параметри алгоритмів підбиралися таким чином, щоб трудомісткість обчислень була приблизно однаковою.Результати порівняння різних алгоритмів показують, що жоден з них не володіє явною перевагою перед іншими. Це побічно підтверджує відому теорему «про відсутність безкоштовних обідів» для метаевристик. Таким чином, в умовах реальної експлуатації розумно застосовувати не одну, а кілька метаевристик і вибирати найкращий результат. Розглянутий в дисертаційній роботі метод використання фрагментарних моделей для пошуку субоптимальних рішень задач класифікації, дозволяє порівняно просто побудувати універсальну комп'ютерну систему для таких завдань. Причому універсальними будуть програми реалізації метаевристик, а індивідуальними методи побудови фрагментарних моделей і алгоритми розрахунку значень критеріїв.^UThe dissertation is devoted to the generalization and development of the theoretical basis for the mathematical apparatus for constructing and researching fragmentary models and metaheuristics methods for solving a classification problem. The models and methods considered in the thesis can be used for resolving many scientific and practical problems, including the problem of manufactory location.The introduction substantiates the relevance of the study, formulates major goals and objectives of the research, shows their connection with scientific programs. Defined research methods, scientific novelty and practical significance of the results.The Chapter 1 shows the overview of the results on the subject of the dissertation work. The choice of directions of further research related to the solution of the optimal classification problem is substantiated. The existing problems of optimal classification and methods of searching for their solutions are considered and analyzed. The computational complexity of existing problems of classification is investigated.It was found that most optimal classification tasks are difficult to solve (complex in the computational sense), since at least one NP-complete problem is polynomially reduced to them. Therefore, it makes sense to look for simple approximate algorithms. The Chapter 2 provides a number of basic concepts and results that are used in the work and relate to the "fragmentary structure" combinatoric object. The peculiarities and properties of fragmentary structures were studied, the connection with the category "bulge" and the task of covering graphs was established. The concept of meta-heuristics is studied and metaheuristic methods of searching for optimal solutions in the problem of classification are analyzed. The connection between the task of optimal permutation and classification has been established.It was found that experimental studies of the distribution of local optimums indicate a high concentration of them near of the global optimum (the hypothesis about the existence of a "great valley" for minimum tasks or "central mountain range" for maximum tasks).It is shown that the problem of finding initial populations for the implementation of an evolutionary-fragmentary model is reduced to the task of covering (or breaking) the permutation space with convex sets.The Chapter 3 discusses the fragmentary algorithm for covering graph stars. The simplest options for the task of placing production in terms of the classification task are analyzed, as well as metaheuristic algorithms finding optimal solutions to complex production placement tasks are given.The coverage problem is formulated.A fragmentary model of the problem is constructed. The condition of joining an elementary fragment is determined.The problems of production location are considered.It is determined that the best results in solving the problem of distribution of economic burden considering the impact on the environment demonstrate the method of swarming of particles with the selection of coefficients of socialization and personalization based on a genetic algorithm.The Chapter 4 proposed software implementations for generating random graphs and solving the classification problem using metaheuristic algorithms. The quality of metaheuristic algorithms for solving the classification problem is evaluated.A number of metaheuristics have been implemented. In particular, the method of random search, the method of iterative local search, the method of simulation of annealing, the evolutionary-fragmentary algorithm, the method of mixed jumping frogs are implemented.A fragmentary models were built for each of the problems and a group of algorithms was used (random search, evolutionary-fragmentary algorithm, annealing simulation method, etc.). The parameters of the algorithms were selected so that the complexity of the calculations was approximately the same.The results of comparing different algorithms show that none of them has a clear advantage over the others. This indirectly confirms the well-known "No free lunch" theorem for metaheuristics. Thus, in the conditions of real operation, it is reasonable to apply not one, but several metaheuristics and choose the best result. The method of using fragmentary models for finding suboptimal solutions to classification problems considered in the dissertation allows building a relatively universal computer system for such problems. Moreover, the programs of realization of metaheuristics will be universal, and the methods of construction of fragmentary models and algorithms of calculation of values ​​of criteria will be individual.