赋权超图划分问题的多水平迁移优化算法研究

摘要 伴随着赋权超图划分问题的规模不断地增长，对赋权超图划分的处理效率和能力、准确性有了更高程度的要求.本文采用形式化符号描述了赋权超图优化划分问题，阐明了基于多水平思想求解该问题的粗化、初始划分和迁移优化三个阶段；提出了基于离散粒子群和多水平思想的迁移优化算法，在|V|维空间中每个粒子所处的位置对应于超图划分方案；伴随着投影优化阶段的细化，每个粒子对应的划分方案映射到下一水平层的粗化超图；随着划分问题解空间的维度|V|增加，粒子的自由度增大；将结点迁移的收益值作为粒子的启发式搜索信息，利用粒子之间聚集协同表现出的智能行为有效地搜索解空间；给出了赋权超图的改进压缩存储格式，提出了割切值和收益值的快速计算方法，有效降低了划分算法的时空复杂度.基于ISPD98测试基准的对比实验数据表明：与基于迁移方法的赋权图、赋权超图优化划分算法相比，本文算法有效地增强了迁移优化算法逃离局部最优的能力