CODEWITHSUNDEEP
artificial-intelligencemathematical-optimizationant-colony
user11406
user11406

Reputation: 1258

Should the amount of pheromone deposited on edges depend on the distance between the nodes in ACO?

I was testing an ACO I built and I noticed that if I used the same graph but if I used meters instead of centimeters when calculating tour distance the amount of pheromone my AC deposits changes. This seems wrong, but after reading the literature I'm not sure what I'm missing.

For example, here is the pheromone update calculation in meters:

Tour distance = 5m

extraPheromone = 0.2 = 1 / 5m

Then in CM:

Tour distance = 500cm

extraPheromone = 0.002 = 1 / 500cm

It also applies when scaling the graph up. If all distances were doubled you would expect the ACO to perform the same, however again this would change the pheromone update calculation and affect the balance between the tour edge distance and pheromone count heuristic used when selecting a tour edge.

Any thoughts on how to solve this?

Upvotes: 0

Views: 85

Answers (1)

dfrib
dfrib

Reputation: 73186

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.

Upvotes: 1

Related Questions