The Application Of Ant Colony Optimization In Solving Several Problems And The Proof Of ACO's Convergence

A population-based simulated evolutionary algorithm called ant colony optimization(ACO for short) was proposed in 1992 by Italian researchers Dorigo M.,Maniezzo V. and Colorni A..Many scholars are attracted to study ACO and in the past ten years the algorithm has been widely applied to the fields of combinatorial optimization network routing, functional optimization, data mining, and path planning of robot etc, and good effects of application are gained.The dissertation focused on the principles, theory, and applications of ACO especially, an in-deep and systemic study on how to improve the basic ACO algorithm, solving Travel sales problem(TSP), nonlinear integer programming, stock index problem and convergence of ACO. The main achievements of this dissertation include:(1) A new ACO algorithm for TSP problem is present. Ants move around the set of integers space, and while walking the ants lays down pheromone on the ground. The pheromone is used to direct the search process. Experimental analyses the carried out on the reasonable selection on the parameters of this algorithm, and basic principles for the parameters selection are provided. Results of the computer programming with MFC shows the effectiveness and generality of the method with different parameters selection. ACO is also compared to genetic algorithm to show its advantage in solving TSP.(2) A ACO algorithm for unconstrained nonlinear integer optimization problem is present. Ants move around the set of integers space,and while walking the ants lays down pheromone on the gournd. The pheromone is used to direct the search process. Experimental analyses are also carried out on the parameters of this algorithm, and deep learning of how to selecting the parameter is present in the way of charts.(3) A new ACO algorithm is used to set up the way of how to solve stock index mode problem and detail steps to programming is also present in this dissertation.(4) A new ACO algorithm is used to set up the way of how to solve power net distribution problem and detail steps to programming is also present in this dissertation.(5) A proof of convergence properties with the theory of absorbing chain is present. The proof sets up an absorbing chain of the use of ACO algorithm and then proves the algorithm can come to absorbing status in limited steps.