蚁群算法.ppt

蚁群算法最初是通过对蚂蚁群落的观察,受蚁群行为特征启发而得出的。蚂蚁是一种群居昆虫,在觅食、清理巢穴等活动中,彼此依赖、相互协作共同完成特定的任务。就个体来讲,单个蚂蚁的智力和体力是极其有限的,服务于整个群落的生存与发展;就群体来讲,蚁群在行为上的分工协作、在完成任务过程中所体现的自组织特征等反应出蚁群具有较高的智能和自我管理能力,具有很高层次组织性,这使得蚁群能够完成一些复杂的任务。蚁群算法求解旅行商问题 1 TSP 问题是典型的 NP完全问题,许多算法验证及算法效率侧试都以 TSP 问题为基础。在蚁群算法研究中,第一个蚁群算法,蚂蚁系统,就是在 TSP 问题的基础上提出来的。而后,依据 TSP 问题,又提出了蚁群算法系列中具有代表性的蚁群系统,最大一最小蚂蚁系统。 2 蚁群的行为是整体协作,相互分工,以一个整体去解决一些对单个蚂蚁看上去是不可能完成的任务。就目前来讲,蚁群至少有三个方面的行为特征对算法研究有很好的启发意义,分别是觅食行为、任务分配、死蚁堆积阁。,会在自己走过的路径上释放一种称为信息家的物质,后续的蚂蚁一般更愿意走那些信息素强度更高的路径。这样,较短路径上单位时间内通过的蚂蚁数目较多,留下的信息素也较多(浓度更高),对妈蚁产生了更强的吸引,使得更多的蚂蚁走较短的路径。这就形成了一个正反馈机制,使得最终所有的蚂蚁都走蚁穴到食物源的最短路径. 3 我们讨论与 TSP 问题相关的蚁群算法。在蚁群算法研究及实现中,并不是直接模拟现实蚁群,而是采用人工妈蚁。人工蚁群与现实蚁群的区别主要包括: (1) 人工蚂蚁是有一定的记忆能力的,它可以记住己经走过的路径,以保证不会重复走相同的城市。现实的蚁群是没有记忆的,蚂蚁间的信息交换主要依靠留在所经过路径上的信息素。(2) 人工蚂蚁不仅仅是依据信息素来确定要走的路径的, 还依据一定的启发信息,比如相邻边的长度,这意味着人工蚂蚁具有一定的视觉能力,而真实蚂蚁几乎没有视觉。(3) 人工妈蚁是生活在一个离散的时间环境下的。我们仅考虑人工蚂蚁位于某个城市,而不考虑蚂蚁在城市间的移动过程,。 4 在用蚂蚁系统解决 TSP 问题时,蚂蚁在构建一条合法路径的过程中进行信息素的更新的,当蚂蚁走过一条边之后, 就对该边进行信息素的更新,将这种更新称为局部更新。在所有蚂蚁都构建了一条合法路径之后对各边进行信息素更新的,将这种更新称为全局更新。蚂蚁释放信息素的量各种模型中也不同。某些模型中, 蚂蚁在自己所走过的边上所释放的信息素是一个常量 Q,而某些模型中,蚂蚁在自己所走过的边上释放的信息素是 Q/dtj ,其中 Q是一个常量, dtj 是蚂蚁走过边的长度。 5 蚂蚁系统的基本思想是: (l) 预先初始化各边信息素强度以及各蚂蚁的禁忌表。各蚂蚁按照一定的概率规则,在禁忌表的制约下选择下一个要到达的结点,直到最终形成一条合法路径。(2) 计算各蚂蚁所产生的路径长度,路径长度是路径中各边长度之和。(3) 更新各边的信息素。各边先进行信息素挥发操作,然后根据各蚂蚁产生的路径长度获取蚂蚁所释放的信息素。(4) 当所有蚂蚁均完成了信息素的更新操作之后,记录当前的最短路径,并且对禁忌表以及信息素的增加值△T(t , t+l) 进行初始化,并转到步骤 2。依此循环下去,直到满足算法的终了条件为止,比如解无法得到进一步的改进或者达到了事先规定的循环次数。 6 在蚂蚁系统具体包括了三个方面的内容。第一、初始化。对于每条边上的信息素初始化为一个较小的数值 r0; 对每只蚂蚁,需要一个禁忌表记录自己已经走过的结点,初始化其禁忌表为该蚂蚁所在的结点,禁忌表长度为 l。蚂蚁在各边上释放信息素的量被初始化为 0。第二、蚂蚁构造路径。蚂蚁按照一定的概率确定下一步要到达的城市。概率的计算如(l) 式。 7 (1) 式表示蚂蚁在 t时刻由城市 i选择城市 j的概率。α是信息素在概率计算中的权重,它的值越大,信息素在蚂蚁选择下一个要到的城市中起到的作用越大。β是启发因子(在TSP 问题中常以 d的倒数来表示)在概率计算中所占的权重,它的值越大, 是不在蚂蚁禁忌表中的城市集合。(1) 式说明,蚂蚁不会选择禁忌表中的城市,这样就保证了解的合法性。 8 第三、对信息素的操作。当所有蚂蚁都找到了一条合法路径之后,就进行信息素的更新 9 10