The Analysis Of Entropy Convergence Of Ant Colony Algorithm And Application

Since 80's of 20th century, some novel heuristics algorithms are created by simulating some natural phenomena or process, such as Ant Colony Algorithm (ACA), Simulated Annealing, Genetic Algorithms and Taboo Search. The particular advantage and mechanism of these algorithms have brought a hot-spot of research, especially the development of ACA in ten years. Because of the simple mechanism, strong lustiness and effective parallelization of ACA, it has attracted more and more researchers and successfully applied to a lot of complicated combinatorial optimization problems.At present the research results of ACA are not concentrated and development of its theory is not matured. In this thesis, the research results of ACA at home and abroad are summarized, the study of entropy convergence of ACA is done, a new improved ant colony algorithm based on the features of entropy convergence is put forward, the procedure code and data structure are detailed. The following part is the main research contents and results of this thesis:(1) The biologic theory of ACA, modeling course and realizing steps are firstly summarized,and then the flow chart of procedure of ACA is presented. (2) The statistical property of ACA is analyzed and studied by experimental methods. The property of entropy convergence of ACA is found by the analysis of experiment, and the equivalent relation between solution convergence of ACA and entropy convergence is resulted. The experimental results show that the ACA with information entropy criterion avoids a lot of surplus computation and reduces running time greatly.(3) In this thesis, an improved ACA based on information entropy is presented to overcome the disadvantages of ACA. First, the idea of improved algorithm, realizing steps and the flow chart of procedure are detailed respectively. The improved algorithm is applied to solve different TSPs and compared with ACO algorithm. The experimental results manifest the superiority and rationality of improved algorithm adequately.(4) In this thesis we provide the description of procedure code of improved algorithm and the data structure in detail, which are convenient for understanding improved algorithm.