面向一类关键节点检测问题的学习型进化算法研究

Critical node detection problems (CNDPs) constitute an important class of graph and network optimization problems with applications to many areas including social network analysis, epidemic control, network security, etc. Unlike previous studies have primarily focused on developing traditional exact algorithms and heuristic algorithms for solving CNDPs, there is very limited work by using machine learning to improve evolutionary algorithms for solving CNDPs. To solve such NP-hard problems efficiently, in this project, we attempt to combine evolutionary algorithms (i.e., memetic algorithm and evolutionary path-relinking algorithm) with machine learning techniques, and propose three new evolutionary algorithms, where machine learning techniques are used for offspring solution construction, key parameter automatic configuration and parent solutions selection in an online learning way. More specifically, three kinds of machine learning based evolutionary algorithms will be proposed, namely a frequent pattern based hybrid evolutionary algorithm, a learning automaton based hybrid evolutionary algorithm and a t-SNE based evolutionary path-relinking algorithm. Research on combining evolutionary algorithms with machine learning not only provides an alternative means to solve CNDPs, but also effectively promotes the applications of machine learning in evolutionary optimization algorithms.

关键节点检测问题是一类重要的图和网络优化问题，它在社交网络分析、疫情控制、网络安全等领域有着广泛的应用。不同于现有的研究采用常规精确算法和启发式算法进行求解，针对现有进化算法存在的问题，引入机器学习增强进化算法性能的研究还比较缺乏。本项目针对关键节点检测这一类复杂NP难问题，以Memetic算法和路径重连等进化算法为基础，致力于引入机器学习构建多种学习型高性能进化算法进行求解。学习型进化算法将以在线学习的方式实现机器学习方法在进化算法的后代解构造、关键参数自适应以及父代解选择上的多角度应用。通过本项目的研究将实现三种识别关键节点的学习型进化算法：①基于频繁模式构建后代解的混合进化算法；②基于学习自动机自适应关键参数的混合进化算法；③基于t-SNE分析结果选择父代解的进化路径重连算法。学习型进化算法的研究不仅为求解关键节点问题提供了一种新的思路，也有效促进了机器学习在进化算法求解中的应用。

关键节点检测问题是一类重要的图和网络优化问题，它在疫情控制、风险评估、碳排放追踪、应急响应、网络安全、社交网络分析等领域有着广泛的应用。本项目针对一类关键节点检测问题，以模因算法等进化算法为基础，致力于提出多种高性能进化算法进行求解。项目经过研究团队的三年努力，已完成了全部研究内容，超额完成了预期研究成果指标。针对不同类型的关键节点检测问题，提出了多个高性能模因搜索算法。本项目具体研究了以下一些关键节点检测问题：1）针对经典的关键节点问题（Critical Node Problem，CNP），提出了一个种群大小自适应的变种群模因搜索算法，该方法能够根据当前的搜索状态，自适应地调节种群大小，相关的研究成果发表在演化计算领域的顶级期刊IEEE TEVC上。2）针对考虑距离的关键节点问题 (Distance-based CNP)，提出了一个基于三个体的模因搜索算法，该方法采用了小种群策略，在整个搜索过程中仅维持一个包含三个个体的小种群，相关研究成果已被运筹优化领域的高水平期刊EJOR正式录用。3) 针对节点加权的关键节点问题 (Node-weighted CNP)，提出了一个延迟接受的迭代局部搜索算法，相关研究成果正式发表在人工智能领域高水平期刊KBS上。4)针对CNP问题的重要变种—k节点割问题，提出了一个快速局部搜索算法，相应的研究成果发表在计算智能领域高水平期刊IEEE TCCS期刊。5）此外还研究了一些相关问题，比如着色旅行商问题、软集群车辆路径优化问题等，相关研究成果发表TS、IEEE TITS等期刊上。项目执行期间，以项目负责人为第一作者或通信作者发表学术论文10篇，其中SCI论文9篇，EI会议论文1篇，依托本项目培养硕士研究生3名。本项目取得的研究成果可为交通、电力、社交等领域的复杂网络分析提供算法支撑，为相关实际应用提供高质量的解决方案。

内容获取失败，请点击重试