Selyutin Y. Fragmentary models in optimal classification problems

The 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.