0

我正在测试我构建的 ACO，我注意到如果我使用相同的图表，但如果我在计算旅行距离时使用米而不是厘米，我的 AC 存款的信息素量会发生变化。这似乎是错误的，但在阅读了文献后，我不确定我错过了什么。

例如，这里是以米为单位的信息素更新计算：

Tour distance = 5m

extraPheromone = 0.2 = 1 / 5m

然后在 CM 中：

Tour distance = 500cm

extraPheromone = 0.002 = 1 / 500cm

它也适用于放大图表。如果所有距离都加倍，您会期望 ACO 执行相同的操作，但是这又会改变信息素更新计算并影响选择游览边缘时使用的游览边缘距离和信息素计数启发式之间的平衡。

关于如何解决这个问题的任何想法？

4

1 回答 1

1

The pheromone levels are just a relative measure to describe how favourable any single edge is. In ACO, tour selection is not heuristic, but probabilistic.

Consider some ant, during the construction of any tour, say S, where the ant is just about to leave node i. As next node, the ant will choose node j (i.e., edge e_ij) with probability

p(e_ij|S) = (tau_ij^alpha * nu_ij^beta) /
            sum(k in allNotYetVisitedNodes) {
                (tau_ik^alpha * nu_ik^beta) }.

Naturally, this expression is unit-less, and any scaling of (all) node distances will not affect these probabilities. The result of the algorithm does not require any specific length unit in the graph defining the nodes; a graph defined in meters will produce a best tour in meters, and one in arbitrary length units le will produce a result in le:s.

于 2015-12-06T02:14:34.970 回答