精华内容
下载资源
问答
  • 同时考虑蚁群算法的所有运行参数, 提出一种基于图知识迁移的蚁群算法参数选择方法. 首先, 将包含知识(蚁群算法的运行参数) 的源任务映射到一个高维的迁移空间, 并通过迁移权值连接不同的源任务, 构造一个模型迁移图;...
  • 详细介绍了神经网络算法... 第二部分详细介绍了智能算法的工程中的应用问题,包括模糊神经网络在工程中的应用、遗传算法在图像处理中的应用、神经网络在参数估计中的应用、基于智能算法的PID控制和智能算法的综合应用等
  • 蚁群算法原理以及应用

    万次阅读 多人点赞 2019-03-09 09:05:12
    蚁群算法是一种群体智能仿生启发式算法,从提出至今已在不同领域的优化问题中已经得到广泛的应用。本文首先对启发式算法蚁群算法的由来以及含义做简要介绍,然后讲述蚁群算法的求解原理,再分别用两个案例解释蚁群...

    关键词:启发式算法 蚁群算法 迭代 正反馈
    1.蚁群算法(ant colony algorithm,ACA)起源和发展历程
    Marco Dorigo等人在研究新型算法的过程中,发现蚁群在寻找食物时,通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标,于是在1991年在其博士论文中首次系统地提出一种基于蚂蚁种群的新型智能优化算法“蚂蚁系统(Ant system,简称AS)”,后来,提出者及许多研究者对该算法作了各种改进,将其应用于更为广泛的领域,如图着色问题、二次分配问题、工件排序问题、车辆路径问题、车间作业调度问题、网络路由问题、大规模集成电路设计等。近些年来,M.Dorigo等人把蚂蚁算法进一步发展成一种通用的优化技术“蚁群优化(Ant Colony Optimization,简称ACO)”,并将所有符合ACO框架的算法称为“蚁群优化算法(ACO algorithm)”。
    初始蚁群爬行路线最终蚁群爬行路线
    具体来说,各个蚂蚁在没有事先告知食物在什么地方的前提下开始寻找食物。当一只找到食物以后,它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近)信息素能够让其他蚂蚁感知从而起到一个引导的作用。通常多个路径上均有信息素时,蚂蚁会优先选择信息素浓度高的路径,从而使浓度高的路径信息素浓度更高,形成一个正反馈。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开辟的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来。最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着。最终,信息素浓度最高的路径即是最终被蚂蚁选中的最优路径。
    与其他算法相比,蚁群算法是一种比较年轻的算法,具有分布式计算、无中心控制、个体之间异步间接通信等特点,并且易于与其他优化算法相结合,经过不少仁人志士的不断探索,到今天已经发展出了各式各样的改进蚁群算法,不过蚁群算法的原理仍是主干。
    2蚁群算法的求解原理
    基于上述对蚁群觅食行为的描述,该算法主要对觅食行为进行以下几个方面模拟:
    1模拟的图场景中包含了两种信息素,一种表示家,一种表示食物的地点,并且这两种信息素都在以一定的速率进行挥发。
    2 每个蚂蚁只能感知它周围的小部分地方的信息。蚂蚁在寻找食物的时候,如果在感知范围内,就可以直接过去,如果不在感知范围内,就要朝着信息素多的地方走,蚂蚁可以有一个小概率不往信息素多的地方走,而另辟蹊径,这个小概率事件很重要,代表了一种找路的创新,对于找到更优的解很重要。
    3、蚂蚁回窝的规则与找食物的规则相同。
    4、蚂蚁在移动时候首先会根据信息素的指引,如果没有信息素的指引,会按照自己的移动方向惯性走下去,但也有一定的机率改变方向,蚂蚁还可以记住已经走过的路,避免重复走一个地方。
    5、蚂蚁在找到食物时留下的信息素最多,然后距离食物越远的地方留下的信息素越少。找到窝的信息素留下的量的规则跟食物相同。蚁群算法有以下几个特点:正反馈算法、并发性算法、较强的鲁棒性、概率型全局搜索、不依赖严格的数学性质、搜索时间长,易出现停止现象。
    蚂蚁转移概率公式:
    在这转移概率公式里插入图片描述
    公式中:是蚂蚁k从城市i转移到j的概率;α,β分别为信息素和启发式因子的相对重要程度;为边(i,j)上的信息素量;为启发式因子;为蚂蚁k下步允许选择的城市。上述公式即为蚂蚁系统中的信息素更新公式,是边(i,j)上的信息素量;ρ是信息素蒸发系数,0<ρ<1;为第k只蚂蚁在本次迭代中留在边(i,j)上的信息素量;Q为一正常系数;为第k只蚂蚁在本次周游中的路径长度。
    在蚂蚁系统中,信息素更新公式为:
    信息素更新公式
    3蚁群算法的求解步骤
    1.初始化参数在计算之初,需要对相关参数进行初始化,如蚁群规模(蚂蚁数量)m、信息素重要程度因子α、启发函数重要程度因子β、信息素会发银子ρ、信息素释放总量Q、最大迭代次数iter_max、迭代次数初值iter=1。
    1. 构建解空间将各个蚂蚁随机地置于不同的出发点,对每个蚂蚁k(k=1,2,3…m),按照(2-1)计算其下一个待访问城市,直到所有蚂蚁访问完所有城市。
    2. 更新信息苏计算每个蚂蚁经过路径长度Lk(k=1,2,…,m),记录当前迭代次数中的最优解(最短路径)。同时,根据式(2-2)和(2-3)对各个城市连接路径上信息素浓度进行更新。
    3. 判断是否终止若iter<iter_max,则令iter=iter+1,清空蚂蚁经过路径的记录表,并返回步骤2;否则,终止计算,输出最优解。
    4. 判断是否终止若iter<iter_max,则令iter=iter+1,清空蚂蚁经过路径的记录表,并返回步骤2;否则,终止计算,输出最优解。3. 判断是否终止若iter<iter_max,则令iter=iter+1,清空蚂蚁经过路径的记录表,并返回步骤2;否则,终止计算,输出最优解。
    蚁群算法流程简图
    4简单案例–依据蚁群算法的步骤求解二元函数最小值优化二元函数:
    (4-1)优化思路:首先,通过对约束条件求解, 我们可以得到满足约束条件的可行解所构成的搜索空间。这是一个二维的凸空间,如果把各个分量的范围搜索等分成离散的点,那么空间整个的大小可以由分量xi的划分粗细来确定。假设,xi被划分成了Ni份,那么整个搜索空间就有2*Ni个。而且为了求得精确解将分量 xi 的区间划分得很细, 那么搜索空间将变得十分巨大, 这也正是问题求解的困难所在,当然这种划分区间的方法也是许多优化算法所一般采用的方法。)将每个分量的取值区间等分成N个点,那么xi就有N种选择二维决策量x就有N^2种选择组合。并将每个分量的N个取值点看作N个城市City。最开始将m个蚂蚁Ant随机地放到x1的N中的m个City上。搜索开始后,Ant按照转移概率进行城市选择。在第一次选择时,用rand函数随机选择,之后可按照选择概率转移。
    本案例的具体步骤为:(1)求解约束条件得出各分量的区间,由题意知[-1,1];(2)将分量区间细化,建立搜索空间,本案例细分成73份,xi=[-1,-1+2/73,…1];(3)判断精度是否满足要求,若满足,则输出最优解并结束, 否则继续(4);(4)每个路径上设置信息量初始值;(5)随机选择路径求解;(6)每个蚂蚁按照选择概率来选择路径求解;
    (7)若每个蚂蚁都找到解,则继续(8),否则转(4);(8)将当前最优解的分量再细化, 转(2)。

    展开全文
  • 蚁群算法是一种应用广泛、性能优良的智能优化算法, 其求解效果与参数选取息息相关. 鉴于此, 针对现有 基于粒子群参数优化的改进蚁群算法耗时较大的问题, 提出一种新的解决方案. 该方案给出一种全局异步与精英策...
  • 基于CT 过程的“四阶段”模型, 构建了算法框架, 改进了位置更新公式, 从而使蚂蚁个体在惯性、认知能力的基础上增强了CT 能力, 提高了蚁群 的整体寻优能力. 仿真结果表明, 所提出的算法搜索能力强、稳定性好, ...
  • 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,…...

    蚁群算法优缺点

    优点
    • 蚁群算法是一种本质上的并行算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信。不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。
    • 蚁群算法是一种自组织的算法。
    • 蚁群算法具有较强的鲁棒性。相对于其他算法,蚁群算法对初始路线的要求不高
    • 此外,蚁群算法的参数较少,设置简单,因而该算法易于应用到组合优化问题的求解。
    • 蚁群算法是一种正反馈算法。正反馈是蚁群算法的重要特征,它使得算法进化过程得以进行。
    缺点
    • 收敛速度慢。蚁群算法中信息素初值相同,选择下一个节点时倾向于随机选择。虽然随机选择能探索更大的任务空间,有助于找到潜在的全局最优解,但是需要较长时间才能发挥正反馈的作用,导致算法初期收敛速度较慢。
    matlab代码和python代码实例

    智能优化算法之蚁群算法代码实现matlab、python

    1. 蚁群算法模拟TSP问题

    • 在时刻 t t t,蚂蚁 k k k 从城市 i i i 转移到城市 j j j 的概率 p i j k ( t ) 为 : p^k_{ij}(t)为: pijk(t)

    在这里插入图片描述

    • 式中, J k ( i ) = { 1 , 2 , … , } − t a b u k J_k(i)=\{1,2,…, \}-tabu_k Jk(i)={12}tabuk 表示蚂蚁 k k k 下一步允许选择的城市集合。禁忌表 t a b u k tabu_k tabuk 记录了蚂蚁 k k k当前走过的城市。当所有 n n n 座城市都加入到禁忌表 t a b u k tabu_k tabuk 中时,蚂蚁 k k k 便完成了一次周游,此时, 蚂蚁 k k k 所走过的路径便是 TSP 问题的一个可行解。
    • (5.1) 中的 η i j η_{ij} ηij 是一个启发式因子,表示蚂蚁从城市 i i i 转移到城市 j j j 的期望程度。在蚁群算法中, η i j η_{ij} ηij 通常取城市 i i i与城市 j j j 之间距离的倒数。
    • α 和 β分别表示信息素和期望启发式因子的相对重要程度。当所有蚂蚁完成一次周游后,各路径上的信息素根据式(5.2)更新:
      在这里插入图片描述
    • 式中: ρ ( 0 < ρ < 1 ) ρ(0<ρ<1) ρ0ρ1表示路径上信息素的蒸发系数, 1 − ρ 1-ρ 1ρ 表示
      信息素的持久性系数; Δ τ i j Δτ_{ij} Δτij 表示本次迭代中边 i j ij ij 上信息素的增量,即
      在这里插入图片描述
    • 其中 Δ τ i j k Δτ_{ij}^k Δτijk 表示第 k k k 只蚂蚁在本次迭代中留在边 i j ij ij 上的信息素量,如果蚂蚁 k k k 没有经过边 ,则 Δ τ i j k Δτ_{ij}^k Δτijk 的值为零。 Δ τ i j k Δτ_{ij}^k Δτijk可表示为:
      在这里插入图片描述
    • 其中 Q Q Q为正常数, 表示第 L k L_k Lk只蚂蚁在本次周游中所走过路径的长度。
    其他模型

    在这里插入图片描述

    2. 基本蚁群算法的具体实现

    • (1)参数初始化。令时间 t = 0 t = 0 t=0 和循环次数 N c = 0 N_c = 0 Nc=0,设置最大循环次数 G G G,将 m m m 个蚂蚁置于 n n n 个元素(城市)上,令有向图上每条边 ( i , j ) (i,j) (i,j) 的初始化信息量 τ i j ( t ) = c τ_{ij}(t) =c τij(t)=c ,其中 c c c 表示常数,且初始时刻 Δ τ i j ( 0 ) = 0 Δτ_{ij}(0)=0 Δτij(0)=0
    • (2)循环次数: N c = N c + 1 N_c = N_c+1 Nc=Nc+1
    • (3)蚂蚁的禁忌表索引号: k = 1 k=1 k=1
    • (4)蚂蚁数目: k = k + 1 k= k+1 k=k+1
    • (5)蚂蚁个体根据状态转移概率公式(5.1)计算的概率选择元素 j j j 并前进, j ∈ { J k ( i ) } j∈\{J_k(i)\} j{Jk(i)}
    • (6)修改禁忌表指针,即选择好之后将蚂蚁移动到新的元素,并把该元素移动到该蚂蚁个体的禁忌表中
    • (7)若集合 C C C 中元素未遍历完,即 k < m k < m km,则跳转到第(4)步;否则执行第(8)步。
    • (8)记录本次最佳路线
    • (9)根据式(5.2)和式(5.3)更新每条路径上的信息量。
    • (10)若满足结束条件,即如果循环次数 N c ≥ G N_c≥G NcG ,则循环结束并输出程序优化结果;否则清空禁忌表并跳转到第(2)步。
      在这里插入图片描述

    3. 关键参数说明

    信息素启发因子: α \alpha α
    • 其值越大,蚂蚁在选择以前走过的路径的可能性就越大,搜索的随机性就会减弱;
    • 而当启发式因子 α 的值过小时,则易使蚁群的搜索过早陷于局部最优。
    • 根据经验,信息素启发式因子 α 取值范围一般为 [ 1 , 4 ] [1,4] [14]时,蚁群算法的综合求解性能较好。
    启发式因子: β \beta β
    • 期望启发因子 β 表示在搜索时路径上的信息素在指导蚂蚁选择路径时的向导性。
    • 期望启发因子 β 的值越大,蚂蚁在某个局部点上选择局部最短路径的可能性就越大,虽然这个时候算法的收敛速度得以加快,但蚁群搜索最优路径的随机性减弱,而此时搜索易于陷入局部最优解。
    • 根据经验,期望启发因子 β 取值范围一般为 [ 3 , 5 ] [3, 5] [35],此时蚁群算法的综合求解性能更好。
    信息素蒸发系数: ρ \rho ρ
    • 信息素蒸发系数 ρ 大小的选择将直接影响到整个蚁群算法的收敛速度和全局搜索性能。
    • ρ 表示信息素蒸发系数,1-ρ 则表示信息素持久性系数。因此,ρ的取值范围应该是0~1之间的一个数
    • ρ 过小时,则表示以前搜索过的路径被再次选择的可能性过大,会影响到算法的随机性能和全局搜索能力;
    • ρ 过大时,说明路径上的信息素挥发的相对变多,虽然可以提高算法的随机搜索性能和全局搜索能力,但过多无用搜索操作势必会降低算法的收敛速度。
    蚂蚁数目: m m m
    • 蚂蚁数目增大后,会使大量的曾被搜索过的解(路径)上的信息素变得趋于平均,信息正反馈的作用不明显。虽然搜索的随机性得到了加强,但收敛速度减慢。
    • 反之,(蚂蚁数量少),特别是当要处理的问题规模比较大时,会使那些从来未被搜索到的解(路径)上的信息素减小到接近于0,搜索的随机性减弱,虽然收敛速度加快了,但会使算法的全局性能降低,算法的稳定性差,容易出现过早停滞现象。
    • m m m 一般取 10 ~ 50 10~50 1050
    信息素强度: Q Q Q
    • 参数 Q Q Q 不必作特别的考虑,可以任意选取。
    最大进化代数: G G G
    • 一般 G G G 取 100 ∼ 500 取100\sim500 100500

    笔记参考

    《智能优化算法及其MTALAB算法实例》第二版

    展开全文
  • 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的 一种仿生算法:蚂蚁在运动过程中,能够在它所经过的路 径上留下信息素(pheromone)的物质进行信息传递,而且 蚂蚁在运动过程中能够感知这种物质,并以此指导自己...

    一、概述以及代码实现

    1.算法概述

    蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的 一种仿生算法:蚂蚁在运动过程中,能够在它所经过的路
    径上留下信息素(pheromone)的物质进行信息传递,而且 蚂蚁在运动过程中能够感知这种物质,并以此指导自己的 运动方向。

    2.代码实现

    %% 导入数据
    citys=round(1000+5000*rand(35,2));
    save citys;
    load citys;
     **%随机生成35个坐标在1000-6000之内的城市坐标** 
    
    %% 计算城市间相互距离
    fprintf('Computing Distance Matrix... \n');
    n = size(citys,1);
    D = zeros(n,n);
    for i = 1:n
        for j = 1:n
            if i ~= j
                D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));
            else
                D(i,j) = 1e-4;      
            end
        end    
    end
    
    %% 初始化参数
    fprintf('Initializing Parameters... \n');
    m = 50;                              % 蚂蚁数量
    alpha = 1;                           % 信息素重要程度因子
    beta = 5;                            % 启发函数重要程度因子
    rho = 0.16;                           % 信息素挥发因子
    Q = 1;                               % 常系数
    Eta = 1./D;                          % 启发函数
    Tau = ones(n,n);                     % 信息素矩阵
    Table = zeros(m,n);                  % 路径记录表
    iter = 1;                            % 迭代次数初值
    iter_max = 150;                      % 最大迭代次数 
    Route_best = zeros(iter_max,n);      % 各代最佳路径       
    Length_best = zeros(iter_max,1);     % 各代最佳路径的长度  
    Length_ave = zeros(iter_max,1);      % 各代路径的平均长度  
    
    %% 迭代寻找最佳路径
    figure;
    while iter <= iter_max
        fprintf('迭代第%d次\n',iter);
        % 随机产生各个蚂蚁的起点城市
          start = zeros(m,1);
          for i = 1:m
              temp = randperm(n);
              start(i) = temp(1);
          end
          Table(:,1) = start; 
          % 构建解空间
          citys_index = 1:n;
          % 逐个蚂蚁路径选择
          for i = 1:m
              % 逐个城市路径选择
             for j = 2:n
                 tabu = Table(i,1:(j - 1));           % 已访问的城市集合(禁忌表)
                 allow_index = ~ismember(citys_index,tabu);
                 allow = citys_index(allow_index);  % 待访问的城市集合
                 P = allow;
                 % 计算城市间转移概率
                 for k = 1:length(allow)
                     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;
             end
          end
          % 计算各个蚂蚁的路径距离
          Length = zeros(m,1);
          for i = 1:m
              Route = Table(i,:);
              for j = 1:(n - 1)
                  Length(i) = Length(i) + D(Route(j),Route(j + 1));
              end
              Length(i) = Length(i) + D(Route(n),Route(1));
          end
          % 计算最短路径距离及平均距离
          if iter == 1
              [min_Length,min_index] = min(Length);
              Length_best(iter) = min_Length;  
              Length_ave(iter) = mean(Length);
              Route_best(iter,:) = Table(min_index,:);
          else
              [min_Length,min_index] = min(Length);
              Length_best(iter) = min(Length_best(iter - 1),min_Length);
              Length_ave(iter) = mean(Length);
              if Length_best(iter) == min_Length
                  Route_best(iter,:) = Table(min_index,:);
              else
                  Route_best(iter,:) = Route_best((iter-1),:);
              end
          end
          % 更新信息素
          Delta_Tau = zeros(n,n);
          % 逐个蚂蚁计算
          for i = 1:m
              % 逐个城市计算
              for j = 1:(n - 1)
                  Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);
              end
              Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);
          end
          Tau = (1-rho) * Tau + Delta_Tau;
        % 迭代次数加1,清空路径记录表
    
     %   figure;
     %最佳路径的迭代变化过程
        [Shortest_Length,index] = min(Length_best(1:iter));
        Shortest_Route = Route_best(index,:);
        plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
        [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
        pause(0.3);
     
        iter = iter + 1;
        Table = zeros(m,n);
    
     % end
    end
    
    %% 结果显示
    [Shortest_Length,index] = min(Length_best);
    Shortest_Route = Route_best(index,:);
    disp(['最短距离:' num2str(Shortest_Length)]);
    disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);
    
    %% 绘图
    figure(1)
    plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
         [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
    grid on
    for i = 1:size(citys,1)
        text(citys(i,1),citys(i,2),['   ' num2str(i)]);
    end
    text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'       起点');
    text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'       终点');
    xlabel('城市位置横坐标')
    ylabel('城市位置纵坐标')
    title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
    figure(2)
    plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')
    legend('最短距离','平均距离')
    xlabel('迭代次数')
    ylabel('距离')
    title('各代最短距离与平均距离对比')
    

    二、结果实现

    在这里插入图片描述

    三.参数设置(控制变量法)

    3.1设定alpha为变量,beta、rho参数不变

    3.1.1alpha=1时;在这里插入图片描述

    3.1.2alpha=3时;在这里插入图片描述

    3.1.3alpha=5时;在这里插入图片描述

    3.1.4alpha=10时;在这里插入图片描述

    实验分析:
    依据实验结果,可以看出当alpha越来越大时,其收敛速度也随之加快。当alpha为5或者10时,其收敛速度在迭代次数少于50时就趋于稳定;
    当alpha为1或者3时,在相同的迭代次数下,其最终的最短距离能达到更加精确的结果,但同时趋于稳定的速度也较之慢了许多。

    结论:
    启发式因子alpha反映了蚂蚁在运动过程中所积累的信息量在知道蚁群搜索中的相对重要程度。
    alpha越大则蚂蚁选择以前走过的路径的可能性就越大,收敛加速但搜索的随机性减弱;
    alpha越小蚂蚁搜索的随机性越大,但是算法收敛速度变慢同时算法容易陷入局部最优解。

    3.2设定beta为变量,alpha、rho参数不变

    3.2.1beta=1时;

    在这里插入图片描述

    3.2.1beta=3时;在这里插入图片描述

    3.2.1beta=5时;在这里插入图片描述

    3.2.1beta=7时;在这里插入图片描述

    3.2.1beta=9时;

    在这里插入图片描述
    结果分析:
    beta过小时,收敛速度比较慢;可以看出beta为1或者3时,可以看出迭代的稳定性是较为差的,beta=1时到将近110迭代次数才趋于稳定;
    beta过大时,收敛速度加快,但如beta=9时,他的最优解明显没有beta=5时的最优解更大。
    结论 :
    beta反映了启发信息在导致蚁群搜索过程中的相对重要程度,其大小反应了蚁群优先过程中的先验性、确定性因素的作用强度。
    beta过大时算法的收敛速度加快,但收能性变差;
    beta过小时,收敛速度较快,但将会陷入纯粹的随机搜索,而在这种情况下很难找到最优解。

    3.3设定rho为变量,alpha、beta参数不变

    3.3.1rho=0.04时;

    在这里插入图片描述

    3.3.2rho=0.07时;

    在这里插入图片描述

    3.3.1rho=0.1时;

    在这里插入图片描述

    3.3.1rho=0.13时;

    在这里插入图片描述

    3.3.1rho=0.16时;

    在这里插入图片描述
    结果分析:
    rho过小时,算法得到的解并不是最优解,但是更容易趋向于稳定;
    过大时,得到的解都较稳定准确,但速度比较慢。
    结论:
    rho是信息素挥发因子,对算法的影响具有双重性。
    当rho较小时搜索空间缩小,收敛性提高,但算法容易陷入局部最优;
    而当rho过大时,搜索空间增大但收敛性降低。

    展开全文
  • 复习蚁群算法

    群智能

    swarm: a large group of insects all moving together.
    个体:群中的成员,之间是平等关系,没有主从关系。

    群智能

    个体仅具有简单智能,群体行为表现出较高级的智能。
    典型的优化算法:蚁群算法、粒子群算法。还有其他的算法:鱼群算法、蜂群算法、蛙跳算法、萤火虫算法、细菌觅食算法等。

    算法大概内容概括
    蚁群优化算法蚂蚁如何在食物源和巢穴之间找到最短路径路径选择;信息素更新;协同工作
    粒子群优化算法鸟群随机搜索食物个体经验;社会学习
    人工鱼群算法鱼在水域的游动觅食行为;追尾行为;聚群行为;随机游动

    蚁群优化算法-Ant Colony Optimization

    背景

    1991年Dorigo解决旅行商问题。改进衍生:蚁群系统,最大最小蚂蚁系统,最优保留蚁群系统。

    核心

    返回:蚂蚁沿着一条路到达终点后会马上返回。
    信息素:信息素多表示经过这里的蚂蚁多,因而会有更多的蚂蚁聚集过来。
    正反馈:某一路径上走过的蚂蚁越多,后来者选择该路径的概率越大。

    基本思想

    蚁群算法流程图

    ACO实现-C++

    以解决100个城市的TSP问题为例。

    // ACO.cpp : This file contains the 'main' function. Program execution begins and ends there.
    //
    
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <windows.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <time.h>
    
    using namespace std;
    
    unsigned seed = (unsigned)time(0);
    
    //城市数目
    #define CITY_NUM 100
    //蚁群规模
    #define ANT_NUM 150
    //迭代最大次数
    #define TMAX 1000
    
    double CityPos[CITY_NUM][2] = {
    {18200.0000, 109550.0000},
    {18200.0000, 109583.3333},
    {18206.3889, 109581.9444},
    {18207.5000, 109477.7778},
    {18215.8333, 109700.5556},
    {18216.6667, 109700.0000},
    {18220.5556, 109510.2778},
    {18223.8889, 109552.2222},
    {18229.7222, 109528.3333},
    {18233.3333, 109533.3333},
    {18233.3333, 109616.6667},
    {18233.8889, 109703.8889},
    {18236.6667, 109625.0000},
    {18243.0556, 109505.0000},
    {18243.6111, 109690.2778},
    {18245.2778, 109373.8889},
    {18246.6667, 109559.7222},
    {18250.0000, 109516.6667},
    {18250.0000, 109583.3333},
    {18257.7778, 109689.4444},
    {18260.5556, 109712.7778},
    {18263.0556, 109580.8333},
    {18263.0556, 109679.7222},
    {18265.0000, 109638.6111},
    {18266.6667, 109483.3333},
    {18266.6667, 109566.6667},
    {18266.6667, 109666.6667},
    {18271.3889, 109705.8333},
    {18278.3333, 109730.2778},
    {18279.4444, 109675.2778},//30个
    {18281.1111, 109480.8333},
    {18281.3889, 109684.1667},
    {18283.3333, 109400.0000},
    {18283.8889, 109569.7222},
    {18283.8889, 109705.5556},
    {18284.4444, 109661.6667},
    {18296.9444, 109611.6667},
    {18302.2222, 109210.0000},
    {18303.8889, 109432.2222},
    {18304.1667, 109528.3333},
    {18304.4444, 109335.2778},
    {18304.4444, 109391.1111},
    {18307.2222, 109144.1667},
    {18314.7222, 109269.7222},
    {18315.2778, 109626.6667},
    {18316.6667, 109166.6667},
    {18316.6667, 109266.6667},
    {18317.2222, 109331.6667},
    {18319.1667, 109442.2222},
    {18319.7222, 109705.0000},//50个
    {18320.2778, 109173.6111},
    {18321.6667, 109551.1111},
    {18325.0000, 109673.3333},
    {18325.8333, 109528.3333},
    {18327.2222, 109256.3889},
    {18327.7778, 109247.5000},
    {18332.5000, 109490.2778},
    {18333.3333, 109450.0000},
    {18335.2778, 109323.0556},
    {18336.1111, 109731.3889},
    {18344.7222, 109452.2222},
    {18347.2222, 109638.8889},
    {18347.7778, 109203.3333},
    {18347.7778, 109587.7778},
    {18349.1667, 109440.8333},
    {18351.3889, 109725.8333},
    {18351.3889, 109726.6667},
    {18355.5556, 109627.2222},
    {18356.1111, 109126.6667},
    {18358.6111, 109126.3889},
    {18359.1667, 108988.6111},
    {18362.7778, 109602.2222},
    {18370.5556, 109099.7222},
    {18370.8333, 109005.5556},
    {18371.6667, 109508.8889},
    {18372.7778, 109163.6111},
    {18374.7222, 109244.4444},
    {18375.5556, 109162.2222},
    {18376.1111, 109035.2778},
    {18378.0556, 109603.3333},
    {18378.0556, 109742.5000},
    {18378.6111, 109641.6667},
    {18388.3333, 109824.7222},
    {18392.2222, 109725.0000},
    {18393.6111, 109430.8333},
    {18397.7778, 109987.5000},
    {18398.6111, 109496.3889},
    {18400.0000, 109730.2778},
    {18400.0000, 109750.0000},
    {18400.8333, 109202.7778},
    {18402.2222, 109283.0556},
    {18403.6111, 109020.8333},
    {18403.6111, 109868.8889},
    {18404.7222, 110018.6111},
    {18406.6667, 109616.6667},
    {18408.6111, 109758.3333},
    {18409.4444, 109676.3889},
    {18414.1667, 110070.2778},
    {18415.8333, 108933.8889},
    {18415.8333, 109725.0000}//100个
    };
    
    //alpha参数
    #define ALPHA 3
    //beta参数
    #define BETA 4
    //rho参数
    #define RHO 0.4
    //Q参数
    #define Q 100
    
    //地图
    const int maxn = 100;
    //距离矩阵
    double dis[maxn][maxn];
    //信息素矩阵
    double info[maxn][maxn];
    //启发因子矩阵
    double E[maxn][maxn];
    //
    int vis[CITY_NUM][CITY_NUM];
    //最佳结果
    double BestLength;
    
    double ans[CITY_NUM];
    const double mmax = 10e9;
    
    //产生随机整数
    //指定范围
    int rnd(int nLow, int nUpper)
    {
        return nLow + (nUpper - nLow) * rand() / (RAND_MAX + 1);
    }
    
    //产生随机浮点数
    //指定范围
    double rnd(double dbLow, double dbUpper)
    {
        double dbTemp = rand() / ((double)RAND_MAX + 1.0);
        return dbLow + dbTemp * (dbUpper - dbLow);
    }
    
    //浮点数取整
    //四舍五入
    double ROUND(double dbA)
    {
        return (double)((int)(dbA + 0.5));
    }
    
    
    //ant
    struct Ant
    {
        //蚂蚁走的路线,时间顺序,存放内容是“第i步到了哪个城市”
        int Path[CITY_NUM];
        //路径的总长度
        double length;
        //标记走过的城市,城市标记表,如果走过了记为1,否则都是0
        int vis[CITY_NUM];
        //当前所处的城市编号
        int cur_cityno;
        //已走城市的数量,会累加
        int moved_cnt;
    
        //初始化函数
        void Init()
        {
            //开辟空间
            memset(vis, 0, sizeof(vis));
            //路径总长度初始化为0
            length = 0;
            //随便定一个起始城市
            cur_cityno = rnd(0, CITY_NUM);
            //路线记录的第一个城市设为刚才random出来的城市
            Path[0] = cur_cityno;
            //在记录城市是否已经走过的数组中标记刚才random出来的城市为1
            vis[cur_cityno] = 1;
            //已经走了一个城市
            moved_cnt = 1;
        }
    
        //选择路径
        //求出蚂蚁要走的下一个城市的编号为多少
        int chooseNextCity()
        {
            //返回的城市编号
            //初始化设置为-1(后续再进行改变)
            int nSelectedCity = -1;
            //计算当前城市和没去过的城市之间的信息素总量
            double dbTotal = 0.0;
            //数组
            //存放城市被选中的概率,也就是公式中的pk(i,j)中分子的部分
            double prob[CITY_NUM];
    
            //转换公式
            //对于每个城市而言
            for (int i = 0; i < CITY_NUM; i++)
            {
                //如果一直以来都没有访问过编号为i的城市
                if (!vis[i])
                {
                    //求分子
                    prob[i] = pow(info[cur_cityno][i], ALPHA) * pow(1.0 / dis[cur_cityno][i], BETA);
    
                    dbTotal = dbTotal + prob[i];
                }
                else
                {
                    prob[i] = 0;
                }
            }
    
            //轮盘赌选择
            double dbTemp = 0.0;
            //如果总的信息素值大于0
            if (dbTotal > 0.0)
            {
                //在0和信息素总含量中随机生成一个阈值
                dbTemp = rnd(0.0, dbTotal);
                for (int i = 0; i < CITY_NUM; i++)
                {
                    if (!vis[i])
                    {
                        //作差
                        dbTemp = dbTemp - prob[i];
                        //如果该城市的信息素含量超过随机生成的阈值大小
                        if (dbTemp < 0.0)
                        {
                            //那么选择该城市
                            nSelectedCity = i;
                            //跳出循环
                            break;
                        }
                    }
                }
            }
            //如果经过轮盘赌还是没选出下一步走哪个城市
            if (nSelectedCity == -1)
            {
                //在所有城市当中选出第一个没去过的城市作为下一步要去的城市
                for (int i = 0; i < CITY_NUM; i++)
                {
                    //遇到第一个没有被访问的城市
                    if (!vis[i])
                    {
                        //选择该城市
                        nSelectedCity = i;
                        //跳出循环
                        break;
                    }
                }
            }
            return nSelectedCity;
        }
        //蚂蚁移动
        void Move()
        {
            //首先找到接下来要去哪个城市
            int nCityno = chooseNextCity();
            //蚂蚁下一步要走这个城市
            Path[moved_cnt] = nCityno;
            //蚂蚁即将经历这个城市
            vis[nCityno] = 1;
            //目前到达这个城市
            cur_cityno = nCityno;
            //蚂蚁的总路线登记累加move的距离
            length = length + dis[Path[moved_cnt - 1]][Path[moved_cnt]];
            moved_cnt++;
        }
        //蚂蚁搜索----总流程
        void Search()
        {
            //先初始化一只蚂蚁
            Init();
            //蚂蚁在地图上走
            while (moved_cnt < CITY_NUM)
            {
                Move();
            }
            //补上终点和起点的路径长度
            length = length + dis[Path[CITY_NUM - 1]][Path[0]];
        }
    };
    
    struct TSP
    {
        //数组
        //存放一群蚂蚁
        Ant ants[ANT_NUM];
        //记录最好结果的蚂蚁信息
        Ant ant_best;
        void Init()
        {
            //初始设置这群蚂蚁中最好的距离是一个超大值
            //等待迭代后进行更新
            ant_best.length = mmax;
    
            //初始化城市间距离矩阵
            //遍历计算,邻接矩阵存放城市之间的欧式距离
            //dis二维数组
            for (int i = 0; i < CITY_NUM; i++)
            {
                for (int j = 0; j < CITY_NUM; j++)
                {
                    double temp1 = CityPos[j][0] - CityPos[i][0];
                    double temp2 = CityPos[j][1] - CityPos[i][1];
                    dis[i][j] = sqrt(temp1 * temp1 + temp2 * temp2);
                }
            }
    
            //初始化信息素
            //info二维数组
            for (int i = 0; i < CITY_NUM; i++)
            {
                for (int j = 0; j < CITY_NUM; j++)
                {
                    info[i][j] = 1.0;
                }
            }
        }
    
        //信息素矩阵更新
        void Updateinfo()
        {
            //信息素增量矩阵
            double tmpinfo[CITY_NUM][CITY_NUM];
            //
            memset(tmpinfo, 0, sizeof(tmpinfo));
            //城市m,初始值设为0
            int m = 0;
            //城市n,初始值设为0
            int n = 0;
            //
            for (int i = 0; i < ANT_NUM; i++)
            {
                //从第一个城市到最后一个城市
                for (int j = 1; j < CITY_NUM; j++)
                {
                    m = ants[i].Path[j];
                    n = ants[i].Path[j - 1];
    
                    //计算信息素增量
                    tmpinfo[n][m] = tmpinfo[n][m] + Q / ants[i].length;
                    //保持信息素增量矩阵的对称性
                    tmpinfo[m][n] = tmpinfo[n][m];
                }
                //最后一个城市到第一个城市
                n = ants[i].Path[0];
                //计算信息素增量
                tmpinfo[n][m] = tmpinfo[n][m] + Q / ants[i].length;
                //保持信息素增量矩阵的对称性
                tmpinfo[m][n] = tmpinfo[n][m];
            }
            //原信息素矩阵耗散后的值加上信息素增量矩阵对应的值
            for (int i = 0; i < CITY_NUM; i++)
            {
                for (int j = 0; j < CITY_NUM; j++)
                {
                    info[i][j] = info[i][j] * RHO + tmpinfo[i][j];
                }
            }
        }
        //寻找路径----总流程
        void Search()
        {
            //进行TMAX次循环
            //里面是每次循环的内容
            for (int i = 0; i < TMAX; i++)
            {
                cout << "当前循环次数为" << i << endl;
                //对于当前设定的种族中的所有蚂蚁而言,都开始分别进行路线搜索
                //并且完成一次搜索
                for (int j = 0; j < ANT_NUM; j++)
                {
                    ants[j].Search();
                }
                //记录最优结果
                for (int j = 0; j < ANT_NUM; j++)
                {
                    //希望找到最短距离
                    if (ant_best.length > ants[j].length)
                    {
                        //更新
                        ant_best = ants[j];
                    }
                }
                //更新信息素
                Updateinfo();
                cout << "目前得到的最短路径长度为" << ant_best.length << endl;
            }
        }
    };
    
    
    
    int main()
    {
        srand(seed);
        TSP tsp;
        tsp.Init();
        tsp.Search();
        cout << "最短路径为" << endl;
        for (int i = 0; i < CITY_NUM; i++)
        {
            cout << tsp.ant_best.Path[i] << endl;
        }
        return 0;
    }
    
    // Run program: Ctrl + F5 or Debug > Start Without Debugging menu
    // Debug program: F5 or Debug > Start Debugging menu
    
    // Tips for Getting Started: 
    //   1. Use the Solution Explorer window to add/manage files
    //   2. Use the Team Explorer window to connect to source control
    //   3. Use the Output window to see build output and other messages
    //   4. Use the Error List window to view errors
    //   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
    //   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
    
    
    展开全文
  • 蚁群优化算法

    千次阅读 2019-11-05 15:06:25
    蚁群优化算法1.蚁群优化算法简介2.蚁群优化算法基本思想3.蚁群优化算法设计流程4.代码实现5.运行结果与分析 1.蚁群优化算法简介 蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士...
  • 解决函数极值问题(二元), 采用三种群智能算法实现, 并进行比较分析 1. 问题重述 求解函数: f(x,y)=6.452(x+0.125y)(cos⁡x−cos⁡(2y))20.8+(x−4.2)2+2(y−7)2+3.226yf(x, y)=\frac{6.452(x+0.125 y)(\cos x-\cos ...
  • 摘要:智能优化算法又称现代启发式算法,是一种具有全局优化性能、通用性强且适合于并行处理的算法。本文主要为大家带来遗传算法蚁群算法的详细解读。
  • 蚁群算法总结

    千次阅读 2019-02-04 12:14:22
    蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的方法。 蚁群算法是一种模拟进化算法,...
  • 文章目录第五章 蚁群优化算法5.1 介绍5.2 人工蚂蚁的概念5.2.1 真实蚂蚁如何工作5.2.2 蚂蚁如何优化食物搜索5.2.3 什么是人工蚂蚁5.2.3.1 相同5.2.3.2 不同5.3 蚂蚁系统5.4 三种模型5.4.1 蚁密系统模型5.4.2 蚁量...
  • 蚁群算法优化PID参数,这是matlab源代码
  • 人工智能7-蚁群优化算法实验

    千次阅读 2019-11-05 17:04:13
    二、蚁群算法相关名词解释及参数设置 三、蚁群算法流程 四、matlab实现及分析 五、蚁群算法的优点 六、疑问 七、代码附件 一、蚁群算法简介 蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于...
  • 智能优化算法——蚁群算法小实践

    千次阅读 2019-07-15 21:47:08
    目的:通过本次实验,学生可以掌握蚁群算法基本原理、蚁群算法流程和关键参数的设置。 要求:上机仿真,调试通过。 二、 实验设备: 计算机、Matlab软件、VC++或C语言软件 三、实验内容: 旅行商问题(TSP)。假设有...
  • 蚁群算法

    万次阅读 多人点赞 2017-05-13 20:23:13
    蚁群算法(AG)是一种模拟蚂蚁觅食行为的模拟优化算法,它是由意大利学者Dorigo M等人于1991年首先提出,并首先使用在解决TSP(旅行商问题)上。 之后,又系统研究了蚁群算法的基本原理和数学模型. 蚁群算法的基本思想...
  • 群体智能算法蚁群算法初探(一)

    千次阅读 2020-03-18 18:57:21
    1.简介 2.算法的步骤 3.算法的应用 4.算法的一些改进
  • 蚁群算法详解

    千次阅读 2020-09-22 19:04:00
    没有中心化的组织,蚁群何以进行高效地搜寻呢?一个快递小哥有5个包裹要送,如何确定一条最短的行进路线?本文我们一起学下常用于路径优化的蚁群算法,主要内容如下:蚁群算法简介蚁群算法原理蚁群算...
  • 融入粒子群与蚁群算法对XML群体概率搜索智能分析,刘波,杨路明,针对XML文档进行群体搜索的特点与不足,提出利用群智能算法的概率变换规则对其进行改进,采用粒子群算法快速生成信息素分布,利用��
  • 该控制器以系统单位阶跃响应的超调量σ、上升时间tr以及调整时间ts为性能指标,针对给定的控制对象,利用所建立的蚁群算法搜索出一组最优PID参数Kp,Ti及Td,作为实时控制中PID控制器的参数。该控制器被用于控制智能仿生...
  • 智能算法---蚁群算法

    千次阅读 2018-08-27 06:51:58
    蚁群算法是一种智能优化算法,通过蚁群优化求解复杂问题,ACO在离散优化问题方面有比较好的优越性。     基本思想(以旅行商问题为例)    设置多只蚂蚁,分头并行搜索。  每只蚂蚁完成一次周游后,在...
  • matlab代码: clear; close all; clc; C = [1304 2312; % 城市坐标 3639 1315; 4177 2244; 3712 1399; 3488 1535; 3326 1556; 3238 1229; 4196 1044; 4312 790; 4386 570; 3007 1970;...
  • 人工智能之优化算法1-蚁群优化算法

    万次阅读 2016-01-12 17:31:57
    智能蚁群算法及其应用》:吴启迪,汪镭,上海科技教育出版社。 链接: http://www.nocow.cn/index.php/%E8%9A%81%E7%BE%A4%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95 蚁群算法的提出: 人类认识事物的能力...
  • 在研究生期间,我当时对一个问题十分怀疑,那就是蚁群算法有什么用,相信很多人或许都对这个问题有过质疑。因为我目前没有见过蚁群算法用在哪个实际问题上过。或许有人参加过公司的一些工作面试,但是很少公司需要你...
  • 在本文的后面,我们使用了三种人工智能算法,包括粒子群智能(PSO),蚁群优化(ACO)和遗传算法(GA),并进行了比较,以实现导致接近最大值或接近最大值的优化参数集。产生楔形裂纹的最小楔入力。
  • 群体智能算法 与大多数基于梯度的优化算法不同,群体智能算法依靠的是概率搜索算法。 与梯度算法及传统演化算法相比优点: 没有集中控制约束,不会因为个体的故障影响整个问题的求解。 以非直接信息交流的...
  • 蚁群算法简析、缺陷、改进

    万次阅读 多人点赞 2020-07-18 18:20:56
    蚁群算法是一种用来寻找优化路径的概率型算法,模拟蚂蚁在寻找食物过程中发现路径的行为。
  • 智能算法---蚁群算法介绍

    万次阅读 多人点赞 2016-09-08 08:34:24
    蚁群算法是一种群智能算法,也是启发式算法。基本原理来源于自然界蚂蚁觅食的最短路径原理。

空空如也

空空如也

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

蚁群智能算法的参数