S. Bazhan. Operator modification of the genetic algorithm for researching processes modeled by rapidly oscillating and discrete functions.
The object of the research: linear operators in a finite dimensional space; functions of one variable defined on a closed segment; vector-valued discrete functions.
The subject of the research: linear operators of a special form that perform crossing over and mutation operations; Cantor sets; applied problems of finding the minimum of a function of one variable; the task of scheduling classes in an educational institution.
The aim of the research.
Development of a mathematical model of a modified genetic algorithm based on the theory of linear operators, with application to the tasks of finding the extreme value of the function of one variable in the decimal version of the representation and tasks.
The first chapter presents the results of the conducted search, systematization and analysis of scientific works of famous scientists. A study of the current state of the theory and practice of the application of genetic algorithms was conducted.
In connection with the specificity of the transfer of natural-evolutionary actions and the preservation of the terminology of genetic processes during the study of scientific works, the use of synonymous meanings of the same processes and elements of the mathematical interpretation of genetic algorithms was noted. Correspondence in the use of genetic and mathematical terminology was established. An overview of theoretical and practical approaches to the application of classical and modified genetic algorithms for solving the problems of finding global extrema of functions of one variable and the problems of arranging a schedule was carried out. A review of studies on the theory of schedules, methods of solving problems in this field with the use of methods of solving transport problems was carried out. As a result of the analysis, a unified approach to solving the problem of finding the global extremum of a function of one variable and arranging a schedule is proposed, based on the application of linear operators, which are, in a certain sense, generalizations of crossing over and mutation operations in the classical genetic algorithm. Algorithms for solving these problems are new, so they need justification of their workability and efficiency. For this purpose, software applications have been developed that enable practical numerical experiments of the automated scheduling classes in an educational institution.
In the second chapter, a mathematical model of operator modification of genetic algorithm is developed, the algorithm of its implementation is given.
The mathematical model of the operator modification of the genetic algorithm is based on the application of linear operators generated by stochastic matrices, which implement the procedure of recombination of elements of the search area.
Three variants of the mutation operation for the operator modification of the genetic algorithm are proposed. The first option is based on a random process of selection of parental chromosomes at the stage of determining the best parental pair of chromosomes on a given segment. The second option of the modification is based on the application of stochastic matrices with the use of random parameters of a certain type, which are stretch operators. The third option of the proposed mutation operation suggests applying the Cantor set as a new method for obtaining population elements.
In the third chapter presents a mathematical model for arranging a schedule of an educational institution based on a special type of transport problem. This section deals with presenting the principles of building the initial reference plan of the class schedule by the minimal element method and the random filling method. The principle of orderliness and ranking of data is substantiated. Also methods of construction and application of the schedule improvement operator are given and task of assigning an auditorium fund for classes has been modelled.
The fourth chapter presents the results of numerical experiments obtained with the help of developed computer programs. Graphical and numerical results are presented for the problem of finding the global minimum of a function of one variable with different conditions of application of operators implementing crossing over and mutation.
The results of solving the task of arranging a schedule of classes in an educational institution using the computer program "Schedule Generator" are presented. An analysis of the results of the comparison of two methods of building a reference plan was conducted. The sections also contains study of the application of operators for permuting the rows of the decomposition matrix, which are an analogue of the mutation operation.
Keywords: mathematical modelling, genetic algorithm, mutation operators, Cantor's set, optimization problems, iterative process, extremum, class schedule.
