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

摘要：

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

关键词：复杂网络、路径优化、分层网络、强化学习

分类号：TP399(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61104004,61170258,U1806201,61671261

在线出版日期：2020-12-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：77-82,88