A normalized minimum cross-entropy pheromone updating rule for ACO algorithm

The pheromone-based parameterized probabilistic model for the ACO algorithm is presented as the construction graph that the combinatorial optimization problem can be mapped on. Based on the construction graph, the solution construction procedure and update rule of pheromone model in the ACO algorithm is illustrated. An iterative update procedure of the probability distribution of the solutions generated by the problem´s probabilistic model is proposed, that will converge to the optimal solutions with probability one, then the minimum cross-entropy pheromone update rule is proposed to approximate the iterative update procedure by minimizing the cross-entropy distance and Monte-Carlo sampling. The normalized pheromone update rule is presented and it can be proved that for the non-constrained matrix construction graph, it is equivalent to the minimum cross-entropy pheromone update rule. Testing experiments show that the normalized update rule is very effective.