精华内容
下载资源
问答
  • 蚁群算法的简单理解
    千次阅读
    2019-12-06 21:01:29

    蚁群优化算法是意大利学者等人在世纪年代初提出的一种源于生物世界的新型启发式仿生算法。它是从自然界中蚂蚁觅食过程的协作方式得到启发而研究产生的。

    在自然界中,蚁群可以在其觅食的过程中逐渐寻找到食物源与巢穴之间的最短路径。单个蚂蚁在运动过程中能够分泌出一种被称作信息素的化学物质,这种物质能够被蚂蚁所感知,并分辨出其浓度,以此来指导自己倾向于朝着信息素强度高的方向运动。这种倾向是概率的,信息素浓度越高,概率越高,但蚂蚁仍然有可能选择信息素浓度低的路径。这样当外部条件改变,出现一条新的更短的路径的时候,蚁群不会因为一条路径上的高信息素浓度而放弃发现更短的路径。路径上的信息素浓度会被蒸发,当路径上长时间无蚂蚁经过,信息素浓度会自然降低。通过信息素,蚁群在觅食过程中就表现出一种复杂的正反馈现象。蚂蚁个体之间通过信息素进行间接的通信和协作。当某条路径相对其他路径长度越短时,该路径上单位时间内经过的蚂蚁就会越多,该路径上积累的信息素也就越多。而较多的信息素会引导更多的蚂蚁选择这条路径。更多的蚂蚁选择这条路径并经过后又会在该路径上积累更多的信息素,如此循环反复,就使得最后大多数蚂蚁都选择相同的且较短的路径。因而当路径的长度互不相同时,蚂蚁最终会收敛到较短的路径上。但即使路径长度相同,也会由于信息的积累速度不同而引导蚂蚁倾向于其中的一条路径,但其收敛的速度会变慢。

    蚁群优化算法就是根据蚁群觅食活动时表现出来的规律,建立的一个利用群体智能进行相互协作,优化搜索的模型。虽然每个个体智能有限,能力很低,但通过群体的高效协作可以解决对于个体而言无法解决的问题。相对于其它的各类智能启发式搜索算法,蚁群算法具有其独特的优越性。它在一系列完全组合优化问题的求解中取得了卓有成效的结果,其中的典型代表有旅行商问题、指派问题以及作业调度等经典组合优化问题。

    简单来说:

    1、蚂蚁在运动过程中可以分泌信息素,且蚂蚁个体之间通过信息素进行间接的通信和协作;

    2、信息素可以被其他蚂蚁识别,且蚂蚁通过概率朝着高浓度的信息素的方向前进(一种正反馈现象);

    3、信息素会被蒸发,若长时间没有蚂蚁经过,信息素将会降低。

    蚁群算法的基本原理:

    其协作方式的本质是

    ①信息素浓度越浓的路径,被蚂蚁选中的概率也就越大,即蚂蚁路径概率选择机制,这是蚁群搜索求解的基础机制;

    ②如果路径越短,那么路径上面的信息素就积累得越快,浓度也就会增长得越快,这是蚁群信息素的更新机制;

    ③蚂蚁能够感应到信息素浓度的不同,蚂蚁之间通过信息素进行通信,告诉其他蚂蚁自己走过的路径,即蚁群协同工作机制。

    蚁群寻找食物的流程:

    A为食物源;E为蚁穴;d为所需要的时间。

    一开始在T=0的时刻,A和E同时出发了30只蚂蚁,由于路上都没有信息素的存在,15只蚂蚁走了BF,15只走了BC,15只蚂蚁走了DF,15只走了DC。在T=1的时刻,从A出发走BC->CD的蚂蚁已经到达了蚁穴,而另一边仅仅走到了一半,并且从E出发走DC->CB的蚂蚁也走到了食物源。在这个时刻BC和CD上的信息素就是另一边的两倍了(因为路径短蚂蚁已经到达终点)。在下一个时刻出发的蚂蚁则会根据信息素的浓度,来选择自身出发的方向。由于蚂蚁选择方向是依据信息素,但不完全依靠信息素。仅仅只会更倾向走向信息素浓度高的方向,但是依旧有可能走向浓度低的反向。所以第三幅图选择不同的方向的比重就不一样。

    蚁群优化算法在优化过程中有两个重要的行为规则

    1、蚂蚁对众多可行路径的选择规则:蚂蚁总是倾向于选择信息素浓度更高的路径。但这是概率的,信息素浓度低的路径也有被选择的可能。蚁群算法中的信息素类似于一种分布式的长期记忆,这种记忆不是局部地存储在于单个的人工蚂蚁上,而是全局地分布在整个问题空间里,是由整个蚁群共同协作形成的。信息素为蚁群中的蚂蚁提供了一种间接联络的方式。

    2、全局信息素更新规则:在路径上的信息素,会随着时间的推移而逐步蒸发散失,路径上的信息素浓度会自然降低,这样没有被选择过的或较少被选择的路径上的信息素会越来越少,该路径会变得越来越不受蚂峡欢迎。每只蚂蚁可以按照路径的长短,或者是找到的食物的质量,在其经过的路径上留下相应数量的信息素。全局信息素更新规则的实质,是人工蚂蚁根据真实蚂蚁在访问过的路径上会留下信息素,以及信息素的自然蒸发过程,模拟出来的信息素更新机制,它会使得越好的解会得到越多的增强,越受蚂蚁的青睐。

    蚁群算法内的参数设置:

    m:蚂蚁数量,约为城市数量的1.5倍。如果蚂蚁数量过大,则每条路径上的信息素浓度趋于平均,正反馈作用减弱,从而导致收敛速度减慢;如果过小,则可能导致一些从未搜索过的路径信息素浓度减小为0,导致过早收敛,解的全局最优性降低;

    α:信息素因子,反映了蚂蚁运动过程中积累的信息量在指导蚁群搜索中的相对重要程度,取值范围通常在[1, 4]之间。如果信息素因子值设置过大,则容易使随机搜索性减弱;其值过小容易过早陷入局部最优;

    β:启发函数因子,反映了启发式信息在指导蚁群搜索中的相对重要程度,取值范围在[3, 4.5]之间。如果值设置过大,虽然收敛速度加快,但是易陷入局部最优;其值过小,蚁群易陷入纯粹的随机搜索,很难找到最优解;

    ρ:信息素挥发因子,反映了信息素的消失水平,相反的反映了信息素的保持水平,取值范围通常在[0.2, 0.5]之间。当取值过大时,容易影响随机性和全局最优性;反之,收敛速度降低;

    Q:信息素常数,表示蚂蚁遍历一次所有城市所释放的信息素总量。越大则收敛速度越快,但是容易陷入局部最优;反之会影响收敛速度。

    我从网上博客找了段代码 (菜菜的我还是写不出来…

    # -*- coding: utf-8 -*-
    """ 
    Created on Wed Jun 16 15:21:03 2018 
    @author: SYSTEM 
    """
    import os
     
    os.getcwd()
    #返回当前工作目录
    import numpy as np
    import matplotlib.pyplot as plt
    # % pylab
    #初始化城市坐标,总共52个城市
    coordinates = np.array([[565.0, 575.0], [25.0, 185.0], [345.0, 750.0], [945.0, 685.0], [845.0, 655.0],
                            [880.0, 660.0], [25.0, 230.0], [525.0, 1000.0], [580.0, 1175.0], [650.0, 1130.0],
                            [1605.0, 620.0], [1220.0, 580.0], [1465.0, 200.0], [1530.0, 5.0], [845.0, 680.0],
                            [725.0, 370.0], [145.0, 665.0], [415.0, 635.0], [510.0, 875.0], [560.0, 365.0],
                            [300.0, 465.0], [520.0, 585.0], [480.0, 415.0], [835.0, 625.0], [975.0, 580.0],
                            [1215.0, 245.0], [1320.0, 315.0], [1250.0, 400.0], [660.0, 180.0], [410.0, 250.0],
                            [420.0, 555.0], [575.0, 665.0], [1150.0, 1160.0], [700.0, 580.0], [685.0, 595.0],
                            [685.0, 610.0], [770.0, 610.0], [795.0, 645.0], [720.0, 635.0], [760.0, 650.0],
                            [475.0, 960.0], [95.0, 260.0], [875.0, 920.0], [700.0, 500.0], [555.0, 815.0],
                            [830.0, 485.0], [1170.0, 65.0], [830.0, 610.0], [605.0, 625.0], [595.0, 360.0],
                            [1340.0, 725.0], [1740.0, 245.0]])
     
    #计算52个城市间的欧式距离
    def getdistmat(coordinates):
        num = coordinates.shape[0]
        distmat = np.zeros((52, 52))
        # 初始化生成52*52的矩阵
        for i in range(num):
            for j in range(i, num):
                distmat[i][j] = distmat[j][i] = np.linalg.norm(coordinates[i] - coordinates[j])
        return distmat
    #返回城市距离矩阵
     
     
    distmat = getdistmat(coordinates)
     
    numant = 60  # 蚂蚁个数
    numcity = coordinates.shape[0]
    # shape[0]=52 城市个数,也就是任务个数
    alpha = 1  # 信息素重要程度因子
    beta = 5   # 启发函数重要程度因子
    rho = 0.1  # 信息素的挥发速度
    Q = 1      # 完成率
     
    iter = 0       #迭代初始
    itermax = 150  #迭代总数
     
    etatable = 1.0 / (distmat + np.diag([1e10] * numcity))
    #diag(),将一维数组转化为方阵 启发函数矩阵,表示蚂蚁从城市i转移到城市j的期望程度
    pheromonetable = np.ones((numcity, numcity))
    # 信息素矩阵 52*52
    pathtable = np.zeros((numant, numcity)).astype(int)
    # 路径记录表,转化成整型 40*52
    distmat = getdistmat(coordinates)
    # 城市的距离矩阵 52*52
     
    lengthaver = np.zeros(itermax)  # 迭代50次,存放每次迭代后,路径的平均长度  50*1
    lengthbest = np.zeros(itermax)  # 迭代50次,存放每次迭代后,最佳路径长度  50*1
    pathbest = np.zeros((itermax, numcity))  # 迭代50次,存放每次迭代后,最佳路径城市的坐标 50*52
     
    while iter < itermax:
        #迭代总数
     
        #40个蚂蚁随机放置于52个城市中
        if numant <= numcity:  # 城市数比蚂蚁数多,不用管
            pathtable[:, 0] = np.random.permutation(range(numcity))[:numant]
            #返回一个打乱的40*52矩阵,但是并不改变原来的数组,把这个数组的第一列(40个元素)放到路径表的第一列中
            #矩阵的意思是哪个蚂蚁在哪个城市,矩阵元素不大于52
        else:  # 蚂蚁数比城市数多,需要有城市放多个蚂蚁
            pathtable[:numcity, 0] = np.random.permutation(range(numcity))[:]
            # 先放52个
            pathtable[numcity:, 0] = np.random.permutation(range(numcity))[:numant - numcity]
            # 再把剩下的放完
            # print(pathtable[:,0])
        length = np.zeros(numant)  # 1*40的数组
     
        #本段程序算出每只/第i只蚂蚁转移到下一个城市的概率
        for i in range(numant):
     
            # i=0
            visiting = pathtable[i, 0]  # 当前所在的城市
            # set()创建一个无序不重复元素集合
            # visited = set() #已访问过的城市,防止重复
            # visited.add(visiting) #增加元素
            unvisited = set(range(numcity))
            #未访问的城市集合
            #剔除重复的元素
            unvisited.remove(visiting)  # 删除已经访问过的城市元素
     
            for j in range(1, numcity):  # 循环numcity-1次,访问剩余的所有numcity-1个城市
                # j=1
                # 每次用轮盘法选择下一个要访问的城市
                listunvisited = list(unvisited)
                #未访问城市数,list
                probtrans = np.zeros(len(listunvisited))
                #每次循环都初始化转移概率矩阵1*52,1*51,1*50,1*49....
     
     
                #以下是计算转移概率
                for k in range(len(listunvisited)):
                    probtrans[k] = np.power(pheromonetable[visiting][listunvisited[k]], alpha) \
                                   * np.power(etatable[visiting][listunvisited[k]], alpha)
                #eta-从城市i到城市j的启发因子 这是概率公式的分母   其中[visiting][listunvis[k]]是从本城市到k城市的信息素
                cumsumprobtrans = (probtrans / sum(probtrans)).cumsum()
                #求出本只蚂蚁的转移到各个城市的概率斐波衲挈数列
     
                cumsumprobtrans -= np.random.rand()
                # 随机生成下个城市的转移概率,再用区间比较
                # k = listunvisited[find(cumsumprobtrans > 0)[0]]
                k = listunvisited[list(cumsumprobtrans > 0).index(True)]
                # k = listunvisited[np.where(cumsumprobtrans > 0)[0]]
                # where 函数选出符合cumsumprobtans>0的数
                # 下一个要访问的城市
     
                pathtable[i, j] = k
                #采用禁忌表来记录蚂蚁i当前走过的第j城市的坐标,这里走了第j个城市.k是中间值
                unvisited.remove(k)
                # visited.add(k)
                #将未访问城市列表中的K城市删去,增加到已访问城市列表中
     
                length[i] += distmat[visiting][k]
                #计算本城市到K城市的距离
                visiting = k
     
            length[i] += distmat[visiting][pathtable[i, 0]]
            # 计算本只蚂蚁的总的路径距离,包括最后一个城市和第一个城市的距离
     
        # print("ants all length:",length)
        # 包含所有蚂蚁的一个迭代结束后,统计本次迭代的若干统计参数
     
        lengthaver[iter] = length.mean()
        #本轮的平均路径
     
     
     
        #本部分是为了求出最佳路径
     
        if iter == 0:
            lengthbest[iter] = length.min()
            pathbest[iter] = pathtable[length.argmin()].copy()
        #如果是第一轮路径,则选择本轮最短的路径,并返回索引值下标,并将其记录
        else:
        #后面几轮的情况,更新最佳路径
            if length.min() > lengthbest[iter - 1]:
                lengthbest[iter] = lengthbest[iter - 1]
                pathbest[iter] = pathbest[iter - 1].copy()
            # 如果是第一轮路径,则选择本轮最短的路径,并返回索引值下标,并将其记录
            else:
                lengthbest[iter] = length.min()
                pathbest[iter] = pathtable[length.argmin()].copy()
     
     
        #此部分是为了更新信息素
        changepheromonetable = np.zeros((numcity, numcity))
        for i in range(numant):#更新所有的蚂蚁
            for j in range(numcity - 1):
                changepheromonetable[pathtable[i, j]][pathtable[i, j + 1]] += Q / distmat[pathtable[i, j]][pathtable[i, j + 1]]
                #根据公式更新本只蚂蚁改变的城市间的信息素      Q/d   其中d是从第j个城市到第j+1个城市的距离
            changepheromonetable[pathtable[i, j + 1]][pathtable[i, 0]] += Q / distmat[pathtable[i, j + 1]][pathtable[i, 0]]
            #首城市到最后一个城市 所有蚂蚁改变的信息素总和
     
        #信息素更新公式p=(1-挥发速率)*现有信息素+改变的信息素
        pheromonetable = (1 - rho) * pheromonetable + changepheromonetable
     
        iter += 1  # 迭代次数指示器+1
        print("this iteration end:",iter)
        # 观察程序执行进度,该功能是非必须的
        if (iter - 1) % 20 == 0:
            print("schedule:",iter - 1)
    #迭代完成
     
     
     
    #以下是做图部分
    #做出平均路径长度和最优路径长度
    fig, axes = plt.subplots(nrows=2, ncols=1, figsize=(12, 10))
    axes[0].plot(lengthaver, 'k', marker='*')
    axes[0].set_title('Average Length')
    axes[0].set_xlabel(u'iteration')
     
    #线条颜色black https://blog.csdn.net/ywjun0919/article/details/8692018
    axes[1].plot(lengthbest, 'k', marker='<')
    axes[1].set_title('Best Length')
    axes[1].set_xlabel(u'iteration')
    fig.savefig('Average_Best.png', dpi=500, bbox_inches='tight')
    plt.close()
    fig.show()
     
    # 作出找到的最优路径图
    bestpath = pathbest[-1]
     
    plt.plot(coordinates[:, 0], coordinates[:, 1], 'r.', marker='>')
    plt.xlim([-100, 2000])
    #x范围
    plt.ylim([-100, 1500])
    #y范围
     
    for i in range(numcity - 1):
        #按坐标绘出最佳两两城市间路径
        m, n = int(bestpath[i]), int(bestpath[i + 1])
        print("best_path:",m, n)
        plt.plot([coordinates[m][0],coordinates[n][0]],   [coordinates[m][1], coordinates[n][1]],  'k')
     
    plt.plot([coordinates[int(bestpath[0])][0],coordinates[int(bestpath[51])][0]],    [coordinates[int(bestpath[0])][1],coordinates[int(bestpath[50])][1]]   ,'b')
     
    ax = plt.gca()
    ax.set_title("Best Path")
    ax.set_xlabel('X_axis')
    ax.set_ylabel('Y_axis')
     
    plt.savefig('Best Path.png', dpi=500, bbox_inches='tight')
    plt.close()
    # 代码来自https://blog.csdn.net/quinn1994/article/details/80324308

     

     

    记录一下,共勉。

    更多相关内容
  • 信息素更新上面对于蚁群算法所做出的改进,
  • 通过分析现有蚁群算法信息素更新模型陷入局部最优的原因,借鉴蚁群模型退火算法思想,根据假设推导出增幅递减信息素更新模型,分析该模型对算法复杂度的影响,并分别采用4 种信息素更新模型求解最短路问题。...
  • 针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。 定义 各个蚂蚁在没有事先告诉他们食物在什么...
  • 路径规划,蚁群算法
  • 为了避免蚁群算法陷入停滞状态,研究了信息素的更新规则,并在信息素增量更新式中加入动态调节因子,使得次优路径上的信息素增量较大,其他路径则没有明显的变化,从而有利于蚂蚁在较短的时间内找到更好的解。...
  • 蚁群算法

    千次阅读 2019-11-05 10:05:16
    蚁群算法是受到蚂蚁觅食过程中表现的智能行为的启发,蚂蚁在觅食过程中会释放一种叫“信息素”的物质,同时蚂蚁会沿着“信息素”浓度高的位置走,最后大部分蚂蚁都能沿着最短觅食路径走。 二、算法流程 以TSP问题为...

    一、基本思想

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

    二、算法流程

    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] 蚁群算法

    展开全文
  • 对于蚁群算法做出的改进,按信息素大小进行排序
  • 利用人工蚁群算法解决多城市间的TSP问题,信息素的更新等。
  • 对于基本蚁群算法(ACA)不适用求解连续空间问题,并且极易陷入局部最优的缺点,提出了一种基于自适应的蚁群算法。路径搜索策略采用基于目标函数值搜索筛选局部最优解的策略,确保能够迅速找到可行解。信息素更新...
  • 蚁群算法详解讲解

    2022-04-09 22:24:43
    0x01 蚁群效应 《昆虫记》中这样描述红蚂蚁:红蚂蚁出征的远近取决于黑蚂蚁家的远近,它们出征的道路并不选择,也没有明确的目的地。除了水路之外,它们都能穿过 单个蚂蚁不存在有规律的、复杂...在理解蚁群算法

    0x01 蚁群效应

    《昆虫记》中这样描述红蚂蚁:
    红蚂蚁出征的远近取决于黑蚂蚁家的远近,它们出征的道路并不选择,也没有明确的目的地。除了水路之外,它们都能穿过

    单个蚂蚁不存在有规律的、复杂的行为体系,较大的不确定性和随机性使单个蚂蚁不具备训练条件,一个庞大的蚁群可以看作一个完备的系统,分工明确,行为轨迹可分析,蚁群效应主要用于管理层面,蚁群具有明确分工和严谨的组织框架

    但蚁群算法使用的分析结构和蚁群效应不同

    0x02 Traveling salesman problem

    在理解蚁群算法时,可以以旅行推销员问题(Traveling salesman problem)为例,这里简称TSP,TSP给出了不同的城市地点以及城市之间的距离,目的是为了找到最近的路线可以穿过所有的城市,并且每个城市只去一次

    imageAddress: https://www.geeksforgeeks.org/wp-content/uploads/Euler12.png

    Traveling salesman problem 与 Hamiltonian path 的区别:
    Hamiltonian path 是一个cycle(圆形),现在又被称为 Hamilton's puzzle,是找到是否有一个环是可以实现每个地点走一次,但是 TSP 的目的是找出是否有一个最短的环

    0x03 蚁群算法

    蚁群算法(Ant Colony Optimization),在很多资料中也被称为蚁群优化算法,是一种基于种群的元启发式算法,可用于找到困难优化问题的近似解

    蚁群中的蚂蚁可以通过某种信息机制进行信息传递,这种信息机制称为“信息素”


    Photo by Maksim Shutov on Unsplash

    信息素,也称做外激素,指的是由一个个体分泌到体外,被同物种的其他个体通过嗅觉器官(如副嗅球、犁鼻器)察觉,使后者表现出某种行为,情绪,心理或生理机制改变的物质。它具有通讯功能。几乎所有的动物都证明有信息素的存在。1959年发表雌蚕蛾会分泌性信息素,是科学界首次证明了性信息素是存在的。

    蚂蚁会在移动的过程中释放一种称之为“信息素”的物质,其他蚂蚁会对“信息素”具有感知能力,它们会沿着“信息素”浓度较高的路径行走,而每只路过的蚂蚁都会在路上留下“信息素”,这就形成了一种类似正反馈的机制,这样经过一段时间后,整个蚁群就会沿着最短路径到达食物源了

    信息素值在运行时被修改,并表示蚁群的累积经验,而启发式值则是问题相关值,在TSP的情况下,启发式值被设置为边缘长度的倒数

    蚁群效应认知步骤

    1. 这些蚂蚁在开始前随意选择地点
    2. 在每个构造步骤中,它沿着图的边缘移动
    3. 每个蚂蚁都能记住自己的运行轨迹,在接下来的移动中,它会选择那些不通向它已经访问过的顶点的边
    4. 蚂蚁一旦访问了图的所有顶点,就构造了一个解,在每一个构建步骤中,蚂蚁会在那些通向尚未访问的顶点的边缘中概率地选择要跟随的边
    5. 概率规则受到信息素值和启发式信息的影响,信息素值和启发式值越高,蚂蚁选择这条边的概率就越高
    6. 一旦所有的蚂蚁完成了它们的旅行,边缘上的信息素就会更新
    7. 每一种信息素值最初都以一定的百分比下降
    8. 随后,每条边接收到的额外信息素数量与它所属的解决方案的质量成正比

    总结一下就是:
    路径较短的蚂蚁释放的信息素量较多,随着时间的推进,较短的路径上累积的信息素浓度逐渐增高,选择该路径的蚂蚁个数也愈来愈多

    0x04 蚁群算法规则

    1. 感知范围
      蚂蚁观察到的范围是一个方格世界,相关参数为速度半径,一般为3,可观察和移动的范围为3x3方格
    2. 环境信息
      蚂蚁所在环境中有障碍物、其他蚂蚁、信息素,其中信息素包括食物信息素、窝信息素,信息素以一定速率消失
    3. 觅食规则
      蚂蚁在感知范围内寻找食物,如果感知到就会过去;否则朝信息素多的地方走,每只蚂蚁会以小概率犯错误,并非都往信息素最多的方向移动。蚂蚁找窝的规则类似,仅对窝信息素有反应
    4. 移动规则
      蚂蚁朝信息素最多的方向移动,当周围没有信息素指引时,会按照原来运动方向惯性移动,而且会记住最近走过的点,防止原地转圈
    5. 避障规则
      当蚂蚁待移动方向有障碍物时,将随机选择其他方向,当有信息素指引时,将按照觅食规则移动
    6. 散发信息素规则
      在刚找到食物或者窝时,蚂蚁散发的信息素最多,当随着走远时,散发的信息素将逐渐减少

    0x05 蚁群算法特点

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

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

    0x04 组合优化问题的形式化定义

    将蚁群算法应用于组合优化问题(COP)的第一步是将COP模型定义为三元组(S,Ω,ƒ),其中:

    • S:在有限的离散决策变量集上定义的搜索空间
    • Ω:变量之间的约束的集合
    • ƒ:


      是一个需要最小化的目标函数

    搜索空间S的定义如下:
    一组离散变量 Xi(1,...,n)


    S的元素是完整的赋值,即每个变量Xi都有一个从Di域中赋值的vji值
    可行解集 SΩ 由 S 中满足集合Ω中所有约束条件的元素给出

    解 s ∈ SΩ ,当下面的式子成立时,s为最优解

    所有全局最优解的集合表示为

    解决COP问题至少需要找到一个

    (COP就是组合优化问题)

    0x05 蚁群优化元启发式算法

    在蚁群算法中,人工蚂蚁通过遍历全连通构造图来求解组合优化问题,定义如下:

    1. 首先,每个实例化的决策变量 Xi=vji 被称为一个解决方案组件,并由cij表示
    2. 所有可能的解决方案组件的集合用 C 表示
    3. 构造图 GC(V,E) 通过将组件 C 与顶点 V 集或边 E 集关联来定义

    信息素trail值 τij 与各组分 cij 相关。
    (注意,信息素值通常是算法迭代t的函数,τij=τij(t))

    信息素值允许对解决方案的不同组分的概率分布进行建模,蚁群算法在搜索过程中使用并更新信息素值

    蚁群超启发式

    Set parameters, initialize pheromone trails
    SCHEDULE_ACTIVITIES
      ConstructAntSolutions
      DaemonActions    {optional}
      UpdatePheromones
    END_SCHEDULE_ACTIVITIES

    最著名的规则是蚂蚁系统(AS)的规则(Dorigo et al. 1991, 1996):

    守护进程的行为

    一旦建立了解决方案,在更新信息素值之前,通常可能需要一些问题的具体行动,这些操作通常被称为守护进程操作
    可以用于实现特定于问题的和/或集中的操作,这些操作不能由单个蚂蚁执行

    最常用的守护进程操作包括对构造的解决方案进行局部搜索,然后使用局部优化的解决方案来决定要更新哪些信息素值

    更新信息素

    信息素更新的目的是增加与好的解决方案相关的信息素值,并减少与坏的解决方案相关的信息素值
    这是通过(i)通过信息素蒸发来降低所有信息素值,和(ii)通过选择一组好的解决方案来增加信息素水平Supd:

    Supd:用于更新信息素的解集
    ρ∈(0,1]:蒸发速率

    信息素的蒸发实现了一种有用的遗忘形式,有利于探索搜索空间中的新领域
    不同的蚁群算法,例如蚁群系统(ACS) (Dorigo & Gambardella 1997)或MAX-MIN蚂蚁系统(MMAS) (Stützle & Hoos 2000),更新信息素的方式不同。

    0x06 主要ACO算法

    这里概述了三个最成功的系统:

    • 蚂蚁系统 Ant system
      (Dorigo 1992, Dorigo et al. 1991, 1996)
    • 蚁群系统 Colony system
      (ACS) (Dorigo & Gambardella 1997)
    • MAX-MIN蚂蚁系统 MAX-MIN ant system
      (MMAS) (Stützle & Hoos 2000)

    为了清楚地说明它们之间的区别,使用旅行推销员问题的例子

    Ant system

    蚁群算法(Ant system, AS)是文献中提出的第一个蚁群算法(Dorigo et al. 1991, Dorigo 1992, Dorigo et al. 1996)
    特点:所有完成的蚂蚁都会更新信息素值

    求解分量cij为图的边,τij的信息素更新,即连接边城市i和j的信息素更新如下:

    ρ∈(0,1]:蒸发速率
    m:蚂蚁🐜的数量


    :第k只蚂蚁在边缘放置的信息素的数量

    Lk:第k只蚂蚁的旅行长度

    蚁群在构造解时,遍历构造图,并在每个顶点进行概率决策

    第k只蚂蚁从城市i到城市j的转移速率

    Ant colony system

    最初提出的蚂蚁系统的第一个重大改进是Dorigo和Gambardella(1997)引入的蚁群系统(ACS)
    ACS和AS之间的第一个重要区别是蚂蚁在构建过程中使用的决策规则的形式

    ACS中的蚂蚁使用所谓的伪随机比例规则:蚂蚁从城市i移动到城市j的概率取决于一个均匀分布在[0,1]上的随机变量q和一个参数q0
    当q≤q0时,在可行分量中,选择使

    乘乘积最大化的分量,否则,使用与as中相同的方程

    这一贪心的规则有利于信息素信息的利用,通过引入一个多样化的组件:局部信息素更新来抵消这一规则
    每一步构建完成后,所有蚂蚁都进行局部信息素更新。每只蚂蚁只将它应用于最后一条经过的边

    ρ∈(0,1]:信息素衰变系数
    τ0:信息素的初始值

    本地更新的主要目标是使后续蚂蚁在一次迭代中执行的搜索多样化
    在一次迭代中,降低边缘上的信息素浓度会鼓励随后的蚂蚁选择其他边缘,从而产生不同的解决方案
    这使得在一次迭代中,几只蚂蚁不太可能产生相同的解决方案,由于ACS中信息素的局部更新,使得信息素的最小值受到限制

    与As一样,ACS也在构建过程的最后执行信息素更新,称为离线信息素更新

    根据公式,ACS离线信息素更新仅由最优蚂蚁执行,即仅更新被最优蚂蚁访问过的边

    ACS引入的大部分创新都是在Ant-Q中首先引入的,Ant-Q是ACS的一个初步版本,由同一作者提出

    MAX-MIN ant system

    MAX-MIN蚂蚁系统(MMAS)是由Stützle和Hoos(2000)提出的对原始蚂蚁系统思想的另一种改进
    MMAS与AS的不同之处在于:

    1. 只有最好的蚂蚁信息素轨迹补充道
    2. 最小值和最大值的信息素是显式有限(在ACS这些值是有限的隐式,即限制的值是一个结果的算法工作而不是一套价值明确的算法设计)。

    信息素更新方程的形式如下:

    当最优的蚂蚁使用边(i,j)时,

    :最优蚂蚁的路线长度
    在ACS中,Lbest可以(根据算法设计者的决定)设置为Lib或Lbs,或两者的组合il;

    References
    https://www.jianshu.com/p/6d16573ef675
    http://www.scholarpedia.org/article/Ant_colony_optimization
    展开全文
  • 每只蚂蚁在构造出一条从起点到终点的路径后,蚁群算法还要求根据路径的总长度来更新这条路径所包含的每条边上信息素的浓度(在旅行商问题中每座城市是图中的一个节点,城市两两间有一条边相连)。下面给出了蚁群...

    信息素的局部更新策略  

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

    .

      上面的第一个公式体现了信息素的更新值的计算,其中,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个缺点:消耗时间长、蚂蚁在下次搜索时目标导向不强导致搜索随机性大、寻优路径上的信息素过度增强导致得到假的最优解。本文提出了基于边缘初始化和自适应全局信息素的...
  • 基于蚁群算法的 TSP 求解,分别采用蚁群算法蚁群算法-粒子群混合算法进行优化求解,使用不同的交叉和变异适应度函数更新粒子,从而实现 TSP问题的优化求解,更加逼近实际问题。
  • 优化算法3--蚁群算法(原理)

    千次阅读 2022-01-02 14:56:42
    1 算法简介 优化问题在科学和工业领域都非常重要。这些优化问题的实际例子有时间表调度、护理时间分配调度、列车调度、容量规划、旅行商...蚁群优化算法(Ant colony optimization, ACO)最早由Marco Dorigo在90年代...
  • 有限级信息素蚁群算法

    千次阅读 2019-01-14 11:39:41
    有限级信息素蚁群算法使用路径等级作为信息素更新的依据,相比于传统的蚁群算法,舍弃了目标函数作为信息素更新的依据这一方法。在TSP问题中,目标函数实际就是路径长度,在传统的蚁群算法信息素更新量为Q/f(x),...
  • 这是本科毕业设计,使用matlab在20乘以20的栅格地图中实现路径规划,包括静态环境...程序可以成功运行,地图可以手动修改,在这里还有自适应改变信息素挥发因数的改进方案,有很多子程序,注释非常详细,希望对你有用
  • 蚁群算法在优化领域,尤其在组合优化问题中获得了较为成功的应用,然而它存在易于早熟收敛、搜索时 间长等不足.针对该问题,提出了一种改进算法.该算法一方面在典型的状态转移规则中融合了一种随机选择策略,保证算法...
  • 将离散空间问题求解的蚁群算法引入连续空间,针对多目标优化问题的特点,提出一种用于求解带有约束条件的多目标函数优化问题的蚁群算法.该方法定义了连续空间中信息量的留存方式和蚂蚁的行走策略,并将信息素交流和基于...
  • 移动机器人路径规划是机器人学的一个重要领域。它要求机器人依据某些规则和原理,在工作区域当中找到一条从起始状态到目标状态规避障碍...这里采用蚁群算法信息素的原理进行寻找最优化距离,做出障碍区块和最优路径!
  • 提出解决车辆路径优化问题的方法, 针对蚁群算法的缺点, 分别对信息素更新策略、启发因子进行改进, 并引入搜索热区机制, 有效解决了蚁群算法的缺陷。最后, 以哈尔滨市局部地图为原型, 应用MATLAB软件对改进蚁群算法...
  • 蚁群算法|4.5

    2021-04-05 15:02:25
    蚁群算法 一、蚁群算法的来源及背景 蚁群算法是意大利学者Dorigo、Maniezzo等人于20世纪90年代看蚂蚁觅食发明的。这意大利的大兄弟在看蚂蚁觅食的时候呢,发现单个蚂蚁的行为比较简单,但是蚂蚁群却能体现一些智能...
  • 智能优化算法之蚁群算法(ACO)

    千次阅读 2021-09-10 19:21:30
    1. 蚁群算法模拟TSP问题 在时刻 ttt,蚂蚁 kkk 从城市 iii 转移到城市 jjj 的概率 pijk(t)为:p^k_{ij}(t)为:pijk​(t)为: 式中, Jk(i)={1,2,…,}−tabukJ_k(i)=\{1,2,…, \}-tabu_kJk​(i)={1,2,…...
  • 关于蚁群算法MMAS

    2021-04-19 02:32:59
    C n个城市的坐标,n×2的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳...
  • 提出一种全局静态环境下移动机器人路径规划的改进势场蚁群算法.该算法采用人工势场法求得的初始路径和机器人与下一个节点之间的距离综合构造启发信息,并引入启发信息递减系数,避免了传统蚁群算法由于启发信息误导所...
  • 提出将蚁群算法用于求解函数优化问题的新方法。使用一定数量的蚂蚁在解空间中首先随机搜索,然后模拟蚂蚁觅食的方式,更新搜索路径上的信息素,按照转移概率来决定搜索方向,即通过信息素来指引搜索,最后搜索收敛于...
  • 基于蚁群算法路径规划 能成功运行 包含蚁群初始化 栅格法建模 信息素 启发函数 画图等部分

空空如也

空空如也

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

蚁群算法信息素