HIGH TECH IN EARTH SPACE RESEARCH

Routing on a graph of number-theoretic objective function and genetic algorithm

Alliluyeva N.V., Rudenko E.M., Semikina E.V.

It is considered the mathematical approach to calculation of routes of unmanned vehicles on the Euler graph of reference points on the ground. The methods for constructing of the objective function of the graph based on algebraic and number-theoretic approach are compared.

The objective graph function as a polynomial of several variables reaches minimal zero value on the sets of vertices of the graph which are the closed routes on the graph. Algebraic approach leads to the objective function as a sum of several polynomials. The first augend takes into account the information about permanence of the minimum length of closed route of Euler graph passing through all edges once. The other augends represent the combinatorial frequency of the vertices of Euler graph in the optimal closed routes of minimal length which is equal to a half of their multiplicity. Analysis of an algebraic objective function as a sum of polynomials shows possibility of finding of closed routes on various Euler models of this graph on the example of the specific graph. Number-theoretical approach leads to construction of the objective function as a polynomial. The theoretical basis for construction of the objective function in this approach are theorems of uniqueness of the representation of integers as a sum in the s-number system and on the uniqueness of a rational number as an irreducible ratio of product of powers of different primes. The mathematical model of route calculation on the graph is based on minimization of s-and- p-multiplicative objective functions of the graph made by genetic algorithm. The effectiveness of the routes calculation has been studied using by means of the constructed objective functions of the graph. Minimal required time is achieved by route calculation using the whole s-objective function. Number-theoretical approach makes it possible to construct the objective functions for extra-large graphs and points to the connection with the distribution of primes and the theory of p-adic numbers. All constructed number-theoretical objective functions have the specificity of achieving the minimum which is equal to zero only on optimal closed routes of the minimal length graph. The interconnection of the applied problem of unmanned aerial vehicles routing on the ground with the mathematical problem of optimization on the graphs by means of number theory and genetic algorithm is shown.

Editorial board

Bobrowsky V.I.
(Ph.D., Associate Professor, Head of Department of "INTELTEH")

Borisov V.V.
(Ph.D., Professor, Actual Member of the Academy of Military Sciences, Professor, Department of Computer Science of MPEI)

Budko P.A.
(Ph.D., Professor, Department of Technical communication and automation in S.M. Budjonny Military Academy of the Signal Corps)

Budnikov S.A.
(Ph.D., associate professor, Actual Member of the Academy of Education Informatization, Head of the automated control systems Department in Russian Air Force Military Educational and Scientific Center “Air Force Academy named after Professor N.E. Zhukovsky and Y.A. Gagarin”)

Verhova G.V.
(Ph.D., Professor, Head of Department of Automation communication companies In the Bonch-Bruevich Saint Petersburg State University of Telecommunications)

Goncharevsky V.S.
(Ph.D., Professor, Honored Worker of Science and Technology of the Russian Federation, Professor of technologies and technical support and maintenance of the automated control systems in Military Space Academy of A.F. Mozhaysky)

Komashinskiy V.I.
(Ph.D., Professor, professor of processing and transmission discrete messages in the Bonch-Bruevich Saint Petersburg State University of Telecommunications)

Kirpanev A.V.
(Ph.D., Associate Professor, Head of JSC "Scientific Production Enterprise "Radar MMS")

Kurnosov V.I.
(Ph.D., Professor, Academician of Academy of Sciences of the Arctic, Academician of the International Academy of Informatization, International Academy of defense, security, law and order, corresponding member of the Academy of Natural Sciences, Senior Researcher" Open Joint Stock Company "Scientific Research Institute "Rubin")

Manuilov Y.S.
(Ph.D., Professor, Department of automated control systems space complexes in Military Space Academy of A.F. Mozhaysky)

Morozov A.V.
(Ph.D., Professor, Actual Member of the Academy of Military Sciences, Head of the Department of automated command and control systems in Military Аcademy of troops of antiaircraft defense)

Moshak N.N.
(Ph.D., Associate Professor, head of the department of "INTELTEH")

Prorok V.Y.
(Ph.D., Professor, professor of automatic control systems in Military Space Academy of A.F. Mozhaysky)

Semenov S.S.
(Ph.D., associate professor, professor of technical communication and automation in S.M. Budjonny Military Academy of the Signal Corps)

Sinicyn E.A.
(Ph.D., Professor, Head of the Research Department of JSC "The All-Russian research institute of radio equipment")

Shatrakov Y.G.
(Ph.D., Professor, Honored Worker of Science, Scientific Secretary of JSC "The All-Russian research institute of radio equipment")