基于分层和强化学习的改进路径搜索算法

复杂网络下的路径搜索问题是网络寻优中的一个难点。现有算法主要存在以下问题：一是往往只能侧重于求解效率和求解精度中的一点；二是对动态变化的复杂网络适应性不强，求解效果不佳。因此，本文提出一种基于双分层和优化Q-Learning的改进路径搜索算法。对于求解时间随规模增加而急剧增长的问题，提出k-core和模块度结合的双分层划分网络的策略，以合理有效地减小网络规模。在子网络求解中，引入强化学习机制对网络进行动态感知，针对算法收敛较慢问题，加入自适应学习因子和记忆因子，优化更新公式，提高收敛速度。最后，在不同幂律指数（2~3）和不同规模的复杂网络下，将所提算法与Dijkstra算法、A*算法和Qrouting算法进行实验对比，结果表明该算法在保证较好求解精度的情况下，能有效地改善求解效率。

Improved Path Search Algorithm Based on Layering and Reinforcement Learning

The problem of path search in a complex network is a difficult point in network optimization. Existing path search algorithms mainly have the following problems: Firstly, they can only focus on one of solution efficiency and solution accuracy; secondly, they are not adaptable to complex networks with dynamic changes, and the solution effect is not good. So this paper proposes an improved path search algorithm based on double layering and optimized Q-Learning. For the problem that the solution time increases sharply with the increase of scale, a dual-layered strategy of dividing the network by combining k-core and modularity is proposed to reduce the network size reasonably and effectively. In the subnet solution, the reinforcement learning mechanism is introduced to dynamically sense the network. For the problem of slow convergence of the algorithm, the adaptive learning factor and memory factor are added to optimize the update formula and improve the convergence speed. Finally, under different power-law exponents (2 to 3) and complex networks of different sizes, the proposed algorithm is compared with Dijkstra algorithm, A* algorithm and Qrouting algorithm. The results show that the algorithm can effectively improve the solution efficiency while ensuring a good solution accuracy.