Improved Ant Colony Algorithm And Its Application

Ant colony algorithm (Ant Colony Optimization, ACO) is a kind of heuristic algorithm simulates the foraging behavior of real ants collective. As a global searching approach, with the distribution of benefits, positive feedback, robustness, easy combination with other heuristic algorithm, ant colony algorithm, has been widely applied in the traveling salesman problem, data mining and optimization fields. Ant colony algorithm has some defects:the algorithm search time is long, the speed of convergence is slow, stagnation in the operation process of the algorithm is easy to fall into local optimal solution.In view of the defects in ant colony algorithm, the ant colony algorithm, to improve the performance of ant colony algorithm has become a trend a measure of the performance of ant colony algorithm optimization is considered from the two aspects of convergence speed and quality, the improved idea of ant colony algorithm is improved in two aspects of selection strategy and information in the algorithm of path-update rule.Based on the analysis of the shortcomings of the ant colony algorithm, combining the polymorphic ant colony algorithm and adaptive ant colony algorithm, this paper proposes an improved ant colony algorithm. The improved algorithm optimization strategy is mainly in the initialization of pheromone of ant colony algorithm, path selection strategy and the pheromone updating rule and so on, combined with the local search algorithm, the ant colony algorithm to get the solution is optimized to improve the quality of solution. Application of improved TSP algorithm to solve the problem, and ant colony system (ACS) and the max min ant algorithm (MMAS), the experimental results show that the algorithm has a certain optimization in convergence speed and convergence results. Combined with the improved ant colony algorithm, the ant colony clustering algorithm was improved, through the comparison of experiment with the K-means algorithm and ant colony clustering algorithm, show that the improved algorithm improves solution accuracy and convergence speed.The main work and achievements are as follows:(1) The initial pheromone in ant colony algorithm path algorithm for solving the lack, slow shortcomings, through the introduction of a pioneer in polymorphic ant colony algorithm ant thoughts in the initialization of pheromone, the ant search results according to the pioneer of path for the initialization of pheromone, which can improve the pheromone of ant algorithm for path selection in the initial stress to expand the role of randomness, ants, and ants search results according to the herald, the establishment of each city I can search the city set, ant can be selected to improve the efficiency of the algorithm in the choice of the path.(2) Using a random proportion of ant colony algorithm in route selecting cities, this selection strategy to ensure that the stochastic route choice, but the operation of algorithm, path path information has obvious advantages will not necessarily choose, need to a long process to get the optimal solution, leading to the convergence speed of the algorithm is slow.Path by using both deterministic and stochastic phase selection strategy to accelerate the convergence of the algorithm, the introduction of disturbance factor in path selection, represents a random value; (0,1) representation of the set threshold (0.8-0.95). When the ants select the node pheromone and heuristic information product maximum, when the ants select the node according to the random principle of proportion, the path selection to ensure the overall situation of the ants search at the same time, accelerate the convergence speed of the algorithm.(3) The pheromones of the ant colony algorithm update, only the global pheromone update, enhance the optimal path pheromone concentration, so that a better information on the path leading to excessive accumulation, the algorithm into a local optimal solution. Through the use of local pheromone updating, the ants immediately upon completion of the transfer, weaken the path through pheromone, prevent a path pheromone increased rapidly, resulting in the search into a local optimal path; and the global pheromone update in all ants complete path construction, according to the solution of the optimal path the pheromone updating, if the solution is more outstanding, enhance the path of the current solution contains the pheromone on the path, otherwise the solution contains the pheromone on the path to weaken, highlighting the good pheromone advantages to speed up the convergence of the algorithm; pheromone updating rule of pheromone intensity when using Q variable function Q (T), the Q value gradually increased with the operation of the algorithm, improve the convergence speed of the algorithm.(4) In each iteration all the ants complete path construction, use of local optimization search algorithm of 2-opt method for the solution of the optimization to improve the quality of solution.(5) Research on the TSPImproved ant colony algorithm is applied to solve the TSP problem, an experiment with TSP problems oliver30 example, effects of the parameters in the algorithm on the performance of the algorithm, and gives the value range of the ideal; on an instance of TSP with ant colony system (ACS), max min ant algorithm (MMAS) and the improved ant colony algorithm and comparison experiment, experiment results show that the improved algorithm can get the optimal solution is known, and the stability of the convergence speed is improved.(6)Ant colony clustering algorithmApplication of improved ant colony algorithm is the ant colony clustering algorithm, the improved ant colony clustering algorithm; the UCI machine learning data sets using ant colony clustering algorithm, K-means algorithm and the improved ant colony clustering algorithm are tested and compared. The experimental results show that the improved algorithm can improve the convergence quality and convergence speed of the algorithm.