具有上限比较的蚂蚁系统算法的运行时分析

蚁群优化(ACO)的运行时分析对于理解算法在计算中的作用至关重要。 本文对蚂蚁系统算法(AS)作为旅行商问题(TSP)的一种ACO进行了运行时分析。 作者通过将最佳算法和信息素矩阵联合表示为离散的随机状态,从而将AS算法建模为吸收马尔可夫链。 AS的运行时间可以通过预期的第一击打时间(FHT)进行评估,这是平均获得全局最优解所需的最少迭代次数。 作者得出了TSP的两种经典AS算法(即蚂蚁数量系统和蚂蚁循环系统)的预期FHT的上限。 他们还以正多边形TSP(RTSP)为案例研究,并通过计算六个RTSP实例获得数值结果。 RTSP是一种特殊但真实的TSP,其中严格施加了三角形不等式的约束。 通过两种AS算法运行时间的比较得出的数值结果验证了我们的理论发现。