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