CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs
A. Chervov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, M. Obozov, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, et al.
本文是一系列研究中的第二篇,这些研究是在非常大的图形上开发基于人工智能的高效方法(例如: 10^70个节点),专注于Cayley图形和数学应用。 开源的 CayleyPy 项目是我们研究的核心组成部分。 本文提出了强化学习方法与第一篇论文更直接的扩散距离方法的新组合。 我们的分析包括为该方法的关键构建块进行基准测试:神经网络的架构,随机行走的生成器和波束搜索路径。 我们将这些方法与经典的计算机代数系统GAP进行了比较,证明它们“克服了GAP”的考虑示例。 作为一个特定的数学应用程序,我们检查Cayley图的对称组与循环移位和换位发生器。 我们为OEIS-A186783猜想提供了强有力的支持,即机器学习和数学方法的直径等于n(n-1)/2。 我们识别推测的最长元素,并生成其所需长度的分解。 我们通过呈现具有给定复杂性的算法来证明n(n-1)/2-n/2-n/2的直径下界和n(n-1)/2++ 3n的上限。 我们还提出了几个以数值实验为动机的猜想,包括对中心极限现象的观察(由Gumbel分布近似增长),图谱的均匀分布,以及对排序网络的数值研究。 为了刺激众包活动,我们在Kaggle平台上创造了挑战,并邀请各方做出贡献,改进和基准测试Cayley图路径查找和其他任务的方法。
This paper is the second in a series of studies on developing efficient artificial intelligence-based approaches to pathfinding on extremely large graphs (e.g. 10^70 nodes) with a focus on Cayley graphs and mathematical applications. The open-source CayleyPy project is a central component of our research. The present paper proposes a novel combination of a reinforcement learning approach with a more direct diffusion distance approach from the first paper. Our analysis includes benchmarking vario...