融合动态层次聚类和邻域区间重组的蚁群算法

Ant colony algorithm based on dynamic hierarchical clustering and neighborhood recombination

针对蚁群算法搜索速度过慢以及解质量不足等问题,提出一种融合动态层次聚类和邻域区间重组的蚁群算法。在初始阶段,调整层次聚类阈值并按照类间距离最小合并的原则迭代至目标簇集,根据预合并系数进行簇间合并,通过蚁群系统得到小类路径并断开重组以加快算法整体收敛速度;接着使用蚁群系统对解空间进行优化,同时并行处理簇集与簇集邻域区间扩散重组,增加解的多样性,进一步固定迭代次数进行比较,若邻域区间重组解质量优于当前优化解则进行推荐处理,提高解的精度;当算法停滞时,引入调整因子降低各路径信息素之间差异以增强蚂蚁搜索能力,有助于算法跳出局部最优。实验结果表明,在面对大规模问题时,算法的精度在3%左右,该方法相比传统方法可以有效提高解的精度和收敛速度。

Aiming at the problem of slow search speed and insufficient solution quality of ant colony algorithm,this paper proposed an ant colony algorithm combining dynamic hierarchical clustering and neighborhood interval reorganization.In the ini-tial stage,the algorithm adjusted the hierarchical clustering threshold and iterated to the target cluster based on the principle of minimum inter-cluster distance merging,and then merged the clusters according to the pre-merging coefficient.In the next place it used ant colony system to generate subclass paths,disconnected and reorganized the initial paths to improve the overall convergence speed of the algorithm.Then the algorithm used ant colony system to optimize the solution space,and at the same time,carried out neighborhood interval diffusion reorganization between clusters to increase the diversity of solutions.Furthermore,if the quality of the reconstructed solution was better than the current optimization solution at a fixed number of iterations,the recommendation process would be carried out to improve the accuracy of the solution.When the algorithm stagnated,it introduced an adjustment factor to reduce the differences between pheromones of each path to enhance the ant search ability,which could help the algorithm jump out of the local optimal.The experiment result shows that the accuracy of the algorithm is about 3%when facing large-scale problems,which can effectively improve the accuracy and convergence rate of the solution.