精华内容
下载资源
问答
  • 蚁群算法 千次阅读
    2019-11-05 10:05:16

    一、基本思想

    蚁群算法是受到蚂蚁觅食过程中表现的群智能行为的启发,蚂蚁在觅食过程中会释放一种叫“信息素”的物质,同时蚂蚁会沿着“信息素”浓度高的位置走,最后大部分蚂蚁都能沿着最短觅食路径走。

    二、算法流程

    TSP问题为例来介绍蚁群算法的基本流程,首先介绍蚁群算法最重要的两个步骤:选择路径和更新信息素

    1. 选择路径

    对每一个蚂蚁,以下面的概率分布来随机选择一个城市访问
    p i , j k = γ i , j σ ∗ η i , j β ∑ z ∈ u n v i s i t e d ( i ) γ i , z σ ∗ η i , z β ( j ∈ u n v i s i t e d ( i ) ) p_{i,j}^k=\frac{\gamma_{i,j}^\sigma*\eta_{i,j}^\beta}{\sum_{z∈unvisited(i)}\gamma_{i,z}^\sigma*\eta_{i,z}^\beta}(j∈unvisited(i)) pi,jk=zunvisited(i)γi,zσηi,zβγi,jσηi,jβ(junvisited(i))
    p i , j k p_{i,j}^k pi,jk:表示第k个蚂蚁在城市i选择访问城市j的概率
    γ i , j \gamma_{i,j} γi,j:表示城市i到城市j的信息素浓度
    η i , j \eta_{i,j} ηi,j:表示城市i到城市j的启发值(一般设置为两个城市距离的倒数)
    σ \sigma σ:表示信息素浓度的权重
    β \beta β:表示启发值的权重
    u n v i s i t e d ( i ) unvisited(i) unvisited(i):表示在城市i还需要访问的城市集合

    2. 更新信息素

    每个蚂蚁遍历完所有的城市并且回到出发城市后,按照下面的公式更新信息素浓度 γ i , j \gamma_{i,j} γi,j
    γ i , j = ( 1 − ρ ) ∗ γ i , j + Δ γ i , j k \gamma_{i,j}=(1-\rho)*\gamma_{i,j}+\Delta\gamma_{i,j}^k γi,j=(1ρ)γi,j+Δγi,jk
    m m m:表示蚂蚁个数
    ρ \rho ρ:表示信息素挥发速度
    ( 1 − ρ ) ∗ γ i , j (1-\rho)*\gamma_{i,j} (1ρ)γi,j:表示原来的信息素的遗留部分
    Δ γ i , j k \Delta\gamma_{i,j}^k Δγi,jk:表示行走距离最短蚂蚁留下的信息素(蚂蚁行走距离的倒数)


    算法流程图如下:
    在这里插入图片描述

    三、应用实现

    测试的城市坐标同老师给我发的微信公众号的学习资料相同干货|十分钟快速get蚁群算法
    程序参数设置如下:
    信息素挥发速度 ρ \rho ρ:0.2
    信息素浓度的权重 σ \sigma σ:1
    启发值的权重 β \beta β:6
    蚂蚁个数 m m m:1.5*城市个数
    结果如下图:
    在这里插入图片描述
    算法收敛速度较快,程序很容易陷入局部最优解,我尝试调了一些参数,发现了如下的规律:

    1. 信息素挥发速度 ρ \rho ρ不能太大,设置为0.5的时候效果已经很差了
    2. 信息素浓度权重 σ \sigma σ和启发值的权重 β \beta β要达到一个平衡,不能某一个的权重过大或者过小
    3. 蚂蚁个数 m m m越大越好,但是越大程序运行时间越长

    简单的蚁群算法很容易陷入局部最优,原因如下:

    当蚂蚁在一条路径上觅食很久时,放置一个近的食物基本没有效果,这可以理解为当一只蚂蚁找到一条路径时,在经过很长时间后大多数蚂蚁都选择了这条路径,这时,突然有一只蚂蚁找到了较近的食物,但因为时间过得太久,两条路径上浓度相差太大(浓度越大,被选择的概率就越大),整个系统基本已经停滞了,陷入了局部最优。(我以为增加信息素的挥发速度能改善这个问题,但是问题并没有得到改善)

    目前有一些改进算法,例如最大最小蚁群算法、排序蚁群算法、基于遗传算法的蚁群算法等

    参考资料

    [1] 干货|十分钟快速get蚁群算法(附代码)
    [2] 蚁群算法(ACO)学习笔记
    [3] 蚁群算法

    更多相关内容
  • 信息素更新上面对于蚁群算法所做出的改进,
  • 通过分析现有蚁群算法信息素更新模型陷入局部最优的原因,借鉴蚁群模型退火算法思想,根据假设推导出增幅递减信息素更新模型,分析该模型对算法复杂度的影响,并分别采用4 种信息素更新模型求解最短路问题。...
  • 针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。 定义 各个蚂蚁在没有事先告诉他们食物在什么...
  • 每只蚂蚁在构造出一条从起点到终点的路径后,蚁群算法还要求根据路径的总长度来更新这条路径所包含的每条边上信息素的浓度(在旅行商问题中每座城市是图中的一个节点,城市两两间有一条边相连)。下面给出了蚁群...

    信息素的局部更新策略  

      每只蚂蚁在构造出一条从起点到终点的路径后,蚁群算法还要求根据路径的总长度来更新这条路径所包含的每条边上信息素的浓度(在旅行商问题中每座城市是图中的一个节点,城市两两间有一条边相连)。下面给出了蚁群算法更新信息素的公式:

    .

      上面的第一个公式体现了信息素的更新值的计算,其中,Ck代表第k只蚂蚁所构造的路径的总长度,Q是凭经验设定的一个参数,通常置为1。component(i,j)表示从城市i到城市j的一条边,m是蚂蚁的总数。上面的第二个公式是说i和j这条边的信息素值tau等于这条边上原有的信息素加上在上一次构造路径活动中所有经过这条边的蚂蚁贡献的信息素更新值(即第一个公式)。

    假设三只蚂蚁构造的路径长度如下所示:

    Tour 1: 450
    Tour 2: 380
    Tour 1: 460

    则它们的信息素的更新值相加结果为:componentNewPheromone = (Q / 450) + (Q / 380) + (Q / 460)

    最后把它加到各个蚂蚁的路径中每条边原来的信息素值之上:

    componentPheromone = componentPheromone + componentNewPheromone

    上述信息素更新过程的伪代码如下所示:

     

    for ant in colony do //蚁群中每条蚂蚁都逐个更新自己路径经过边上的的信息素
        tour = ant.getTour(); //蚂蚁计算路径的总长度
        pheromoneToAdd = getParam('Q') / tour.distance(); //蚂蚁计算信息素的更新值
        for cityIndex in tour do //回溯路径中的每个城市
            if lastCity(cityIndex) do // 如果当前城市是路径上的最后一个城市,取出它和第一个城市间的边
                edge = getEdge(cityIndex, 0)
            else do
                edge = getEdge(cityIndex, cityIndex+1) //否则,取当前城市和路径上下一个城市间的边
            end if
            currentPheromone = edge.getPheromone(); //获得边上之前的信息素
            edge.setPheromone(currentPheromone + pheromoneToAdd)//原有信息素加上更新值后得到新信息素
        end for // ant路径上所有的边的信息素更新完毕
    end for //蚁群中所有蚂蚁都处理完毕

     信息素的挥发

    在自然界中蚂蚁遗留下来的信息素经过一段时间后会挥发,我们在算法中也模拟上述过程,具体公式如下:

    rho是一个人为设定的参数,称为挥发率,一般为0-1间的数。

    相应的伪代码如下所示:

    for edge in edges
        updatedPheromone = (1 - getParam('rho')) * edge.getPheromone()
        edge.setPheromone(updatedPheromone)
    end for

    精英蚂蚁策略

     精英蚂蚁是对蚁群算法的一种改进,所谓精英蚂蚁是指当全部蚂蚁都构造完各自的路径之后,所有路径中最短的那条路径所对应的蚂蚁。精英蚂蚁策略的公式如下所示,它和上面的信息素局部更新公式的唯一区别在于精英蚂蚁在像其它蚂蚁一样更新完自己路径上的信息素后,还要再重复一遍信息素的更新过程,只不过这次要把更新值乘上一个参数e,e通常选在0和1之间。

     

    转载于:https://www.cnblogs.com/zhaogeatdlnu/p/5706033.html

    展开全文
  • 蚁群算法在优化领域,尤其在组合优化问题中获得了较为成功的应用,然而它存在易于早熟收敛、搜索时 间长等不足.针对该问题,提出了一种改进算法.该算法一方面在典型的状态转移规则中融合了一种随机选择策略,保证算法...
  • 针对蚁群算法在求解大规模优化问题时存在的3个缺点:消耗时间长、蚂蚁在下次搜索时目标导向不强导致搜索随机性大、寻优路径上的信息素过度增强导致得到假的最优解。本文提出了基于边缘初始化和自适应全局信息素的...
  • 为了避免蚁群算法陷入停滞状态,研究了信息素更新规则,并在信息素增量更新式中加入动态调节因子,使得次优路径上的信息素增量较大,其他路径则没有明显的变化,从而有利于蚂蚁在较短的时间内找到更好的解。...
  • 对于基本蚁群算法(ACA)不适用求解连续空间问题,并且极易陷入局部最优的缺点,提出了一种基于自适应的蚁群算法。路径搜索策略采用基于目标函数值搜索筛选局部最优解的策略,确保能够迅速找到可行解。信息素更新...
  • 路径规划,蚁群算法
  • 对于蚁群算法做出的改进,按信息素大小进行排序
  • 为了提高ACO算法的解题能力,提出一种新型信息素更新策略(PACS),然后将PACS算法与其他蚁群算法分别应用于旅行商问题(TSP)进行仿真实验。仿真结果表明,PACS算法具有优良的全局优化性能,可抑制算法过早收敛于次...
  • 利用人工蚁群算法解决多城市间的TSP问题,信息素更新等。
  • 针对蚁群优化算法的关键步骤——信息素轨迹更新过程进行了深入分析。...在此基础上针对这个现象提出了一种基于Metropolis接受准则的信息素更新策略,并通过在不同规模的TSP上的实验,证明了这种新策略的有效性。
  • 蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是...

    蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。这种算法具有分布计算信息正反馈启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。[鲁棒性会比较好。]

    蚁群算法的求解质量好,主要有两个方面的原因:1) 采用正反馈机制,使得蚁群搜索过程中不断收敛,最终逼近最优解。2) 使用轮盘赌算法,保证了解空间的多样性,且受初始值的影响不大。

    以下是蚁群算法ACO应用到VRP问题中的注释。

    1.1 蚁群算法基本思想

    在蚁群算法中,蚂蚁的行走路径表示待优化问题的可行解(蚂蚁代表车辆,各个可能存放食物的点是顾客点),整个蚂蚁群体的所有路径构成待优化问题的解空间(即VRP问题的解,多个车辆构成的多个回路)。算法基本原理如下:

    1) 蚂蚁在路径上释放路径长度有关的信息素。(信息素是指导蚂蚁行走的关键,也就是目标函数。)

    2) 路径较短的蚂蚁释放的信息素量较多。随着时间的推进,较短的路径上累积的信息素浓度逐渐增高,选择该路径的蚂蚁个数也愈来愈多。(路径较短,即解越好,吸引着别的蚂蚁,也就是信息素越多)。

    3) 最优路径上的信息素浓度越来越大。

    4) 整个蚂蚁会在正反馈的作用下集中到最佳的路径上,最终蚁群找到最优寻食路径。

    1.2 蚁群算法核心步骤

    (1)路径构建

    路径构建包括初始城市的选择和下一个到达城市的选择。每个蚂蚁都随机选择一个城市作为其出发城市,并维护一个路径记忆表,用来存放该蚂蚁依次经过的城市。

    蚂蚁在构建路径的每一步中,按照轮盘赌法选择下一个要到达的城市。其中t时刻,蚂蚁k从i城市到j城市的转移概率计算:

    \alpha信息素重要程度因子;\beta启发函数重要程度因子;\gamma信息素挥发速度,越小则残留的信息素越多,也就是无效信息会继续搜索,收敛速度慢;1-rho代表残留系数。

    (2)信息素更新     

    在不断的研究探索中,学者们基于“信息素”的更新方式将蚁群算法分为三类模型 :

    a)循环模型(cycle):每只蚂蚁可释放的信息素总量是恒定的。

    b)密度模型(denseness):在蚂蚁走过一条路径后,无论该路径长度如何,所释放 的信息素浓度均相同。

    c)数量模型(quantity):每只蚂蚁在同一条路径上释放的信息素浓度均相同。

    在对此三类模型不断地实验与实践应用中,循环模型(通常用Q表示)因其更为合理的逻辑,在三类 模型中脱颖而出,被证明为最优模型。在后续研宄中,众多学者引入各类算法和技术, 将蚁群算法不断改进,其中主流的改进思路有三.基于信息素更新方式进行改进、基于 路径选择逻辑进行改进、引入其他算法与蚁群算法进行融合,产出了多种改进后的算法.

    迭代过程中,问题空间中的所有路径上的信息素都会发生改变。其中第一部分是信息素的蒸发(弱化信息素因素,避免都往当前最好的路径上走,避免局部最优);然后,所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素,公式如下: 

    等式右边第一部分代表了信息素自身挥发后剩余的信息素;第二部分是每只蚂蚁经过路径ij留下的信息素,若蚂蚁没走过该路径,则该部分为0。

    (3)蚁群算法流程

         了解了蚁群算法的基本思想后,我们来看看蚁群算法的流程图:

    1) 初始化参数:信息素重要程度,启发函数重要因子,信息素挥发因子,信息素释放总量,设置迭代计数器初始值iter=0,设置最大迭代代数iteration,随机生成M个蚂蚁个体作为初始群体P(0)。 

    2) 个体评价:计算群体P(t)中各蚂蚁个体的适应度, 对于TSP/VRP问题适应度函数就是指路径长度的计算。

    3) 解空间构建:解空间即路径构建,包括蚁群的初始城市选择下一个到达城市的选择。首先随机给蚁群分配出发点,然后根据(2)节转移概率(会用到信息素矩阵)构建式子(以及轮盘赌)选择下一个访问的城市,直到所有蚂蚁访问完所有的城市。

    4) 信息素更新:计算各个蚂蚁经过的路径长度,并根据信息素更新公式对各个城市连接路径上的信息素浓度进行更新。

    5)终止条件判断:若iter=iteration,则以过程中所得到的具有最大适应度个体作为最优解输出,终止计算。

    注,程序设计中会用到的参数:

    候选解为蚂蚁个数*城市个数组成的矩阵。即每一次迭代中,一只蚂蚁有一条自己的路径,则每次迭代中,共有蚂蚁个数条解。

    path_best为每次迭代生成的最好解所存的矩阵。

    展开全文
  • 路径较短的蚂蚁释放的信息素量较多,随着时间的推进,较短的路径上累积的信息素浓度逐渐增高,选择该路径的蚂蚁个数也愈来愈多。最终,整个蚂蚁会在正反馈的作用下集中到最佳的路径上,此时对应的便是待优化问题的最...
  • 针对交互网络中实体的非法、异常活动日趋隐蔽,复杂的交互关系又加剧了网络分析...在真实金融交互网络上的实验结果表明,所提模型在最优解质量和性能上均优于传统蚁群算法,且相比于贪心算法具有更好的覆盖率和准确率。
  • 提出解决车辆路径优化问题的方法, 针对蚁群算法的缺点, 分别对信息素更新策略、启发因子进行改进, 并引入搜索热区机制, 有效解决了蚁群算法的缺陷。最后, 以哈尔滨市局部地图为原型, 应用MATLAB软件对改进蚁群算法...
  • 基于蚁群算法的 TSP 求解,分别采用蚁群算法蚁群算法-粒子群混合算法进行优化求解,使用不同的交叉和变异适应度函数更新粒子,从而实现 TSP问题的优化求解,更加逼近实际问题。
  • 提出将蚁群算法用于求解函数优化问题的新方法。使用一定数量的蚂蚁在解空间中首先随机搜索,然后模拟蚂蚁觅食的方式,更新搜索路径上的信息素,按照转移概率来决定搜索方向,即通过信息素来指引搜索,最后搜索收敛于...
  • 基于蚁群算法路径规划 能成功运行 包含蚁群初始化 栅格法建模 信息素 启发函数 画图等部分
  • 将离散空间问题求解的蚁群算法引入连续空间, 针对多目标优化问题的特点, 提出一种用于求解带有约束 条件的多目标函数优化问题的蚁群算法. 该方法定义了连续空间中信息量的留存方式和蚂蚁的行走策略, 并将信息...
  • 蚁群优化算法(ACO)

    千次阅读 2022-03-27 10:18:55
    定义对照表: 蚁群觅食 蚁群优化算法 蚁群 种群规模(搜索空间的一组有效解) 觅食空间 问题搜索空间(解的规模,维度) 信息素 信息素浓度变量 所有的路径 有效解 最短路径 问题最优解 蚁群算法形式化: ​​​​...

    背景知识

    蚁群优化算法是Marco Dorigo 受到蚂蚁寻找食物发现路径的行为启发,在博士论文提出的算法,是一种用来寻找优化路径的概率型算法,刚开始是为了解决 TSP(旅行商问题) ,即旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。目前其应用扩展到了优化问题领域的各个方面,算法设计得到不断的改进,逐渐构筑起一套成熟的算法框架,成为组合优化领域最具有潜力的算法之一。组合优化问题:如旅行商问题、指派问题、Job—shop调度问题、车辆路由问题、图着色问题和网络路由问题等。

    优点:

    • 是一种本质上的并行算法,即各个蚂蚁各自寻找路径。
    • 是一种自组织的算法,所谓自组织就是没有外界干预,自己从无序到有序的过程。
    • 具有较强的鲁棒性。
    • 是一种正反馈算法。(蚂蚁能够最终找到最优路径,直接依赖于其在路径上信息素的堆积,而信息素的堆积是一个正反馈的过程。)

    缺点:

    • 收敛速度慢(因为需要等,但是节奏可以自己控制)
    • 易陷入局部最优(可以通过增加跳转目标的随机性改进)
    • 对于解空间为连续的优化问题不适用(蚁群优化算法适用于离散问题,粒子群算法适合解连续空间问题,参照上一篇)

    算法思想

    情景:蚂蚁寻找食物源,蚂蚁到达食物源患有多条路径,蚂蚁在选择路径时回释放一种信息素,此信息素会随时间含量不断减少,如此路径较短的蚂蚁往复次数多,留下的信息素含量不断增多,而蚂蚁会做出选择走信息素多的路,随时间发展,路径短的蚂蚁会越来越多。

    思想抽象:蚂蚁的行走路径表示待优化问题的可行解,整个蚂蚁群体的所有路径构成待优化问题的解空间。由于路径较短的蚂蚁释放的信息素量较多,随着时间的推进,较短的路径上累积的信息素浓度逐渐增高,选择该路径的蚂蚁个数也愈来愈多。最终,整个蚂蚁会在正反馈的作用下集中到最佳的路径上,此时对应的便是待优化问题的最优解

    定义对照表:

    蚁群觅食蚁群优化算法
    蚁群种群规模(搜索空间的一组有效解)
    觅食空间问题搜索空间(解的规模,维度)
    信息素信息素浓度变量
    所有的路径有效解
    最短路径问题最优解

    蚁群算法形式化:

    • ​​​​每只蚂蚁对应一个计算智能体
    • 蚂蚁根据概率选择位置进行移动
    • 在经过的路径上留下“信息素”
    • “信息素”会随时间挥发
    • “信息素”浓度大的路径在后序选择中会以更高的概率被选中

    算法流程

    • 对相关参数进行初始化,包括蚁群规模、信息素因子、启发函数因子、信息素的挥发因子、信息素常数、以及最大迭代次数等,以及将数据读入程序,并进行预处理:比如将城市的坐标信息转化为城市间的距离矩阵。
    • 随机将蚂蚁放于不同的出发点,对每个蚂蚁计算其下个访问城市,直到有蚂蚁访问完所有的城市。
    • 计算各蚂蚁经过的路径长度Lk,记录当前迭代次数最优解,同时对路径上的信息素浓度进行更新。
    • 判断是否到达迭代次数,若否,返回步骤2;是,结束程序。
    • 输出结果,并根据需要输出寻优过程中的相关指标,如运行时间、迭代次数等。


    旅行商问题

    核心是蚁群优化算法的两个公式,一个是路径构建(计算选择城市概率的),另一个是更新信息素的。

    • N个城市的有向图 G=(N, A)   其中N={1,2....n}   A={(i,j) | i,j\inN}
    • 城市之间的距离表示为  (d_{ij})_{n*n}   即节点 i 和节点 j 的距离
    • 目标函数  f(w)=\sum_{l=1}^{n}d_{i_{l}-1}d_{i_{l}}     目标函数是每个城市都经过一次的总路程,i1,i2 表示第一个和第二个到达的城市。
    • w=(i1,i2, ...in)  为城市1,2...n  的一个排列(即TSP问题任意可行解)。

    路径构建

    首先呢我们将m只蚂蚁随机放置在n个城市上,我们需要让蚂蚁去移动,那么就要计算蚂蚁选择移动的下一个城市的概率,位于城市 i 的第 k 只蚂蚁选择下一个城市 j 的概率为:

    公式分析: 蚂蚁选择下一个城市的概率是与信息素成正比的,信息素浓度越大被选择的几率越大。城市之间的距离越短,被选择的几率越大。选择因素有权重,引入了次幂\alpha \beta

    • \tau _{ij}(t)  表示时间 t 时刻,边(i,j)上的信息素浓度
    • \eta _{ij}=1/d_{ij}  根据距离定义的启发信息
    • \alpha \beta 为两个常数,反映信息素和启发信息的相对重要性
    • allowed 为尚未访问的节点集合

    信息素更新

    通过上面的式子可以观察到城市之间的距离事固定的,所以如果信息素也不变,则每只蚂蚁到达同一个城市后的选择都是一样的了,这不是我们目的,所以需要更新概率则只能更新\tau _{i,j}(t)(信息素)

    • 在算法初始化时,问题空间中所有的边上的信息素都被初始化为C。  注:C太小,算法容易早熟,会快速进入局部最优,反之,信息素对搜索方向的指导作用太低。
    • 每一轮过后,问题空间中的所有路径上的信息素都会发生蒸发。信息素蒸发是自然界本身固有的特征,在算法中能够帮助避免信息素的无限积累,使得算法可以快速丢弃之前构建过的较差的路径。
    • 所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素,蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。

    当所有的蚂蚁都经过了所有的城市,则开始进行信息素的更新,按照以下公式:

    • Q 为常数,  w_{k} 表示第 k 只蚂蚁在本轮迭代走过的路径,L_{k} 为路径长度, \rho 为小于1 的常数,反映信息素的挥发速度
    • Q/L_{k} 表示第 k 只蚂蚁在该路径上留下的平均信息素

     公式分析:信息素更新理解为,这一刻  ij  路径上的信息素浓度等于上一刻的信息素浓度乘以挥发速度\rho ,再加上上一时间段内所有蚂蚁在该路径上释放的的信息素浓度之和。


    算法测试

    测试代码

    clc;clear;
    t0=clock;   %用于计时
    %% 初始化城市信息
    n=30;                    %定义城市个数
    city=[(randperm(100,n))',(randperm(100,n))'];  %获取城市坐标  产生n个1-100的随机数,不重复
    figure('name','蚁群优化算法');
    plot(city(:,1),city(:,2),'o');  %描点   city--(30,2)
    for i=1:n
        text(city(i,1)+0.5,city(i,2),num2str(i));       %标号  
    end
    title('蚁群优化算法');
    %设置横纵坐标范围
    grid on     %网格线
    hold on     %图像保持而不被刷新
    
    %% 求出各个城市之间的距离
    D=zeros(n,n);         %新建一个n*n的矩阵存放距离
    for i=1:n
       for j=1:n
           if i~=j
               D(i,j)=sqrt(sum((city(i,:)-city(j,:)).^2));
           else
               D(i,j)=eps;     %设置成一个很小的数,但不能为0,因为后面分母中会用到
           end
       end
    end
    
    %% 初始化参数
    m=75;                   %蚂蚁数量
    alpha = 1;              %信息素重要程度因子
    beta = 5;               %启发函数重要程度因子
    rho = 0.2;              %信息素挥发因子
    Q=10;                   %常系数
    Eta = 1./D;             %启发函数(距离的倒数)
    Tau = ones(n,n);        %信息素矩阵(初始时每条路上的信息素都设为1)
    Table = zeros(m,n);     %路径记录表,记录m个蚂蚁走过的路径
    % iter = 1;               %迭代次数初值
    iter_max = 100;         %最大迭代次数
    Route_best = zeros(iter_max,n);     %各代最佳路径
    Length_best = zeros(iter_max,1);    %各代最佳路径的长度
    Length_ave = zeros(iter_max,1);     %各代路径的平均长度
    
    %% 迭代寻找最佳路径
    for iter=1:iter_max
        %随机产生蚂蚁的起点城市
        for i=1:m
           Table(i,1)=randperm(n,1);   %产生一个0-n=30 的随机数  75*30
        end
        citys_index=1:n;        %定义全部城市索引
        for i=1:m               %遍历所有蚂蚁
           for j=2:n            %遍历其他所有城市
               tabu=Table(i,1:(j-1));      %已访问城市(禁止访问表)
               allow=citys_index(~ismember(citys_index,tabu)); %除去已访问城市(待访问城市)
               P=allow;         %存放概率,定义成什么都可以,只要和allow长度一样
               %计算城市间的选择概率
               for k=1:length(allow)
                   %tabu(end)代表该蚂蚁此刻所在城市,allow(k)代表该蚂蚁即将去向的城市
                   P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;
               end
               P=P/sum(P);      %得到最终去往其他城市的概率集合
               Pc=cumsum(P);    %累计概率
               %轮盘赌选择下一个城市
               target_index=find(Pc>=rand);     %从累计概率中找出大于随机值的情况
               target=allow(target_index(1));   %取出第一个即为轮盘赌的结果
               Table(i,j)=target;               %确定第i只蚂蚁去往的第j-1个城市 
           end
        end
        %每只蚂蚁周游一遍后计算每只蚂蚁的路径长度
        Length=zeros(m,1);
        for i=1:m
            for j=1:(n-1)
                Length(i)=Length(i)+D(Table(i,j),Table(i,j+1));
            end
            %最后加上最后一个点回到起点的距离
            Length(i)=Length(i)+D(Table(i,n),Table(i,1));
        end
        %% 计算最短路径距离及平均距离
        [min_length,min_index]=min(Length);     %取出最短路径及其下标
        if iter==1
            Length_best(iter)=min_length;           %保存此次最短路径距离
        else
            Length_best(iter)=min(Length_best(iter-1),min_length);  %选择本次和上次中最短路径较小的
        end
        Route_best(iter,:)=Table(min_index,:);  %保存此次最短路线路径
        Length_ave(iter)=mean(Length);          %保存此次路线距离平均值
        
        %% 更新信息素
        Tau_Ant=Q./Length;          %每条蚂蚁在路径上留下的信息素浓度
        Tau_Temp=zeros(n,n);
        for i=1:m
            for j=1:n-1
                %更新信息素
                Tau_Temp(Table(i,j),Table(i,j+1))=Tau_Temp(Table(i,j),Table(i,j+1))+Tau_Ant(i);
            end
            %最后更新最后一个节点到起点的信息素
            Tau_Temp(Table(i,n),Table(i,1))=Tau_Temp(Table(i,n),Table(i,1))+Tau_Ant(i);
        end
        Tau=(1-rho)*Tau+Tau_Temp;   %信息素挥发后再加上新增的信息素
        Table = zeros(m,n);     %清空路线,进行下一轮周游
    end
    
    %% 命令行窗口显示结果
    [min_length,min_index]=min(Length_best);         %取出最短路径及其下标
    Finnly_Route=Route_best(min_index,:);
    last_time=etime(clock,t0);
    disp(['最短距离为:' num2str(min_length)]);
    disp(['最短路径为:' num2str(Finnly_Route)]);
    disp(['运行时间:' num2str(last_time) '秒']);
    
    %% 绘图
    plot([city(Finnly_Route,1);city(Finnly_Route,1)],...
         [city(Finnly_Route,2);city(Finnly_Route,2)],'bo-');  %描点
    text(city(Finnly_Route(1),1),city(Finnly_Route(1),2),'    起点');
    text(city(Finnly_Route(end),1),city(Finnly_Route(end),2),'    终点');
    
    figure(2);
    subplot(1,2,1);     %显示在一行两列图像中的第一列
    plot(Length_best);
    xlabel('迭代次数');
    ylabel('最短距离');
    title('最短距离收敛曲线');
    
    subplot(1,2,2);     %显示在一行两列图像中的第二列
    plot(Length_ave);
    xlabel('迭代次数');
    ylabel('平均距离');
    title('平均距离收敛曲线');

    总结:

    • 蚂蚁数量m;m过大时,会导致搜索过的路径上信息素变化趋于平均,难以找到目标路径;m过小时,易使未被搜索到的路径信息素减小到0,这样可能会出现早熟,找不到全局最优解。蚂蚁数设定为城市数量的1.5倍比较合适
    • 信息素重要程度因子alpha:信息素因子alpha反映了蚂蚁在移动过程中所积累的信息量在指导蚁群搜索中的相对重要程度,alpha值过大,蚂蚁选择以前走过的路径概率大,搜索随机性减弱;值过小,则会类似于贪婪算法,使搜索过与陷入局部最优。信息素因子大致选择在[1,4]区间
    • 启发函数重要程度因子beta;启发函数因子beta反映了启发式信息在指导蚁群搜索过程中的相对重要程度,其大小反映的是蚁群寻优过程中先验性和确定性因素的作用强度。beta过大时,虽然收敛速度会加快,但容易陷入局部最优;过小时,容易陷入随机搜索,找不到最优解。启发函数因子选择在[3,5]区间
    • 信息素挥发因子rho:信息素挥发因子表示信息素的消失水平,它的天小直接关系到蚁群算法的全局搜索能力和收敛速度。信息素挥发因子选择[0.2,0.5]区间

    算法改进思路



    精英策略的蚂蚁系统(Elitist Ant System, EAS)

    问题:当城市的规模较大时,问题的复杂度呈指数级增长,仅仅靠这样一个基础单一的信息素更新机制引导搜索偏向,搜索效率有瓶颈。

    方法:

    • 通过一种“额外的手段”强化某些最有可能成为最优路径的边,让蚂蚁的搜索范围更快、更正确的收敛。
    • 在算法开始后即对所有已发现的最好路径给予额外的增强,并将随后与之对应的行程记为Tb(全局最优行程);
    • 当进行信息素更新时,对这些行程予以加权,同时将经过这些行程的蚂蚁记为“精英”,从而增大较好行程的选择机会。

    信息素更新公式:

    \tau _{ij}(t+1) = \rho* \tau _{ij}(t)+\Delta\tau _{ij}+e*\Delta\tau _{ij}^{b}

    \Delta \tau _{ij}^{b}=\begin{cases} & \text{Qb/Cb}, (i,j)\in Tb\\ & \text{ 0 } otherwise \end{cases}

    特点:能快速的获得更好的解,如果选择的精英过多会较早收敛与局部最优解。


    基于排列的蚂蚁系统(Rank-based AS, ASrank )

    人们提出了在精英策略的基础上,对其余边的信息素更新机制加以改善

    • 与精英策略相似,总更新较好的路径上的信息素,选择标准是路程长度
    • 每只蚂蚁释放信息素的强度通过下列公式决定。

    \tau _{ij}(t+1) = \rho* \tau _{ij}(t)+\Delta\tau _{ij}+w*\Delta\tau _{ij}^{b} 

    \Delta \tau _{ij}=\sum_{k=1}^{w-1}(w-k)\Delta \tau _{ij}^{k}

    \Delta \tau _{ij}^{b}=\begin{cases} & \text{Q/C}, (i,j)\in R^{k}\\ & \text{ 0 } otherwise \end{cases}

    \Delta \tau _{ij}^{b}=\begin{cases} & \text{Qb/Cb}, (i,j)\in Tb\\ & \text{ 0 } otherwise \end{cases}

     注:w为每次迭代后释放信息素的蚂蚁总数,一般设置为6


    最大最小蚂蚁系统(MAX-MIN Ant System, MMAS)

    问题:

    • 大规模的TSP,由于搜索蚂蚁的个数有限,而初始化时蚂蚁的分布是随机的,这会不会造成蚂蚁只搜索了所有路径 中的小部分就以为找到了最好的路径,所有的蚂蚁都很快聚集在 同一路径上,而真正优秀的路径并没有被搜索到呢?
    • 当所有蚂蚁都重复构建着同一条路径的时候,意味着算法的已经进入停滞状态。此时不论是基本AS、EAS还是ASrank , 之后的迭代过程都不再可能有更优的路径出现。这些算法收敛的效果虽然是“单纯而快速的”,但我们都懂得欲速而不达的道理,我们有没有办法利用算法停滞后的迭代过程进一步搜索以保证找到更接近真实目标的解呢?

    对于最大最小蚂蚁系统

    • 该算法修改了AS的信息素更新方式,只允许迭代最优蚂蚁(在本次迭代构建出最短路径的蚂蚁),或者至今最优蚂蚁   释放信息素
    1. 借鉴于精华蚂蚁系统,但又有细微的不同。在EAS中,只允许至今最优的蚂蚁释放信息素,而在MMAS中,释放信息素的不仅有可能是至今最优蚂蚁,还有可能是迭代最优蚂蚁。
    2. 实际上,迭代最优更新规则和至今最优更新规则在MMAS中是交替使用的,这两种规则使用的相对频率将会影响算法的搜索效果。只使用至今最优更新规则进行信息素的更新,搜索的导向性很强,算法会很快的收敛到Tb附近,反之,如果只使用迭代最优更新规则,则算法的探索能力会得到增强,但搜索效率会下降。
    • 路径上的信息素浓度被限制在[min,max ]范围内
    1. 是为了避免某些边上的信息素浓度增长过快,出现算法早熟现象
    2. 蚂蚁是根据启发式信息和信息素浓度选择下一个城市的。启发式信息的取值范围是确定的。
    3. 当信息素浓度也被限定在一个范围内以后,位于城市i的蚂蚁k选择城市j作为下一个城市的概率pk(i,j)也将被限制在一个区间内。
    • 信息素的初始值被设为其取值上限,这样有助于增加算法初始阶段的搜索能力
    1. 使得算法在初始阶段,问题空间内所有边上的信息素均被初始化τmax的估计值,且信息素蒸发率非常小(在MMAS中,一般将蒸发率设为0.02)。
    2. 算法的初始阶段,不同边上的信息素浓度差异只会缓慢的增加,因此,MMAS在初始阶段有着较基本AS、EAS和ASrank更强搜索能力。
    3. 增强算法在初始阶段的探索能力有助于蚂蚁“视野开阔地”进行全局范围内的搜索,随后再逐渐缩小搜索范围,最后定格在一条全局最优路径上。

    之前的蚁群算法,包括AS、EAS以及ASrank,都属于“一次性探索”,即随着算法的执行,某些边上的信息素量越来越小,某些路径被选择的概率也越来越小,系统的探索范围不断减小直至陷入停滞状态。

    • 为了避免搜索停滞,问题空间内所有边上的信息素都会被重新初始化
    1. 当算法接近或者是进入停滞状态时,问题空间内所有边上的信息素浓度都将被初始化,从而有效的利用系统进入停滞状态后的迭代周期继续进行搜索,使算法具有更强的全局寻优能力。

    蚁群系统(Ant Colony System)

    上述EAS、ASrank 以及MMAS都是对AS进行了少量的修改而获得了更好的性能。1997年,蚁群算法的创始人Dorigo在Ant colony system:a cooperative learning approach to the traveling salesman problem一文中提出了一种新的具有全新机制的ACO 算法——蚁群系统,是蚁群算法发展史上的又一里程碑。

    ACS与AS之间存在三方面的主要差异

    • 使用一种伪随机比例规则选择下一个城市节点, 建立开发当前路径与探索新路径之间的平衡
    • 信息素全局更新规则只在属于至今最优路径的边上蒸发和释放信息素
    • 新增信息素局部更新规则,蚂蚁每次经过空间内的某条边,他都会去除该边上的一定量的信息素,以增加后续蚂蚁探索其余路径的可能性。

    状态转移规则

    一只蚂蚁从节点 i 到下一个节点遵循以下规则(伪随机比例规则)

    j=arg\max_{allowed}{ [\tau_{ij} *\eta_{ij}^{\beta }]} ---if q<q_{0} 

    j=p_{ij}^{k}(t)

    •  q 是【0,1】区间均匀分布的随机数
    • q_{0} 的大小决定了利用先验只是与探索新路径之间的相对重要性

    信息素全局更新规则

    • ACS  只增强属于全局最优解的路径上的信息素,更新公式如下:

    \tau _{ij}(t+1) =(1-\rho)* \tau _{ij}(t)+\rho *\Delta\tau _{ij}^{b}

    \Delta \tau _{ij}^{b}=\begin{cases} & \text{Qb/Cb}, (i,j)\in Tb\\ & \text{ 0 } otherwise \end{cases}

    • 注:0<\rho<1 是信息素的挥发参数,Cb是从寻找开始到当前为止全局最优的路径长度

    信息素局部更新规则

    • 引入了负反馈机制,每当一只蚂蚁从一个节点移动到另一个节点时,该路径上的信息素都按照如下公式被相应的消除一部分,实现信息素的局部调整,减小已选择过的路径再次被选择的概率

    \tau _{ij}(t+1) =(1-\xi )* \tau _{ij}(t)+\xi *\tau _{0}


    小白一个,参照多篇,自我总结,侵删(私聊我),勿喷!!!

    展开全文
  • 这是本科毕业设计,使用matlab在20乘以20的栅格地图中实现路径规划,包括静态环境...程序可以成功运行,地图可以手动修改,在这里还有自适应改变信息素挥发因数的改进方案,有很多子程序,注释非常详细,希望对你有用
  • 针对传统蚁群算法在移动机器人路径规划问题中存在的易陷入局部最优与收敛速度慢等问题,提出 一种改进的蚁群算法。首先根据起点到终点距离和地图参数构建全局优选区域,提高该区域内初始信息素浓 度,避免算法初期...
  • 蚁群分泌的信息素存在正反馈,使得较佳的解具有大概率被选到,当全局都选用较佳的解,变可以得到整体的最优解。2几个关键点:1) 概率选择:受信息素浓度和启发函数影响,启发函数为距离的倒数2)信息素挥发考虑到信息...
  • 蚁群算法求解旅行商问题,课后作业ddddddddddd
  • 提出一种全局静态环境下移动机器人路径规划的改进势场蚁群算法.该算法采用人工势场法求得的初始路径和机器人与下一个节点之间的距离综合构造启发信息,并引入启发信息递减系数,避免了传统蚁群算法由于启发信息误导所...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,352
精华内容 940
关键字:

蚁群算法信息素更新