Font Size: a A A

Research On Ant Colony Optimization And Its Application

Posted on:2008-12-25Degree:DoctorType:Dissertation
Country:ChinaCandidate:Y P LiuFull Text:PDF
GTID:1118360212989546Subject:Control Science and Engineering
Abstract/Summary:PDF Full Text Request
Ant colony optimization (ACO) was introduced by M. Dorigo and colleagues as a novel nature-inspired metaheuristic based on the phenomenon of real ants foraging behavior in the early 1990s. ACO belongs to the class of swarm intelligence, which obtained encouraging results for the solving of NP-hard combinatorial optimization problems. Now, ACO has become an independent branch of intelligent computation and has been discussed as a special session in many international conferences. More and more researchers have paid attention to ACO.In recent 15 years, ACO has developed quickly and its application fields extend much wider from traveling salesman problem (TSP) to scheduling problems, assignment problems, and vehicle routing problems, etc.. In contrast, the research on ACO theory develops slowly, especially in the aspect of parameters setting and the proof of convergence. The scheme of network routing based on ACO has been paid much attention due to the similarities between network routing problems and ACO in many characteristics, such as information distribution, dynamic and asynchronous characteristics. Recently, the hybrid of ACO and other intelligent computation algorithms attracts much attention of researchers.The dissertation focuses on the research of the above-mentioned problems. The main achievements and contents include the follows.1. Parameters setting for a class of simplified ACO are studied based on the full-connection graph G mapped from the combinatorial optimization minimum problems. For the parameters setting, the follows are discussed. The pheromone increment Δτ = g(s) is proved as a value between the maximum pseudo feasible solution smax and the minimum one smin, i.e.g(smax)≤Δτ≤g(smin), which provides a sound theoretic basis for the determination of the initial values of the pheromone. The range of the pheromone evaporation coefficient is shrunken from ρ(?) (0, 1)to (?) where emin and emax are the maximum and minimum weights of the construction graph G. The number of maximum iteration is discussed, too.2. For the convergence, the follows are investigated. First, the probability that the algorithm finds the global best solution can be closed to 1 with arbitrary precision for sufficiently large product of the number of ants and the number ofiteration, i.e. m ·t→ +∞. Secondly, the up bound of m·t for the algorithm to find the global optimum is investigated. Thirdly, the time that the best solution will be outstanding is discussed due to the pheromone updating in the case that ACO has found one of the best solutions. Finally, the low probability bound that ants construct the best found solution is proved as the probability for the random search method to construct an arbitrary solution in the case that ACO has found the best one.3. A novel ACO-Unified Framework (ACO-UF) is proposed. The unification technique is adopted in ACO-UF, which help ACO easily overcome the backward that standard ACO suffers in solving isomorphic problems. ACO-UF also benefits the initialization of pheromone. MMAS (Max-Min ant system) is implemented under ACO-UF, and the parameter settings are experimented and investigated based on TSP.4. A novel distributed multicast routing algorithm based on ACO (DMRACO) with quality of service (QoS) is proposed. The algorithm tries to construct the minimum-cost tree that satisfies with the delay bound by taking advantage of the local information in the case that the source node does not possess the whole network information. Combining the characteristic of multicast routing, the algorithm was improved. The factors that impact the performance of DMRACO, such as network size, multicast size and delay bound, are studied based on the simulation experiments. Simulation results show that DMRACO can obtain acceptable results compared with BSMA and KMB, which are two kinds of centralized network routing algorithm with good performance.5. A new neural network (NN) training algorithm, ACO-BP algorithm, is proposed. ACO-BP scheme adopts ACO to search the optimal combinations of weights in the solution space, then uses BP algorithm to obtain the accurate optimal solutions quickly. The ACO-BPNN, BPNN, ACONN and GANN were applied to the problems of function approaching. Experiment results show that the proposed ACO-BP scheme can obtain the best performance among the above-mentioned algorithms. ACO-BP neural network is adopted to model coal ash fusion temperature based on its chemical compositions. Data of 80 typical coal ash samples were gathered and used for training and testing. Experiment results show that the ACO-BP model can obtain better predictive results than experiential formula and BP model.
Keywords/Search Tags:ant colony optimization (ACO), combinatorial optimization, convergence, parameter setting, ACO-Unified Framework, network routing, multicast routing, BP algorithm, ACO-BP neural network, coal ash fusion temperature
PDF Full Text Request
Related items