An adaptive premium penalty ant colony optimization algorithm

This paper proposes an ant colony optimization algorithm of adaptive premium penalty. The proposed algorithm is based on the MAX-MIN Ant System and introduces a new adaptive discriminative premium penalty pheromone renewal strategy. The proposed strategy is based on the fact that a better path has much better sections and a worse path has much worse sections. By comparing the sections of the best and worst ant´s paths, the algorithm carries out discriminative premium penalty pheromone renewal strategy to enhance the pertinence of pheromone release. The better sections will have more pheromone and the worse sections will have less pheromone. The discriminative pheromone release will strengthen the search guide of the region near the optimal solution. It can reduce the search of useless areas, and accelerate the convergence of solutions and their stabilities, so that the solution search efficiency will be enhanced. In order to avoid the defect that the higher penalty error rate and lower reward effectiveness rate at the primary stage may decrease algorithm performance, we take the strategy to update the incentive coefficient adaptively with the evolution process. The traveling salesman problem dataset has been selected to evaluate the effectiveness of the algorithm. The results show that both solution quality and convergence rate obtained by the proposed algorithm are better than that of the MAX-MIN Ant System. The experiments confirm the effectiveness of the proposed algorithm.