计算机应用研究

作者：陶子君,陆芷,蒙炳金,

单位：上海理工大学管理学院,上海200093；

关键词：符号网络划分,启发式,变邻域搜索,强化学习,

基金：国家自然科学基金青年项目(72101149)；上海市浦江人才计划资助项目(22PJC080)；；

给定一个无向图，符号网络划分问题（signed graph partitioning problem，SGPP）是将节点集合划分为K（K≥2）个互不相交的非空分组，旨在最小化所有位于分组内的负符号边权重之和加上位于分组之间的正符号边权重之和，使网络划分结构尽量趋于平衡。SGPP是NP难问题，在计算机视觉、社交网络分析、生物信息学等实际领域中具有重要应用。但大数据时代的到来给求解大规模SGPP带来一定的挑战。因此，设计新颖且高效的学习驱动型扩展变邻域搜索算法（learning driven extended variable neighborhood search，LDEVNS）来求解SGPP。具体来说，该算法设计全新的快速增量更新策略以及高效的扩展变邻域搜索，同时结合强化学习机制来调整算法搜索过程中的前进方向，进一步探索更有希望的解空间区域来找到更高质量的求解方案。实验部分使用15组大规模社交网络图来评估LDEVNS的高性能，实验结果显示，LDEVNS在求解质量和计算时间方面相较于当前表现最佳的算法具有显著优势，同时也验证了强化学习在LDEVNS中的有效性。

来源：2025年第3期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2025年第3期