精华内容
下载资源
问答
  • 同时考虑蚁群算法的所有运行参数, 提出一种基于图知识迁移的蚁群算法参数选择方法. 首先, 将包含知识(蚁群算法的运行参数) 的源任务映射到一个高维的迁移空间, 并通过迁移权值连接不同的源任务, 构造一个模型迁移图;...
  • 蚁群算法是一种应用广泛、性能优良的智能优化算法, 其求解效果与参数选取息息相关. 鉴于此, 针对现有 基于粒子群参数优化改进蚁群算法耗时较大问题, 提出一种新解决方案. 该方案给出一种全局异步与精英策...
  • 五、蚁群算法的优点 六、疑问 七、代码附件 一、蚁群算法简介 蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。...

    目录

     

    一、蚁群算法简介

    二、蚁群算法相关名词解释及参数设置

    三、蚁群算法流程

    四、matlab实现及分析

    五、蚁群算法的优点

    六、疑问

    七、代码附件


    一、蚁群算法简介

    蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。

    蚂蚁找到最短路径要归功于信息素和环境,假设有两条路可从蚁窝通向食物,开始时两条路上的蚂蚁数量差不多:当蚂蚁到达终点之后会立即返回,距离短的路上的蚂蚁往返一次时间短,重复频率快,在单位时间里往返蚂蚁的数目就多,留下的信息素也多,会吸引更多蚂蚁过来,会留下更多信息素。而距离长的路正相反,因此越来越多的蚂蚁聚集到最短路径上来。

    蚂蚁具有的智能行为得益于其简单行为规则,该规则让其具有多样性和正反馈。在觅食时,多样性使蚂蚁不会走进死胡同而无限循环,是一种创新能力;正反馈使优良信息保存下来,是一种学习强化能力。两者的巧妙结合使智能行为涌现,如果多样性过剩,系统过于活跃,会导致过多的随机运动,陷入混沌状态;如果多样性不够,正反馈过强,会导致僵化,当环境变化时蚁群不能相应调整。

    二、蚁群算法相关名词解释及参数设置

    (1)名词解释:

    1.蚁群:搜索空间的一组有效解(表现为种群规模m)。

    2.觅食空间:问题的搜索空间(表现为问题的规模、解的维数n)。

    3.信息素:信息素浓度变量。

    4.蚁巢到食物的一条路径:问题的最优解。

    (2)参数的经验设置

    1.蚁群数目m:影响着算法的搜索能力和计算量。蚂蚁数目过多时,每轮选代的计算量大、且被搜索过的路径上信息素变化比较平均,此时算法的全局随机搜索能力得到增强,但收敛速度减慢;蚁群数目过少时,算法的探索能力变差,容易出现早熟现象。特别是当问题规模很大时,算法的全局寻优能力会变得十分糟糕。

    2.信息素权重α 与启发式信息权重β:决定算法搜索的导向,影响算法的搜索能力。α越小,最邻近城市被选中的概率越大,蚂蚁越注重"眼前利益”,α=0时,算法等同于随机贪婪算法;β越小,蚂蚁越倾向于根据信息素浓度确定路径,算法收敛越快,β=0时,构建出的最优路径与实际目标有着较大差异,算法的性能比较情糕。

    3.信息素挥发因子ρ :影响蚂蚁个体之问相互影响的强弱,关系到算法的全局搜索能力和收敛速度。ρ较大时,信息素挥发速率大,那些从未被蚂蚁选择过的边上的信息索急剧减小到接近0,降低算法的全局探索能力;ρ较小时,算法具有较高的全局搜索能力,但是由于各个路径的信息素浓度差距拉大较慢,算法收敛速度较慢。

    4.初始信息素量γ 0:决定算法在初始化阶段的探索能力,影响算法的收做速度。γ 0太小,未被蚂蚁选择过的边上信息素太少,蚂蚁很快就全部集中在一 条局部最优的路径上,算法容易早熟;γ 0太大,信息素对搜索方向的引导能力增长得十分缓慢,算法收慢。

    5.终止条件:决定算法运行何时结束由其体的应用和问题本身的确定。将最大循环数设定为500、1000、 5000,或者最大的函数评估次数,等等;也可以使用算法求解得到一个可接受的解作为终止条件;或者是当算法在很长一段迭代中没有得到任何改善时,可以终止算法。
     

    三、蚁群算法流程

    四、matlab实现及分析

    1.先根据上述所说的蚁群算法参数的经验设置,先确定alpha=1,beta=4,然后运行比较rho=0.5和rho=2的结果

    (1)alpha=1,beta=4,rho=0.5的结果:

    (2)alpha=1,beta=4,rho=2的结果:

    (3)结论:比较figure1的两张图可知,当alpha=1,beta=4的前提条件下,rho=0.5会比rho=2得到的最短距离比较小;比较figure2的两张图可知,当alpha=1,beta=4的前提条件下,rho=0.5的迭代次数在40左右就开始收敛了,而rho=2的迭代次数在75左右才开始收敛,由此可知,rho越小算法的收敛程度越快,算法综合性较好。

    2.先根据第一问的前提及蚁群算法参数的经验设置,先确定rho=0.5,然后alpha=1,beta=4,然后运行比较。

    (1)alpha=1,beta=4,rho=0.5的运行结果如上述1中的“(1)alpha=1,beta=4,rho=0.5”的结果所示。

    (2)alpha=4,beta=4,rho=0.5的运行结果:

    (3)结论:比较figure1的两张图可知,当beta=4,rho=0.5的前提条件下,alpha=1会比alpha=4得到的最短距离比较小;比较figure2的两张图可知,当beta=4,rho=0.5的前提条件下,alpha=1的迭代次数在40左右就开始收敛了,而alpha=4的迭代次数在10左右才开始收敛,由此可知,alpha越大迭代次数越少,收敛速度越快算法综合性较好。

    3.先根据第一问的前提及蚁群算法参数的经验设置,先确定alpha=1,rho=0.5,然后beta=1,beta=4运行比较。

    (1)alpha=1,beta=4,rho=0.5的运行结果如上述1中的“(1)alpha=1,beta=4,rho=0.5”的结果所示。

    (2)alpha=1,beta=1,rho=0.5,的运行结果:

    (3)结论:比较figure1的两张图可知,当alpha=1,rho=0.5的前提条件下,beta=4会比beta=1得到的最短距离比较小;比较figure2的两张图可知,当alpha=1,rho=0.5的前提条件下,beta=4的迭代次数在40左右就开始收敛了,而beta=1的迭代次数在55左右才开始收敛,由此可知,beta越大迭代次数越少,收敛速度越快,算法综合性较好。

     

     

     

    五、蚁群算法的优点

    (1)采用正反馈机制,使得搜索过程不断收敛,最终逼近最优解。

    (2)每个个体可以通过释放信息素来改变周围的环境,且每个个体能够感知周围环境的实时变化,个体间通过环境进行间接地通讯。

    (3)搜索过程采用分布式计算方式,多个个体同时进行并行计算,大大提高了算法的计算能力和运行效率。

    (4)启发式的概率搜索方式不容易陷入局部最优,易于寻找到全局最优解。

    六、疑问

    同一个数据,在不更改alpha (信息素重要程度因子)beta (启发函数重要程度因子)rho(信息素挥发因子)的情况下,多次运行代码,得到的迭代次数一样,但是得到的最短距离和最短路径不一样,而且会随着运行次数增加,每次都可以找到比以前更优的最短距离和最短路径,这是为什么呢?同样一个数据下,得到的最短路径可以不唯一,但是得到的最短路径不应该是一样的吗?不是很明白,希望有解答。

    如下图为同一数据下多次运行的结果图(什么都没有更改,只是重新运行了):

    第一次运行结果:

    第一次运行

     

    第一次运行

     

    第一次运行结果

     

    第二次运行结果:

    第二次运行

     

    第二次运行

     

    第二次运行结果

     

    七、代码附件

    %% 旅行商问题(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 = 1;                            % 启发函数重要程度因子
    rho = 0.5;                           % 信息素挥发因子
    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('各代最短距离与平均距离对比')
    

     

    展开全文
  • beta反映了启发信息在导致蚁群搜索过程中的相对重要程度,其大小反应了蚁群优先过程中的先验性、确定性因素的作用强度。 beta过大时算法的收敛速度加快,但收能性变差; beta过小时,收敛速度较快,但将会陷入纯粹...

    一、概述以及代码实现

    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过大时,搜索空间增大但收敛性降低。

    展开全文
  • 蚁群算法

    2020-11-18 11:46:05
    蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新可能性。蚁群算法是一种用来寻找优化...

    1.蚁群算法简介

    蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
    蚁群算法是一种仿生学算法,是由自然界中蚂蚁觅食的行为而启发的。在自然界中,蚂蚁觅食过程中,蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图(1)显示了这样一个觅食的过程。
    这里写图片描述

    在图1(a)中,有一群蚂蚁,假如A是蚁巢,E是食物源(反之亦然)。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了一个障碍物(图1(b)),那么,在B点(或D点)的蚂蚁将要做出决策,到底是向左行驶还是向右行驶?由于一开始路上没有前面蚂蚁留下的信息素(pheromone),蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时,它将会在它行进的路上释放出信息素,并且这种信息素会以一定的速率散发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度,做出决策,往左还是往右。很明显,沿着短边的的路径上信息素将会越来越浓(图1(c)),从而吸引了越来越多的蚂蚁沿着这条路径行驶。

    2.TSP问题描述

    蚁群算法最早用来求解TSP问题,并且表现出了很大的优越性,因为它分布式特性,鲁棒性强并且容易与其它算法结合,但是同时也存在这收敛速度慢,容易陷入局部最优(local optimal)等缺点。
    TSP问题(Travel Salesperson Problem,即旅行商问题或者称为中国邮递员问题),是一种NP-hard问题,此类问题用一般的算法是很大得到最优解的,所以一般需要借助一些启发式算法求解,例如遗传算法(GA),蚁群算法(ACO),微粒群算法(PSO)等等。
    TSP问题可以分为两类,一类是对称TSP问题(Symmetric TSP),另一类是非对称问题(Asymmetric TSP)。所有的TSP问题都可以用一个图(Graph)来描述:
    令V={C1,C2,…,Ci,…,Cn},i=1,2,…,n是所有城市的集合,Ci表示第i个城市,n为城市的数目;
    E={(r,s):r,s∈V}是所有城市之间连接的集合;
    C={Crs:r,s∈V}是所有城市之间连接的成本度量(一般为城市之间的距离);
    如果Crs=Csr,那么该TSP问题为对称的,否则为非对称的。
    一个TSP问题可以表达为:
    求解遍历图G=(V,E,C),所有的节点一次并且回到起始节点,使得连接这些节点的路径成本最低。

    3.蚁群算法原理

    假如蚁群中所有蚂蚁的数量为m,所有城市之间的信息素用矩阵pheromone表示,最短路径为bestLength,最佳路径为bestTour。每只蚂蚁都有自己的内存,内存中用一个禁忌表(Tabu)来存储该蚂蚁已经访问过的城市,表示其在以后的搜索中将不能访问这些城市;还有用另外一个允许访问的城市表(Allowed)来存储它还可以访问的城市;另外还用一个矩阵(Delta)来存储它在一个循环(或者迭代)中给所经过的路径释放的信息素;还有另外一些数据,例如一些控制参数(α,β,ρ,Q),该蚂蚁行走完全程的总成本或距离(tourLength),等等。假定算法总共运行MAX_GEN次,运行时间为t。
    蚁群算法计算过程如下:
    (1)初始化
    设t=0,初始化bestLength为一个非常大的数(正无穷),bestTour为空。初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点。
    (2)为每只蚂蚁选择下一个节点。
    为每只蚂蚁选择下一个节点,该节点只能从Allowed中以某种概率(公式1)搜索到,每搜到一个,就将该节点加入到Tabu中,并且从Allowed中删除该节点。该过程重复n-1次,直到所有的城市都遍历过一次。遍历完所有节点后,将起始节点加入到Tabu中。此时Tabu表元素数量为n+1(n为城市数量),Allowed元素数量为0。接下来按照(公式2)计算每个蚂蚁的Delta矩阵值。最后计算最佳路径,比较每个蚂蚁的路径成本,然后和bestLength比较,若它的路径成本比bestLength小,则将该值赋予bestLength,并且将其Tabu赋予BestTour。
    这里写图片描述
    (公式1)
    这里写图片描述
    (公式2)
    这里写图片描述
    (公式3)

    其中pij(t)表示选择城市j的概率,k表示第k个蚂蚁,τij (t)表示城市i,j在第t时刻的信息素浓度,ηij表示从城市i到城市j的可见度,ηij=1/dij,dij表示城市i,j之间的成本(或距离)。由此可见dij越小,ηij越大,也就是从城市i到j的可见性就越大。
    Δτkij表示蚂蚁k在城市i与j之间留下的信息素。
    Lk表示蚂蚁k经过一个循环(或迭代)锁经过路径的总成本(或距离),即tourLength,α,β,Q 均为控制参数。
    (3)更新信息素矩阵
    令t=t+nt,按照(公式3)更新信息素矩阵phermone。
    这里写图片描述(公式4)

    τij(t+n)为t+n时刻城市i与j之间的信息素浓度。ρ为控制参数,Deltaij为城市i与j之间信息素经过一个迭代后的增量。并且有
    这里写图片描述(公式5)

    其中Δτkij由公式计算得到。
    (4)检查终止条件
    如果达到最大代数MAX_GEN,算法终止,转到第(5)步;否则,重新初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点,重复执行(2),(3),(4)步。
    (5)输出最优值

    4.算法流程图

    这里写图片描述

    5.java实现

    在该java实现中我们选择使用tsplib上的数据att48,这是一个对称tsp问题,城市规模为48,其最优值为10628.其距离计算方法如图(2)所示:
    这里写图片描述
    图2 att48距离计算方法

    实现中,使用了两个java类,一个Ant类,一个ACO类。
    Ant类

    package com.gbs.bean;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collection;
    import java.util.Collections;
    import java.util.Random;
    /**
     * 蚂蚁类
     * Cloneable这个类为克隆类,使用Object的clone()方法
     * @author gbs
     *
     */
    public class Ant implements Cloneable{
    
        /**
         * Vector与ArrayList一样,也是通过数组实现的,不同的是它支持线程的同步,
         * 即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,
         * 但实现同步需要很高的花费,因此,访问它比访问ArrayList慢。
         */
        private ArrayList<Integer> allowedCities;//允许访问的城市
    
        private ArrayList<Integer> tabu;//禁忌表,记录已经访问过的城市
    
        private int [][] distance;//距离矩阵
    
        private double[][] delta; //信息素变化矩阵
    
        private double alpha;
    
        private double beta;
    
        private int cityNum;//城市数量
    
        private int tourLength;//路径的长度
    
        private int firstCity; //起始城市
    
        private int currentCity; //当前城市
    
        public Ant(int cityNum) {
            this.cityNum = cityNum;
            this.tourLength = 0;
        }
    
        public Ant() {
            this.cityNum = 30;
            this.tourLength = 0;
        }
    
        /**
         * 初始化蚂蚁,并为蚂蚁随机选择第一个城市
         * @param distance
         * @param a
         * @param b
         */
        public void init(int[][] distance,double a,double b) {
            this.alpha = a;
            this.beta = b;
            this.distance = distance;
            this.allowedCities = new ArrayList<Integer>();
            this.tabu = new ArrayList<Integer>();
            this.delta = new double[cityNum][cityNum];
            for(int i = 0;i < this.cityNum;i++) {
                Integer city = new Integer(i);
                this.allowedCities.add(city);
                for (int j = 0;j < this.cityNum;j++) {
                    this.delta[i][j] = 0.d;
                }
            }
    
            Random random = new Random(System.currentTimeMillis());
            this.firstCity = random.nextInt(this.cityNum);
    
            for (Integer city:this.allowedCities) {
                if(city.intValue() == this.firstCity) {
                    this.allowedCities.remove(city);
                    this.tabu.add(city);
                    break;
                }
            }
    
            this.currentCity = this.firstCity;
        }
    
        /**
         * 选择下一个城市
         * @param pheromone 信息素矩阵
         */
        public void selectNextCity(double[][] pheromone) {
            double[] p = new double[this.cityNum];//转移概率
            double sum = 0.d;//转移概率的分母
            for (Integer city : this.allowedCities) {
                sum += Math.pow(pheromone[this.currentCity][city.intValue()],
                        this.alpha)*Math.pow(1.d/this.distance[this.currentCity][city.intValue()], this.beta);
            }
            for (int i = 0; i < this.cityNum; i++) {
                boolean flag = false;
                for (Integer city : this.allowedCities) {
                    if(i == city.intValue()) {
                         p[i] = (double) ((Math.pow(pheromone[this.currentCity][i], 
                                 this.alpha)*Math.pow(1.d/this.distance[this.currentCity][i], this.beta))/sum);
                         flag = true;
                         break;
                    }
                }
                if(!flag)
                    p[i] = 0.d;
            }
    
            /**
             * 如果每次都直接选择最大概率的城市作为下一个城市,就会使算法过早收敛,
             * 最后停止搜索可能获得的仅仅是次优解,而使用轮盘赌可以提高算法的全局搜索能力,又不失局部搜索
             * 所以这里选择轮盘赌选择下一个城市。参考《计算智能》清华大学出版社
             */
            //轮盘赌选择下一个城市
             double sumSelect = 0.d;
             int selectCity = -1;
             Random random = new Random(System.currentTimeMillis());
             double selectP = random.nextDouble();
             while(selectP == 0.f) {
                 selectP = random.nextDouble();
             }
             for(int i = 0;i < this.cityNum;i++) {
                 sumSelect += p[i];
                 if(sumSelect >= selectP) {
                     selectCity = i;
                    //从允许选择的城市中去除select city
                     this.allowedCities.remove(Integer.valueOf(selectCity));
                    //在禁忌表中添加select city
                     this.tabu.add(Integer.valueOf(selectCity));
                    //将当前城市改为选择的城市
                     this.currentCity = selectCity;
                     break;
                 }
             }
        }
    
        /**
         * 计算路径长度
         * @return
         */
        public int calculateTourLength() {
            int length = 0;
    
            for(int i = 0;i < this.tabu.size()-1;i++) {
                length += this.distance[this.tabu.get(i).intValue()][this.tabu.get(i+1).intValue()];
            }
            return length;
        }
    
        public ArrayList<Integer> getAllowedCities() {
            return allowedCities;
        }
    
        public void setAllowedCities(ArrayList<Integer> allowedCities) {
            this.allowedCities = allowedCities;
        }
    
        public ArrayList<Integer> getTabu() {
            return tabu;
        }
    
        public void setTabu(ArrayList<Integer> tabu) {
            this.tabu = tabu;
        }
    
        public int[][] getDistance() {
            return distance;
        }
    
        public void setDistance(int[][] distance) {
            this.distance = distance;
        }
    
        public double[][] getDelta() {
            return delta;
        }
    
        public void setDelta(double[][] delta) {
            this.delta = delta;
        }
    
        public double getAlpha() {
            return alpha;
        }
    
        public void setAlpha(double alpha) {
            this.alpha = alpha;
        }
    
        public double getBeta() {
            return beta;
        }
    
        public void setBeta(double beta) {
            this.beta = beta;
        }
    
        public int getCityNum() {
            return cityNum;
        }
    
        public void setCityNum(int cityNum) {
            this.cityNum = cityNum;
        }
    
        public int getTourLength() {
            return tourLength;
        }
    
        public void setTourLength(int tourLength) {
            this.tourLength = tourLength;
        }
    
        public int getFirstCity() {
            return firstCity;
        }
    
        public void setFirstCity(int firstCity) {
            this.firstCity = firstCity;
        }
    
        public int getCurrentCity() {
            return currentCity;
        }
    
        public void setCurrentCity(int currentCity) {
            this.currentCity = currentCity;
        }
    
        @Override
        public String toString() {
            return "Ant [allowedCities=" + allowedCities + ", tabu=" + tabu + ", distance=" + Arrays.toString(distance)
                    + ", delta=" + Arrays.toString(delta) + ", alpha=" + alpha + ", beta=" + beta + ", cityNum=" + cityNum
                    + ", tourLength=" + tourLength + ", firstCity=" + firstCity + ", currentCity=" + currentCity + "]";
        }
    
    }

    ACO类

    package com.gbs.bean;
    
    import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    
    /**
     * 蚁群算法类
     * @author gbs
     *
     */
    public class ACO {
    
        private Ant[] ants; //蚂蚁
        private int antNum; //蚂蚁数量
        private int cityNum; //城市数量
        private int MAX_GEN; //运行代数
        private double[][] pheromone; //信息素矩阵
        private int[][] distance; //距离矩阵
        private int bestLength; //最佳长度
        private int[] bestTour; //最佳路径
        //三个参数
        private double alpha;
        private double beta;
        private double rho;
    
        public ACO() {
    
        }
    
        public ACO(int antNum, int cityNum, int mAX_GEN, double alpha, double beta, double rho) {
            this.antNum = antNum;
            this.cityNum = cityNum;
            this.MAX_GEN = mAX_GEN;
            this.alpha = alpha;
            this.beta = beta;
            this.rho = rho;
            this.ants = new Ant[this.antNum];
        }
    
        public void init(String path) {
            int []x;
            int []y;
            String buffer;
            BufferedReader br;
            try {
                br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
                this.distance = new int[this.cityNum][this.cityNum];
                x = new int[cityNum];  
                y = new int[cityNum];  
                //读取城市的坐标
                for (int i = 0; i < cityNum; i++) {  
                    buffer = br.readLine();
                    String[] str = buffer.split(" ");  
                    x[i] = Integer.valueOf(str[1]);  
                    y[i] = Integer.valueOf(str[2]);  
                } 
                /**
                 * 计算距离矩阵 ,针对具体问题,距离计算方法也不一样,此处用的是att48作为案例,
                 * 它有48个城市,距离计算方法为伪欧氏距离,最优值为10628
                 */
                for(int i = 0;i < this.cityNum - 1;i++) {
                    for(int j = i + 1;j < this.cityNum;j++) {
                        double rij = Math.sqrt(((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]))/10.0);
                        int tij = (int)Math.round(rij);
                        if(tij < rij)
                            tij++;
                        this.distance[i][j] = tij;
                        this.distance[j][i] = tij;
                    }
                }
                this.distance[this.cityNum-1][this.cityNum-1] = 0;
                //初始化信息素矩阵
                this.pheromone=new double[this.cityNum][this.cityNum];
                for(int i = 0;i < this.cityNum;i++) {
                    for(int j = 0;j < this.cityNum;j++) {
                        this.pheromone[i][j] = 0.1d;
                    }
                }
                //初始化最优路径的长度
                this.bestLength=Integer.MAX_VALUE;
                //初始化最优路径
                this.bestTour=new int[this.cityNum+1];  
                //随机放置蚂蚁  
                for(int i = 0;i < this.antNum;i++){  
                    this.ants[i]=new Ant(this.cityNum);  
                    this.ants[i].init(this.distance, this.alpha, this.beta);  
                }  
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    
        /**
         * 更新信息素
         */
        private void updatePheromone() {
            //信息素挥发  
            for(int i = 0;i < this.cityNum;i++)  
                for(int j = 0;j < this.cityNum;j++)  
                    this.pheromone[i][j] = this.pheromone[i][j] * (1 - this.rho);
            //信息素更新
            for(int i = 0;i < this.cityNum;i++) {
                for(int j = 0;j < this.cityNum;j++) {
                    for(int k = 0;k < this.antNum;k++) {
                        this.pheromone[i][j] += this.ants[k].getDelta()[i][j];
                    }
                }
            }
        }
    
        public void solve() {
            for (int g = 0; g < this.MAX_GEN; g++) {
                //每一只蚂蚁移动的过程
                for (int i = 0; i < this.antNum; i++) {
                    for (int j = 0; j < this.cityNum; j++) {
                        this.ants[i].selectNextCity(this.pheromone);
                    }
                    this.ants[i].getTabu().add(this.ants[i].getFirstCity());
                    //计算蚂蚁获得的路径长度  
                    this.ants[i].setTourLength(this.ants[i].calculateTourLength());  
                    if(this.ants[i].getTourLength() < this.bestLength){  
                        //保留最优路径  
                        this.bestLength = this.ants[i].getTourLength();  
                        System.out.println("第"+g+"代,发现新的解"+this.bestLength); 
                        for(int k = 0;k < this.ants[i].getTabu().size();k++)  
                            this.bestTour[k] = this.ants[i].getTabu().get(k).intValue();;  
                    }
                    //更新信息素变化矩阵
                    for (int j = 0; j < this.ants[i].getTabu().size()-1; j++) {
                        this.ants[i].getDelta()[this.ants[i].getTabu().get(j).intValue()][this.ants[i].getTabu().get(j+1).intValue()] = (double) (1.0/this.ants[i].getTourLength());
                        this.ants[i].getDelta()[this.ants[i].getTabu().get(j+1).intValue()][this.ants[i].getTabu().get(j).intValue()] = (double) (1.0/this.ants[i].getTourLength());
                    }
                }
                //更新信息素
                this.updatePheromone();
                //重新初始化蚂蚁
                for(int i = 0;i < this.antNum;i++){  
                    this.ants[i].init(this.distance, this.alpha, this.beta);
                }
            }
            //打印最佳结果
            this.printOptimal();
        }
    
        public void printOptimal() {
             System.out.println("The optimal length is: " + this.bestLength);
             System.out.println("The optimal tour is: ");
             for (int i = 0; i < this.bestTour.length; i++) {
                 System.out.println(this.bestTour[i]);
             }
        }
    
        public Ant[] getAnts() {
            return ants;
        }
    
        public void setAnts(Ant[] ants) {
            this.ants = ants;
        }
    
        public int getAntNum() {
            return antNum;
        }
    
        public void setAntNum(int antNum) {
            this.antNum = antNum;
        }
    
        public int getCityNum() {
            return cityNum;
        }
    
        public void setCityNum(int cityNum) {
            this.cityNum = cityNum;
        }
    
        public int getMAX_GEN() {
            return MAX_GEN;
        }
    
        public void setMAX_GEN(int mAX_GEN) {
            MAX_GEN = mAX_GEN;
        }
    
        public double[][] getPheromone() {
            return pheromone;
        }
    
        public void setPheromone(double[][] pheromone) {
            this.pheromone = pheromone;
        }
    
        public int[][] getDistance() {
            return distance;
        }
    
        public void setDistance(int[][] distance) {
            this.distance = distance;
        }
    
        public int getBestLength() {
            return bestLength;
        }
    
        public void setBestLength(int bestLength) {
            this.bestLength = bestLength;
        }
    
        public int[] getBestTour() {
            return bestTour;
        }
    
        public void setBestTour(int[] bestTour) {
            this.bestTour = bestTour;
        }
    
        public double getAlpha() {
            return alpha;
        }
    
        public void setAlpha(double alpha) {
            this.alpha = alpha;
        }
    
        public double getBeta() {
            return beta;
        }
    
        public void setBeta(double beta) {
            this.beta = beta;
        }
    
        public double getRho() {
            return rho;
        }
    
        public void setRho(double rho) {
            this.rho = rho;
        }
    
        @Override
        public String toString() {
            return "ACO [ants=" + Arrays.toString(ants) + ", antNum=" + antNum + ", cityNum=" + cityNum + ", MAX_GEN="
                    + MAX_GEN + ", pheromone=" + Arrays.toString(pheromone) + ", distance=" + Arrays.toString(distance)
                    + ", bestLength=" + bestLength + ", bestTour=" + Arrays.toString(bestTour) + ", alpha=" + alpha
                    + ", beta=" + beta + ", rho=" + rho + "]";
        }
    
    }

    Test类:

    package com.gbs.test;
    
    import com.gbs.bean.ACO;
    
    public class Test {
        public static void main(String[] args) {
            ACO aco = new ACO(200, 48, 2000, 1.d, 5.d, 0.5d);
            aco.init("d://cities.txt");
            aco.solve();
        }
    }

    注:调试代码时遇到一个致命的问题就是忽略了float和double的精度。浪费了三四个小时debug居然是这个错误引起的,float的精度一旦不够,在java中会出现NAN和INFINITY。
    https://www.cnblogs.com/zhisuoyu/archive/2016/03/24/5314541.html(此网址讲述了NAN和INFINITY的区别)。

    6.存在问题

    (1)对于大规模组合优化问题,算法的计算时间而且复杂。由于蚁群算法的时间复杂度是,因此在处理较大规模的组合优化问题时,运算量较大,时间较长。
    (2)算法容易在某个或某些局部最优解的邻域附近发生停滞现象,造成早熟收敛,即搜索进行到一定程度后,所有蚂蚁发现的解完全一致,不能继续对解空间进一步搜索,不利于发现全局最优解。
    (3)不能较好的解决连续域问题。
    (4)由于蚁群算法中蚂蚁个体的运动过程的随机性,当群体规模设置较大时,很难在较短时间内从杂乱无章的路径中找出一条较好的路径。
    (5)信息素更新策略,路径搜索策略和最优解保留策略都带有经验性,没有经过严格的理论论证。因此基本蚁群算法的求解效率不高、收敛性较差、求解结果具有较大的分散性。

    附件:https://download.csdn.net/download/msc694955868/13123019

     

    展开全文
  • 混沌蚂蚁群算法是受自然界真实蚂蚁的混沌行为和自组织行为启发而产生的一种基于群智能理论的优化算法。介绍了该算法的基本原理,并在对其进行算法分析的基础之上,提出了一种改进的混沌蚂蚁群算法,该改进算法采用全面...
  • 目的:通过本次实验,学生可以掌握蚁群算法基本原理、蚁群算法流程和关键参数的设置。 要求:上机仿真,调试通过。 二、 实验设备: 计算机、Matlab软件、VC++或C语言软件 三、实验内容: 旅行商问题(TSP)。假设有...

    实验五 蚁群算法
    一、实验目的与要求:
    目的:通过本次实验,学生可以掌握蚁群算法基本原理、蚁群算法流程和关键参数的设置。
    要求:上机仿真,调试通过。
    二、 实验设备:
    计算机、Matlab软件、VC++或C语言软件
    三、实验内容:
    旅行商问题(TSP)。假设有一个旅行商人要游览全国31个省会城市,他需要选择所要走过的路径,路径的限制是每个城市只能游览一次,而且最后要回到原来出发的城市。路径的选择要求是:所选择路径的路程为所有路径之中的最小值。
    全国31个省会城市的坐标为【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】
    四、实验原理:
    (1)蚁群算法原理;
    蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中,能够在它所经过的路径上留下一种外激素的物质进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。
    (2)蚁群算法流程或步骤。
    在这里插入图片描述
    图1.蚁群算法流程图
    1.对相关参数进行初始化,包括蚁群规模、信息素因子、启发函数因子、信息素挥发因子、信息素常数、最大迭代次数等。
    2.随机将蚂蚁放于不同出发点,对每个蚂蚁计算其下个访问城市,直到有蚂蚁访问完所有城市。
    3.计算各蚂蚁经过的路径长度,记录当前迭代次数最优解,同时对路径上的信息素浓度进行更新。
    4.判断是否达到最大迭代次数,若否,返回步骤2;若是,则结束程序。
    5.输出优化结果。

    五、实验结果
    在这里插入图片描述
    图2.第4次迭代图像
    在这里插入图片描述
    图3.第10次迭代图像
    在这里插入图片描述
    图4.第20次迭代图像
    在这里插入图片描述
    图5.第50次迭代图像
    在这里插入图片描述
    图6.第100次迭代图像
    在这里插入图片描述
    图7.第200次迭代图像

    在这里插入图片描述
    图8.适应度进化曲线
    通过上述实验结果可以看出,蚁群算法中的tsp问题的图像中距离的下降速度先快后慢,在迭代100次左右收敛到最优解。在适应度曲线中可以看到,算法在局部最优解时的优化能力:随着迭代次数的增长会不断跳出局部最优解,最终收敛到全局最优解。

    六、思考蚁群算法关键参数设置对算法结果的影响。
    1.蚂蚁数量:蚂蚁数量的数量很重要,因为数量过大时,会导致搜索过的路径上信息素变化趋于平均,这样就不好找出好的路径了;数量过小时,易使未被搜索到的路径信息素减小到0,这样可能会出现早熟,没找到全局最优解。一般蚂蚁数设定为城市数的1.5倍较稳妥。
    在这里插入图片描述
    图9.蚂蚁数量为10第200次迭代图像
    在这里插入图片描述
    图10.蚂蚁数量为50第200次迭代图像
    2.最大迭代次数:最大迭代次数值过小,可能导致算法还没收敛就已结束;过大则会导致资源浪费。一般最大迭代次数可以取100到500次。一般来讲,建议先取200,然后根据执行程序查看算法收敛的轨迹来修改取值。针对本次实验的最大迭代次数取值200以内即可。
    在这里插入图片描述
    图11.适应度进化曲线
    3.信息素强度:信息素强度表示蚂蚁循环一周时释放在路径上的信息素总量,其作用是为了充分利用有向图上的全局信息反馈量,使算法在正反馈机制作用下以合理的演化速度搜索到全局最优解。值越大,蚂蚁在已遍历路径上的信息素积累越快,有助于快速收敛。
    在这里插入图片描述
    图12.信息素为100适应度进化曲线
    在这里插入图片描述
    图13.信息素为1000适应度进化曲线
    4.信息素因子:信息素因子反映了蚂蚁在移动过程中所积累的信息量在指导蚁群搜索中的相对重要程度,其值过大,蚂蚁选择以前走过的路径概率大,搜索随机性减弱;值过小,等同于贪婪算法,使搜索过早陷入局部最优。实验发现,信息素因子选择[1,4]区间,性能较好。

    5.期望启发因子:启发函数因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度,其大小反映的是蚁群寻优过程中先验性和确定性因素的作用强度。过大时,虽然收敛速度会加快,但容易陷入局部最优;过小时,容易陷入随机搜索,找不到最优解。实验研究发现,当启发函数因子为[3,5]时,综合求解性能较好。

    展开全文
  • 详细介绍了神经网络算法... 第二部分详细介绍了智能算法的工程中的应用问题,包括模糊神经网络在工程中的应用、遗传算法在图像处理中的应用、神经网络在参数估计中的应用、基于智能算法的PID控制和智能算法的综合应用等
  • 基于蚁群算法的TSP问题1. 准备TSP数据1.1 随机生成TSP数据1.2 保存.mat文件2. alpha、beta、rho参数设置2.1 1. 准备TSP数据 1.1 随机生成TSP数据 %命令行输入: citys=rand(50,2)*5000; %更改当前工作区中的citys...
  • 1.蚂蚁系统(Ant System) 2.精英蚂蚁系统(Ant system ...针对路径Tbs额外强化是通过向Tbs中每一条边增加e/Lbs大小信息素得到,其中e是一个参数,它定义了给予路径Tbs权值大小,Lbs代表了Tbs长度,...
  • 数学建模方法:蚁群算法

    热门讨论 2010-05-21 15:35:07
    基于蚁群智能和支持向量机人脸性别分类方法 蚁群算法在啤酒发酵控制优化中应用 一种基于时延信息多QoS快速自适应路由算法 蚁群算法参数α、β、ρ设置研究——以TSP问题为例 基于人工蚁群优化矢量...
  • 蚁群算法求解TSP

    2019-04-15 17:12:04
    蚁群算法是一种经典传统人工智能算法,早在上个世纪90年代就提出了。网络中已经有很多教材与教程,这里不再复述。 推荐《人工智能导论》(第四版),王万良编著,其6.7章节将蚁群算法讲非常简单清楚。 网上也有...
  • 利用蚁群算法,对TSP旅行商问题进行应用和优化。 随机生成不同的城市序列。 选取不同的参数,验证蚁群算法的效率。 对蚁群算法进行改进,改造成精英蚂蚁算法,并进行分析。
  • 群算法, 改进相关参数, 实现参数的自适应控制以及遗传算法与蚁群算法混合优化策略有机集成. 通过仿真实例表 明了混合智能算法在解决旅行商问题(TSP) 50 座城市最短路径寻优时有效性.</p>
  • 蚁群算法(ACO)是受自然界中蚂蚁搜索食物行为启发,是一种群智能优化算法。它基于对自然界真实蚁群的集体觅食行为研究,模拟真实的蚁群协作过程。算法由若干个蚂蚁共同构造解路径,通过在解路径上遗留并交换信息...
  • 基于无线传感器网络的蚁群路由优化算法在物联网形式油气产量中应用研究 绪 论 选题背景及研究意义 随着时代快速发展对油气田站库以及井场等工作场地进行收集参数数据收集进程控制以及参数的优化等都变...
  • 为了解决规模复杂的旅行商问题,提出了融合蚁群算法和粒子群算法的一种群体智能混合算法,并构建了惯性权值模糊自适应调整模型。针对此混合算法易陷入局部最优,设计了参数自动调节机制,以达到局部搜索和全局搜索...
  • 依赖于无线传感器网络的蚁群路由优化算法在物联网形式油气产量中应用研究 第一章绪 论 1选题背景及研究意旨 随着时代快速发展对油气田站库以及井场等工作场地进行收集参数数据收集进程操纵以及参数的...
  • 在本文后面,我们使用了三种人工智能算法,包括粒子群智能(PSO),蚁群优化(ACO)和遗传算法(GA),并进行了比较,以实现导致接近最大值或接近最大值优化参数集。产生楔形裂纹最小楔入力。
  • 初始化蚁群参数,如蚂蚁数量、聚类数量等;每只蚂蚁对应一个解集: 样品号 1 2 … N 蚂蚁SiS_iSi​ 类别1 类别2 … 类别1 上述表表示蚂蚁SiS_iSi​把N个样本分归属到分类中。 构建信息素矩阵 ...
  • .word可编辑. . 专业.专注 . 目录 TOC \o "1-3" \h \z \u 1. 整体结构与功能划分 2 (一) 总体结构 2 (二) 类划分与功能说明 2 i. NewJFrame 类 2 ii. Ant类 2 iii. ACO类 2 iv. parameter类 3 v.... 参数 3
  • 粒子群算法.pptx

    2020-05-21 00:21:17
    智能优化计算华东理工大学自动化系 2007年 第六章 群智能算法 智能优化计算华东理工大学自动化系 2007年 6.1 群智能 6.1.1 群智能的概念 6.1.2 群智能算法 6.2 蚁群优化算法原理 6.2.1 蚁群算法的起源 6.2.2 蚁群...
  • 蚁群优化算法作为群智能理论主要算法之一,已经成功应用在众多研究领域优化问题上,但是在遥感数据处理领域还是一个新研究课题。蚁群优化具有自组织、合作、通信等智能化优点,对数据无需统计分布参数的先验...
  •  1.2 群智能算法 3  1.3 模拟退火算法 5  1.4 禁忌搜索算法 5  1.5 神经网络算法 6  参考文献 6 第2章 遗传算法 9  2.1 引言 9  2.2 遗传算法理论 10  2.2.1 遗传算法的生物学基础 10  2.2.2 遗传算法理论...
  • 粒子群算法求函数极值

    万次阅读 2017-07-06 15:29:51
    所有的群智能算法都是通过模拟自然界中的生物群体的行为来解决问题的一种思想,同遗传算法一样,群智能算法的数学理论基础相对薄弱,缺乏具备普遍意义的理论性分析,算法中涉及的各种参数设置一直没有确切地理论依据...
  • 蚁群算法具有分布计算,群体智能等优势,在路径规划算法上具有很大潜力,本案例研究了基于蚁群算法的三维路径规划算 法。 25 有导师学习神经网络的回归拟合——基于近红外光谱的汽油辛烷值预测(郁磊) 神经网络的...
  • 遗传算法与蚁群算法的对比分析 一.引言 遗传算法喝蚁群算法都是时效的最优化搜索算法,在解决诸如TSP这类组合优化问题时,它们各有所长。 本文使用MATLAB先来分析遗传算法自身的参数影响,再进一步对比分析两种算法...
  • 22 蚁群算法的优化计算——旅行商问题(TSP)优化(郁磊) 23 基于蚁群算法的二维路径规划算法(史峰) 24 基于蚁群算法的三维路径规划算法(史峰) 25 有导师学习神经网络的回归拟合——基于近红外光谱的汽油辛烷...
  • 摘要:蚁狮优化(Ant Lion Optimizer,ALO)算法是Mirjalili于2015提出一种新型元启发式群智能算法[1]。由于引入了随机游走、轮盘赌策略及精英策略,使得 ALO 算法成为一种种群多样、寻优性能强、调节参数少、易于...
  • 目 录 第1章 概述 1 1.1 进化类算法 2 1.2 群智能算法 3 1.3 模拟退火算法 5 1.4 禁忌搜索算法 5 1.5 神经网络算法 6 参考文献 6 第2章 遗传算法 9 2.1 引言 9 2.2 遗传算法理论 10 2.2.1 遗传算法的生物学基础 10 ...

空空如也

空空如也

1 2 3
收藏数 49
精华内容 19
关键字:

蚁群智能算法的参数