下载文档原格式
基于智能算法的DNA序列比对研究【摘要】计算机分子生物学是一门交叉学科,以计算机、网络为工具,采用数学、信息科学、生物学的理论、方法和技术来研究生物大分子。
生物信息学的目的是揭示遗传和功能信息的根本规律,以及基因组信息结构的复杂性,进一步解释生物的遗传语言。
序列比对是生物信息学中基本的信息处理方法之一,可以发现生物序列之间的进化、功能和结构信息,为生物信息学提供理论基础。
序列比对分析最初是由生物同源性的研究提出的,后随着技术发展,其应用范围越来越广。
本文重点介绍了分子生物学的背景知识、DNA序列比对的基本原理、人工鱼群算法与蚁群算法的基本思想。
首先介绍了序列比对涉及的基本问题:基本操作、相关定义、空位罚分和替换矩阵,然后介绍了双序列比对算法:NW算法、Smith-Waterman算法与BLAST算法,针对多序列比对,介绍了基本算法有:渐进比对算法和迭代比对算法。
最后将人工鱼群算法应用在DNA双序列比对中,通过实验证明了算法的可行性。
同时对经典蚁群算法进行改进,并将改进的智能蚁群算法应用在双序列比对中,通过实验证明算法的速度和准确率都有了明显的提高。
本文第四章中,通过对人工鱼群算法的基本思想、运算流程及应用等方面的研究,将其应... 更多还原【Abstract】 Computational Molecular Biology is aninterdisciplinary which uses computers, Internet, Mathematics, Informatics and Biology as tools to deal with research onbiomacromolecule. The purpose of Computational Molecular Biology is to reveal basic rules for genetic information, functional information and the complexity of genome structure. Sequence alignment is a basic information processing approach in Computational Molecular Biology. Sequence alignment can find genentic information, functional info... 更多还原【关键词】双序列比对；人工鱼群算法；蚁群算法；【Key words】DNA pair-wise sequence alignment；Artificial Fish-swarm Algorithm；Ant Colony Algorithm；【索购全文】Q联系Q：138113721 Q联系Q: 139938848付费即发摘要6-7Abstract 7-8第一章绪论9-151.1 研究背景和意义9-101.1.1 研究背景9-101.1.2 序列比对意义101.2 国内外研究现状10-121.2.1 双序列比对10-111.2.2 多序列比对11-121.3 本文主要研究内容12-131.3.1 序列比对算法121.3.2 基于人工鱼群算法的DNA 双序列比对121.3.3 基于改进蚁群算法的DNA 双序列比对12-131.4 本文创新点131.5 本文组织结构13-15第二章DNA 序列比对15-252.1 生物信息学背景知识15-172.1.1 蛋白质与核酸15-162.1.2 中心法则16-172.2 DNA 序列比对的数学描述17-202.2.1 DNA 双序列比对的数学描述17-182.2.2 DNA 多序列比对的数学描述18-202.3 序列比对基本原理20-252.3.1 基本操作202.3.2 相关定义20-212.3.3 空位罚分21-222.3.4 替换矩阵22-25第三章序列比对算法研究25-323.1 双序列比对算法25-293.1.1 NW 算法25-263.1.2 Smith-Waterman 算法26-283.1.3 BLAST 算法28-293.2 多序列比对算法29-323.2.1 渐进比对算法29-313.2.2 迭代比对算法31-32第四章基于人工鱼群算法的DNA 双序列比对32-444.1 人工鱼群算法32-374.1.1 人工鱼群算法的基本思想32-334.1.2 人工鱼群算法的定义33-344.1.3 人工鱼群算法的描述34-364.1.4 人工鱼群算法的研究现状36-374.2 人工鱼群算法在DNA 双序列中的应用37-424.2.1 算法思想37-404.2.2 算法描述40-414.2.3 算法流程41-424.3 算法实现与实验结果分析42-434.3.1 参数设置424.3.2 实验结果与分析42-434.4 本章小结43-44第五章基于改进蚁群算法的DNA 双序列比对44-565.1 蚁群算法的原理与应用44-475.1.1 蚁群算法的基本原理445.1.2 蚁群算法的发展44-455.1.3 蚁群算法的计算模型45-465.1.4 蚁群算法的应用46-475.2 蚁群算法在DNA 双序列比对的应用47-505.2.1 蚁群算法求解DNA 双序列比对的模型47-485.2.2 蚁群算法求解DNA 序列比对的算法流程48-505.3 改进蚁群算法在DNA 双序列比对中的应用50-525.3.1 算法改进策略50-515.3.2 算法描述51-525.4 算法实现与实验结果分析52-555.4.1 参数设置525.4.2 实验结果与分析52-555.5 本章小结55-56第六章总结与展望56-586.1 研究总结566.2 研究展望56-58参考文献。
－5009－0引言俗话说“物以类聚，人以群分”，人们在不知不觉中进行着聚类活动，它是人们认识和探索事物之间内在联系的有效手段。
聚类在数据挖掘中有着重要的地位，它既可以用作独立的数据挖掘工具，来发现数据库中数据分布的一些深入信息，也可以作为其它数据挖掘算法的预处理步骤。
因此，聚类算法的研究具有很重要的现实意义。
蚁群算法不依赖于具体问题，具有全局优化能力，因此受到了广大学者的注意。
此后蚁群算法不断被改进并应用于不同领域。
在聚类分析方面，Deneubourg等人受蚂蚁堆积尸体和分类它们的幼体启发，最早将蚁群算法用于聚类分析，从此开始了蚁群聚类算法的研究。
本文详细地讨论了现有的蚁群聚类算法的基本原理与性能，在归纳总结的基础上提出需要完善的地方，以推动蚁群聚类算法的进一步研究及在更广阔的领域内得到应用。
1聚类概念及数学模型聚类就是把一组个体按照相似性归为若干类或簇，使得属于同一类或簇的个体之间的差别尽可能的小，而不同类或簇的个体间的差别尽可能大。
聚类质量是用对象的相异度来评估，而不同类型变量的相异度的计算方法是不同的，常用的度量方法是区间标度变量中的欧几里得距离。
聚类的数学描述：设样本集={,=1,2,…,}，其中为维模式向量，其聚类问题就是找到一个划分={1,2,…,}，满足==1，≠，=，,=1,2,…,，≠，且使得总的类内离散度和==1,最小，其中为的聚类中心，=1,2,…,；,为样本到其聚类中心的距离，即,=‖‖。
聚类目标函数为各样本到对应聚类中心的距离总和，聚类中心=1，||为的样本数目。
2蚁群聚类算法分类及应用由于现实的蚁群运动过程接近于实际的聚类问题，所以近年来涌现出大量的蚁群聚类算法。
这些算法不仅思想、原理不同，而且算法的特性也根据解决问题的不同而不同，如初始参数及待聚类数据的要求、聚类形状等。
根据改进方式的不同，蚁群聚类算法可分3类：①基于蚂收稿日期：2007-10-17 E-mail：05lihua@作者简介：裴振奎(1962－)，男，山东东营人，博士研究生，副教授，硕士生导师，研究方向为机器学习与计算智能；李华(1977－)，女，山东滨州人，硕士研究生，研究方向为数据挖掘、自然计算；宋建伟(1982－)，女，河北廊坊人，硕士研究生，研究方向为网络安全、计算智能；韩锦峰(1981－)，女，山西大同人，硕士研究生，研究方向为计算智能、数据库系统理论。
蚁群算法应用场景
一、蚁群算法的概念
蚁群算法是一种仿生优化算法，以蚂蚁的行为模式为模型，通过模拟蚂蚁搜索食物的行为，在最短的时间内找到最优解的算法。
该算法在搜索路径到达最优解的过程中，可以充分利用食物的信息，以帮助蚂蚁到达最优解。
二、蚁群算法的应用场景
1、多目标优化问题
多目标优化问题是指在满足多个目标的情况下，求出最优解的问题，又称为复合优化问题。
蚁群算法在多目标优化中能够有效地解决这类问题，能够找到具有较高的效率的最优解。
2、网络路径优化
网络路径优化是为了求解两点之间最优路径，在满足网络要求的同时使得传输花费最小，以达到快捷通讯的目的。
蚁群算法可以在网络路径规划时帮助求解最优解，使整个网络路径规划的效率更高。
3、图像处理
图像处理是指对图像进行处理，以达到优化图像的操作，而蚁群算法能够有效地解决图像处理问题。
它可以自动地搜索图像，找出可以优化的特征，并优化图像，以提高图像质量。
4、规划与排序
规划与排序是指将一定的任务进行组合并排序，以达到最大的效率。
蚁群算法在规划与排序中可以有效地搜索任务，找出具有最优解
的排序组合，以提高效率。
5、求解调度问题
调度问题是指在满足约束情况下，求解满足最优的调度任务的问题。
蚁群算法在解决调度问题时可以有效地搜索调度任务，找出最优的调度组合，以达到最佳效果。
《蚁群算法的研究及其在路径寻优中的应用》篇一蚁群算法研究及其在路径寻优中的应用一、引言随着科技的快速发展和人们对算法的不断研究，许多高效的优化算法逐渐浮出水面。
其中，蚁群算法作为一种启发式搜索算法，在路径寻优问题中展现出强大的能力。
本文将首先对蚁群算法进行详细的研究，然后探讨其在路径寻优中的应用。
二、蚁群算法的研究1. 蚁群算法的起源与原理蚁群算法是一种模拟自然界蚂蚁觅食行为的优化算法。
它通过模拟蚂蚁在寻找食物过程中释放信息素并跟随信息素移动的行为，来寻找最优路径。
该算法的核心思想是利用正反馈机制和群体智能，通过个体间的信息交流和协同工作来找到最优解。
2. 蚁群算法的特点蚁群算法具有以下特点：一是具有较强的鲁棒性，对问题的模型要求不高；二是易于与其他优化算法结合，提高求解效率；三是具有分布式计算的特点，可以处理大规模的优化问题。
三、蚁群算法在路径寻优中的应用1. 路径寻优问题的描述路径寻优问题是一种典型的组合优化问题，如物流配送、旅行商问题等。
在这些问题中，需要找到一条或多条从起点到终点的最优路径，使得总距离最短或总成本最低。
2. 蚁群算法在路径寻优中的应用原理蚁群算法在路径寻优中的应用原理是通过模拟蚂蚁的觅食行为，将问题转化为在图论中的路径搜索问题。
蚂蚁在搜索过程中会释放信息素，信息素会随着时间逐渐挥发或扩散。
蚂蚁根据信息素的浓度选择路径，同时也会释放新的信息素。
通过这种正反馈机制，蚁群算法能够在搜索过程中找到最优路径。
3. 蚁群算法在路径寻优中的优势蚁群算法在路径寻优中具有以下优势：一是能够处理大规模的路径寻优问题；二是具有较强的全局搜索能力，能够找到全局最优解；三是具有较好的鲁棒性和稳定性，对问题的模型要求不高。
四、实验与分析为了验证蚁群算法在路径寻优中的效果，我们进行了多组实验。
实验结果表明，蚁群算法在处理不同规模的路径寻优问题时，均能取得较好的效果。
同时，通过对算法参数的调整，可以进一步提高算法的求解效率和精度。
蚁群算法原理及应用蚁群算法是一种仿生学算法，源于观察蚂蚁在寻找食物时的行为。
蚂蚁会释放一种叫做信息素的化学物质，他们通过感知周围环境中信息素的浓度来确定前进的方向，从而找到最短路径。
这种行为激发了人们的兴趣，并产生了一种算法，叫做蚁群算法。
蚁群算法是一种基于人工智能和模拟生物学行为的算法，其模型模拟了蚂蚁群的生物行为。
这个算法利用了如下两个原则：正反馈原则和负反馈原则。
正反馈原则表示，当一只蚂蚁找到一个食物源时，它会释放更多的信息素。
这就会吸引更多的蚂蚁来到这个地方。
这样就会形成一个正反馈环路，吸引更多的蚂蚁前来寻找食物源。
负反馈原则则是取决于路径的长度。
当一只蚂蚁走过一个路径时，它会释放少量的信息素。
这对于后来的蚂蚁没有吸引力，因为它们寻找的是最短路径。
因此，这个算法会抑制过度访问较长的路径。
蚁群算法的应用是多种多样的。
它最初被用于解决数字优化问题，如让搜索引擎更加快速地搜索结果。
蚁群算法还被用于处理路径优化问题，如在工业生产中优化物流方式、优化进程流程等等。
它也可以被用于解决网络优化问题，如希望让多个节点之间的通信更加协调顺畅。
此外，蚁群算法也可以在机器学习领域中用于无监督聚类。
蚁群算法的这个特性能够自动聚类数据，而不是强制类别。
蚁群算法的优点是可以在没有先验知识的情况下，通过不断自我修正来确定最优解。
其他优点包括执行优化和决策，具备分布式处理和并行特性，算法简单，无需专业知识和特殊设备，便于应用和推广。
然而，它的缺点也是显而易见的。
它可能容易受到局部最优解的影响。
当蟻群搜索路径被卡住在局部最优解上时，很难跳出这个局部最优值陷阱。
因此，对算法参数的准确调节和合理设置具有至关重要的意义。
总之，蚁群算法是一种非常有效的算法，可以广泛应用于各种不同的领域。
它的潜力非常巨大，因此它也成为了很多优化和决策问题中的首选工具。
虽然它还存在一些不足，但蚁群算法的复杂度和效率适用于许多实际应用问题。
蚁群算法改进及应用研究摘要：蚁群算法是一种启发式优化算法，其物理现象的模拟和仿生方法使其在多个领域得到广泛应用。
本文将介绍蚁群算法的基本原理，并对其改进方法进行探讨。
在应用方面，将重点讨论蚁群算法在路线规划、图像处理、机器学习和网络优化等领域的应用。
通过对蚁群算法的研究和改进，将有助于提高算法的性能和适应性。
1. 引言蚁群算法是一种基于觅食行为的模拟算法，最早由意大利科学家Marco Dorigo等人于1992年提出。
蚁群算法的基本原理来自于觅食过程中蚂蚁的行为，通过模拟蚂蚁的觅食路径选择和信息素沉积行为，实现对问题的优化求解。
2. 蚁群算法的基本原理蚁群算法的基本原理是通过蚂蚁之间的正反馈作用进行信息传递和问题求解。
蚂蚁在觅食过程中会留下一种称为信息素的物质，用于标记路径的好坏。
蚂蚁选择路径时，会倾向于选择信息素浓度高的路径，从而形成一种积累性的正反馈循环。
在这个过程中，较短路径上的信息素浓度会逐渐增加，吸引更多的蚂蚁选择该路径，集中力量探索更优解。
3. 蚁群算法的改进方法为了提高蚁群算法的搜索效率和求解能力，研究者们提出了多种改进方法。
其中，一些方法采用了参数调整和策略改进的方式，如引入启发式信息和适应性参数。
另一些方法则通过改变信息素更新策略和蚂蚁的移动方式来改进算法性能。
例如，引入局部更新策略和全局更新策略，以增加算法的全局搜索能力和局部搜索能力。
4. 蚁群算法在路线规划中的应用蚁群算法在路线规划中具有很好的应用潜力。
通过模拟蚂蚁在寻找食物过程中的路径选择行为，可以有效地解决旅行推销员问题等路线规划问题。
在实际应用中，蚁群算法已经被用于城市交通规划、船舶调度和智能导航系统等领域，取得了良好的效果。
5. 蚁群算法在图像处理中的应用蚁群算法在图像处理中也有不少应用。
例如，通过模拟蚂蚁的觅食路径选择行为，可以实现图像分割、边缘检测和图像增强等任务。
此外，蚁群算法还可以用于图像压缩、图像重建和图像分类等方面。
《蚁群算法的研究及其在路径寻优中的应用》篇一蚁群算法研究及其在路径寻优中的应用一、引言蚁群算法（Ant Colony Optimization，ACO）是一种仿生算法，借鉴了蚁群寻找食物过程中的寻路行为和寻优特性。
由于其高效且自适应的优点，蚁群算法已被广泛应用于解决复杂的路径寻优问题。
本文将研究蚁群算法的基本原理，分析其特性和优缺点，并详细阐述其在路径寻优中的应用。
二、蚁群算法的基本原理蚁群算法是一种模拟自然界中蚁群觅食行为的优化算法。
在自然界中，蚂蚁通过信息素（pheromone）的传递来寻找食物源，并找到最优的路径。
蚁群算法借鉴了这一特性，通过模拟蚂蚁的寻路过程，寻找最优解。
蚁群算法的核心思想是正反馈原理和群体行为。
在算法中，每只蚂蚁在寻找路径的过程中会释放信息素，并按照信息素的浓度来选择下一步的路径。
随着时间的推移，较短的路径上信息素的浓度会逐渐增大，形成正反馈机制。
蚂蚁通过群体的协同作用和互相影响来找到最优的路径。
三、蚁群算法的特性及优缺点1. 特性：（1）分布式：蚁群算法通过大量蚂蚁的协同工作来寻找最优解，具有较好的分布式特性。
（2）正反馈：算法中存在正反馈机制，能够自动放大较优解的信息素浓度。
（3）并行性：蚂蚁在寻找路径的过程中可以并行工作，提高了算法的效率。
（4）鲁棒性强：蚁群算法对初始解的依赖性较小，具有较强的鲁棒性。
2. 优点：（1）适用于解决复杂的路径寻优问题。
（2）能够找到全局最优解或近似最优解。
（3）具有良好的鲁棒性和稳定性。
3. 缺点：（1）计算量大：由于需要模拟大量蚂蚁的寻路过程，计算量较大。
（2）易陷入局部最优：在特定情况下，算法可能陷入局部最优解而无法找到全局最优解。
四、蚁群算法在路径寻优中的应用蚁群算法在路径寻优问题中具有广泛的应用，如物流配送、网络路由、城市交通等。
下面以物流配送为例，介绍蚁群算法在路径寻优中的应用。
在物流配送中，需要确定配送车辆的行驶路线，以最小化总行驶距离和成本。
蚁群算法及其在序列比对中的应用研究综述 摘要：蚁群算法是一种新颖的仿生进化算法。作为一种全局搜索的方法，蚂蚁算法具有正反馈性、并行性、分布性、自组织性等特点，自提出以来，便在求解复杂组合优化问题上显示出了强大的优势。序列比对是生物信息学的基础，通过在比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。本文首先详细阐述了蚁群算法的基本原理、各种改进技术及收敛性分析，然后对蚁群算法在双序列比对和多序列比对的应用研究进行了综述和评价，最后指出了下一步的研究方向。 关键词：蚁群算法；序列比对；信息素 Abstract: Ant colony algorithm (ACA) is a novel bionic evolutionary algorithm. As a global searching approach，ACA has some characteristic，such as positive feedback, distributing，paralleling, self-organizing, etc，and from it was introduced, it has been used to solve all kinds of complex optimization problem. Sequence alignment is the basement of Bioinformatics. With the wealth of sequence information obtained from sequence alignment, one can infers the structure, function and evolutionary relationship of genes. In this paper, the basic principles of ACA are introduced at length, and various improvements and convergence Analysis of ACA are also presented. Then the current study of double sequence alignment and multiple sequence alignment based on ant colony algorithm are reviewed and evaluated. Finally, some future research directions about ACA are proposed. Key words: Ant Colony Algorithm; Sequence Alignment; Pheromone
1 引言
蚁群算法(Ant Algorithm)是一种源于大自然中生物世界的新的仿生类算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行为特性，通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。由于在模拟仿真中使用的是人工蚂蚁概念，因此有时亦被称为蚂蚁系统(Ant System)。据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可见提示下找出从其窝巢至食物源的最短路径，并能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物——信息激素(Pheromone)，使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息激素轨迹(Trail)也越来越多，以致信息素强度增大（随时间的推移会逐渐减弱），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强蚁群算法及其在序列比对中的应用研究综述 度，这种选择过程被称之为蚂蚁的自催化行为。由于其原理是一种正反馈机制，因此，也可将蚁群系统理解成增强型学习系统。 蚁群算法由意大利学者M．Dorigo等人在20世纪90年代初提出来的[1~3]。发展到今天已经有十几年的路程，在这一段时间里人们不断的对蚁群算法提出一些改进方法。有Dorigo等人提出的一种称之为Ant—Q System[4]的蚁群算法，该算法只让每次循环中的最短路径上的信息量作更新，强化了信息的反馈。德国学者Stutzle和Hoos提出了一种最大最小蚂蚁系统(MAX-MIN ant system，MMAS) [5]，MMAS对信息量的上下界作了限定，并且在算法中采用了轨迹平滑机制。直
到今天，MMAS仍然是解决TSP、QAP等离散域优化问题的最好蚁群算法模型之一，很多对蚁群算法的改进策略都渗透着MMAS的思想。另外还有国内的学者吴庆洪等人提出了一种具有变异特征的蚁群算法[6]，他们在蚁群算法中引入了逆转变异机制。蚁群算法具有较好的鲁棒性，并行分布式计算及易于与其他启发式方法结合等优点，在短期内得到了很大发展，其应用领域也不断得到扩展[7~10]。 目前已有一些学者将蚁群算法应用到序列比对这一领域当中，其中梁栋等人将蚁群算法应用于序列比对，并提出基于自适应调整信息素的改进算法[11]，其结果表明，蚁群算法可以有效地运用于双序列比对问题。陈娟等人[12,13]提出了蚁群优化算法在多序列比对中的应用及渐进算法结合蚁群算法在多序列比较中的应用，并取得了较好的效果。Yixin Chenl等人[14]提出了基于分割方法的蚁群多序列比对方法。该算法采用蚁群算法将递归地将序列分割成垂直分割成若干子序列。S．R．Jangam等人[15] 在遗传算法中嵌入使用了蚁群算法来解决双序列比对问题。Zne-Jung Le等人[16]结合了遗传算法和蚁群算法来解决多序列比对问题。为了将这些分散的文献和资料集中起来,本文对蚁群算法及其在序列比对中的应用研究进行了较全面地综述。
2 蚁群算法的原理
用于优化领域的人工蚂蚁算法，其基本原理吸收了生物界中蚂蚁群体行为的某些显著特征： (1) 察觉小范围区域内状况并判断出是否有食物或其他同类的信息素轨迹； (2) 释放自己的信息素； (3) 所遗留的信息素数量会随时间而逐步减少。 由于自然界中的蚂蚁基本没有视觉，既不知向何处去寻找和获取食物，也不知发现食物后如何返回自己的巢穴，因此它们仅仅依赖于同类散发在周围环境中的信息素，来决定自己何去何从。有趣的是，尽管没有任何先验知识，但蚂蚁们还是有能力找到从其巢穴到食物源的最佳路径，甚至在该路线放置障碍物之后，它们仍然能很快重新找到新的最佳路线。这里，用一个形象化的图2.01来说明 蚂蚁群体的路径搜索原理和机制。 图2.01蚂蚁从蚁穴移至食物源 假定障碍物的周围有两条道路可从蚂蚁的巢穴到达食物源：Nest-ABD-Food和Nest-ACD-Food，分别具有长度4和6。蚂蚁在单位时间内可移动一个单位长度的距离。开始时所有道路上都未留有任何信息素。在t=0时刻，20只蚂蚁从巢穴出发移动到A。它们以相同概率选择左侧或右侧道路，因此平均有10只蚂蚁走左侧，10只走右侧。在t=4时刻，第一组到达食物源的蚂蚁将折回。在t=5时刻，两组蚂蚁将在D点相遇。此时BD上的信息素数量与CD上的相同，因为各有10只蚂蚁选择了相应的道路。从而有5只返回的蚂蚁将选择BD而另5只将选择CD。在t=8时刻，前5个蚂蚁将返回巢穴，而AC，CD和BD上各有5个蚂蚁。在t=9时刻，前5个蚂蚁又回到A并且再次面对往左还是往右的选择。这时，AB上的轨迹数是20而AC上是15，因此将有较多数的蚂蚁选择往左，从而增强了该路线的信息素。随着该过程的继续，两条道路上信息素数量的差距将越来越大，直至绝大多数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短，因此，在相同的时间区间内，短的路线会有更多的机会被选择。 蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路径，并且能随环境的变化而变化，适应性的搜索新的路径，产生新的选择。其根本原因是蚂蚁在寻找食物源时，能在其走过的路上释放信息素，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比，当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最蚁群算法及其在序列比对中的应用研究综述 终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。
3 基本蚁群算法的过程
基本的蚁群算法可以应用于基于图表示的组合优化问题中（如 TSP），其简单表述如下：在起始时刻进行初始化，将m个蚂蚁随机放在n个城市上，城市间的每一条边都有一个初始外激素强度值)0(ij。每个蚂蚁k的禁忌表kTabu的第一个元素为其初始城市。然后每个蚂蚁从城市i到城市j，依据概率函数
(1) 选择将要移动的城市，这个概率取决于城市间的距离和信息素的强度。其中)(tij表示边),(ji上信息素的强度；ij表示城市间距离因子，通常取为距离的倒
数；集合}{},,2,1{kkTabunallowed，α和β都是控制信息素与可见度的相对重要性的参数。可见转移概率是可见度和t时刻信息素强度的权衡。 在n次循环后，所有蚂蚁的禁忌表都填满后，计算每个蚂蚁走过的路径的长度，并找到最短路径保存，记录此路径并更改该路径上的信息素 。信息素更新的公式是：
(2) (3) 其中ij表示在某条边上的累加新增信息素的和，ρ表示信息素消散的等级，kij
表示在时刻t和t+ n之间第k个蚂蚁在边(i ,j)留下的信息素的数量。如果在时刻t和t+n之间第k个蚂蚁经过边(i,j)，则
(4) 其中Q 为常量，kL为第k个蚂蚁周游的路径长度。 这一过程重复直至达到最大迭代次数maxNC结束，或者所有蚂蚁都走同一路线。后一种情况被称为停滞状态。如果算法在NC次循环后终止，蚂蚁算法的复
,0,][)]([][)]([)(kallowedsisisijijkijallowedjt
t
tpk
lkkijij1
ijijijtt.1
0),(,jiedgeant
L
Q
kkk
ij
