Font Size: a A A

Some Improved Methods Based On Swarm Intelligence And Their Applications In Some Fields

Posted on:2010-09-03Degree:DoctorType:Dissertation
Country:ChinaCandidate:Y ZhangFull Text:PDF
GTID:1118360272497279Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
In this thesis, we present some novel improvements and results for a computational paradigm called Ant Colony Optimization (ACO). And we also design a hybrid optimization algorithm with Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO) in order to improve the selections of parameters of ACO. Simulation results show that ACO algorithm with our improvement can get a better solution always. And the speed of convergence of ACO algorithm could be enhanced greatly. We use the improved algorithm to deal with some combinatorial optimization problems, include Traveling Salesman Problem(TSP), Multicast Routing Problem(MRP) and Finding Motif Problem(FMP). Simulation experiments show that the improved methods are effective.We begin with the introduction of some related topics, including the Combinatorial Optimization and using the Traveling Salesman Problem as an example. Some famous Heuristic Algorithms for Combinatorial Optimization are described briefly and the method of colony intelligent solving the same problem along with its advantages is also given. Then we introduce the background and the details of Ant Colony Optimization. Among the applications of ACO, we emphasize some existing methods solving TSP problem by ACO. The new improvements and results of ACO are presented, which are the main contributions of the thesis.We put some improvements on ACO through analyzed the performance of it. And we proposed some improvements on ant colony optimization algorithm to solve Traveling Salesman Problem. First, a novel optimized implementing approach is designed to reduce the processing costs involved with routing of ants in the conventional ACO. The results of the simulated experiments show that the improved algorithm not only reduces the number of routing in the ACO but also surpasses existing algorithms in performance for solving large-scale TSP problems. The individual variation is introduced in the ACO, which enables the strategy of ants'route selection to possess variety. Simulations show that the speed of convergence of the improved ACO algorithm can be enhanced greatly. At last the PSO is used to optimize the parameters in the ACO, which makes the selection of parameters do not depend on artificial experiences or trial and error, but rely on the adaptive search of the particles in the PSO. Simulation results show that the speed of convergence of ACO algorithm could be enhanced greatly by our methods. We use the improved algorithm to solving the TSP and MRP in order to prove the validity of it. We also deal the FMP with our improved method. Simulation results show that our improved method is effective.In this thesis, we focus on improving the performance of the ACO and applied to some related fields. The main work and innovations are as follows.1. We do some works in order to improve the performances of the ACO. Two improvements on Ant Colony Optimization (ACO) algorithm are presented in this thesis. A novel optimized implementing approach is designed to reduce the processing costs involved with routing of ants in the conventional ACO. The results of the simulated experiments show that the improved algorithm not only reduces the number of routing in the ACO but also surpasses existing algorithms in performance for solving large-scale TSP problems. The individual variation is introduced in the ACO, which enables the strategy of ants'route selection to possess variety. Simulations show that the speed of convergence of the improved ACO algorithm can be enhanced greatly compared with the traditional ACO.2. In this thesis, we present a hybrid optimization algorithm with particle swarm optimization (PSO) and ant colony optimization (ACO). Unlike the conventional ACO or PSO, the new optimization scheme makes full use of the attributes of both algorithms. In the proposed algorithm, the PSO is used to optimize the parameters in the ACO, which makes the selection of parameters do not depend on artificial experiences or trial and error, but rely on the adaptive search of the particles in the PSO. We also try to find the best assembled of the parameters by a series of experiments. Simulation results show that works had great effects in practicality.3. Three improvements on the Dijkstra algorithm based on ACO are presented in this thesis. The improvements are given as follows:(1)A novel optimized implementing approach is designed to reduce the processing costs involved with routing of ants in the conventional ACO. (2) Based on the model of network routing, the set of candidates is limited to the nearest c points in order to reduce the counting of other points. (3) In order to prevent selecting blocked points we mark the flags on these points. Simulations show that the speed of convergence of the improved algorithm can be enhanced greatly compared with the traditional algorithm.4. We also apply the improve algorithm to solve bioinformatics problems.First, we introduce the canonical Huffman code to wavelet tree of biological sequences. Compared with Huffman code based wavelet tree, the memory space used to represent the shape of wavelet is not needed. In case of large alphabet, this part of memory is not neligible.We present an efficient construction algorithm for this index, which is on-line and linear. And we also applied this structure to Protein sequences. The second, for the finding motif problem of biological sequences, a mixture Gibbs sampling algorithm based on ACO is presented. Based on mixture motifs model learning though ACO, a greedy strategy that adds sequentially new motif to mixture model is employed. Experiments results indicate that the proposed algorithm is advantageous in identifying motifs characteristic of biological families.At last, the contents of the paper are summarized and the future work to do is proposed.
Keywords/Search Tags:Swarming Intelligence, Ant Colony Optimization, Particle Swarm Optimization, Traveling Salesman Problem, Multicast Routing Problem, Finding Motif Problem
PDF Full Text Request
Related items