精华内容
下载资源
问答
  • 2021-04-22 19:24:36

    本帖最后由 小蜗 于 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

    更多相关内容
  • 蚁群算法参数α、β、ρ设置的研究——以TSP问题为例.pdf
  • 蚁群算法调参记录

    千次阅读 2018-05-27 09:26:07
    蚁群算法主要有5个参数a信息素重要程度,b启发式因子重要程度,c信息素蒸发系数,ant蚂蚁数量,iter迭代次数制作了一个50个节点的地图,用交叉对比的方法寻找最佳参数首先调b蚂蚁数100,迭代数100.很明显b越小距离和...

    蚁群算法主要有5个参数

    a信息素重要程度,

    b启发式因子重要程度,

    c信息素蒸发系数,

    ant蚂蚁数量,

    iter迭代次数

    制作了一个50个节点的地图,用交叉对比的方法寻找最佳参数

    首先调b


    蚂蚁数100,迭代数100.

    很明显b越小距离和平均值越大,标准差也越大,b=14的时候距离的平均值,最小值,和标准差都几乎是最小的,当b=20的时候距离变大。

    这件事的可能原因是b大一些会使城市的权重和sum变的很小Math.pow(1.0/distance[currentCity][i], b),可能会达到2.397101359805423E-30,这样会使优势城市权重占比变的非常突出。而如果b很小比如如果b=2,sum可能等于9.226501283762148E-7,这样会使被选城市的权重占比看起来优势模糊。

    所以b选择14.

    然后调节a


    a对效果的影响看起来像是单调的,随着a的减小平均值,标准差都在减小。当a=0.0001的时候得到的最小值更小些,所以a取0.0001.

    然后调节r

    蚂蚁数100,迭代数100.

     

    当r等于0的时候意味着信息素矩阵没有遗忘,当r=1的时候相当于蚂蚁完全是在随机运动,但是可以看到即便是没有信息素矩阵的帮助只是靠着城市之间距离的关系得到的值也并不是非常差,71212相比67801相差大概5%。

    通过对比可以发现除了r=1完全遗忘,其余的值对结果的影响都不是很明显。也就是说信息素只要不是全忘了对结果相差不大。

    所以r选择0.5,

    然后调节蚂蚁数和迭代数



    增加蚂蚁数和迭代数效果非常明显,随着蚂蚁数*迭代数的增大,距离平均值和标准差都在减小。耗时也在等比例的增大。

    综合起来

    a信息素重要程度,a越小得到的距离越小

    b启发式因子重要程度,有至少一个最优值

    c信息素蒸发系数,只要不是1,相差并不是特别大

    ant蚂蚁数量,数量越多性能越好,越稳定,耗时也越大

    iter迭代次数,数量越多性能越好,越稳定,耗时也越大


    原始数据地图





















    展开全文
  • 蚁群算法参数设置一直是依靠经验和试验来确定,造成试验工作量大且难以得到最优的参数组合,影响了算法的使用.通过将蚁群算法基本模型的参数设定问题描述成均匀设计中多因素多水平的试验设计,从而能够用较少的试验...
  • 蚁群算法参数设置一直是依靠经验和试验来确定,造成试验工作量大且难以得到最优的参数组合,影响了算法的使用。通过将蚁群算法基本模型的参数设定问题描述成均匀设计中多因素多水平的试验设计,从而能够用较少的...
  • 蚁群算法

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

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

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

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

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

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

    人工蚁群与真实蚁群对比:

    基于TSP问题的基本蚁群算法:

    TSP求解中,假设蚁群算法中的每只蚂蚁是具有以下特征的简单智能体:

    每次周游,每只蚂蚁在其经过的支路(i,j)上都留下信息素。

    蚂蚁选择城市的概率与城市之间的距离和当前连接支路上所包含的信息素余量有关。

    ƒ为了强制蚂蚁进行合法的周游,直到一次周游完成后,才允许蚂蚁游走已访问过的城市(这可由禁忌表来控制)。

    基本蚁群的两个过程:

    (1)状态转移

    (2)信息素更新

    (1)状态转移

    为了避免残留信息素过多而淹没启发信息,在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后,要对残留信息进行更新处理。

    由此,t+n时刻在路径(i,j)上的信息量可按如下规则进行调整: 

    (2)信息素更新模型

    蚁周模型(Ant-Cycle模型)

    蚁量模型(Ant-Quantity模型)

    蚁密模型(Ant-Density模型)

    区别:

    1.蚁周模型利用的是全局信息,即蚂蚁完成一个循环后更新所有路径上的信息素;

    2.蚁量和蚁密模型利用的是局部信息,即蚂蚁完成一步后更新路径上的信息素。

    蚁群算法基本流程:

    蚁群算法中主要参数的选择:

    蚁群算法中主要参数的理想选择如下:

    国内外,对于离散域蚁群算法的改进研究成果很多,例如自适应蚁群算法、基于信息素扩散的蚁群算法等,这里仅介绍离散域优化问题的自适应蚁群算法。

    自适应蚁群算法:对蚁群算法的状态转移概率、信息素挥发因子、信息量等因素采用自适应调节策略为一种基本改进思路的蚁群算法。

    自适应蚁群算法中两个最经典的方法:蚁群系统(AntColony System, ACS)和最大-最小蚁群系统(MAX-MINAnt System, MMAS)。

    蚁群系统对基本蚁群算法改进:

    蚂蚁的状态转移规则不同;

    ②全局更新规则不同;


    ③新增了对各条路径信息量调整的局部更新规则


    用蚁群算法求解TSP问题:一个旅行商人要拜访全国31个省会城市,需要选择最短的路径.

    %%%一个旅行商人要拜访全国31个省会城市,需要选择最短的路径%%%%
    
    
    %%%蚁群算法解决TSP问题%%%%%%%
    
    clear all; %清除所有变量
    close all; %清图
    clc ;      %清屏
    m=50;    %% m 蚂蚁个数
    Alpha=1;  %% Alpha 表征信息素重要程度的参数
    Beta=5;  %% Beta 表征启发式因子重要程度的参数
    Rho=0.1; %% Rho 信息素蒸发系数
    NC_max=200; %%最大迭代次数
    Q=100;         %%信息素增加强度系数
    
    C=[
    1304 2312;
    3639 1315;
    4177 2244;
    3712 1399;
    3488 1535;
    3326 1556;
    3238 1229;
    4196 1004;
    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 2367;
    3394 2643;
    3439 3201;
    2935 3240;
    3140 3550;
    2545 2357;
    2778 2826;
    2370 2975
    ];                %%31个省会坐标
    %%-------------------------------------------------------------------------
    %% 主要符号说明
    %% C n个城市的坐标,n×2的矩阵
    %% NC_max 最大迭代次数
    %% m 蚂蚁个数
    %% Alpha 表征信息素重要程度的参数
    %% Beta 表征启发式因子重要程度的参数
    %% Rho 信息素蒸发系数
    %% Q 信息素增加强度系数
    %% R_best 各代最佳路线
    %% L_best 各代最佳路线的长度
    %%=========================================================================
    %%第一步:变量初始化
    n=size(C,1);%n表示问题的规模(城市个数)
    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))
            Randpos=[Randpos,randperm(n)];
        end
        Tabu(:,1)=(Randpos(1,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 length(find(visited==k))==0   %开始时置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)) %最大迭代次数后最短距离
    
    figure(1) 
    plot(L_best)
    xlabel('迭代次数')
    ylabel('目标函数值')
    title('适应度进化曲线')
    
    
    figure(2)
    subplot(1,2,1)                  %绘制第一个子图形
       %画路线图
    %%=========================================================================
    %% 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('旅行商问题优化结果 ')
    
    subplot(1,2,2)                  %绘制第二个子图形
    plot(L_best)
    hold on                         %保持图形
    plot(L_ave,'r')
    title('平均距离和最短距离')     %标题
    
    
    
    

    输出结果如下:





    展开全文
  • 蚁群算法动画演示

    2017-02-20 12:54:04
    动态演示蚁群优化算法的过程,可以设置相关参数来获得最优路径
  • 根据基本蚁群算法的两个常用信息素更新公式,研究了算法中最初信息量、信息素挥发因子、信息素增量之间的关系以及变化规律,找到了其不等式关系,并进行了仿真证明。
  • 蚁群算法参数设置对超声回波估计性能的影响
  • 目录 蚁群算法定义 蚁群算法原理 蚁群算法基本流程 matlab源码: ...蚁群算法定义 ...蚁群算法(ant colony optimization, ACO),...针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了...

    目录

    蚁群算法定义

    蚁群算法原理

    蚁群算法基本流程

    matlab源码:


    蚁群算法定义

            蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。


    蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信,它在问题空间的多点同时进行独立搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。

    蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。蚂蚁在运动过程中会留下信息素,蚂蚁在运动时又可以感知这种物质,来确定自己的运动方向。因此,大量蚂蚁组成的蚂蚁群体的集体行为表现出一种信息的正反馈现象。


    蚁群算法的思想来源于自然界蚂蚁觅食,蚂蚁在寻找食物源时,会在路径上留下蚂蚁独有的路径标识——信息素,蚂蚁会感知其他蚂蚁在各条路径上留下的信息素,并根据各条路径上的信息素浓度来选择之后要走的路,路径上留有的信息浓度越高,则蚂蚁更倾向于选择该路径。在蚂蚁选择某条路径后也会在改路径上留下信息素吸引更多蚂蚁选择该路径,随着时间的推移,信息素浓度不断增大,蚂蚁选择路径的概率也随之增高,由此形成了正反馈机制。由于蚁群算法的正反馈性,因此蚁群算法也属于增强型学习算法的其中一种。


    蚁群算法原理

    初始时刻,不妨将P kij (t)设为t时刻蚂蚁k从结点i转移到结点j的概率。“蚂蚁TSP”策略收到两方面的左右,首先是访问某结点的概率,这个概率的大小依赖于其他蚂蚁释放的信息素浓度。所以定义:

    式中,nkij (t)为启发函数,表示蚂蚁从结点i转移到结点j的概率;allowk为蚂蚁k下一步可转移结点的集合,随着时间的推移,allowk储存的元素数量会减小,最终会变为空集合。a 为信息素重要程度因子。

    与实际情况类似的一点是:随着时间的推移,残留在路径上的信息素会逐渐挥发,蚂蚁在经过路径时残留的信息素量也会逐渐等同于信息素挥发量,最终使信息素残留量趋于稳定。令α表示信息素挥发程度,那么所有蚂蚁遍历完所有结点之后,各路径上的信息素残留量的数学表达式如下:

    式中,ckij为第k只蚂蚁在连接结点i 与结点k的路径上释放信息素而增加的信息素浓度。Δckij为所有蚂蚁在结点i 与结点k 连接路径上释放信息素而增加的信息素浓度,通常情况下:

    式中,Q为路径信息素常量,I为第k 只蚂蚁所经过路径的总长度[3]。

    蚂蚁回退策略

    蚂蚁在搜索路径时,以当前节点为中心,来选择目标路径上的下一个节点,在搜索复杂环境中会有不连通路径,此刻蚂蚁无路可行,即落入陷阱,由于蚂蚁落入陷阱而不能自救,就会处于死亡状态,算法会出现停滞现象。这说明算法健壮性不够强,需要设计策略来避免蚂蚁陷入陷阱中。因此为了避免此类问题,加入蚂蚁回退策略来提高算法鲁棒性。改进的信息素更新。

    在基本蚁群算法中,蚁群完成一次循环后信息素更新如下:

    式中:P表示信息素挥发率,取值范围( 0,1) ;   k/ij表示在节点i到j路径上,第k只蚂蚁释放的信息素。为了避免传统蚁群算法陷入局部最优和提高收敛速度。研究表明,狼群捕获猎物后会把食物分给最强壮的狼吃,保证强壮狼群捕获更多的猎物来维持种群生存,而弱小的狼最终会被饿死而淘汰。加入狼群分配策略后,进行更新的信息素如下:

    式中 :Lb本次局部循环最短路径,Lg 是本次局部最差路径 ;b,w分别表示本次循环中局部最短、最差蚂蚁个数[4]。

    改进的转移概率

    蚁群算法中不可避免出现死锁蚂蚁,究其根本原因是由于蚂蚁在搜索路径时不可避免会遇到周围的节点都是己走过的或者存在障碍物的情形,蚂蚁不可通过,只能停留在原地。根据公式为此搜索初期采取避障策略,增加避障因子,为了提高算法效率,定义一个用于替代启发函数   ij 的目标吸引度函数。

    式中: gjs 表示用DIJKSTRA 算法计算的节点j 到目标点g的最短距离。将式代如式,得到了蚂蚁改进后的转移概率为:

    根据环境的建立可对蚂蚁在复杂野外环境下的路径搜索进行引导,提高了蚂蚁选择离目标点更邻近节点的概率


    蚁群算法基本流程

     



     C#工程源码:

    点击这里获取基于C#的蚁群算法工程源码


    matlab源码:

    %% 旅行商问题(TSP)优化
    %% 清空环境变量
    clear all
    clc
    
    %% 导入数据
    load citys_data.mat
    
    %% 计算城市间相互距离
    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 = 7;                            % 启发函数重要程度因子
    rho = 0.1;                           % 信息素挥发因子
    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('各代最短距离与平均距离对比')
    
    

    展开全文
  • 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的 一种仿生算法:蚂蚁在运动过程中,能够在它所经过的路 径上留下信息素(pheromone)的物质进行信息传递,而且 蚂蚁在运动过程中能够感知这种物质,并以此指导自己...
  • 一 引言蚁群算法(ant colonyoptimization,ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型技术。...针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真...
  • 智能优化算法之蚁群算法(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,…...
  • 三、蚁群算法及流程 在算法初始时刻,将m只蚂蚁随机的放到n座城市,同时将禁忌表tabu的第一个元素设置为当前所在城市。此时各路径上的信息素量相等,设 ,(c是一个较小的常数),每只蚂蚁根据路径上残留的信息素和...
  • %%参数设置? w=0.6;%惯性因子? c1=2;%加速常数 c2=2;%加速常数? Dim=3;%维数 SwarmSize=50;%粒子规模? ObjFun=@PIDcl;%待优化函数句柄? MaxIter=100;%最大迭代次数? MinFit=-Inf;%最小适应值 Vmax=1; Vmin=-1; Ub=...
  • 一 引言蚁群算法(ant colonyoptimization,ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型技术。...针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真...
  • 蚁群算法的优化问题

    2021-04-22 11:11:37
    title(['蚁群算法优化路径(最优路径距离:' num2str(Shortest_Length) ')']); figure(2) plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:'); legend('最优路径距离','平均距离'); xlabel('迭代次数'); ...
  • 7 2004 年 7 月 Geomatics and Information Science of Wuhan University J uly 2004 ( ) 文章编号 :16718860 2004 07059705 文献标识码 :A 蚁群算法参数 设置的研究 以 TSP 问题为例 1 1 叶志伟
  • 蚁群算法简介

    2021-12-13 19:53:27
    蚁群算法简介 蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是...
  • 蚁群算法代码实现

    2021-05-21 08:59:24
    旅行商问题大都是用遗传算法求解,不过蚁群算法比它高效得多,在百度的蚁群算法吧里有人发了个注释清晰的代码,有兴趣的可以去研究一下蚁群算法和模拟退火算法,这两者都可以解决旅行商问题。而关于遗传算法和模拟...
  • 【智能算法第一期】蚁群算法原理

    千次阅读 2022-04-06 17:07:52
    1. 什么是蚁群算法蚁群算法的本身来源于一种生物的自然现象,即蚂蚁在寻找食物过程中发现路径的行为,是一种模拟进化的算法。蚁群算法的寻优快速性是由通过正反馈式的信息传递和积累来实现的,分布式计算特征...
  • 蚁群算法(实例帮助理解)

    千次阅读 多人点赞 2021-08-21 11:05:10
    蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 它能够求出从原点出发,经过若干个给定的需求点,最终返回...
  • 蚁群算法matlab源码Jx-WFST:包装功能选择工具箱 “迈向人才科学家:共享和学习” --- 介绍 该工具箱提供了40多种包装功能选择方法 A_Main文件提供了有关如何在基准数据集上应用这些方法的示例 这些方法的源代码是...
  • 蚁群算法详解讲解

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

    万次阅读 多人点赞 2020-07-18 18:20:56
    蚁群算法是一种用来寻找优化路径的概率型算法,模拟蚂蚁在寻找食物过程中发现路径的行为。
  • 一、旅行商问题概述 旅行商问题又称TSP问题,即给定一系列...但是,随着问题规模的增大,精确算法将变得无能为力,因此,在后来的研究中,国内外学者重点使用近似算法或启发式算法,主要有遗传算法、模拟退火法、...
  • 蚁群算法规划路径

    2021-05-24 06:03:24
    蚁群算法可以用于路径规划,在本例中,地形矩阵用0表示无障碍物、用1表示有障碍物,机器人从1x1处走到10x10处,使用蚁群算法找最短路径。步骤如下:初始化参数、地形矩阵、信息素矩阵和启发式因子矩阵。启发式因子...
  • 优化算法|蚁群算法的理解及实现

    千次阅读 2021-01-03 22:19:57
    蚁群算法1. 蚁群算法基本原理2. 蚁群算法实现 1. 蚁群算法基本原理 蚁群算法(Ant Colony Algorithm, ACA)由Marco Dorigo于1992年提出。 蚁群原理: 蚁群算法的基本原理来源于自然界觅食的最短路径原理。根据昆虫学...

空空如也

空空如也

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

蚁群算法参数设置

友情链接: icasso122.zip