Research And Application On Ant Colony Clustering Based On Reinforcement Learning

Ant colony algorithm is a typical example which uses swarm intelligence to solve practical problems, it was first proposed by the Italian scholar Dorigo 90 years in the 20th century. As the global optimization and random searching method, it has many advantages such as simplicity, robustness, distribution and parallel. Since it was proposed, it has been applied to TSP problems, Quadratic assignment problems, machine learning and other aspects. Despite all this, there are many problems should be perfect urgently in theory and application methods, such as easy to fall into stagnation and slow convergence.Some improved methods are proposed to avoid falling into stagnation and low speed of convergence, and the main research results are concluded as follows:i. Proposing a mechanism of dynamic evaporation rate to balance the contradict between solution efficiency and solution quality. Setting evaporation rate for a big value at the beginning, thus the colony will do as much as possible of the search, increasing the possibility of finding the optimum solution; while at the end of the algorithm, setting small value for evaporation rate, for the algorithm should not be in too much to explore, but to speed up the convergence around the possible optimal solutions. The experiments show that the algorithm can quickly converge to the optimal solution; that is it will not only increase the global search capability, but also to a certain extent, accelerate the speed of convergence.ii. Introducing the thought of reinforcement mechanism from reinforcement learning. Reinforcement learning thought is introducd into the updating mechanism of pheromone of ant colony algorithm, when updating pheromone after each iteration, reward the best current path with an additional random amount of reward, and also punish the worst path with giving a random amount of punishment. iii. Redefining the heuristic information to guide the algorithm converge fast. Adjusting the definition of heuristic information to make more efficient use of heuristic information to speed up the convergence in the algorithm later. The heuristic information would not be constant, but continuously been adjusted with the iterative process moving forward, ensuring the algorithm converges to the optimal solution quickly.iv. Introducing the boundary symmetric mutation strategy to get variation of Iteration results symmetrically. Paths are almost complex overlapping in "the center" area, so the difference of the tour path is more determined by "boundary" paths. When applying the variation strategy, we mainly aimed at "boundary"paths, such as mutation can improve the efficiency of mutation, also can obtain better quality solutions.