Article

Download article

The analysis of the investigation results on the realization of routing task based on neural networks and genetic algorithms

Konstantin Kolesnikov, Anait Karapetyan, V. Bahan

Abstract

There appears a necessity to solve tasks concerning the shortest ways with several optimization criteria. For this reason the task of the formation of new approaches and algorithms for the solution of problems of optimal rooting in networks becomes an actual one. The object of the study is to research the efficiency of the use of net resources in the distributed networks by means of artificial neural networks and genetic algorithms. As a result of the researches the modeling of the developed method of route optimization by means of genetic algorithms has been done. The researches have been performed using the presented algorithm with various preconditions (populations sizes, mutation percentage). The conclusion is made based on the two last researches: the first minimal determined value with 3 % error between them was found less than in 5 seconds. The following solutions differ by less than 1 % error. It is possible to speed up the work of algorithm by assigning right sizes of original population and mutation percentage. One more approach to solve the routing task is the use of neural networks. Hopfileld’s neural network algorithm with the use of Lyapunov’s function has been chosen to solve the task of routes optimization. Using the gradient descent method it has allowed to minimize the function and to find the stable state of Hopfileld’s network which corresponds to the shortest way between the nodes. To research the possibilities of Hopfileld’s neural network when solving the task of finding the shortest way the structures with numbers of nodes 5, 10, 15 and 20 were used. The obtained results show that graphs can contain the solutions consisting of four, five and six arrows and that the solutions contain only routes of four and five arrows when the expression of improved Lyapunov’s function is used. At the same time the neural network in the course of routes search is aimed to find more solutions containing the shortest way with the smallest number of arrows

Keywords:

routing, adaptive routing, multicriterion optimization, genetic algorithm, neural networks, Hopfield nets

Retrieved from Volume 21, No. 1, 2016

Pages 28-34

References Suggested citation

References

  1. Bilous, R.V., & Pohorilyi, S.D. (2010). Features of applied use of genetic algorithm for finding optimal paths in graphs. Reyestratsiya, zberihannya i obrobka danykh, 12(2), 81–87.
  2. Galushkin, A.I. (1995). Neurocomputers in the development of US military technology. Zarubezhnaya Radioelektronika, (6), 4–21.
  3. Gladkov, L.A., Kureychik, V.V., & Kureychik, V.M. (2006). Genetic algorithms (2nd ed.). Moscow: Fizmatlit.
  4. Hopfield, J.J., & Tank, D.W. (1985). Neural computation of decisions in optimization problems. Biological Cybernetics, 52(3), 141–152. https://doi.org/10.1007/BF00336987
  5. Kolesnikov, K.V., Karapetyan, A.R., & Kravchenko, O.V. (2010). Application of Hopfield neural networks to adaptive data routing problems in telecommunications. Avtomatika, 2, 168–169.
  6. Kolesnikov, K.V., Karapetyan, A.R., & Tsarenko, T.A. (2013). Genetic algorithms for multi-criteria optimization in adaptive data routing networks. Visnyk NTU “KhPI”, (56(1029)), 44–50.
  7. Kolesnikov, K.V., Nikulin, O.H., & Karapetyan, A.R. (2013). Use of neural network models to find optimal paths in networks with adaptive packet routing. Visnyk. Novi rishennya v suchasnykh tekhnolohiyakh, (56), 50–56.
  8. Rosenberg, R.S. (Year unknown). Simulation of genetic populations with biochemical properties. Mathematical Biosciences, 7, 223–257.
  9. Wieselthier, J.E., Barnhart, C.M., & Ephermides, A. (1994). A neural networks approach to routing without interference in multihop networks. IEEE Transactions on Communications, 42(1), 166–177. https://doi.org/10.1109/26.274065
  10. Wosserman, F. (1990). Neurocomputer technology: Theory and practice. Moscow: Mir.

Suggested citation

Kolesnikov, К., Karapetyan, A., & Bahan, V. (2016). The analysis of the investigation results on the realization of routing task based on neural networks and genetic algorithms. Bulletin of Cherkasy State Technological University, 21(1), 28-34.