The Cellular Ant Algorithm And Its Application Research

This area of research contains many unsolved famous problems that have great challenges, such as those so called NP-hard problems like the traveling salesman problem, degree-constrained minimum spanning tree problem, quadratic assignment problem, graph coloring problem etc. Since these problems have many applications in real situations, it is quite important to find some applicable algorithms. In recent years, there appeared several evolutionary algorithms for solving the NP-hard problems from nature in this field, typically like simulated annealing, genetic algorithm, tabu search, ant algorithm, etc.Ant colony algorithm was first proposed in 1991 and published at international magazine in 1996. Compared with other bionical algorithms for TSP, the ant algorithms have some good properties as a searching optimization approach in some test experiments and solving different discrete systems optimization problems successfully. The concept of cellular automata were first proposed by Von Neumann in simulating system of living with reproducing. Wolfram et al took the method of dynamic system, computational theory and the method of form language for studying the cellular automata. Cellular automata were applied in many fields and have provided effective virtual laboratory in the field of large-scale simulation computing for studying the behavior of systems.This dissertation proposes a new algorithm -- cellular ant algorithm-- for function and discrete systems optimization based on ant algorithm and cellular automata.The dissertation gives convergence analysis for cellular ant algorithm and numerical simulation that show the algorithm is robust and efficient, and extends the application area to the multi-objective optimization.The dissertation provides a new method for systems science, artificial intelligence, optimization theory and complexity science, and provides effective and basic tools and methods for many fields of engineering technology and social economy with wide effects.The contents of the dissertation includes:Chapter 1 gives the background and the contents of the whole dissertation.Chapter 2 generally introduces computational complexity and surveys some main ideas of evolutionary algorithms and their development. Chapter 3 describes the basic principles of ant algorithm and Cellular Automata.Chapter 4 proposes a new optimization algorithm—cellular ant algorithm. Firstly the function optimization, then discusses the discrete systems optimization, like classical TSP, lastly discusses the resolution of some extended TSP. These problems include bottleneck TSP, minimum ratio TSP, time-constrained TSP. Large number of tests and comparisons show the effectiveness of the searching strategy.Chapter 5 gives convergence analysis for cellular ant algorithm of function and discrete systems based on the theory of random fixed point, and makes the relevant theoretical foundation of the convergence property of the algorithm.In Chapter 6, a cellular ant algorithm for solving multi-objective function optimization is presented. The algorithm can be used for solving the multi-objective function and discrete systems optimization. The simulation results show that the algorithm can efficiently reach the true Pareto frontier.In short, the research results of the dissertation theoretically provides a new kind algorithm for NP-hard problems and gives convergence proof of the algorithm. Practically, the dissertation develops a series of strategies for solving different systems optimization problems.