空间连接处理中提炼步骤的遗传优化

摘要

内务处理是用来优化空间连接处理提炼步骤的I/O代价,属于NP-难的问题,现有求解方法复杂度太高.本文将页面聚簇和聚簇调度问题分别归约为图的k划分和最长路径问题,提出了改进的遗传算法和基于最大生成树的近似算法进行求解.对经典遗传算法的进行了修正以满足页面聚簇划分约束.近似算法的解大于最优解的一半.理论分析和仿真实验验证了算法的可行性和有效性.