| A wonderful self-organization behavior will usually be produced from the collective behavior of social animals. Take a colony of ants for example, blind ants can find the shortest routing path from their nest to food source. Biologists had studied the phenomenon carefully and found that ants cooperate to find the shortest routing path by means of indirect communications using a kind of substance call "pheromone". Inspired from this, a population-based simulated evolutionary algorithm called ant colony optimization (ACO for short) was proposed by Italian researchers M. Dorigo, V. Maniezzo and A. Colorni. 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 focuses on the principles, theory, and applications of ACO, especially, an in-deep and systemic study on how to improve the basic ACO algorithm, parallel implementation of ACO, solving the problems such as combinatorial optimization problem and path planning of robot, The main achievements of this dissertation include:1. An adaptive ant colony algorithm (AACA) was proposed. In AACA, the transition probability with which ant used to select next city is dynamically adjusted based on the number of Average Node Branching (ANB) to balance the "exploration" and "exploitation" of the searching process. In this way, not only the ability of searching better solution is kept, but also the stagnation behavior of the algorithm is avoided. Simulated experiments show that stagnation behavior of basic ACO algorithm are avoided in AACA algorithm and a good ability of searching better solution in the last runs of AACA algorithm.2. A hybrid behavior based ant colony algorithm (HBACA) is proposed. The influences of ant' behavior on performance of ACO algorithms are analyzed, the definition of ant' behavior is given, and a model of the algorithm is designed. Four kinds of concrete ant's behaviors are designed base on the definition of ant's behavior. By tuning the proportion of ant with different behaviors, not only the high capability of searching good solution is kept but also the stagnation behavior is avoided. The parameters setting of the algorithm are discussed first and a comparison of HBACA algorithm and AS algorithm is performed. The experimental results show that the algorithm is better than AS algorithm.3. A parallel implementation of ACO is presented. Taking advantage of clustering feature in TSP problem, the problem is divided into several sub-problems in data domain by clustering processing. And then all the sub-problems will be solved in parallel by ant algorithm respectively. At last all the solutions of each sub-problem will be merged into the solution of the problem to be solved by some rules. Simulated experiment on TSP problems with clustering feature has shown that the algorithm can converge to the (near) best solution of the problem with great rate. It also shows that the more the number of clustering of TSP problem, the more higher performance of the algorithm is, but when the clustering feature of TSP is not distinct, the algorithm will become general ACO algorithm.4. An ant colony algorithm to tackle k-person traveling salesman problem (K-TSP) is proposed (ACA-KTSP). In the algorithm all the ants are divided averagely into m groups, in which there are k ants. In each group, k ants are imposed to construct a feasible solution of the problem, and in the algorithm, m group of ants cooperate to search the best solution of the problem. The experimental results show that the algorithm is effective for K-TSP problem.5. An ACO algorithm to solve 0-1 knapsack problem (KP) is presented (ACA-KP). The construction graph for KP problem is designed. Based on the construction graph, two state transition formulas are designed and a priority of the formulas is defined, ants move on the construction graph node...
|
PDF Full Text Request