I have implemented an Ant System algorithm to solve the TSP which obtains tour results only about 5% longer the optimum tour (acceptable). Now I am trying to implement the similar Max Min Ant System algorithm.
The algorithm I have implements works as follows:
func UpdateMaxMin {
// decay pheromone
graph.decayPheromone()
// get best path from this iteration
bestPath = paths[0]
for path in paths {
bestPath = path.length < bestPath.length ? path : bestPath
}
// update for only the best path (sometimes use the global best)
if random(0, 10) > 8 {
graph.updatePheromone(globalBestPath)
} else {
graph.updatePheromone(bestPath)
}
// clamp pheromone levels between min and max
graph.clampPheromone()
// check for stagnation
if graph.checkStagnation() {
// update max
max = 1 / (rho * globalBestPath.Length)
// reset all pheromones to max
graph.SetPheromoneMatrix(max)
}
}
However, the algorithm stagnates far too quickly (after only a few iterations) and once it has stagnated, the max pheromone becomes a tiny number (smaller than min).
From what I have found online I am using a pheromone decay rate of rho = 0.5 and initialising max to a large number and min to
a := antCount
p := math.Pow(0.05, 1/a)
min = max * (1 - p) / (((a / 2) - 1) * p)
Besides this, the actual amount of pheromone which the best ant deposits on each edge in their tour is calculated by:
deposit = 1 / tour.Length
However, this value is much much much too small to actually create a distinct best path - for example, if the pheromone starts at 5, after the first tour it will decay to 2.5 and the best ant will lay down about 0.001 pheromone on relevant edges. Even if I multiply the deposit by the number of ants a huge number of ants is required to create a significant change.
The results of my MMAS are better than random but much worse than the vanilla AS. The MMAS constructs tours about twice as long as the optimal tour.
Could anyone point out my mistake (or suggest improvements) to my algorithm?
