Neural network-based methods for finding the shortest path and establishing associative connections between objects

Eugene Fedorov, Olga Nechyporenko, Maryna Chychuzhko, Vladyslav Chychuzhko, Ruslan Leshchenko

Abstract


Nowadays, solving optimizations problems is one of the tasks for intelligent computer systems. Currently, there is a problem of insufficient efficiency of optimizations tasks solving methods (for example, high computing time and/or accuracy). The object of the research is the process of finding the shortest path and establishing associative connections between objects. The subject of the research is the methods of finding the shortest path and establishing associative connections between objects based on neural networks with associative memory and neural network reinforcement training. The objective of this work is to improve the efficiency of finding the shortest path and establishing associative connections between objects through neural networks with associative memory and neural network reinforcement training. To achieve this goal, a neuro-associative method and a neural network reinforcement training method was developed. The advantages of the proposed methods include the following. First, the proposed bi-directional recurrent correlative associative memory, which uses hetero-associative and auto-associative memory and an exponential weighting function, allows for increasing the associative memory capacity while preserving learning accuracy. Second, the Deep Q-Network (DQN) reinforcement learning method with dynamic parameters uses the ε-greedy approach, which in the initial iterations is close to random search, and in the final iterations is close to directed search, which is ensured by using dynamic parameters and allows increasing the learning speed while preserving learning accuracy. Conducted numerical research allowed us to estimate both methods (for the first method, the root mean square error was 0.02, and for the second method it was 0.05). The proposed methods allow expanding the field of application of neural networks with associative memory and neural network reinforcement learning, which is confirmed by their adaptation for the tasks of finding the shortest path and establishing associative connections between objects and contribute to the effectiveness of intelligent computer systems of general and special purpose. Prospects for further research are to investigate the proposed methods for a wide class of artificial intelligence problems.

Keywords


reinforcement learning; neural network; associative memory; establishing associative connections between objects; finding the shortest path

Full Text:

PDF

References


Neskorodieva, T., Fedorov, E., Chychuzhko, M. & Chychuzhko, V. Metaheuristic method for searching quasi-optimal route based on the ant algorithm and annealing simulation. Radioelectronic and Computer Systems, 2022, no. 1, pp. 92-102. DOI: 10.32620/reks.2022.1.07.

Strilets, V., Donets, V., Ugryumov, M., Artiuch, S., Zelenskyi, R. & Goncharova. T. Agent-oriented data clustering for medical monitoring. Radioelectronic and Computer Systems, 2022, no 1, pp. 103-114. DOI: 10.32620/reks.2022.1.08.

Ottoni, A. L. C., Nepomuceno, E. G., de Oliveira, M. S. & de Oliveira, D. C. R. Reinforcement learning for the traveling salesman problem with refueling. Complex & Intelligent Systems, 2021, vol. 8, pp. 2001-2015. DOI: 10.1007/s40747-021-00444-4.

Jaderberg, M. Human-level performance in first-person multiplayer games with population-based deep reinforcement learning. Available at: https://arxiv.org/abs/1807.01281. (accessed Feb. 15, 2023).

Silver, D. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXivLabs, 2017. DOI: 10.48550/arXiv.1712.01815.

Silver, D. et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 2018, no. 362, iss. 6419, pp. 1140-1144. DOI: 10.1126/science.aar6404.

Pouncy, T., Gershman, S., Tsividis, P., Xu, J. & Tenenbaum, J. Human learning in Atari. Available at: http://hdl.handle.net/1721.1/112620 (accessed Feb. 15, 2023).

Kumaran, D., Hassabis, D. & McClelland, J. What learning systems do intelligent agents need? Complementary learning systems theory updated. Trends Cogn. Sci, 2016, no. 20, iss. 7, pp. 512-534. DOI: 10.1016/j.tics.2016.05.004.

Gershman, S. J. & Daw, N. D. Reinforcement learning and episodic memory in humans and animals: an integrative framework. Annu. Rev. Psychol, 2017, no. 68, pp. 101-128. DOI: 10.1146/annurev-psych-122414-033625.

Ballard, I., Wagner, A. D. & McClure, S. M. Hippocampal pattern separation supports reinforcement learning. bioRxiv, 2018, pp. 293-332. DOI: 10.1101/293332.

Vikbladh, O., Shohamy, D. & Daw, N. Episodic contributions to model-based reinforcement learning. Annual Conference on Cognitive Computational Neuroscience CCN, 2017, pp. 1-2. Available at: https://ccneuro.org/abstracts/abstract_3000200.pdf. (accessed Feb. 15, 2023).

Kulkarni, T. D., Narasimhan, K., Saeedi, A. & Tenenbaum, J. Hierarchical deep reinforcement learning: integrating temporal abstraction and intrinsic motivation. arXivLabs, 2016, pp. 1-14. DOI: 10.48550/arXiv.1604.06057.

Higgins, I. et al. Darla: improving zero-shot transfer in reinforcement learning. arXivLabs, 2018. DOI: 10.48550/arXiv.1707.08475.

Botvinick, M., Weinstein, A., Solway, A. & Barto, A. Reinforcement learning, efficient coding, and the statistics of natural tasks. Current Opinion in Behavioral Sciences, 2015, vol. 5, pp. 71-77. DOI: 10.1016/j.cobeha.2015.08.009.

Botvinick, M., Ritter, S., Wang, J. X., Kurth-Nelson, Z., Blundell, C. & Hassabis, D. Reinforcement learning, fast and slow. Trends in Cognitive Sciences, 2019, vol. 23, iss. 5, pp. 408-422. DOI: 10.1016/j.tics.2019.02.006.

Hessel, M. Modayil, J., Hasselt, H. et al. Rainbow: combining improvements in deep reinforcement learning. arXivLabs, 2017. DOI: 10.48550/arXiv.1710.02298.

Duan, Y., Schulman, J., Chen, X., Bartlett, P.L., Sutskever, I. & Abbeel, P. Rl2: Fast reinforcement learning via slow reinforcement learning. arXivLabs, 2017. DOI: 10.48550/arXiv.1611.02779.

Dunovan, K. & Verstynen, T. Believer-skeptic meets actor-critic: Rethinking the role of basal ganglia pathways during decision-making and reinforcement learning. Frontiers in Neuroscience, 2016, vol. 10. DOI: 10.3389/fnins.2016.00106.

Sutton, R. S. & Barto, A. G. Reinforcement Learning: An Introduction (2nd ed.). The MIT Press, 2018. 338 p. Available at: https://inst.eecs.berkeley.edu/~cs188/fa19/assets/files/SuttonBartoIPRLBook2ndEd.pdf (accessed Feb. 15, 2023).

Wang, J. X., Kurth-Nelson, Z., Kumaran, D., Tirumala, D., Soyer, H. & Leibo, J. Z. Prefrontal cortex as a meta-reinforcement learning system. Nature Neuroscience, 2018, vol. 21, iss. 66, pp. 860-868. DOI: 10.1038/s41593-018-0147-8.

Wang, J. X., Kurth-Nelson, Z., Tirumala, D., Soyer, H., Leibo, J. Z. & Munos. R. Learning to reinforcement learn. arXivLabs, 2017, pp.1611.05763.

Xu, Z., Hasselt, H., Hessel, M., Oh, J., Singh, S. & Silver, D. Meta-Gradient Reinforcement Learning with an Objective Discovered Online. arXivLabs, 2020. DOI: 10.48550/arXiv.2007.08433.

Xu, Z., Hasselt, H. & Silver, D. Meta-gradient reinforcement learning. arXivLabs, 2018. DOI: 10.48550/arXiv.1805.09801.

Robertazzi, F., Vissani, M., Schillaci, G. & Falotico, E. Brain-inspired meta-reinforcement learning cognitive control in conflictual inhibition decision-making task for artificial agents. Neural Networks, 2022, vol. 154, pp. 283-302. DOI: 10.1016/j.neunet.2022.06.020.

Lobo, R. A. & Valle, M. E. Ensemble of Binary Classifiers Combined Using Recurrent Correlation Associative Memories. arXivLabs, 2020, pp. 1-14. DOI: 10.48550/arXiv.2009.08578.

Krivtsov, S., Meniailov, I., Bazilevych, K. & Chumachenko. D. Predictive model of COVID-19 epidemic process based on neural network. Radioelectronic and Computer Systems, 2022, no. 4, pp. 7-18. DOI: 10.32620/reks.2022.4.01.

Martyniuk, T., Krukivskyi, B., Kupershtein, L. & Lukichov V. Neural network model of heteroassociative memory for the classification task. Radioelectronic and Computer Systems, 2022, no. 2, pp. 108-117. DOI: 10.32620/reks.2022.2.09.

Kobayashi, M. Quaternionic Hopfield neural networks with twin-multistate activation function. Neurocomputing, 2017, vol. 267, pp. 304-310. DOI: 10.1016/j.neucom.2017.06.013.

Javidmanesh, E. Global Stability and Bifurcation in Delayed Bidirectional Associative Memory Neural Networks with an Arbitrary Number of Neurons. J. Dyn. Sys., Meas., Control, 2017, vol. 139, iss. 8. 5 p. DOI: 10.1115/1.4036229.

Du, K. L. & Swamy, M. N. S. Neural Networks and Statistical Learning. Springer-Verlag London, 2014, 824 p. DOI: 10.1007/978-1-4471-5571-3.

Aggarwal, C. C. Neural Networks and Deep Learning. Cham, Switzerland, Springer, 2018. 497 p. DOI: 10.1007/978-3-031-29642-0.

Neskorodieva, T. & Fedorov, E. Method for automatic analysis of compliance of settlements with suppliers and settlements with customers by neural network model of forecast. Advances in Intelligent Systems and Computing, AISC, Springer, Cham, 2021, vol. 1265, pp. 156–165. DOI: 10.1007/978-3-030-58124-4_15.

Neskorodieva, T. & Fedorov, E. Neural Network models ensembles for generalized analysis of audit data transformations. Lecture Notes in Networks and Systems, Springer, Cham, 2022, vol. 344, pp. 263-279. DOI: 10.1007/978-3-030-89902-8_21.

Sturtevant, N. R. Benchmarks for Grid-Based Pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 2012, vol. 4, no. 2, pp. 144-148. DOI: 10.1109/TCIAIG.2012.2197681.




DOI: https://doi.org/10.32620/reks.2023.2.05

Refbacks

  • There are currently no refbacks.