精华内容
下载资源
问答
  • 数学建模-启发式算法-蚁群算法
    千次阅读
    2020-02-29 11:27:00

    蚁群算法

    蚁群算法,由Marco Dorigo于1992年在他的博士论文中提出,是一种灵感来源于蚂蚁在寻找食物过程中发现路径的行为,用来在图中寻找优化路径的算法。

    算法原理

    蚂蚁在运动的过程中,会在它所经过的路径上留下一种称之为信息素的物质进行信息传递,而且蚂蚁在运动的过程中能够感知这种物质,并以此指导自己的运动方向,其中信息素浓度与路径长度成反比。 假如此路径已被前蚂蚁走过已经留下了信息素,当后来的蚂蚁经过此位置时,会更可能选择信息素较高的路径,注意是可能不是一定,只是概率更大,然后大量蚂蚁组成的群体行为便展现出一种信息正反馈的现象,某一路径上走的蚂蚁越多,后来者选择该路径概率越大,而信息素浓度与路径长度成反比,最终出现最优路径的概率也越大。
    在这里各细节不逐一介绍,在后文的算法步骤种涉及的每一个对象都会详细介绍。

    算法特点

    • 其原理是一种正反馈机制或者称为增强型学习系统;它通过最优路径上蚂蚁数量增加导致后来蚂蚁选择该路径概率增大达到最终收敛于最优路径。
    • 它是一种通用型随机优化方法,它吸收了蚂蚁的行为特征,它使用人工蚂蚁进行仿真。
    • 它是一种分布式的优化方法,多个体同时进行搜索,具有本质并行性,大大提高了算法的搜索效率。
    • 它是一种启发式算法,不容易陷入局部最优而更容易搜索到全局最优。
    • 它是一种全局优化的方法,不仅可以用于求解单目标优化问题,而且可用于求解多目标优化问题。

    算法步骤

    以TSP问题为例。即在有限个城市内找到路径最短的距离组合。

    • 初始化参数

    在计算的开始需要对一些相关的参数进行初始化,如:
    蚂蚁数量,既然是蚁群算法,我们肯定要拥有自己的蚁群,由它们对问题的解进行搜索,蚂蚁数量根据经验一般设定为目标数的1.5倍比较好,当蚂蚁数量较多时,所有蚂蚁不容易收敛于一个解,而数量较少时,解的效果可能不会让人满意。
    信息素重要程度因子,这个参数是指在蚂蚁移动的过程种产生的信息素对蚂蚁的影响程度,比较好理解,参数越大,蚂蚁选择以前走过路径的可能性越大,会使蚁群更容易的收敛,导致搜索的随机性减弱不利于寻找全局最优解,过小的话就没有了信息素的意义,此参数一般为[0,5]之间比较好。
    启发函数重要程度因子,它反映了启发式信息在指导蚁群在路径搜索中的相对重要程度,其大小反映的是蚁群寻优过程种先验性、确定性因素作用的强度。当它越大也是更容易导致收敛过快。一般设置为[0,5]。
    信息素挥发因子,它是指信息素的消失水平,它的大小直接关系到算法的全局搜索能力和收敛速度,过大导致信息素挥发过快,一些较好的路径会被排除,过小导致路径残留信息素较多,影响算法效率。一般设置为[0.2,0.5]。
    信息素常量,它是指蚂蚁在将路径走完时总共释放的信息素数量,它往往和启发函数一起作用,一般设置在[10,1000],问题规模越大信息素越高较好。
    迭代次数,它是指整个蚁群累积搜索了多少次,注意蚁群算法在搜索过程种是整个蚁群同时开始搜索,然后此蚁群循环迭代,此参数一般设置为[100,500]之间,迭代次数设置的过高对算法没有实质意义,一般使其能够收敛即可。

    • 构建模型

    我们要知道目标蚂蚁是在固定的解空间内寻找最优解,首先肯定是将蚂蚁放在各个不同的出发点,然后让蚂蚁根据选择依据选择下一个要访问的城市,这个选择依据我们一般使用轮盘赌的方法,其中第i只蚂蚁到第j个城市的概率为:
    P i j = τ i j α D i j β P^{}_{ij}=\frac{{\tau^{}_{ij}}^{\alpha}}{{D^{}_{ij}}^{\beta}} Pij=Dijβτijα
    其中 α \alpha α为信息重要程度因子, β \beta β为启发函数重要程度因子, τ i j {\tau^{}_{ij}} τij为第i个目标到第j个目标直接的信息素, D i j {D^{}_{ij}} Dij表示第i个目标到第j个目标直接的距离。然后让蚂蚁根据此规则进行搜索即可。

    • 更新信息素

    计算各蚂蚁经过的路径长度,记录当前最优解,之后将路径上的信息素进行更新,新的信息素量等于原本就有的信息素挥发后剩下的量加上此蚂蚁走过留下的信息素。在迭代过程中始终对信息素进行累加,以保证最终蚂蚁能够收敛到最优解。其中增加的信息素为:
    Δ τ i j = Q L \Delta{\tau^{}_{ij}}=\frac{Q}{L} Δτij=LQ
    Q为之前设置的信息素常量,L为蚂蚁走过总距离的长度,增加的信息素保证增加在此蚂蚁走过的所有路径段上。即假如一只蚂蚁走过的路径为:1->5->3->2->4->1,那么在1-5、5-3、3-2、2-4、4-1之间的路径上都要加上 Δ τ i j \Delta{\tau^{}_{ij}} Δτij
    在这里插入图片描述

    • 判断算法是否达到迭代次数

    这就比较简单了,每当该种群走完之后都判断一下,作为算法停止依据,最终选择当前最优解近似作为全局最优解。

    流程图

    Created with Raphaël 2.2.0 开始 初始化参数 构建模型 更新信息素 达到最大迭代次数 输出最优解 结束 迭代次数+1, 情况路径记录表 yes no

    代码

    % 数据准备
    % 清空环境变量
    clear all;
    clc;
    close all;
    % 程序运行计时开始
    t0 = clock;
    %导入数据
    citys=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;...
        4196 1044;4312  790;4386  570;3007 1970;2562 1756;2788 1491;2381 1676;...
        1332  695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;...
        4263 2931;3429 1908;3507 2376;3394 2643;3439 3201;2935 3240;3140 3550;...
        2545 2357;2778 2826;2370 2975];
    %--------------------------------------------------------------------------
    %% 计算城市间相互距离
    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 = 200;                      % 最大迭代次数 
    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);   
                 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);     
                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('算法收敛轨迹')
    %--------------------------------------------------------------------
    
    更多相关内容
  • 蚁群算法启发式搜索算法之一。想学习算法的可以学学。济南大学的教材。
  • 蚁群算法Python实现.zip

    2020-03-30 22:04:07
    蚁群算法的 Python 实现。除此之外,还有这些算法的集合:差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁群算法、免疫优化算法、鱼群算法
  • 本帖最后由 小蜗 于 2016-4-9 10:09 编辑鄙人初学蚁群算法,运行时遇到了问题。参数我输入的是:m=30;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;C是一个24X2的矩阵,工作区如图。但是无法运行,显示参数不足。跪求...

    本帖最后由 小蜗 于 2016-4-9 10:09 编辑

    鄙人初学蚁群算法,运行时遇到了问题。参数我输入的是:m=30;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;C是一个24X2的矩阵,工作区如图。但是无法运行,显示参数不足。跪求大神指教!急!在线等!

    程序如下:

    function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=UntitledYQSF5(C,NC_max,m,Alpha,Beta,Rho,Q)

    %%-------------------------------------------------------------------------

    %% 主要符号说明

    %% C n个城市的坐标,n×2的矩阵

    %% NC_max 最大迭代次数

    %% m 蚂蚁个数

    %% Alpha 表征信息素重要程度的参数

    %% Beta 表征启发式因子重要程度的参数

    %% Rho 信息素蒸发系数

    %% Q 信息素增加强度系数

    %% R_best 各代最佳路线

    %% L_best 各代最佳路线的长度

    %%=========================================================================

    %%第一步:变量初始化

    n=size(C,1);%n表示问题的规模(城市个数)

    %%size(A,n)如果在size函数的输入参数中再添加一项n,并用1或2为n赋值,则 size将返回矩阵的行数或列数。其中r=size(A,1)该语句返回的时矩阵A的行数, c=size(A,2) 该语句返回的时矩阵A的列数。

    D=zeros(n,n);%D表示完全图的赋权邻接矩阵

    for i=1:n

    for j=1:n

    if i~=j

    D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;

    else

    D(i,j)=eps;      %i=j时不计算,应该为0,但后面的启发因子要取倒数,用eps(浮点相对精度)表示

    end

    D(j,i)=D(i,j);   %对称矩阵

    end

    end

    Eta=1./D;          %Eta为启发因子,这里设为距离的倒数

    Tau=ones(n,n);     %Tau为信息素矩阵

    Tabu=zeros(m,n);   %存储并记录路径的生成

    NC=1;               %迭代计数器,记录迭代次数

    R_best=zeros(NC_max,n);       %各代最佳路线

    L_best=inf.*ones(NC_max,1);   %各代最佳路线的长度

    L_ave=zeros(NC_max,1);        %各代路线的平均长度

    while NC<=NC_max        %停止条件之一:达到最大迭代次数,停止

    %%第二步:将m只蚂蚁放到n个城市上

    Randpos=[];   %随即存取

    for i=1:(ceil(m/n))  %ceil函数是取比它大的最小整数  假如5只蚂蚁4座城市 需要循环2次

    Randpos=[Randpos,randperm(n)];%随迭代次数改变?

    end

    Tabu(:,1)=(Randpos(1,1:m))';    %%表示将m个蚂蚁随机,每个蚂蚁放到前面产生的城市序列中,每个蚂蚁一个城市,需要m个,所以提取前面1:m个序列

    %%第三步:m只蚂蚁按概率函数选择下一座城市,完成各自的周游

    for j=2:n     %所在城市不计算

    for i=1:m

    visited=Tabu(i,1:(j-1)); %记录已访问的城市,避免重复访问

    J=zeros(1,(n-j+1));       %待访问的城市

    P=J;                      %待访问城市的选择概率分布

    Jc=1;

    for k=1:n

    if isempty(find(visited==k, 1))   %开始时置0

    J(Jc)=k;

    Jc=Jc+1;                         %访问的城市个数自加1

    end

    end

    %下面计算待选城市的概率分布

    for k=1:length(J)

    P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);

    end

    P=P/(sum(P));

    %按概率原则选取下一个城市

    Pcum=cumsum(P);     %cumsum,元素累加即求和

    Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线

    to_visit=J(Select(1));

    Tabu(i,j)=to_visit;

    end

    end

    if NC>=2

    Tabu(1,:)=R_best(NC-1,:);

    end

    %%第四步:记录本次迭代最佳路线

    L=zeros(m,1);     %开始距离为0,m*1的列向量

    for i=1:m

    R=Tabu(i,:);

    for j=1:(n-1)

    L(i)=L(i)+D(R(j),R(j+1));    %原距离加上第j个城市到第j+1个城市的距离

    end

    L(i)=L(i)+D(R(1),R(n));      %一轮下来后走过的距离

    end

    L_best(NC)=min(L);           %最佳距离取最小

    pos=find(L==L_best(NC));

    R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线

    L_ave(NC)=mean(L);           %此轮迭代后的平均距离

    NC=NC+1;                      %迭代继续

    %%第五步:更新信息素

    Delta_Tau=zeros(n,n);        %开始时信息素为n*n的0矩阵

    for i=1:m

    for j=1:(n-1)

    Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);

    %此次循环在路径(i,j)上的信息素增量

    end

    Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);

    %此次循环在整个路径上的信息素增量

    end

    Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发,更新后的信息素

    %%第六步:禁忌表清零

    Tabu=zeros(m,n);             %%直到最大迭代次数

    end

    %%第七步:输出结果

    Pos=find(L_best==min(L_best)); %找到最佳路径(非0为真)

    Shortest_Route=R_best(Pos(1),:); %最大迭代次数后最佳路径

    Shortest_Length=L_best(Pos(1)); %最大迭代次数后最短距离

    subplot(1,2,1)                  %绘制第一个子图形

    DrawRoute(C,Shortest_Route)     %画路线图的子函数

    subplot(1,2,2)                  %绘制第二个子图形

    plot(L_best)

    hold on                         %保持图形

    plot(L_ave,'r')

    title('平均距离和最短距离')     %标题

    function DrawRoute(C,R)

    %%=========================================================================

    %% DrawRoute.m

    %% 画路线图的子函数

    %%-------------------------------------------------------------------------

    %% C Coordinate 节点坐标,由一个N×2的矩阵存储

    %% R Route 路线

    %%=========================================================================

    N=length(R);

    scatter(C(:,1),C(:,2));

    hold on

    plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)],'g')

    hold on

    for ii=2:N

    plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g')

    hold on

    end

    title('GIS配送优化结果 ')

    工作区.png

    (10.37 KB, 下载次数: 0)

    2016-4-9 10:05 上传

    442a53943febe9465fc072b4fbe10813.gif

    b2a5a3e0dcc7d508e00275fe42fce1b5.gif

    工作区截屏

    10d3e3c2e517067725a87db93bf2fcc6.png

    2.png

    (74.89 KB, 下载次数: 0)

    2016-4-9 10:05 上传

    442a53943febe9465fc072b4fbe10813.gif

    b2a5a3e0dcc7d508e00275fe42fce1b5.gif

    编辑器和命令窗口截屏

    31453f3c8058e2673bbdedc55277f31e.png

    展开全文
  • 一种改进的启发式蚁群算法(论文) An Improved Heuristic Ant-Clustering Algorithm
  • 本资源为使用蚁群算法来优化路径,并使用在具体的旅行商问题上,主函数将寻优过程和收敛曲线绘图显示
  • 群体智能算法作为智能启发式算法,它与自然界的生物的行为有着密不可分的关系,这也引起了许多学者和专家的浓厚的兴趣,各类智能算法也相继问世智能优化算法可以解决多种最优化问题,提供了遗传算法、蚁群算法、狼群...
  • 蚁群算法matlab源码解决TSP-VRP 求解旅行商问题和车辆路径问题的启发式算法的MATLAB实现。 目标 探索每次路线规划中所有车辆行驶的最小距离的值。 (如果愿意,目标函数的类型可以是距离以外的其他东西,例如时间,...
  • 基于启发式规则和蚁群算法的车间作业调度方法,陈英武,邢立宁,车间作业调度问题是一个典型的NP-hard问题,也是一个前沿性的研究课题,已受到学术界和工业界的广泛关注。该文提出了一种基于启发�
  • 以卫星舱布局问题作为研究背景,求解了带平衡约束的矩形布局问题。...在启发式策略的基础上,设计了蚁群算法搜索优化定位次序,从而得到优化的布局。数值仿真结果表明,该布局方法具有优良的计算性能。
  • 6.7 蚁群算法及其应用 产生背景 20世纪90年代初意大利科学家Marco Dorigo等受 蚂蚁觅食行为的启发提出蚁群算法(Ant Colony OptimizationACO) 一种应用于组合优化问题的启发式搜索算法 在解决离散组合优化方面具有...
  • 改进了信息素的更新方式,以提高蚁群算法的自适应性,使得算法在执行过程中能根据收敛和进展情况,相应地调整信息残留程度,从而提高收敛速度或全局搜索能力;引人了一种确定性搜索方法,加快启发式搜索的收敛速度....
  • 基于启发式蚁群算法的协同多目标攻击空战决策研究
  • 借鉴蚁群算法的进化思想, 提出一种求解连续空间优化问题的蚁群算法。该算法主要包括全局 搜索、 局部搜索和信息素强度更新规则。在全局搜索过程中, 利用信息素强度和启发式函数确定蚂蚁移 动方向。在局部...
  • 蚁群算法_蚁群算法_

    2021-09-30 08:07:54
    蚁群算法是一种用来寻找优化路径的概率型算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。
  • 蚂蚁会分泌一种叫做信息素的化学物质,蚂蚁的许多行为受信息素的调控。蚂蚁在运动过程中能够感知其经过的路径上信息素的浓度,蚂蚁倾向朝着信息素浓度高的方向移动。 蚂蚁从A点出发,速度相同,食物在D点,取得...

    一、原理   

         蚂蚁会分泌一种叫做信息素的化学物质,蚂蚁的许多行为受信息素的调控。蚂蚁在运动过程中能够感知其经过的路径上信息素的浓度,蚂蚁倾向朝着信息素浓度高的方向移动。

        

        蚂蚁从A点出发,速度相同,食物在D点,取得食物后再折返回蚁巢。可能随机选择路线ABD(9个时间单位)或ACD(18个时间单位)。假设蚂蚁每经过一处所留下的信息素为一个单位,则经过36个时间单位后,所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物,此时ABD的路线往返了2趟,每一处的信息素为4个单位,而ACD的路线往返了一趟,每一处的信息素为2个单位,其比值为2:1。

        单位时间内路径上通过蚂蚁的数量越多,则该路径上留下的信息素浓度越高。因此,最短路径上走过的蚂蚁数量越多,则后来的蚂蚁选择该路径的机率就越大,从而蚂蚁通过信息的交流实现了寻找食物和蚁巢之间最短路的目的。

    二、蚁群算法

    蚁群算法的基本原理:


    1、蚂蚁在路径上释放信息素。

    2、碰到还没走过的路口,就随机挑选一条路走。同时,释放与路径长度有关的信息素。

    3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时,就选择信息素浓度较高路径。

    4、最优路径上的信息素浓度越来越大。

    5、最终蚁群找到最优寻食路径。

    流程

    三、案例

    对于 TSP(旅行商问题),其流程图如下

    https://leovan.me/cn/2019/04/heuristic-algorithms/

    https://blog.csdn.net/qq_33829154/article/details/85258615

    https://blog.csdn.net/qq_36744449/article/details/120033201

    https://www.cnblogs.com/caiyishuai/p/13270746.html

    https://blog.csdn.net/weixin_42715356/article/details/83590449

    展开全文
  • 蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是...
  • 我的机器学习教程「美团」算法工程师带你入门机器学习 以及「三分钟系列」数据结构与算法已经开始更新了,欢迎大家订阅~这篇专栏整合了这几年的算法知识,简单易懂,也将是我实体书的BLOG版。 欢迎大家扫码关注微信...

    我的机器学习教程「美团」算法工程师带你入门机器学习  以及 「三分钟系列」数据结构与算法  已经开始更新了,欢迎大家订阅~这篇专栏整合了这几年的算法知识,简单易懂,也将是我实体书的BLOG版。

    欢迎大家扫码关注微信公众号「图灵的猫」,除了有更多AI、算法、Python相关文章分享,还有免费的SSR节点和外网学习资料。其他平台(微信/知乎/B站)也是同名「图灵的猫」,不要迷路哦~

     

    一、退火算法

    模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。

    模拟退火算法新解的产生和接受可分为如下四个步骤:

    第一步是由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。

    第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。

    第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropolis接受准则: 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。

    第四步是当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。

    有关退火算法的CSDN文章:模拟退火算法 - ACdreamer - 博客频道 - CSDN.NET

    二、遗传算法

    遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。

    遗传算法是基于生物学的,理解或编程都不太难。下面是遗传算法的一般算法:

    1. 建初始状态 初始种群是从解中随机选择出来的,将这些解比喻为染色体或基因,该种群被称为第一代,这和符号人工智能系统的情况不一样,在那里问题的初始状态已经给定了。
    2. 评估适应度 对每一个解(染色体)指定一个适应度的值,根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈,可以把它理解成为要得到答案,系统可能需要利用的那些特性。
    3. 繁殖 繁殖(包括子代突变) 带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物,他们由来自父母的基因结合而成,这个过程被称为“杂交”。
    4. 下一代 如果新的一代包含一个解,能产生一个充分接近或等于期望答案的输出,那么问题就已经解决了。如果情况并非如此,新的一代将重复他们父母所进行的繁衍过程,一代一代演化下去,直到达到期望的解为止。
    5. 并行计算 非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构,指定一个节点为“农场主”节点,负责选择有机体和分派适应度的值,另外的节点作为“劳工”节点,负责重新组合、变异和适应度函数的评估。

     

    三、蚁群算法

     

    各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后,它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近)来实现的,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开辟的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来。最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着。

    下面是本算法的一些说明:

    1. 范围 蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是3),那么它能观察到的范围就是3*3个方格世界,并且能移动的距离也在这个范围之内。
    2. 环境 蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,还有信息素,信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。
    3. 觅食规则 在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。
    4. 移动规则 每只蚂蚁都朝向信息素最多的方向移,并且,当周围没有信息素指引的时候,蚂蚁会按照自己原来运动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈,它会记住刚才走过了哪些点,如果发现要走的下一点已经在之前走过了,它就会尽量避开。
    5. 避障规则 如果蚂蚁要移动的方向有障碍物挡住,它会随机的选择另一个方向,并且有信息素指引的话,它会按照觅食的规则行为。
    6. 信息素规则 每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多,并随着它走远的距离,播撒的信息素越来越少。

     

    根据这几条规则,蚂蚁之间并没有直接的关系,但是每只蚂蚁都和环境发生交互,而通过信息素这个纽带,实际上把各个蚂蚁之间关联起来了。比如,当一只蚂蚁找到了食物,它并没有直接告诉其它蚂蚁这儿有食物,而是向环境播撒信息素,当其它的蚂蚁经过它附近的时候,就会感觉到信息素的存在,进而根据信息素的指引找到了食物。

     

    以上是算法学习过程中所引用的一些理论上的知识,有关应用请参看具体应用部分。

    展开全文
  • 蚁群算法的Matlab实现

    2020-10-29 21:50:18
    蚁群算法(Ant Algorithm),源于求解旅行商TSP问题,是一种寻找优化路径的概率型算法,灵感来源于蚂蚁寻找食物中发现路径的行为,本质是进化算法中一种启发式全局的优化算法。
  • 针对蚁群算法应用于自动导引小车路径规划收敛速度慢、极易陷入局部最优的缺点,提出一种基于信息素负反馈的超启发式蚁群优化(ACONhh)算法。该算法充分利用历史搜索信息和持续获得错误经验,较快引导蚁群探索最优...
  • 蚁群算法详解讲解

    2022-04-09 22:24:43
    0x01 蚁群效应 《昆虫记》中这样描述红蚂蚁:红蚂蚁出征的远近取决于黑蚂蚁家的远近,它们出征的道路并不选择,也没有明确的目的地。除了水路之外,它们都能穿过 单个蚂蚁不存在有规律的、复杂...在理解蚁群算法
  • 什么是启发式算法?  启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指...
  • 蚁群算法原理简述.pdf

    2019-07-26 14:55:42
    蚁群算法是一种基于种群的启发式仿生进化系统,,该算法采用了分布式正反馈并行计算机制,易于与其他方法结合,而 且具有较强的鲁棒性。
  • 针对重叠社团检测准确率提升问题,提出了一种基于改进蚁群算法的新型重叠社团检测算法。该算法包含位置初始化、运动和后处理三个阶段,分别通过初始位置识别与标签列表存储、基于节点间相似度的启发式信息重定义、...
  • 在MATLAB中利用蚁群算法进行优化PID参数,function [Pid_kp_Opertimizer,Pid_ti_Opertimizer,Pid_td_Opertimizer,Overshoot,Tr,Ts]=OptimizerPID1(m,NC_max,Alpha,Beta,Rho,Q) %% 主要符号说明 %% NC_max 最大迭代...
  • 提出一种带容量约束车辆路由问题(CVRPs) 的改进蚁群算法. 该算法使用一种新的蚂蚁位置初始化方式, 增加了蚂蚁走出最优路径的可能性. 在搜索过程中, 以客户之间路径的节省量作为启发式信息. 信息素更新采用一种...
  • 这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法蚁群系统(Ant System或Ant Colony System)是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。...
  • 人工蚁群算法是受到蚂蚁在觅食过程中能发现...对蚁群算法的起源和发展历史、算法理论研究的主要内容和方法、基于算法的改进以及应用范畴等,进行了系统的总结与综述,并对这一新型现代启发式算法的发展方向进行了展望.
  • 对于基本蚁群算法(ACA)不适用求解连续空间问题,并且极易陷入局部最优的缺点,提出了一种基于自适应的蚁群算法。路径搜索策略采用基于目标函数值搜索筛选局部最优解的策略,确保能够迅速找到可行解。信息素更新...

空空如也

空空如也

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

蚁群算法的启发式信息