| 求解基于距离的关键节点问题的路径重连算法 |
| Evolutionary path relinking algorithm for distance-based critical node problem |
| 摘要点击 59 全文点击 0 投稿时间：2025-01-06 修订日期：2025-11-17 |
| 查看/发表评论 下载PDF阅读器 |
| 中文关键词 复杂网络; 关键节点检测; 启发式优化; 进化计算; 路径重连 |
| 英文关键词 complex networks; critical node detection; heuristic optimization; evolutionary computation; path relinking |
| 基金项目 国家自然科学基金项目（面上项目，重点项目，重大项目） |
| 投稿方向 复杂网络、智能优化 |
| 作者 | 单位 | 邮编 | | 周扬名* | 上海交通大学 | 200030 | | 申宇轩 | 上海交通大学 | | | 魏君陶 | 上海交通大学 | | | 厉嘉琪 | 华东理工大学 | |
|
| 中文摘要 |
| 深入研究了基于距离的关键节点问题(Distance-based Critical Node Problem, DCNP), 该问题作为经典关键节点问题的一个重要扩展, 在交通网络, 通讯网络, 航空网络, 以及社交网络等复杂网络分析中展现了较高的实用价值. 比如, 在社交网络中, 非相邻的节点之间的互动价值应该取决于节点之间的距离. 针对这一复杂NP-hard问题, 提出了一种高效的进化路径重连搜索(Evolutionary Path Relinking, EPR)算法, 该算法集成了四个核心算法模块: 知识驱动的种群初始化, 基于切点的局部搜索, 频繁项集驱动的解重构, 以及考虑相似性的种群管理. 实验结果表明, EPR算法在多数基准测试算例上优于快速三个体模因搜索算法, 尤其在求解效率方面表现更优. |
| 英文摘要 |
| This paper studies the distance-based critical node problem (DCNP), which is an important extension of the classical critical node problem. The DCNP has broad applications in analyzing complex networks, including transportation, communication, aviation, and social networks. To effectively solve this NP-hard problem, this work proposes an evolutionary path relinking (EPR) algorithm. The proposed EPR integrates four main algorithmic modules: knowledge-driven population initialization, cut vertex-based local search, frequent itemset-driven solution reconstruction, and similarity-based population management. Extensive evaluations on both synthetic and realworld instances show the superiority of EPR for solving DCNP. In particular, \textcolor{blue}{EPR outperforms the existing best-performing algorithm called fast tri-individual memetic search algorithm. |
| 关闭 |
|
|
|
|
|
