Публікація: Математичні моделі та методи розв'язання оптимізаційних задач сенсорного покриття об'єктів контролю
Завантаження...
Дата
2019
Автори
Назва журналу
ISSN журналу
Назва тома
Видавництво
ХНУРЕ
Анотація
Робота присвячена розв’язанню оптимізаційних задач покриття областей складної форми ідентичними кругами, які зв'язані мережею з'єднань. Розроблено математичні засоби для моделювання відношень між геометричними об'єктами, що беруть участь у покритті і ґрунтуються на використанні нових класів функцій – функції, що моделює відношень покриття для трьох кіл, псевдонормалізованих функцій належності й функцій квазіналежності. Побудовано узагальнену математичну модель задачі, множина реалізацій якої охоплює широкий клас наукових і прикладних задач покриття області однаковими колами. Досліджено властивості моделі й запропоновано стратегію розв’язання, яка ґрунтується на методі мультистарту. Для реалізації стратегії розв’язання розроблені швидкі й ефективні алгоритми побудови стартових покриттів; методи генерації простору розв’язків і функції мети задачі по стартовій точці й реалізований програмний інтерфейс із сучасними програмними пакетами для дискретної й нелінійної оптимізації. Розроблено й реалізовано комплекс програм для розв’язання оптимізаційної задачі покриття області довільної просторової форми колами рівного радіуса, які зв'язані мережею (у тому числі з урахуванням похибок вихідних даних).
The work is devoted to the study and solution of optimization problems of coverage with identical circles of areas of complex shape. New constructive mathematical tools have been developed for modeling the relationship between the circles involved in the coating, as well as between the circles and the covered area to build a mathematical model. The tools are based on the use ofwell-known belonging functions and phi-functions, as well as new classes of functions — the function that formalizes the coverage relations for three circles, adjusted belonging functions and quasi-belonging functions. A generalized mathematical model of the problem of covering with identical circles is constructed based on the tools developed in this work. As a result, the optimization problem is represented as a non-linear programming problem. The set of realizations of the model covers a wide class of scientific and applied problems of covering with circles. A strategy has been developed for solving problems of covering with identical circles of areas of arbitrary shape, taking into account technological restrictions on the placement of circles in the form of restrictions on the minimum and maximum allowable distances and zones of prohibition. The strategy is proposed on the basis of a study of the properties of the generalized model and the current state of the software used to solve optimization problems. It uses the multi-start method to find an approximation to the global extremum by solving a sequence of local optimization problems from starting points. To implement the strategy have being proposed and implemented: - two effective methods for constructing admissible starting points for covering problems with circles of the same radius: an optimization method based on a greedy algorithm of optimization by variable groups to cover arbitrary areas and a section-regular covering method for rectangular areas. The first one uses of wfunctions that describe in an analytical form the area of intersection of objects. The second method uses covering of the area by rectangular sections. Each of section is covered by circles placed in the nodes of a two-dimensional lattice; - methods for generating solution space by starting point for the main implementations of the generalized model: minimizing the length of the wires, minimizing the radius of the covering circles, minimizing the number of covering circles, correcting unacceptable coverage, correcting unacceptable placement of sensors, optimizing the coverage density; - methods of generating of objective function by the starting point for the listed in the preceding paragraph cover tasks. To generate the objective function in the problem of minimizing the length of the wires, it is necessary to solve the auxiliary combinatorial optimization problems – the traveling salesman problem for the case of ring-type connections and the routing problem for routes for the case of stub-type connections; - the method of local optimization for the problem of non-smooth programming, based on reducing the process of solving the original problem to solving a sequence of non-linear programming problems with constraints described by inequalities with differentiable functions; C++ code interfaces with recent combinatorial VPRH optimization packages (for solving the traveling salesman and routing problems) and IPOPT (for solving local optimization problems). The computational experiments carried out in the work convincingly confirmed the constructiveness of the developed mathematical modeling tools and demonstrated the adequacy of the constructed mathematical model of the task of covering the same radius of a region with a complex form of its implementation. The practica lsignificance of the results lies in the development and implementation of a set of programs for solving an optimization problem of covering an area of arbitrary spatial shape with identical circles connected by a wired network (including the possibility of accounting of the initial data errors) and a number of important tasks from a practical point of view, including adjustments of invalid coverings, minimizing the radius of the covering circles, optimizing the quality of coverings, etc. The “Vesta” program complex can be directly applied for designing systems of diagnostics, monitoring and control, housing construction, as well as reducing the time to solve these problems. The developed software package is used in the department of regulatory and technical work and control over fire protection and licensing systems of the Main Directorate of the State Emergency Situations Service of Ukraine in the Kharkiv region, “NVP Brand” Ltd as well as in the educational process of the National University of Civil Defence of Ukraine.
Опис
Ключові слова
математичне моделювання, оптимізація, покриття, розміщення пожежних сповіщувачів, трасування з’єднань, mathematical modeling, optimization, coverage, placement of fire detectors, connection trace
Бібліографічний опис
Антошкін О. А. Математичні моделі та методи розв'язання оптимізаційних задач сенсорного покриття об'єктів контролю : автореф. дис. ... канд. техн. наук : 01.05.02 "Математичне моделювання та обчислювальні методи" / О. А. Антошкін ; М-во освіти і науки України, Харків. нац. ун-т радіоелектроніки. – Харків, 2019. – 22 с.