Ant Colony Algorithm Based on Price Fluctuation Strategy and Dynamic Backtracking Mechanism

Abstract

In order to solve the problems of traditional ant colony algorithm in traveling salesman problem (TSP), such as easy to fall into local optimum and slow convergence speed, this paper proposes an ant colony algorithm based on price fluctuation strategy and dynamic backtracking mechanism. In the price fluctuation strategy, the complete iteration period of ant colony algorithm is classified according to the idea of time series. According to the balance of price fluctuation, the supply-demand relationship that affects the price fluctuation is matched. By analyzing different demands of the algorithm in different classifications, the pheromone volatilization factor is adaptively and dynamically supplied to accelerate the convergence speed of the algorithm and ensure the diversity of the algorithm solution. When the supply relationship of the price fluctuation strategy can not be balanced, the algorithm will face local optimization problem. In this case, the dynamic backtracking mechanism is introduced to trace the path pheromone to the period of significant similarity difference based on the individual similarity of iterative optimal ant, which can effectively jump out of the local optimum while ensuring the convergence speed. Different test sets in TSP are simulated by MATLAB. The results show that the algorithm can effectively improve the quality of solution and balance the relationship between diversity and convergence speed on the basis of ensuring the convergence speed in medium and large scale city set.

Keywords

• |ant colony algorithm|price fluctuation strategy|dynamic backtracking mechanism|individual similarity|traveling salesman problem (tsp)