最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 蚁群算法详解

    没有中心化的组织,蚁群何以进行高效地搜寻呢?一个快递小哥有5个包裹要送,如何确定一条最短的行进路线?

    本文我们一起学下常用于路径优化的蚁群算法,主要内容如下:

    • 蚁群算法简介
    • 蚁群算法原理
    • 蚁群算法实例

    1.蚁群算法简介

    如何寻找一条合适的路径,几乎是一个永恒的话题。每个人、每天都会遇到。大到全国列车的运行规划,小到每个人的手机导航。其中一部分是关于“如何寻找两个位置间的最短距离”的,这一部分有较为成熟的理论与确切的解法,还有与之匹配的各种算法。

    蚁群系统(Ant System(AS)Ant Colony System(ACS))是由意大利学者DorigoManiezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中,发现蚁群整体会体现一些智能的行为,例如蚁群可以在不同的环境下,寻找最短到达食物源的路径。

    后经进一步研究发现,这是因为蚂蚁会在其经过的路径上释放一种可以称之为“信息素(pheromone)”的物质,蚁群内的蚂蚁对“信息素”具有感知能力,它们会沿着“信息素”浓度较高路径行走,而每只路过的蚂蚁都会在路上留下“信息素”,这就形成一种类似正反馈的机制,这样经过一段时间后,整个蚁群就会沿着最短路径到达食物源了。

    由上述蚂蚁找食物模式演变来的算法,即是蚁群算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。在数字时代背景下,蚁群算法在网络路由中的应用受到越来越多学者的关注,并提出了一些新的基于蚂蚁算法的路由算法。

    同传统的路由算法相比较,该算法在网络路由中具有信息分布式性、动态性、随机性和异步性等特点,而这些特点正好能满足网络路由的需要。

    2.蚁群算法原理

    蚁群算法是从自然界中真实蚂蚁觅食的群体行为得到启发而提出的,其很多观点都来源于真实蚁群,因此算法中所定义的人工蚂蚁与真实蚂蚁存在一定的辩证关系。

    自组织行为特征

    蚁群的自组织行为特征主要有:

    • 高度结构化的组织
      虽然蚂蚁的个体行为极其简单,但由个体组成的蚁群却构成高度结构化的社会组织,蚂蚁社会的成员有分工,有相互的通信和信息传递。

    • 自然优化
      蚁群在觅食过程中,在没有任何提示下总能找到从蚁巢到食物源之间的最短路径;当经过的路线上出现障碍物时,还能迅速找到新的最优路径。

    • 信息正反馈
      蚂蚁在寻找食物时,在其经过的路径上释放信息素(外激素)。蚂蚁基本没有视觉,但能在小范围内察觉同类散发的信息素的轨迹,由此来决定何去何从,并倾向于朝着信息素强度高的方向移动。

    • 自催化行为
      某条路径上走过的蚂蚁越多,留下的信息素也越多(随时间蒸发一部分),后来蚂蚁选择该路径的概率也越高。

    算法基本思想

    1. 根据具体问题设置多只蚂蚁,分头并行搜索。
    2. 每只蚂蚁完成一次周游后,在行进的路上释放信息素,信息素量与解的质量成正比。
    3. 蚂蚁路径的选择根据信息素强度大小(初始信息素量设为相等),同时考虑两点之间的距离,采用随机的局部搜索策略。这使得距离较短的边,其上的信息素量较大,后来的蚂蚁选择该边的概率也较大。
    4. 每只蚂蚁只能走合法路线(经过每个城市1次且仅1次),为此设置禁忌表来控制。
    5. 所有蚂蚁都搜索完一次就是迭代一次,每迭代一次就对所有的边做一次信息素更新,原来的蚂蚁死掉,新的蚂蚁进行新一轮搜索。
    6. 更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。
    7. 达到预定的迭代步数,或出现停滞现象(所有蚂蚁都选择同样的路径,解不再变化),则算法结束,以当前最优解作为问题的最优解。

    其中,为边上的信息素量,刚开始时,为本次迭代边上的信息素增量,为第k只蚂蚁在本次迭代中留在边上的信息素量,为信息素挥发系数。Q是正常数,m是蚂蚁数量,n是城市数量,为蚂蚁k在本次周游中所走路径的长度。

    其中为信息素的相对重要程度,为启发式因子的相对重要程度,而是蚂蚁k下一步允许选择的城市集合。
    为启发式因子,反应蚂蚁由城市i转移到城市j的启发程度,为城市之间的距离。

    算法步骤

    我们了解了信息素计算公式和蚂蚁的转移概率之后,看下具体流程图如下:

    1. 初始化参数:开始时,每条边的信息素量都相等,即:
    2. 将各只蚂蚁放置各顶点,禁忌表为对应的顶点。
    3. 1只蚂蚁,计算转移概率,按照轮盘赌的方式选择下一个顶点,更新禁忌表,再计算概率,再选择顶点,再更新禁忌表,直至遍历所有顶点一次。
    4. 计算该只蚂蚁留在各边的信息素量,该蚂蚁死去。
    5. 重复3-4步,直至m只蚂蚁都周游完毕。
    6. 计算各边的信息素增量和信息素量。
    7. 计算本次迭代的路径,更新当前的最优路径,清空禁忌表。
    8. 判断是否达到预定的迭代步数,或者是否出现停滞现象,若是则算法结束,输出当前最优路径,否则转到步骤2,进行下一次迭代。

    算法特点

    与其他优化算法相比,蚁群算法具有以下几个特点:

    • 采用正反馈机制,使得搜索过程不断收敛,最终逼近最优解。
    • 每个个体可以通过释放信息素来改变周围的环境,且每个个体能够感知周围环境的实时变化,个体间通过环境进行间接地通讯。
    • 搜索过程采用分布式计算方式,多个个体同时进行并行计算,大大提高了算法的计算能力和运行效率。
    • 启发式的概率搜索方式不容易陷入局部最优,易于寻找到全局最优解。

    3.蚁群算法实例

    该算法应用于其他组合优化问题,如旅行商问题、指派问题、Job—shop调度问题、车辆路由问题、图着色问题和网络路由问题等。

    知道了上面的算法原理,我们来看下开头的那个问题,一个快递小哥有5个包裹要送,如何确定一条最短的行进路线?

    假设由于某种原因,城市道路均是单行道,即A->BB->A的距离不相同,也就是说这是一个不对称的TSP问题。现在城市距离信息如下表:

    设置参数:,为禁忌表,那么第一次迭代第一只蚂蚁周游如下:

    第一次迭代第二只蚂蚁周游如下:

    依次类推,第一次迭代完成之后,我们得到信息素矩阵如下:

    接着进行第二次迭代,第二次迭代第一只蚂蚁周游如下:

    依次类推,发现第二次迭代的时候,假如五只蚂蚁走的是同一条路,那么算法收敛结束。最优路径为A->E->D->C->B->A,最优路径的距离为9.

    至此,我们从蚁群算法的简介,原理以及实例方面对蚁群算法进行了详细的阐述,希望对大家有所帮助。

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 蚁群算法详解

    发表评论

    • 53会员总数(位)
    • 322资源总数(个)
    • 20本周发布(个)
    • 3 今日发布(个)
    • 334稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情