Applying Vertex Coloring To Improve Ant Colony Algorithm

Ant Colony Optimization (ACO) is a new bionic optimization algorithm, which simulates ants to find food。The algorithm uses a positive feedback from the catalytic mechanism and has strong robustness, good distributed computer system and eases integration with other methods, etc. ACO has already demonstrated their excellent performance and great development potential in solving many complex optimization problems, particularly for traveling salesman problem (TSP).In the TSP problems, the running time of ACO is proportional to the two times of the number of cities. For a large scale TSP problem, it will cost a long running time. In order to speed up the running time, the Thesis presents a new clustering method– Vertex Coloring Cluster (VCC) which divides the cities into several categories and lets the ACO act on each class (ACO_VCC). This is equivalent to lower the number of cities and accelerate the running speed. Meanwhile, based on the ACO_VCC, the strategy of little window and the cross removal are also introduced into the Thesis (ACO_VCC_LWCR) to speed up the running time and optimize the running results.In this thesis, the results of ACO are summarized from domestic to foreign and the basic ACO is described in detail. In addition, this thesis proposes a new improved algorithm which introduces Vertex Coloring Cluster (VCC) method into the ACO. And the steps and data structure of the algorithm are detailed. The main research results of this thesis are below:(1)Describes the origin idea of the ACO, the bionic principle of ACO, the abstract modeling of the ACO. Summarizes the concrete steps and gives a flow chart of the ACO.(2)Describes K-Means clustering algorithm model , implementation steps and the program structure, as well as introduces K-Means clustering method into the ACO and elaborates its characteristics .(3)For the shortcomings of the ACO, this thesis presents a new clustering method– Vertex Coloring Cluster (VCC), and applies VCC into the ACO ( ACO_VCC) to improve the ACO, while based on the ACO_VCC , the strategy of little window and the cross removal are also introduced into ACO_VCC (ACO_VCC_LWCR) to further improve ACO.(4)The results of the simulation fully demonstrate the superior rationality of the improved algorithm.