【作者】 张毅；

【导师】 梁艳春；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2009， 博士

【摘要】 本文对群智能算法中的蚁群算法进行了改进,并将粒子群算法应用于蚁群算法的主要参数选择,取得很好的结果。将改进方法应用于一系列组合优化问题——经典旅行商问题、多点路由问题、生物信息学中的基序发现问题等,实验结果表明改进方法是有效的。本文的主要内容之一是针对基本蚁群算法在处理大规模优化问题上算法执行效率很低的缺点进行的改进,改进的算法以提高算法的执行效率和提高解的质量为目的。首先,针对基本蚁群算法的选路时间过长的问题,引入选路优化策略,减少了算法中蚂蚁的选路次数,显著提高了算法的执行效率。尤其对于以往较难处理的大规模TSP问题,改进算法在执行效率上有明显的优势。其次,改进的算法引入了蚂蚁个体差异,并将不同蚂蚁选路策略混合应用,使改进后的蚁群算法在加快收敛速度和提高解的质量的同时,避免了过早停滞现象。最后,由于蚁群算法是概率算法,解的质量依赖于概率函数的参数选择,传统的人工经验方法设置固定的参数不能使所有问题的解得到优化,所以本文引入粒子群优化算法动态调节函数中的参数。模拟实验结果表明改进算法较之基本蚁群算法在收敛速度和解的质量上都有明显提高。为了验证改进算法的有效性,将改进的方法应用于经典旅行商问题和多点路由问题,实验结果表明,本文的改进方法是有效的。本文针对生物信息学中的蛋白质和基因海量数据的检索和模式识别的问题进行了研究。首先,针对蛋白质的海量数据设计了高效的检索方法和压缩方法。实现了一种既能高效检索海量数据同时又能对其进行一定的压缩的数据结构,通过正规哈夫曼编码对蛋白质数据进行有效压缩和高效索引,取得了很好的结果。其次,利用改进的蚁群算法和传统的吉布斯抽样识别算法相结合进行基序发现识别问题的优化,得到了很好的实验结果。本文的工作主要有以下四个方面:1.设计并实现了一种基于选路优化和个体差异的改进的蚁群算法。该算法较之基本蚁群算法在算法的执行效率和解的质量上都有很大改进,性能上优于基本蚁群算法。2.对蚁群算法的参数进行了优化处理,设计了一种基于蚁群算法和粒子群算法的混合算法。混合算法主要是通过粒子群算法自动调节蚁群算法的主要参数,使参数选择不再完全依赖于人工经验。实验结果表明混合算法是有效的。3.将改进的蚁群算法应用于典型的组合优化问题——经典旅行商问题和多点路由问题。在经典旅行商的多个实例中得到了现有的最优解,而且算法的效率得到了提高。在处理多点路由问题时,在算法的执行效率和解的质量上都得到了很有效的改进。4.将改进的蚁群算法应用于生物信息学中的序列基序发现识别问题。首先,针对生物信息学中的海量数据问题进行了有效的处理。通过基于正规哈夫曼编码对生物序列数据进行有效压缩。其次,在已有的吉布斯抽样识别算法处理基序发现问题的基础上,用改进的蚁群算法对算法进行优化,在不影响解的质量的前提下,有效减少了算法的运行时间,取得了很好的结果。更多还原

【Abstract】 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.更多还原