平衡最小平方和聚类(Balanced Minimum Sum of Squares Clustering,BMSSC)问题简称平衡聚类问题。该问题需要将给定的数据点集合划分到6)个簇中,使每个簇中数据点个数是平衡的,同时最小化所有数据点到其簇中心的欧氏距离平方和。BMSSC属...
详细信息
平衡最小平方和聚类(Balanced Minimum Sum of Squares Clustering,BMSSC)问题简称平衡聚类问题。该问题需要将给定的数据点集合划分到6)个簇中,使每个簇中数据点个数是平衡的,同时最小化所有数据点到其簇中心的欧氏距离平方和。BMSSC属于NP完全问题,有很多应用场景,例如MBA学生分组、照片查询系统等。研究有效求解BMSSC问题的算法,具有重要的理论意义和实际应用价值。
为了求解平衡聚类问题,提出了一种路径重连遗传算法(Genetic Algorithm with Path-Relinking,GA-PR)。该算法主要研究混合种群初始解构造算法、路径重连算法以及基于适应性评估函数的种群管理策略。混合种群初始解构造算法同时使用带有随机性的贪心初始化策略和随机初始化策略两种算法初始化种群,保证了种群初始解的优度和多样性。路径重连算法通过对父代个体进行路径重连生成子代,继承父代优秀特征,提高了子代质量。基于适应性评估函数的种群管理策略在对种群中个体进行替换的时候,通过适应性评估函数来兼顾种群中个体优度和种群多样性,帮助遗传算法找到更好的解。
在学术界广泛使用的16个基准算例集上(共计160个算例),GA-PR与BMSSC问题上的其他算法进行了对比。在算法10次运行的最优结果对比中,GA-PR算法在128个算例上优于BK-Means算法,在108个算例上优于VNS-LIMA算法,在53个算例上优于MA算法。在算法10次运行的平均结果对比中,GA-PR算法在148个算例上优于BK-Means算法,在142个算例上优于VNS-LIMA算法,在84个算例上优于MA算法。GA-PR算法在160个算例上刷新了其中53个算例已知的最优结果,相比于其他算法在同等时间内计算出的解质量更高、稳定性更好。
暂无评论