蚁群算法整理ppt.ppt
蚁群算法最初是通过对蚂蚁群落的观察，受蚁群行为特征启发而得出的。蚂蚁是一种群居昆虫，在觅食、清理巢穴等活动中，彼此依赖、相互协作共同完成特定的任务。就个体来讲，单个蚂蚁的智力和体力是极其有限的，服务于整个群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、在完成任务过程中所体现的自组织特征等反应出蚁群具有较高的智能和自我管理能力，具有很高层次组织性，这使得蚁群能够完成一些复杂的任务。,蚁群算法求解旅行商问题,TSP问题是典型的NP完全问题，许多算验证法及算法效率侧试都以TSP问题为基础。在蚁群算法研究中，第一个蚁群算法，蚂蚁系统，就是在TSP问题的基础上提出来的。而后，依据TSP问题，又提出了蚁群算法系列中具有代表性的蚁群系统，最大一最小蚂蚁系统。,蚁群的行为是整体协作，相互分工，以一个整体去解决一些对单个蚂蚁看上去是不可能完成的任务。就目前来讲，蚁群至少有三个方面的行为特征对算法研究有很好的启发意义，分别是觅食行为、任务分配、死蚁堆积阁。蚁群的觅食行为指蚂蚁从巢穴出发寻找食物并且将食物搬回巢穴的行为.当蚂蚁出外寻找食物时，会在自己走过的路径上释放一种称为信息家的物质，后续的蚂蚁一般更愿意走那些信息素强度更高的路径。这样，较短路径上单位时间内通过的蚂蚁数目较多，留下的信息素也较多(浓度更高)，对妈蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。这就形成了一个正反馈机制，使得最终所有的蚂蚁都走蚁穴到食物源的最短路径.,我们讨论与TSP问题相关的蚁群算法。在蚁群算法研究及实现中，并不是直接模拟现实蚁群，而是采用人工妈蚁。人工蚁群与现实蚁群的区别主要包括:(1)人工蚂蚁是有一定的记忆能力的，它可以记住己经走过的路径，以保证不会重复走相同的城市。现实的蚁群是没有记忆的，蚂蚁间的信息交换主要依靠留在所经过路径上的信息素。(2)人工蚂蚁不仅仅是依据信息素来确定要走的路径的，还依据一定的启发信息，比如相邻边的长度，这意味着人工蚂蚁具有一定的视觉能力，而真实蚂蚁几乎没有视觉。(3)人工妈蚁是生活在一个离散的时间环境下的。我们仅考虑人工蚂蚁位于某个城市，而不考虑蚂蚁在城市间的移动过程，即只考虑在某些离散时间点上的蚂蚁.而现实世界中的蚂蚁处于一个连续的时间维中。,三种模型的实现大致相同，主要区别是在信息素的更新方式上。在用蚂蚁系统解决TSP问题时，蚁量模型和蚁密模型是蚂蚁在构建一条合法路径的过程中进行信息素的更新的，当蚂蚁走过一条边之后，就对该边进行信息素的更新，后文将这种更新称为局部更新。而蚁周模型是在所有蚂蚁都构建了一条合法路径之后才对各边进行信息素更新的，后文将这种更新称为全局更新，并且三者在蚂蚁释放信息素的量上面也不同。蚁密模型中，蚂蚁在自己所走过的边上所释放的信息素是一个常量Q，而蚁量模型中，蚂蚁在自己所走过的边上释放的信息素是Q/dtj，其中Q是一个常量，而成是蚂蚁走过边的长度。蚁周模型中蚂蚁释放信息素的量在后文说明。,蚂蚁系统的基本思想是:(l)预先初始化各边信息素强度以及各蚂蚁的禁忌表。各蚂蚁按照一定的概率规则，在禁忌表的制约下选择下一个要到达的结点，直到最终形成一条合法路径。(2)计算各蚂蚁所产生的路径长度，路径长度是路径中各边长度之和。(3)更新各边的信息素。各边先进行信息素挥发操作，然后根据各蚂蚁产生的路径长度获取蚂蚁所释放的信息素。(4)当所有蚂蚁均完成了信息素的更新操作之后，记录当前的最短路径，并且对禁忌表以及信息素的增加值T(t，t+l)进行初始化，并转到步骤2。依此循环下去，直到满足算法的终了条件为止，比如解无法得到进一步的改进或者达到了事先规定的循环次数。,在蚂蚁系统具体包括了三个方面的内容。第一、初始化。对于每条边上的信息素初始化为一个较小的数值r0;对每只蚂蚁，需要一个禁忌表记录自己已经走过的结点，初始化其禁忌表为该蚂蚁所在的结点，禁忌表长度为l。蚂蚁在各边上释放信息素的量被初始化为0。第二、蚂蚁构造路径。蚂蚁按照一定的概率确定下一步要到达的城市。概率的计算如(l)式。,(1)式表示蚂蚁在t时刻由城市i选择城市j的概率。是信息素在概率计算中的权重，它的值越大，信息素在蚂蚁选择下一个要到的城市中起到的作用越大。是启发因子(在TSP问题中常以d的倒数来表示)在概率计算中所占的权重，它的值越大，启发因子在蚂蚁选择城市的过程中所起的作用越大.allowed是不在蚂蚁禁忌表中的城市集合。(1)式说明，蚂蚁不会选择禁忌表中的城市，这样就保证了解的合法性。,基于蚁群算法的全局路径规划,1 环境模型的建立,算法步骤Step 1：Rob根据探测到的环境信息，用第1节的方法建立环境模型，并以图型结构存储到机器中；Step 2：初始化蚁群算法控制参数：设置初始信息素，初始化迭代计数器n=0，最大迭代次数初始化为MAX，迭代禁忌表清空等；Step 3：将m只蚂蚁放置在出发点Start_P，并将其添加到禁忌表Tabuk（k=1,2,m）中；Step 4：任意蚂蚁k根据路径选择策略，构建一条从Start_P到Target_sub的避障路径Path（Start_P，Target_sub）；Step 5：利用适应值评价函数对蚁群规划的路径给出评价，并将路径上的信息素利用评价函数进行更新；Step 6：若蚁群找到的路径满足要求或迭代次数达最大值，则给出最优路径；否则，迭代次数加1，清空禁忌表，转向Step 3。,路径选择策略 在蚂蚁路径探索过程中，从开始点出发，依次选取下一结点，直到到达目标点，搜索到一条路径，然后进行释放信息素等操作。为了防止停滞现象，采用如下方法进行路径点的选择。设t时刻，蚂蚁k所在栅格gi的序号为i，选择满足如下条件的j位置：,表示t时刻在i和j连线上残留的信息素强度；表示从i到j的期望程度。allowedi 表示蚂蚁k在i位置允许选择的节点集合，allowedi=S-Tabuk(t)。q，q0是为了防止出现停滞而设的随机搜索策略所需参数。q0为给定参数，0q01。q是（0，1）内服从均匀分布的随机变量，在算法中根据环境不同随机选择。E由蚂蚁k从i转移到j的概率决定：,适应值评价函数设计 以路径长度为主要评判依据，同时考虑安全性，将第k只蚂蚁找到的路径path的适应值评价函数设计为：为权重系数；Sk(path)是第k只蚂蚁所找到的路径path与障碍物接近程度，依此作为安全性条件。,信息素更新策略 当所有蚂蚁完成一次规划即一次迭代之后，信息素更新依据每只蚂蚁找到的路径的适应值评价函数进行。表示蚂蚁k在本次迭代中留在边（i,j）上的信息素量。,其中，Fitk为第k只蚂蚁搜索到路径对应的适应值函数值；Fitbest为本次迭代中找到的最优路径对应的适应值函数值。,为路径上信息素的蒸发函数；,1 2为权重。在信息素更新过程中对本次迭代的最优解进行奖励，所以在信息素更新时，本次迭代的最优路径要额外的释放信息素，释放信息素的多少通过调节 来控制。,实验结果,
