Методика построения субоптимальных маршрутов для группы беспилотных летательных аппаратов на основе биоинспирированных алгоритмов при наличии препятствий

Постановка задачи: Применение различных алгоритмов решения задачи коммивояжера, таких как метод ветвей и границ, генетический алгоритм, алгоритм имитации отжига, жадный алгоритм, зачастую не учитывают реальных возможностей вычислительных машин, способных их реализовать. Повышенные требования предъявляются к бортовым вычислителям беспилотных летательных аппаратов (БЛА), осуществляющих специфические задачи в условиях неблагоприятной внешней среды. Увеличивать возможности бортового вычислителя до варианта электронной вычислительной машины, реализующего функции расчета на «земле», не представляется, в настоящее время, возможным из-за ограничений, связанных с массово-габаритными показателями аппарата. Поэтому вопросы синтеза алгоритмов оптимизации с целью удовлетворения требований к аппаратно-программной части беспилотного летательного аппарата военного назначения остаются самостоятельной проблемой. Целью работы является построение алгоритма решения задачи коммивояжера, основанного на совместном использовании муравьиного и генетического алгоритмов, что позволит реализовать вычислительные процедуры алгоритмов решения различных специальных задач, требующие от вычислителя больших объемов памяти и высокой скорости обработки информации. Используемые методы: для решения задачи поиска целевых объектов противника в условиях неблагоприятных действий внешней среды наиболее подходящими по своей вычислительной сложности, оптимальному времени на поиск, и отвечающими требованиям бортовых вычислителей, являются муравьиный и генетический алгоритмы. В качестве критериев оптимизации решаемой задачи в работе предлагается использовать максимизацию количества точек в маршруте и минимизацию времени их облета БЛА. Новизна: элементами новизны представленной работы являются с одной стороны, применение комплексного критерия, включающего в себя минимизацию времени решения задачи и максимизацию количества точек облета маршрута, а с другой стороны, построение процедуры итерактивного исключения «подциклов», входящих в структуру алгоритма, что позволяет разрешить NP-сложность решения такого типа задач за полиномиальное время. Результат: использование представленного алгоритма поиска субоптимального решения задачи коммивояжера с учетом приоритета целей, неравнозначности точек облета и, возникающих на пути препятствий, в условиях дестабилизирующих воздействий противника позволило обеспечить требуемые вычислительные возможности бортового вычислителя БЛА при максимальном покрытии зоны облета. Предложена процедура сужения полного множества оптимальных маршрутов облета неравноценных точек до парето-оптимального множества. Разработанные программы на языке C++, и построенная информационно-вычислительная система с визуальным интерфейсом позволили провести оценку сложности алгоритмов. Комплексирование методов имитации отжига, муравьиного алгоритма с генетическим алгоритмом для решения поставленной задачи позволило снизить время работы алгоритма на 13% по сравнению с методом ветвей и границ. Практическая значимость: выполненные в работе исследования показали, что предложенный алгоритм может быть реализован в виде программы, записанной в память современного бортового спецвычислителя БЛА, что позволит осуществлять автономный полет группой БЛА на больших территориях и охватывать более 66 точек облета.
Purpose. The use of various algorithms for solving the traveling salesman problem, such as the method of branches and boundaries, genetic algorithm, simulated annealing algorithm, greedy algorithm, often do not take into account the real capabilities of computers capable of implementing them. Increased requirements are imposed on on-board computers of unmanned aerial vehicles (UAVs) performing specific tasks in an unfavorable external environment. It is not currently possible to increase the capabilities of the on-board computer to a computer variant that implements the calculation functions on the "Ground" due to the limitations associated with the mass-dimensional characteristics of the device. Therefore, the issues of synthesis of existing optimization algorithms in order to meet the requirements for the hardware and software of an unmanned aerial vehicle remain an independent problem. The aim of the work is to build an algorithm for solving the traveling salesman problem based on the combined use of ant and genetic algorithms, which will allow implementing computational procedures for algorithms for solving various special tasks that require large amounts of memory and high information processing speed from the computer. Methods: to solve the problem of searching for enemy targets in the conditions of unfavorable actions of the external environment, the most suitable in terms of computational complexity, optimal search time and meeting the requirements of on-board computers are ant and genetic algorithms. As criteria for optimizing the problem being solved, it is proposed to use maximizing the number of points in the route and minimizing the time of their flight by an unmanned aerial vehicle. Novelty. The novelty elements of the presented work are, on the one hand, the application of a complex criterion, which includes minimizing the time of solving the problem and maximizing the number of points of flight of the route, and on the other hand, the construction of a procedure for iterative elimination of "subcycles" included in the structure of the algorithm, which allows to solve the NP-complexity of solving this type of problems in polynomial time. Results. The use of the presented algorithm for searching for a suboptimal solution to the traveling salesman problem, taking into account the priority of targets, the disparity of flyover points and obstacles arising on the way, under the influence of electronic warfare and enemy air defense, made it possible to provide the required computing capabilities of the onboard computer with maximum coverage of the flyover zone. A procedure is proposed for narrowing the complete set of optimal flyby routes of unequal points to a Pareto-optimal set. The developed program codes in the C++ language, and the built information and computing system. Practical relevance. the research carried out in the work has shown that such an algorithm can be implemented in the form of a program recorded in the memory card of an onboard modern special calculator of an unmanned aerial vehicle, which will allow autonomous flight by a group of UAVs over large territories and cover more than 66 points of flight.