Pheromone mark ant colony optimization with a hybrid node-based pheromone update strategy

An improved ant colony optimization (ACO) algorithm called pheromone mark ACO abbreviated PM-ACO is proposed for the non-ergodic optimal problems. PM-ACO associates the pheromone to nodes, and has a pheromone trace of scatter points which are referred to as pheromone marks. PM-ACO has a node-based pheromone update strategy, which includes two other rules except a best-so-far tour rule. One is called r-best-node update rule which updates the pheromones of the best-ranked nodes, which are selected by counting the nodes' passed ants in each iteration. The other one is called relevant-node depositing rule which updates the pheromones of the k-nearest-neighbor (KNN) nodes of a best-ranked node. Experimental results show that PM-ACO has a pheromone integration effect of some neighbor arcs on their central node, and it can result in instability. The improved PM-ACO has a good performance when applied in the shortest path problem.