Ant Colony Algorithm With Surplus Assignment Strategy

Ant System (AS) and Max-Min Ant System (MMAS) are two Algorithm models of Ant Colony Algorithm. Both of them include pheromone quantity update rule. AS Algorithm often uses Ant-Cycle model to update pheromone quantitiy, and MMAS Algorithm uses the way of restricting maximum and minimum of pheromone quantity to update it. In practical problems, they are used widely.AS'and MMAS'update rule are united in this paper. Because Ant-Cycle model uses "equal principle" to update pheromone quantity, that is, each arc of one fixed tour, no matter it is good or bad, is supplied equal amount pheromone quantity, and Max-Min Ant System uses the standard of "one sword cuts" to update pheromone quantity, that is, each arc's pheromone quantity that is belowτmin or overτmax, no matter it is good or bad, is ordered asτmin orτmax. In the update process, both of the two Algorithms don't show each arc's character when the pheromone quantity are supplied. Because of this, we bring forward a new strategy—Surplus Assignment Strategy, then based on this new strategy we bring forward a new algorithm—Ant Colony Algorithm with Surplus Assignment Strategy. In the update process of the new Algorithm:firstly, "equal principle" is improved as "proportional principle"; secondly, the standard of "one sword cuts" is improved as "surplus assignment" strategy. After using the new principle update pheromone quantity, each superior arc's pheromone quantity is decreased, and each inferior arc's pheromone quantity is supplied. And meanwhile, their own character can be also showed after the pheromone quantity is supplied.We prove the new Algorithm is convergent in probability in this paper. That is, it assures the feasibility of the new Algorithm.Comparing with "the laboratory of the Ant Colony Algorithm" and the current public best result, the result which we gain is better than the former and close to the later in simulation experiment. So, it assures the effectiveness of the new Algorithm.