求解大规模图划分问题的混合遗传算法

来源：吉林大学学报·理学版杂志2025年第3期北京时间：

作者：曹欢欢, 刘红卫, 路文军

单位：西安电子科技大学 数学与统计学院, 西安 710126

摘要：针对大规模图划分问题中划分方案数量随顶点数指数级增长而导致的计算复杂性, 以及传统遗传算法在处理大规模问题时效率和精度不足的问题, 提出一种混合遗传算法. 首先, 该算法对经过二进制编码的个体进行最佳匹配, 通过识别并筛选出优良基因, 有效缩小搜索范围, 聚焦于更具潜力的搜索区域; 其次, 为避免传统交叉操作可能产生的非法解, 该算法摒弃了随机交叉策略, 仅生成一个潜在解； 最后, 在变异操作中引入禁忌搜索算子, 生成完整的个体, 从而增强算法的局部搜索能力, 实现全局搜索与局部搜索之间的动态平衡. 将该混合遗传算法应用于超大规模集成电路划分问题的实验结果表明, 该算法可有效改进大规模图二划分问题解的质量.

关键词：图划分,遗传算法,最佳匹配,优良基因,禁忌搜索