Applying Local Clustering Method To Improve The Running Speed Of Ant Colony Optimization

Ant Colony Optimization (ACO) is the algorithm that inspiredby the foraging behavior of ant colonies and has be applied to solve many opti-mization problem, especially Traveling Salesman Problem (TSP). ACO attractsthe interest of many researchers since 1991. Its running time is proportional tothe squared number of cities, and the number of cities slows down running speedheavily. And improving its running speed is one of study focuses. To improveits running speed, the method is used in this paper that classifying all citiesinto di?erent classes and letting ACO act on these classes with smaller sizes.The quality of classification impacts the quality of ACO solution heavily. Toguarantee the high quality of solution, an clustering algorithm named speciallocal clustering is presented inthis paper, which generates compact classes. Thesimulation shows that the method presented in this paper can improve ACOrunning speed by 200 factors at least.Chapter 1 contains the introduction of the mode and the program of ACO.and it is the base of research in the follow.Chapter 2 contains the introduction of K-Means Clustering and Local Clus-tering. Clustering is the classification of objects into di?erent classes (or groups),so that the data in each subset (ideally) share some common trait. LC is theimprovement of K-Means Clustering, and its essential idea is that, delete all points in the class which distortion sequence converge firstly from training set.It can cut down the running time of ACO by clustering.Chapter 3 focuses on the improvement of LC. Special LC algorithm (SLC)is presented under the condition of spherical distribution, and SLC-Mixture ispresented under the condition of mixture distribution by improvement of LC.Chapter 4 applies clustering algorithm presented above to improve ACO,and improve the quality of solution and running speed. ACO-SLC is presentedby applying SLC to ACO under the condition of spherical distribution. TheACO-SLC with little-window strategy and cross-edges removing called ACO-SLC-LWCR is presented, in which the method of cross-edges removing proposedin this paper is used to improve the quality of solution and little-window strategyis applied to improve running speed. The low quality of solution will appearpossibly when ACO-SLC is applied to process mixture distribution. To processmixture distribution, the method named ACO-SLC-Mixture is proposed in thischapter.Chapter 5 is the simulation of the algorithms presented above. It showsthat ACO-SLC, ACO-SLC-LWCR and ACO-SLC-Mixture are faster than ACOby factors of 415~-10736, 390~-10192 and 257-9419 respectively. The quality ofthe solutions of ACO-SLC is bad. ACO-SLC-LWCR and ACO-SLC-Mixtureare the improvement of ACO-SLC, and the quality of the solutions of them isbetter than that of ACO-SLC. The error of the solutions of ACO-SLC-Mixtureis less than ACO in most cases, and is bigger than ACO by 2% at most.