蚁群算法 订阅
蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 [1]  这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。 [2] 展开全文
蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 [1]  这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。 [2]
信息
外文名
ant colony optimization
提出时间
1992年
简    称
ACO
提出人
Marco Dorigo
中文名
蚁群算法
所属学科
计算机
蚁群算法背景
蚁群系统(Ant System或Ant Colony System)是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中,发现单个蚂蚁的行为比较简单,但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下,寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现,蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质,蚁群内的蚂蚁对“信息素”具有感知能力,它们会沿着“信息素”浓度较高路径行走,而每只路过的蚂蚁都会在路上留下“信息素”,这就形成一种类似正反馈的机制,这样经过一段时间后,整个蚁群就会沿着最短路径到达食物源了。 [3] 
收起全文
精华内容
下载资源
问答
  • 蚁群算法

    万次阅读 多人点赞 2018-07-20 09:57:00
    1.蚁群算法原理 1.1蚁群算法的基本思想 1.2蚁群算法的数学模型 1.3蚁群算法流程 2.蚁群算法的MATLAB实现 2.1算法设步骤 2.2程序代码 3.算法关键参数的设定 1.参数设定的准则 2.蚂蚁数量 3.信息素因子 4....

    所有博文已迁移至个人网站:https://www.ravenxrz.ink,请勿再留言评论

    新链接:https://www.ravenxrz.ink/archives/3b36af0a.html

    1.蚁群算法原理

    1.1蚁群算法的基本思想

    蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理,蚂蚁在寻找食物源时,能在其走过的路径上释放一种蚂蚁特有的分泌物–信息素,使得一定范围内的其他蚂蚁能够察觉到并由此影响他们以后的行为。当一些路径上通过的蚂蚁越来越多时,其留下的信息素也越来越多,以致信息素强度增大,所以蚂蚁选择选该路径的概率也越高,从而更增加了该路径的信息素强度,这种选择过程被称为蚂蚁的自催化行为。由于其原理是一种正反馈机制,因此,也可将蚂蚁王国理解为所谓的增强型学习系统。

    1.2蚁群算法的数学模型

    这个利用TSP问题来说明这个数学模型,对于TSP问题,设蚂蚁群体中蚂蚁的数量为m,城市的数量为n,城市i与城市j之间的距离为dij,t时刻城市i与城市j连接路径上的信息素浓度为cij(t)。初始时刻,蚂蚁被放置在不同的城市里,且各城市键连接路径上的信息素浓度相同。然后蚂蚁将按一定概率选择线路,不放设pKij(t)为t时刻蚂蚁k从城市i转移到城市j的概率。“蚂蚁TSP”策略收到两方面的左右,首先是访问某城市的期望,领完便是其他蚂蚁释放的信息素浓度。所以已定义:

    pijk(t)=[cij(t)]a[nij(t)]bsum([cij(t)]a[nij(t)b]),jallowk0,jallowk p^k_{ij}(t) =\frac{[c_{ij}(t)]^a*[n_{ij}(t)]^b}{sum([c_{ij}(t)]^a*[n_{ij}(t)^b]} ),j∈allowk \\ 0,j∉allowk

    • nij(t)n_{ij}(t)为启发函数,表示蚂蚁从城市i转移到城市j的期望;

    • allowkallowk为蚂蚁kk带访问城市集合,开始时,allowkallowk中有n1n-1个元素,即包括除了蚂蚁kk出发城市的其他多个城市,随着时间的推移,allowkallowk中的元素越来越少,直至为空;

    • aa 为信息素重要程度因子

    • bb为启发函数因子
      在蚂蚁遍历各城市的过程中,与实际情况相似的是,在蚂蚁释放信息素的同事,各个城市之间连接路径上的信息素的强度也在通过挥发等方式逐渐消失。为了描述这个特征,设ρ表示信息素挥发程度。这样所有蚂蚁完成走完一遍所有城市之后,各个城市键连接路径上的信息素浓度为
      cij(t+1)=1ρcij(t)+ΔcijΔcij=Δcijk c_{ij}(t+1) = (1-ρ)*c_{ij}(t)+\Delta c_{ij} \\ \Delta c_{ij} = \sum{}{} \Delta c_{ij}^k

    • Δcijk\Delta c_{ij}^k为第k只蚂蚁在城市i与城市k连接路径上释放信息素而增加的信息素浓度

    • Δcij\Delta c_{ij} 为所有蚂蚁在城市i与城市j连接路径上释放信息素而增加的信息素浓度。
      一般情况下
      Δcijk=QLk,ki访j0, \Delta cijk = \frac{Q}{L_k} , 若蚂蚁k从城市i访问了城市j \\ 0 ,否则

    • $Q $为信息素常数

    • LkL_k 为第k只蚂蚁经过路径总长度

    1.3蚁群算法流程

    蚁群算法流程.png

    2.蚁群算法的MATLAB实现

    2.1算法设步骤

    1.数据准备
    2.计算城市距离矩阵
    3.初始化参数
    4.迭代寻找最佳路径
    5.结果显示

    2.2程序代码

    程序中使用到的文件"Chap9_citys_data.xlsx"链接如下:
    链接:https://pan.baidu.com/s/1MStyADIrhFtDHoVJUuTjzg
    提取码:t24f

    %--------------------------------------------------------------------------
    %% 数据准备
    % 清空环境变量
    clear all
    clc
    
    % 程序运行计时开始
    t0 = clock;
    %导入数据
    citys=xlsread('Chap9_citys_data.xlsx', 'B2:C53');
    %--------------------------------------------------------------------------
    %% 计算城市间相互距离
    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
    %--------------------------------------------------------------------------
    %% 初始化参数
    m = 75;                              % 蚂蚁数量
    alpha = 1;                           % 信息素重要程度因子
    beta = 5;                            % 启发函数重要程度因子
    vol = 0.2;                           % 信息素挥发(volatilization)因子
    Q = 10;                               % 常系数
    Heu_F = 1./D;                        % 启发函数(heuristic function)
    Tau = ones(n,n);                     % 信息素矩阵
    Table = zeros(m,n);                  % 路径记录表
    iter = 1;                            % 迭代次数初值
    iter_max = 100;                      % 最大迭代次数 
    Route_best = zeros(iter_max,n);      % 各代最佳路径       
    Length_best = zeros(iter_max,1);     % 各代最佳路径的长度  
    Length_ave = zeros(iter_max,1);      % 各代路径的平均长度  
    Limit_iter = 0;                      % 程序收敛时迭代次数
    %-------------------------------------------------------------------------
    %% 迭代寻找最佳路径
    while iter <= iter_max
        % 随机产生各个蚂蚁的起点城市
          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
                 has_visited = Table(i,1:(j - 1));           % 已访问的城市集合(禁忌表)
                 allow_index = ~ismember(citys_index,has_visited);    % 参加说明1(程序底部)
                 allow = citys_index(allow_index);  % 待访问的城市集合
                 P = allow;
                 % 计算城市间转移概率
                 for k = 1:length(allow)
                     P(k) = Tau(has_visited(end),allow(k))^alpha * Heu_F(has_visited(end),allow(k))^beta;
                 end
                 P = P/sum(P);
                 % 轮盘赌法选择下一个访问城市
                Pc = cumsum(P);     %参加说明2(程序底部)
                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,:);
              Limit_iter = 1; 
              
          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,:);
                  Limit_iter = iter; 
              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-vol) * Tau + Delta_Tau;
        % 迭代次数加1,清空路径记录表
        iter = iter + 1;
        Table = zeros(m,n);
    end
    %--------------------------------------------------------------------------
    %% 结果显示
    [Shortest_Length,index] = min(Length_best);
    Shortest_Route = Route_best(index,:);
    Time_Cost=etime(clock,t0);
    disp(['最短距离:' num2str(Shortest_Length)]);
    disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);
    disp(['收敛迭代次数:' num2str(Limit_iter)]);
    disp(['程序执行时间:' num2str(Time_Cost) '秒']);
    %--------------------------------------------------------------------------
    %% 绘图
    figure(1)
    plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...  %三点省略符为Matlab续行符
         [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(['ACA最优化路径(最短距离:' num2str(Shortest_Length) ')'])
    figure(2)
    plot(1:iter_max,Length_best,'b')
    legend('最短距离')
    xlabel('迭代次数')
    ylabel('距离')
    title('算法收敛轨迹')
    %--------------------------------------------------------------------------
    %% 程序解释或说明
    % 1. ismember函数判断一个变量中的元素是否在另一个变量中出现,返回0-1矩阵;
    % 2. cumsum函数用于求变量中累加元素的和,如A=[1, 2, 3, 4, 5], 那么cumsum(A)=[1, 3, 6, 10, 15]。
    

    程序结果:

    image.png

    image.png

    3.算法关键参数的设定

    1.参数设定的准则

    1. 尽可能在全局上搜索最优解,保证解得最有型
    2. 算法尽快手链,以节省寻优时间
    3. 尽量反映客观存在的规律,以保证这种仿生算法的真实性

    2.蚂蚁数量

    一般设置蚂蚁数量为城市数的1.5倍比较稳妥

    3.信息素因子

    信息素因素a反映蚂蚁在运动过程中所积累的信息量在知道蚁群搜索中的相对重要程度。当a∈[1,4]时,综合求解性能较好

    4.启发函数因子

    启发函数因子b,反映了启发式信息在知道蚁群搜索过程中的相对重要程度,其大小反映了蚁群巡游过程中小言行、确定性因素的作用强度。b过大是,蚂蚁在某个局部点上选择局优的可能性大。b∈[3,4.5],综合求解性能较好。

    5.信息素挥发因子

    信息素挥发因子ρ描述信息素的消失水平,而1-ρ则为信息素残留因子。ρ∈[0.2,0.5]时,综合求解能力较好

    6. 最大迭代次数

    一般去100-500

    7. 组合参数设计策略

    可按照一下策略来进行参数的组合设计:

    1. 确定蚂蚁数目,蚂蚁数目与城市规模之比约为1。5
    2. 参数粗调,即调整取值范围较大的a,b以及Q
    3. 参数微调,即调整取值范围较小的ρ

    4.总结

    蚁群算法有一下特点:

    1. 从算法的性质而言,蚁群算法是在寻找一个比较好的局部最优解,而不是强调全局最优解
    2. 开始时算法收敛速度较快,在随后寻优过程中,迭代一定次数后,容易出现停滞现象
    3. 蚁群算法对TSP及相似问题具有良好的适应性,无论城市规模大还是小,都能进行有效地求解,而且求解速度相对较快
    4. 蚁群算法解得稳定性较差,及时参数不变,每次执行程序都有可能得到不同界,为此需要多执行几次,已寻找最佳解。
    5. 蚁群算法中有多个需要设定的参数,而且这些参数对程序又都有一定的影响,所以选择合适的参数组合在算法设计过程中也非常重要。
    展开全文
  • 分 数_ 任课教师签字_ 华北电力大学研究生结课作业 学 年 学 期20 10 学年第二学期 课 程 名 称人工智能与知识工程 学 生 姓 名张华壮 学 号2 10222 1007 题 目蚁群算法概述 提 交 时 间20 11/4/ 13 1 蚁群算法概述 ...
  • 蚁群算法原理介绍;蚁群算法起源;蚁群行为描述;蚁群行为描述;基本蚁群算法的机制原理;基本蚁群算法的系统学特征;蚁群算法是一个系统;蚁群算法满足分布式计算;蚁群算法具有自组织的特征;蚁群算法具有正反馈的特征;自...
  • 蚁群算法发展;蚂蚁的生物学特征;蚁群算法起源;蚁群算法的基本原理;蚁群算法的基本原理;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;蚁群算法模型的建立;蚁群算法模型的建立;蚁群算法模型的建立;蚁群...
  • 蚁群算法蚁群算法

    2017-02-16 19:02:12
    蚁群算法蚁群算法

空空如也

空空如也

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

蚁群算法