精华内容
下载资源
问答
  • 蚁群算法的基本原理;蚁群算法的基本原理;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;蚁群算法模型的建立;蚁群算法模型的建立;蚁群算法模型的建立;蚁群算法模型的建立; 蚁群算法的基本步骤 ;基本蚁群...
  • 蚁群算法原理及matlab代码实现

    万次阅读 多人点赞 2019-04-27 15:13:30
    蚁群算法基本原理: 背景: 在自然界中,生物群体所表现出的智能得到越来越多的关注,许多的群智能优化算法都是通过对群体智能的模拟而实现的。其中模拟蚂蚁群体觅食的蚁群算法成为一种主要的群智能算法。 算法...

    蚁群算法基本原理:

    背景: 在自然界中,生物群体所表现出的智能得到越来越多的关注,许多的群智能优化算法都是通过对群体智能的模拟而实现的。其中模拟蚂蚁群体觅食的蚁群算法成为一种主要的群智能算法。

    算法原理:

    在自然界中,对于觅食的蚂蚁群体,其可以在任何和没有提示的情况下找到食物和巢穴之间的最短路径。并且能够根据和环境的变迁,自适应地找到新的最优路径。根据生物学家研究,蚂蚁群体这一行为的根本原因是:蚂蚁在寻找食物的过程中,能在其走过的路径上释放一种特殊的物质----信息素,随着时间的推移,这种信息素会逐渐地挥发,而对于后来的蚂蚁,选择某条路径的概率与该路径上信息素的浓度成正比。当某一条路径上通过的蚂蚁越多的时候,这条路径上的信息素的浓度就会累积越大,后来的蚂蚁选择此路径的概率也就越大。路径上蚂蚁越多,导致信息素浓度越高,从而会吸引更多的蚂蚁,从而形成一种正反馈机制,通过这种机制,最终蚁群可以发现最短路径。

    真实蚁群觅食过程:

            在觅食的初始阶段,环境中没有信息素,所以蚂蚁选择哪条路径完全是随机的。之后选择路径就会受到信息素的影响。这里需要说明的时是,信息素是一种生物体内分泌的化学物质,会随着时间的推移而挥发,如果每只蚂蚁在单位距离上留下的信息素浓度相同,则对于越短的路径,信息素的残留浓度就会越高,这被后来的蚂蚁选择的概率也就越大。而经过的蚂蚁越多,由于群体中的正反馈机制,路径上信息素的浓度也就越大,最终会导致整个蚁群寻找到最短路径。

    举个栗子:

    如下图所示:

     

    假设从A点到B点,A,B之间的距离一定,有三条路径可选。

    初始时每条路径分配一只蚂蚁,记为1,2,3,假设L(ACB)=2*L(ADB), L(AEB)=3*L(ADB),所有蚂蚁的行走速度相同。假设蚂蚁沿着ADB从A到B,需要4个单位时间;所以在t取不同值的时候:

    t=4:

    蚂蚁1到达D, 蚂蚁2走到一半路程,蚂蚁3走了三分之一的路程

    t=8:

    蚂蚁1返回A, 蚂蚁2到达B,蚂蚁3走了三分之二的路程

    .....

    t=48:

    蚂蚁1往返于AB之间6次, 蚂蚁2往返于AB间3次,蚂蚁3往返于AB间2次

    在不考虑信息素挥发的条件下:

    三条路径上信息素浓度之比:D(ADB):D(ACB):D(AEB)=6:3:2

    按照蚁群寻找路径的正反馈机制:按照信息素的指导,蚁群在路径ADB上指派6只蚂蚁,在路径ACB上指派3只蚂蚁,在路径AEB上指派2只蚂蚁.

    若继续寻找,则按照正反馈机制,最终所有蚂蚁都会选择最短的路径ABD,而放弃其他两条路径。

    蚁群算法数学模型的建立:

    1.在对实际的蚁群进行建模的过程中,需要解决,蚁群中蚂蚁个体的建模问题,信息素的更新机制,以及整个蚁群的内部机制

    a. 信息素的更新机制:

           信息素的更新方式有两种,一种是挥发,也就是所有路径上的信息素以一定的比率减少。另一种是信息素的增强,给有蚂蚁走过的路径增加信息素。

    b. 蚂蚁个体的建模问题:

           虽然单个蚂蚁可以构造出问题的可行解,但是蚂蚁个体之间需要通过协作才能找出待优化问题的最优解或者次优解,而信息素就是蚂蚁之间进行互相协作的媒介。信息素的蒸发机制使得对过去的寻优历史有一定的遗忘度,避免使后来的蚂蚁在搜索中受到较差解的影响。

    下面以TSP问题为例,给出蚁群算法的模型:
    参考文献:【1】M. Dorigo, V. Maniezzo and A. Colorni, "Ant system: optimization by a colony of cooperating agents," in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29-41, Feb. 1996.

    TSP问题: 

    在一张地图上有n个城市,一名推销员需要不重复的一次走过n个城市进行推销,求解他按照怎样的路径,从才能使走过的距离最短。

    这个问题的解法可以描述如下:

    假设城市 i 的坐标坐标为

    城市i,j之间的距离可以表示为:

    为每只蚂蚁设置一个禁忌表,记录其走过的城市(防止重复走过城市),禁忌表中第一个位置是蚂蚁是初始时刻蚂蚁所在的城市,当所有城市都加入禁忌表的时候,表示蚂蚁走完了所有的城市,完成一次周游。令 为城市i, j之间的信息素的量,初始时刻其取值为:

    假设在(t, t+n)时刻所有蚂蚁完成一次周游,则在t+n时刻城市i, j 之间的信息素含量可以表示为:

    其中:表示时间段 (t, t+n) 之间信息素的挥发系数。则表示信息素的剩余量。挥发系数取值范围(0, 1)

              表示在时间段 (t, t+n) 之间信息素的增加量,其计算方式如下所示:

    表示第k只蚂蚁在本次迭代中留在路径i, j之间的信息素的量, 计算方式如下所示(ant-cycle模型):

    其中:是正常数, 表示蚂蚁k在周游中经过的路径。

    原文中对参数的解释如下:

    同时论文中还提到两种的计算方式:

    (1)ant-density模型

    (2)ant-quantity模型:

      ant-cycle模型的实际效果更好,因为他应用了全局信息更新路径上的信息素,而其他两种模型只是用了局部信息。

    在t时刻, 蚂蚁k从城市i转移到城市可的概率可以由以下方式计算得到:

    其中:是一个启发式因子,计算方式为:

    表示蚂蚁从城市i转移到城市j的期望程度。

    表示在城市i处蚂蚁k可以选择走的城市的集合。表示信息素和期望启发式因子的相对重要程度。

    分析上面的公式可知:

     路径i,j信息素含量越高,蚂蚁选择该路径的概率越大,而路径i.j之间的距离越大吗,启发式因子就越小,则蚂蚁选择该路径的概率就越小,蚂蚁选择路径i,j的概率与上述两个因素都有关系。

    matlab代码实现:

    clear all;
    close all;
    clc;
    C = [1304 2312;         % 城市坐标
        3639 1315;
        4177 2244;
        3712 1399;
        3488 1535;
        3326 1556;
        3238 1229;
        4196 1044;
        4312 790;
        4386 570;
        3007 1970;
        2562 1756;
        2788 1491;
        2381 1676;
        1332 695;
        3715 1678;
        3918 2179;
        4061 2370;
        3780 2212;
        3676 2578;
        4029 2838;
        4263 2931;
        3429 1980;
        3507 2376;
        3394 2643;
        3439 3201;
        2935 3240;
        3140 3550;
        2545 2357;
        2778 2826;
        2370 2975];
    % figure(1);
    % scatter(C(:,1),C(:,2),'k','d');
    % title('城市分布图');
    
    [M,N] = size(C);
    % M为问题的规模  M个城市
    distance = zeros(M,M);     % 用来记录任意两个城市之间的距离
    % 求任意两个城市之间的距离
    for m=1:M
        for n=1:M
            distance(m,n) = sqrt(sum((C(m,:)-C(n,:)).^2));
        end
    end
    m = 50;   % 蚂蚁的个数   一般取10-50    
    alpha = 1;   %  信息素的重要程度    一般取【1,4】
    beta = 5;    %  启发式英子的重要程度   一般取【3,5】
    rho = 0.25;    % 信息素蒸发系数
    G = 150;
    Q = 100; % 信息素增加系数
    Eta = 1./distance;  % 启发式因子
    Tau = ones(M,M);  % 信息素矩阵  存储着每两个城市之间的信息素的数值
    Tabu = zeros(m,M);  % 禁忌表,记录每只蚂蚁走过的路程
    gen = 1;  
    R_best = zeros(G,M);  % 各代的最佳路线
    L_best = inf.*ones(G,1);   % 每一代的最佳路径的长度     初始假设为无穷大
    %   开始迭代计算
    while gen<G
        %  将m只蚂蚁放到n个城市上
        random_pos = [];
        for i=1:(ceil(m/M))  % m只蚂蚁随即放到M座城市 
            random_pos = [random_pos,randperm(M)];   %  random_pos=[1~31 + 1~31]   将每只蚂蚁放到随机的城市  在random_pos 中随机选择m个数,代表蚂蚁的初始城市
        end
        Tabu(:,1) = (random_pos(1,1:m))';   % 第一次迭代每只蚂蚁的禁忌表
        
        for i=2:M      %  从第二个城市开始
            for j=1:m   %  每只蚂蚁
                visited = Tabu(j,1:(i-1));   %  在访问第i个城市的时候,第j个蚂蚁访问过的城市
                % visited=visited(1,:);
                unvisited = zeros(1,(M+1-i));  %  待访问的城市
                visit_P = unvisited;   %  蚂蚁j访问剩下的城市的概率
                count = 1;
                for k=1:M   % 这个循环是找出未访问的城市  
                    if isempty(find(visited==k))   %还没有访问过的城市  如果成立。则证明第k个城市没有访问过
                        unvisited(count) = k;
                        count = count+1;
                    end
                end
                %  计算待选择城市的概率
                for k=1:length(unvisited)    % Tau(visited(end),unvisited(k))访问过的城市的最后一个与所有未访问的城市之间的信息素
                    visit_P(k) = ((Tau(visited(end),unvisited(k)))^alpha)*(Eta(visited(end),unvisited(k))^beta);
                end
                visit_P = visit_P/sum(visit_P);   %  访问每条路径的概率的大小
                %   按照概率选择下一个要访问的城市
                %   这里运用轮盘赌选择方法      这里也可以选择选择概率最大的路径去走, 这里采用轮盘赌选择法。
                Pcum = cumsum(visit_P);
                selected = find(Pcum>=rand);
                to_visited = unvisited(selected(1));
                Tabu(j,i) = to_visited;  % 添加到禁忌表
            end
        end
        if gen>=2
            Tabu(1,:) = R_best(gen-1,:);
        end
        %  记录m只蚂蚁迭代的最佳路线
        L = zeros(1,m);
        for i=1:m
            R = Tabu(i,:);
            L(i) = distance(R(M),R(1));   % 因为要走一周回到原来的地点    
            for j=1:(M-1)
                L(i) = L(i)+distance(R(j),R(j+1));
            end
        end
        L_best(gen) = min(L);    %  记录每一代中路径的最短值
        pos = find(L==L_best(gen));
        R_best(gen,:) = Tabu(pos(1),:);   % 最优的路径
        
        %  更新信息素的值
        Delta_Tau = zeros(M,M);
        for i=1:m   %  m只蚂蚁
            for j=1:(M-1)   %  M座城市
                Delta_Tau(Tabu(i,j),Tabu(i,j+1)) = Delta_Tau(Tabu(i,j),Tabu(i,j+1)) + Q/L(i);    %  m只蚂蚁的信息素累加 这里采用的是论文中ant-cycle模型
            end
            Delta_Tau(Tabu(i,M),Tabu(i,1)) = Delta_Tau(Tabu(i,M),Tabu(i,1)) + Q/L(i);
        end
        Tau = (1-rho).*Tau+Delta_Tau;   % 更新路径上的信息素含量
        %  禁忌表清零
        Tabu = zeros(m,M);
        
        for i=1:(M-1)
            plot([C(R_best(gen,i),1),C(R_best(gen,i+1),1)],[C(R_best(gen,i),2),C(R_best(gen,i+1),2)],'bo-');
            hold on;
        end
        plot([C(R_best(gen,n),1),C(R_best(gen,1),1)],[C(R_best(gen,n),2),C(R_best(gen,1),2)],'ro-');
        title(['最短路径:',num2str(L_best(gen))]);
        hold off;
        pause(0.05);
        gen = gen+1;
    end
    
    figure(2);
    plot(L_best);
    title('路径长度变化曲线');
    xlabel('迭代次数');
    ylabel('路径长度数值');

    运行结果:

     

    最优路径相同,只是起点不一样。

     

    展开全文
  • 蚁群算法发展.pptx

    2020-06-20 07:58:01
    蚁群算法的基本原理;蚁群算法的基本原理;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;蚁群算法模型的建立;蚁群算法模型的建立;蚁群算法模型的建立;蚁群算法模型的建立; 蚁群算法的基本步骤 ;基本蚁群...
  • 蚁群算法原理与实现(python)

    千次阅读 2019-12-25 19:45:29
    文章目录蚁群算法的背景蚁群算法的思想蚁群算法的python实现实例总结 蚁群算法的背景 古有牛顿在苹果树下被苹果砸中发现万有引力,三十年前有人观察蚂蚁觅食发明蚁群算法蚁群算法是意大利学者Dorigo、Maniezzo等人...

    蚁群算法的背景

    古有牛顿在苹果树下被苹果砸中发现万有引力,三十年前有人观察蚂蚁觅食发明蚁群算法。蚁群算法是意大利学者Dorigo、Maniezzo等人于20世纪90年代看蚂蚁觅食发明的。蹲在地上看蚂蚁,也能发明新成果,曾经的我咋就光看蚂蚁,给蚂蚁的觅食捣蛋呢。这意大利的大兄弟在看蚂蚁觅食的时候呢,发现单个蚂蚁的行为比较简单,但是蚂蚁群却能体现一些智能行为,比如蚂蚁能在不同环境中,寻找最短的从蚂蚁窝到达食物的路径。经过进一步研究发现,蚂蚁在找食物的路径会留下记号(生物学称之为“信息素”),蚂蚁群里的蚂蚁会根据这个记号,也就是信息素行走,每个蚂蚁都做记号,经过一段时间后,整个蚂蚁群就会找到一个最短的到达食物的路径了。

    蚁群算法的思想

    蚁群算法具体的思想是什么呢?我是一只小蚂蚁,我要去找食儿。我带上几个兄弟一起走,一起去找事儿。可是食物在哪儿呢?我们也不知。那我们分头行动随机找,记得做标记。过了很久很久之后,我找到了食物,带着食物原路返回告诉大家我找到食物了。在蚂蚁窝里,我和兄弟们分享了找食物的路线,有的长,有的短。这些食物还不够,我们继续又出发。沿着大家新的路径去搬食物。有时候我会走错路,走了弯路;有时候,我走错路,却发现一条捷径。经过一次又一次的外出搬运食物,回到蚂蚁窝,我们找到了一个最方便的路径。这就是蚁群算法的基本思想。

    蚁群算法可以很好的解决旅行商问题。所谓旅行商问题,是存在一些城市,旅行商如何从某个城市出发,经过所有城市后返回出发城市的最短路径。

    下面用旅行商问题来继续阐述蚁群算法。
    1、首先有一组蚂蚁,也就是小蚂蚁和它的兄弟们,从某个城市出发,完成一个城市遍历的路径。
    2、当某个小蚂蚁站在人生的十字路口,哦不,是城市交叉路况,那么必须要走向一个城市,如果某个城市越远,那么将更有可能先不走。比如,当小蚂蚁站在天津,有一条路上北京,有一条路去深圳,那么小蚂蚁最有可能先踏上进京之路,因为近啊。
    3、当某个城市边际上的记号信息素越多,则更有可能被选中。比如在天津,如果去深圳上记号信息素多,则可能先去深圳,尽管进京之路比较短,这是其他蚂蚁兄弟的记号表示的,相信蚂蚁兄弟。
    4、每次回到出发点,蚂蚁兄弟标记在路上的记号信息素会挥发。
    这里有两个关键点,即下一个城市的选择和信息素的更新。

    现在给出一些数字表示:
    城市数量为M,蚁群规模(蚂蚁数量)m、信息素重要程度因子α、启发函数重要程度因子β,即启发式信息的相对重要程度、信息素会发银子ρ、信息素释放总量Q、最大迭代次数iter_max、迭代次数初值iter=1。

    小蚂蚁现在位于城市 i i i,到其他城市 j j j的距离为 d i j d_{ij} dij,信息素浓度为 p i j p_{ij} pij,那么小蚂蚁朝哪个城市前进呢。从当前城市 i i i到城市 j j j的概率是 q i j = p i j α ∗ ( 1 / d i j ) β q_{ij}=p^\alpha_{ij}*(1/d_{ij})^\beta qij=pijα(1/dij)β
    现在小蚂蚁知道了到其他城市的概率,可是该走哪条路呢。小蚂蚁拿出勇闯天涯的雪花啤酒瓶放在地上转个圈,瓶口指向哪个城市就去哪个城市吧。这就是轮盘对赌。把每个城市的转移概率除以所有城市的转移概率之和,那就是该城市被选中的概率,然后随机一个0到1的数,该随机数落到哪个区间就被选中。现在有ABCDE四个城市可以选择,那么可以看到下图里,D城市在所有城市中占据的分量最大,则最有可能被选中。可以参考这里轮盘对赌
    在这里插入图片描述

    当小蚂蚁走完所有的城市,那就对应着一条路径。蚂蚁兄弟也有搜索路径。根据小蚂蚁和蚂蚁兄弟的探路结果,更新下蚂蚁群体对路径的认识,那就是信息素的更新。两个城市之间的信息素更新公式为
    p i j = ρ ∗ p i j + Q / s u m p_{ij}=\rho*p_{ij}+Q/sum pij=ρpij+Q/sum
    其中sum是每个蚂蚁走过的距离之和。

    蚁群算法的python实现实例

    我们用python的GUI模块Tkinter来验证我们的小蚂蚁是怎么寻找最优路径的。python代码如下:

    # -*- coding: utf-8 -*-
    # @Time    : 2019/12/25 16:23
    # @Author  : HelloWorld!
    # @FileName: ant.py
    # @Software: PyCharm
    # @Operating System: Windows 10
    # @Python.version: 3.6
    
    
     #城市数量为M,
    # 蚁群规模(蚂蚁数量)m、
    # 信息素重要程度因子α、
    # 启发函数重要程度因子β,即启发式信息的相对重要程度、
    # 信息素会发银子ρ、
    # 信息素释放总量Q、
    # 最大迭代次数iter_max、迭代次数初值iter=1。
    import random
    import copy
    import sys
    import math
    import tkinter
    import threading
    from functools import reduce
    (ALPHA,BETA,RHO,Q)=(1,2,0.5,100)
    #城市数,小蚂蚁个数
    (city_num,ant_num)=(50,50)
    #城市坐标
    distance_x = [
        178, 272, 176, 171, 650, 499, 267, 703, 408, 437, 491, 74, 532,
        416, 626, 42, 271, 359, 163, 508, 229, 576, 147, 560, 35, 714,
        757, 517, 64, 314, 675, 690, 391, 628, 87, 240, 705, 699, 258,
        428, 614, 36, 360, 482, 666, 597, 209, 201, 492, 294]
    distance_y = [
        170, 395, 198, 151, 242, 556, 57, 401, 305, 421, 267, 105, 525,
        381, 244, 330, 395, 169, 141, 380, 153, 442, 528, 329, 232, 48,
        498, 265, 343, 120, 165, 50, 433, 63, 491, 275, 348, 222, 288,
        490, 213, 524, 244, 114, 104, 552, 70, 425, 227, 331]
    #城市距离和初始信息素
    distance_graph=[[0 for col in range(city_num)] for raw in range(city_num)]
    print(distance_graph)
    pheromone_graph=[[1 for col in range(city_num)] for raw in range(city_num)]
    
    #------------------小蚂蚁好多个,有灵魂,值得用一个类表示----------------------
    class Ant():
        def __init__(self,ID):
            self.ID=ID #蚂蚁公民怎么能没有身份证呢。
            self.__clean_data()#小蚂蚁初始化出生地
        def __clean_data(self):
            self.path=[]#小蚂蚁的路径
            self.total_distance=0 #小蚂蚁当前路径的总距离
            self.move_count=0 #小蚂蚁的移动次数
            self.current_city=-1 #小蚂蚁的当前所在城市
            self.open_table_city=[True for i in range(city_num)] #标记哪个城市去过,哪个没去过;也称为禁忌表
            city_index=random.randint(0,city_num-1)#随机初始化出生地
            self.current_city=city_index
            self.path.append(city_index)
            self.open_table_city[city_index]=False
            self.move_count=1
    
        #小蚂蚁如何选择下一个城市
        def __choice_next_city(self):
            next_city=-1
            select_citys_prob=[0 for i in range(city_num)]#去下一个城市的概率
            total_prob=0
    
            #小蚂蚁掐指一算,去下一个城市的概率
            for i in range(city_num):
                if self.open_table_city[i]: #如果下一个城市没去过,还可以去
                    try:
                        #选中概率:与信息素浓度呈正比,与距离呈反比
                        select_citys_prob[i]=pow(pheromone_graph[self.current_city][i],ALPHA)*\
                                             pow(1/distance_graph[self.current_city][i],BETA)
                        total_prob+=select_citys_prob[i]
                    except ZeroDivisionError as e:
                        print('Ant ID: {ID}, current city: {current}, target city: {target}'.
                              format(ID=self.ID,current=self.current_city,target=i))
                        sys.exit(1)
    
            #勇闯天涯啤酒瓶,轮盘对赌
            if total_prob>0:
                #产生随机概率
                temp_prob=random.uniform(0,total_prob)
                for i in range(city_num):
                    if self.open_table_city[i]:
                        temp_prob-=select_citys_prob[i]
                        if temp_prob<0:
                            next_city=i
                            break
            #如果没有从轮盘对赌中选出,则顺序选择一个未访问城市
            if next_city==-1:
                for i in range(city_num):
                    if self.open_table_city[i]:
                        next_city=i
                        break
            if next_city==-1:
                next_city=random.randint(0,city_num-1)
                while False==self.open_table_city[next_city]:
                    next_city=random.randint(0,city_num-1)
    
            #返回下一个城市序号
            return next_city
    
        #计算路径总距离
        def __cal_total_distance(self):
            temp_distance=0
            for i in range(1,city_num):
                start, end =self.path[i],self.path[i-1]
                temp_distance+=distance_graph[start][end]
    
            #回路
            end=self.path[0]
            temp_distance+=distance_graph[start][end]
            self.total_distance=temp_distance
        #小蚂蚁移动操作
        def __move(self,next_city):
            self.path.append(next_city)
            self.open_table_city[next_city]=False
            self.total_distance+=distance_graph[self.current_city][next_city]
            self.current_city=next_city
            self.move_count+=1
        #小蚂蚁踏上寻路之旅
        def search_path(self):
            #初始化数据
            self.__clean_data()
    
            #搜索路径,遍历完所有城市为止
            while self.move_count<city_num:
                next_city=self.__choice_next_city()
                self.__move(next_city)
            #计算路径总长度
            self.__cal_total_distance()
    
            # 搜索路径,一直到遍历完所有城市路径
    
    #------------------------------小蚂蚁来解决TSP问题--------------------------------------------------
    class TSP():
    
        def __init__(self,root,width=800,height=600,n=city_num):
            self.root=root
            self.width=width
            self.height=height
            #城市数目
            self.n=n
    
            #tkinter 来画布
            self.canvas=tkinter.Canvas(root,width=self.width,height=self.height,bg= "#EBEBEB", xscrollincrement=1,yscrollincrement=1)
            self.canvas.pack(expand=tkinter.YES,fill=tkinter.BOTH)
            self.title("TSP蚁群算法(n:初始化 e:开始搜索 s:停止搜索 q:退出程序)")
            self.__r = 5
            self.__lock = threading.RLock()  # 线程锁
    
            self.__bindEvents()
            self.new()
    
        #计算城市之间的距离,欧拉距
        for i in range(city_num):
            for j in range(city_num):
                temp_distance = pow((distance_x[i] - distance_x[j]), 2) + pow((distance_y[i] - distance_y[j]), 2)
                temp_distance = pow(temp_distance, 0.5)
                distance_graph[i][j] = float(int(temp_distance + 0.5))
    
            # 按键响应程序
        def __bindEvents(self):
    
            self.root.bind("q", self.quite)  # 退出程序
            self.root.bind("n", self.new)  # 初始化
            self.root.bind("e", self.search_path)  # 开始搜索
            self.root.bind("s", self.stop)  # 停止搜索
    # 更改标题
        def title(self, s):
            self.root.title(s)
    
        # 初始化
        def new(self, evt=None):
            # 停止线程
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
    
            self.clear()  # 清除信息
            self.nodes = []  # 节点坐标
            self.nodes2 = []  # 节点对象
    
            # 初始化城市节点
            for i in range(len(distance_x)):
                # 在画布上随机初始坐标
                x = distance_x[i]
                y = distance_y[i]
                self.nodes.append((x, y))
                # 生成节点椭圆,半径为self.__r
                node = self.canvas.create_oval(x - self.__r,
                                               y - self.__r, x + self.__r, y + self.__r,
                                               fill="#ff0000",  # 填充红色
                                               outline="#000000",  # 轮廓白色
                                               tags="node",
                                               )
                self.nodes2.append(node)
                # 显示坐标
                self.canvas.create_text(x, y - 10,  # 使用create_text方法在坐标(302,77)处绘制文字
                                        text='(' + str(x) + ',' + str(y) + ')',  # 所绘制文字的内容
                                        fill='black'  # 所绘制文字的颜色为灰色
                                        )
    
            # 顺序连接城市
            # self.line(range(city_num))
             # 初始城市之间的距离和信息素
            for i in range(city_num):
                for j in range(city_num):
                    pheromone_graph[i][j] = 1.0
    
            self.ants = [Ant(ID) for ID in range(ant_num)]  # 初始蚁群
            self.best_ant = Ant(-1)  # 初始最优解
            self.best_ant.total_distance = 1 << 31  # 初始最大距离
            self.iter = 1  # 初始化迭代次数
    
    # 将节点按order顺序连线
        def line(self, order):
            # 删除原线
            self.canvas.delete("line")
    
            def line2(i1, i2):
                p1, p2 = self.nodes[i1], self.nodes[i2]
                self.canvas.create_line(p1, p2, fill="#000000", tags="line")
                return i2
    
            # order[-1]为初始值
            reduce(line2, order, order[-1])
    
        # 清除画布
        def clear(self):
            for item in self.canvas.find_all():
                self.canvas.delete(item)
    
        # 退出程序
        def quite(self, evt):
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
            self.root.destroy()
            print(u"\n程序已退出...")
            sys.exit()
    
            # 停止搜索
        def stop(self, evt):
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
    
        #开始搜索,小蚂蚁开始行动
            # 开始搜索
        def search_path(self, evt=None):
            # 开启线程
            self.__lock.acquire()
            self.__running = True
            self.__lock.release()
    
            while self.__running:
                #遍历每一只蚂蚁
                for ant in self.ants:
                    ant.search_path() #小蚂蚁ant完成一个路径搜索
                    #我们的小蚂蚁是不是找到比当前最优的路径了
                    if ant.total_distance<self.best_ant.total_distance:
                        #更新最优
                        self.best_ant=copy.deepcopy(ant)
                # 更新信息素
                self.__update_pheromone_gragh()
                print(u"迭代次数:", self.iter, u"最佳路径总距离:", int(self.best_ant.total_distance))
                # 连线
                self.line(self.best_ant.path)
                # 设置标题
                self.title("TSP蚁群算法(n:随机初始 e:开始搜索 s:停止搜索 q:退出程序) 迭代次数: %d" % self.iter)
                # 更新画布
                self.canvas.update()
                self.iter += 1
          # 更新信息素
        def __update_pheromone_gragh(self):
    
            # 获取每只蚂蚁在其路径上留下的信息素
            temp_pheromone = [[0.0 for col in range(city_num)] for raw in range(city_num)]
            for ant in self.ants:
                for i in range(1, city_num):
                    start, end = ant.path[i - 1], ant.path[i]
                    # 在路径上的每两个相邻城市间留下信息素,与路径总距离反比
                    temp_pheromone[start][end] += Q / ant.total_distance
                    temp_pheromone[end][start] = temp_pheromone[start][end]
    
            # 更新所有城市之间的信息素,旧信息素衰减加上新迭代信息素
            for i in range(city_num):
                for j in range(city_num):
                    pheromone_graph[i][j] = pheromone_graph[i][j] * RHO + temp_pheromone[i][j]
    
        # 主循环
        def mainloop(self):
            self.root.mainloop()
    
    
    # ----------- 程序的入口处 -----------
    
    if __name__ == '__main__':
        TSP(tkinter.Tk()).mainloop()

    初始的城市分布情况如图所示:
    在这里插入图片描述
    迭代30次左右的情况
    在这里插入图片描述
    600次左右的情况

    在这里插入图片描述

    总结

    蚁群算法广泛应用在TSP(商旅问题)路径优化问题 调度问题 着色问题 聚类分析 网络路由 数据挖掘 工业PCB 板
    其它组合优化。
    蚁群算法的优点缺点:
    具有较强的鲁棒性、优良的分布式计算机制和正反馈机制、易于与其他方法相结合等优点,缺点是求解时间长,初始信息素匮乏,容易出现停滞现象。

    参考文献https://blog.csdn.net/weixin_39383896/article/details/101568241

    展开全文
  • 蚁群算法

    万次阅读 2016-06-08 10:38:13
    蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是...
    转自百度百科和http://www.cnblogs.com/biaoyu/archive/2012/09/26/2704456.html
    蚁群算法(ant colony optimization, ACO),又称 蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟 进化算法,初步的研究表明该算法具有许多优良的性质。针对 PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
    中文名
    蚁群算法
    外文名
    ant colony optimization
    简    称
    ACO
    别    称
    蚂蚁算法
    速度半径
    (一般是3)

    定义

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

    原理

    编辑
    设想,如果我们要为蚂蚁设计一个人工智能的程序,那么这个程序要多么复杂呢?首先,你要让蚂蚁能够避开障碍物,就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物,其次,要让蚂蚁找到食物,就需要让他们遍历空间上的所有点;再次,如果要让蚂蚁找到最短的路径,那么需要计算所有可能的路径并且比较它们的大小,而且更重要的是,你要小心翼翼地编程,因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序!太复杂了,恐怕没人能够完成这样繁琐冗余的程序。
    然而,事实并没有你想得那么复杂,上面这个程序每个蚂蚁的核心程序编码不过100多行!为什么这么简单的程序会让蚂蚁干这样复杂的事情?答案是:简单规则的涌现。事实上,每只蚂蚁并不是像我们想象的需要知道整个世界的信息,他们其实只关心很小范围内的眼前信息,而且根据这些局部信息利用几条简单的规则进行决策,这样,在蚁群这个集体里,复杂性的行为就会凸现出来。这就是 人工生命、复杂性科学解释的规律!那么,这些简单规则是什么呢?

    问题

    编辑
    蚂蚁究竟是怎么找到食物的呢?在没有蚂蚁找到食物的时候,环境没有有用的信息素,那么蚂蚁为什么会相对有效的找到食物呢?这要归功于蚂蚁的移动规则,尤其是在没有信息素时候的移动规则。首先,它要能尽量保持某种惯性,这样使得蚂蚁尽量向前方移动(开始,这个前方是随机固定的一个方向),而不是原地无谓的打转或者震动;其次,蚂蚁要有一定的随机性,虽然有了固定的方向,但它也不能像粒子一样 直线运动下去,而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性,尽量保持原来的方向,但又有新的试探,尤其当碰到障碍物的时候它会立即改变方向,这可以看成一种选择的过程,也就是环境的障碍物让蚂蚁的某个方向正确,而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如 迷宫的地图中仍然能找到隐蔽得很好的食物。
    当然,在有一只蚂蚁找到了食物的时候,大部分蚂蚁会沿着信息素很快找到食物的。但不排除会出现这样的情况:在最初的时候,一部分蚂蚁通过随机选择了同一条路径,随着这条路径上蚂蚁释放的信息素越来越多,更多的蚂蚁也选择这条路径,但这条路径并不是最优(即最短)的,所以,导致了迭代次数完成后,蚂蚁找到的不是最优解,而是次优解,这种情况下的结果可能对实际应用的意义就不大了。
    蚂蚁如何找到最短路径的?这一是要归功于信息素,另外要归功于环境,具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多,因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物,开始的时候,走这两条路的蚂蚁数量同样多(或者较长的路上蚂蚁多,这也无关紧要)。当蚂蚁沿着一条路到达终点以后会马上返回来,这样,短的路蚂蚁来回一次的时间就短,这也意味着重复的频率就快,因而在单位时间里走过的蚂蚁数目就多,洒下的信息素自然也会多,自然会有更多的蚂蚁被吸引过来,从而洒下更多的信息素……;而长的路正相反,因此,越来越多地蚂蚁聚集到较短的路径上来,最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题,实际上蚂蚁逐渐接近全局最短路的,为什么呢?这源于蚂蚁会犯错误,也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径,这可以理解为一种创新,这种创新如果能缩短路途,那么根据刚才叙述的原理,更多的蚂蚁会被吸引过来。

    详细说明

    编辑

    范围

    蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是3),那么它能观察到的范围就是3*3个方格世界,并且能移动的距离也在这个范围之内。

    环境

    蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,还有信息素,信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的 环境信息。环境以一定的速率让信息素消失。

    觅食规则

    在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。

    移动规则

    每只蚂蚁都朝向信息素最多的方向移,并且,当周围没有信息素指引的时候,蚂蚁会按照自己原来运动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈,它会记住刚才走过了哪些点,如果发现要走的下一点已经在之前走过了,它就会尽量避开。

    避障规则

    如果蚂蚁要移动的方向有障碍物挡住,它会随机的选择另一个方向,并且有信息素指引的话,它会按照觅食的规则行为。

    信息素规则

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

    相关研究

    编辑

    引申

    跟着蚂蚁的踪迹,你找到了什么?通过上面的原理叙述和实际操作,我们不难发现蚂蚁之所以具有智能行为,完全归功于它的简单行为规则,而这些规则综合起来具有下面两个方面的特点:
    1、多样性
    2、 正反馈
    多样性保证了蚂蚁在觅食的时候不至走进死胡同而无限循环,正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力,而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见,而多样性是打破权威体现的创造性,正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。
    引申来讲,大自然的进化,社会的进步、人类的创新实际上都离不开这两样东西,多样性保证了系统的创新能力,正反馈保证了优良特性能够得到强化,两者要恰到好处的结合。如果多样性过剩,也就是系统过于活跃,这相当于蚂蚁会过多的随机运动,它就会陷入混沌状态;而相反,多样性不够,正反馈机制过强,那么系统就好比一潭死水。这在蚁群中来讲就表现为,蚂蚁的行为过于僵硬,当环境变化了,蚂蚁群仍然不能适当的调整。
    既然复杂性、智能行为是根据底层规则涌现的,既然底层规则具有多样性和正反馈特点,那么也许你会问这些规则是哪里来的?多样性和正反馈又是哪里来的?我本人的意见:规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢?为什么在你眼前呈现的世界是如此栩栩如生呢?答案在于环境造就了这一切,之所以你看到栩栩如生的世界,是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了,被环境淘汰了!

    搜索引擎算法

    蚁群算法的由来:蚂蚁是地球上最常见、数量最多的昆虫种类之一,常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征,引起了一些学者的注意。意大利学者M.Dorigo,V.Maniezzo等人在观察蚂蚁的觅食习性时发现,蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现,蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的 挥发性化学物质来进行通信和协调的。 化学通信是蚂蚁采取的基本信息交流方式之一,在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁 觅食行为的研究,他们发现,整个蚁群就是通过这种信息素进行相互协作,形成 正反馈,从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。
    这样,M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是:通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递,搜索从蚁巢至食物间最短路径的集体寻优特征,以及该过程与 旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时,该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维 背包问题等,显示了其适用于组合优化类 问题求解的优越特征。
    多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发,该算法现已被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通等领域。
    蚁群算法之所以能引起相关领域研究者的注意,是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中,寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免,同时,具有贪婪启发
    图3蚁群在障碍物前经过一段时间后的情形 图3蚁群在障碍物前经过一段时间后的情形
    式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力,已经在最初的算法模型基础上得到了很大的改进和拓展。
    经过一定时间,从食物源返回的蚂蚁到达D点同样也碰到障碍物,也需要进行选择。此时A, B两侧的信息素浓度相同,它们仍然一半向左,一半向右。但是当A侧的蚂蚁已经完全绕过障碍物到达C点时,B侧的蚂蚁由于需走的路径更长,还不能到达C点,图3表示蚁群在障碍物前经过一段时间后的情形。
    此时对于从蚁巢出发来到C点的蚂蚁来说,由于A侧的信息素浓度高,B侧的信息素较低,就倾向于选择A侧的路径。这样的结果是A侧的蚂蚁越来越多,最终所有蚂蚁都选择这条较短的路径,图4 表示蚁群最终选择的路径
    图4 蚁群最终选择的路径 图4 蚁群最终选择的路径
    上述过程,很显然是由蚂蚁所留下的信息素的“正反馈”过程而导致的。蚂蚁个体就是通过这种信息的交流来达到搜索食物的目的。蚁群算法的基本思想也是从这个过程转化而来的。
    蚁群算法的特点:
    1)蚁群算法是一种自组织的算法。在系统论中,自组织和它组织是组织的两个基本分类,其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部,来自于系统内部的是自组织,来自于系统外部的是他组织。如果系统在获得空间的、时间的或者功能结构的过程中,没有外界的特定干预,我们便说系统是自组织的。在抽象意义上讲,自组织就是在没有外界作用下使得系统熵减小的过程(即是系统从无序到有序的变化过程)。蚁群算法充分体现了这个过程,以蚂蚁群体优化为例子说明。当算法开始的初期,单个的人工蚂蚁无序的寻找解,算法经过一段时间的演化,人工蚂蚁间通过信息激素的作用,自发的越来越趋向于寻找到接近最优解的一些解,这就是一个无序到有序的过程。
    2)蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统,它在问题空间的多点同时开始进行独立的解搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。
    3)蚁群算法是一种正反馈的算法。从真实蚂蚁的觅食过程中我们不难看出,蚂蚁能够最终找到最短路径,直接依赖于最短路径上信息激素的堆积,而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说,初始时刻在环境中存在完全相同的信息激素,给予系统一个微小扰动,使得各个边上的轨迹浓度不相同,蚂蚁构造的解就存在了优劣,算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素,而更多的信息激素又吸引了更多的蚂蚁,这个正反馈的过程使得初始的不同得到不断的扩大,同时又引导整个系统向 最优解的方向进化。因此,正反馈是蚂蚁算法的重要特征,它使得算法演化过程得以进行。
    4)蚁群算法具有较强的鲁棒性。相对于其它算法,蚁群算法对初始路线要求不高,即蚁群算法的求解结果不依赖于初始路线的选择,而且在搜索过程中不需要进行人工的调整。其次,蚁群算法的参数数目少,设置简单,易于蚁群算法应用到其它组合优化问题的求解。
    蚁群算法的应用进展以蚁群算法为代表的蚁群智能已成为当今分布式人工智能研究的一个热点,许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究。美国 五角大楼正在资助关于群智能系统的研究工作-群体战略(Swarm Strategy),它的一个实战用途是通过运用成群的空中 无人驾驶飞行器和地面车辆来转移敌人的注意力,让自己的军队在敌人后方不被察觉地安全进行。英国电信公司和美国世界通信公司以电子蚂蚁为基础,对新的电信网络管理方法进行了试验。群智能还被应用于工厂生产计划的制定和运输部门的后勤管理。美国太平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件,结果每年至少节约了1000万美元的费用开支。英国 联合利华公司己率先利用群智能技术改善其一家牙膏厂的运转情况。美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用这种技术来改善其运转的机能。鉴于群智能广阔的应用前景,美国和欧盟均于近几年开始出资资助基于群智能模拟的相关研究项目,并在一些院校开设群体智能的相关课程。国内,国家自然科学基金”十五”期间 学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题。
    蚁群优化算法最初用于解决TSP问题,经过多年的发展,已经陆续渗透到其他领域中,比如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用,其中最成功的是在组合优化问题中的应用。
    在网络路由处理中,网络的流量分布不断变化,网络链路或结点也会随机地失效或重新加入。蚁群的自身催化与正向 反馈机制正好符合了这类问题的求解特点,因而,蚁群算法在网络领域得到一定应用。蚁群 觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。因而,实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。
    在某群体中若存在众多无智能的个体,它们通过相互之间的简单合作所表现出来的智能行为即称为集群智能(Swarm Intelligence)。互联网上的交流,不过是更多的神经元连接(人脑)通过互联网相互作用的结果,光缆和路由器不过是轴突和突触的延伸。从 自组织现象的角度上看,人脑的智能和蚁群也没有本质上的区别,单个 神经元没有智能可言,单个蚂蚁也没有,但是通过连接形成的体系,是一个智能体。(作者: 李精灵 编选:中国电子商务研究中心)


    1. 蚁群算法简介

         蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。经过20多年的发展,蚁群算法在理论以及应用研究上已经得到巨大的进步。

          蚁群算法是一种仿生学算法,是由自然界中蚂蚁觅食的行为而启发的。在自然界中,蚂蚁觅食过程中,蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图(1)显示了这样一个觅食的过程。

    image

    图(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 V={c1,c2,…,ci,…,cn},i=1,2,…,n是所有城市的集合.  ci ci表示第i个城市,  n n为城市的数目;

    E={(r,s):r,sV} E={(r,s):r,s∈V}是所有城市之间连接的集合;

    C={crs:r,sV} C={crs:r,s∈V}是所有城市之间连接的成本度量(一般为城市之间的距离);

    如果 crs=csr crs=csr, 那么该TSP问题为对称的,否则为非对称的。

    一个TSP问题可以表达为:

    求解遍历图 G=(V,E,C) G=(V,E,C)所有的节点一次并且回到起始节点,使得连接这些节点的路径成本最低。

    3. 蚁群算法原理

          假如蚁群中所有蚂蚁的数量为m,所有城市之间的信息素用矩阵pheromone表示,最短路径为bestLength,最佳路径为bestTour。每只蚂蚁都有自己的内存,内存中用一个禁忌表(Tabu)来存储该蚂蚁已经访问过的城市,表示其在以后的搜索中将不能访问这些城市;还有用另外一个允许访问的城市表(Allowed)来存储它还可以访问的城市;另外还用一个矩阵(Delta)来存储它在一个循环(或者迭代)中给所经过的路径释放的信息素;还有另外一些数据,例如一些控制参数 (αβρQ) (α,β,ρ,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)

    其中 p(t)ij pij(t)表示选择城市j的概率, k k表示第 k k个蚂蚁, τ(t)ij τij(t)表示城市 i,j i,j在第 t t时刻的信息素浓度, ηij ηij表示从城市i到城市j的可见度,

    ηij=1dij ηij=1dij dij dij表示城市 i,j i,j之间的成本(或距离)。由此可见 dij dij越小, ηij ηij越大,也就是从城市 i i j j的可见性就越大。 Δτkij Δτijk表示蚂蚁 k k在城市 i i j j之间留下的信息素。

    Lk Lk表示蚂蚁 k k经过一个循环(或迭代)锁经过路径的总成本(或距离),即tourLength. α,β,Q α,β,Q 均为控制参数。

    (3)更新信息素矩阵

    t=t+n t=t+nt,按照(公式3)更新信息素矩阵phermone。

    τij(t+n)=ρτij(t)+Δτij τij(t+n)=ρ⋅τij(t)+Δτij

    (公式3)

    τij(t+n) τij(t+n) t+n t+n时刻城市 i i j j之间的信息素浓度。 ρ ρ为控制参数, Deltaij Deltaij为城市 i i j j之间信息素经过一个迭代后的增量。并且有

    Δτij=k=1mΔτkij Δτij=∑k=1mΔτijk

    (公式4)

    其中 Δτkij Δτijk由公式计算得到。

    (4)检查终止条件

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

    (5)输出最优值

    4. Java实现

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

    image

    图(2)att48距离计算方法

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

    具体实现代码如下(此代码借鉴了蚁群优化算法的JAVA实现):

    Ant类:

      1: import java.util.Random;
    
      2: import java.util.Vector;
    
      3: 
    
      4: /**
    
      5:  * 
    
      6:  * @author BIAO YU
    
      7:  *
    
      8:  */
    
      9: public class Ant implements Cloneable {
    
     10: 
    
     11:   private Vector<Integer> tabu; //禁忌表
    
     12:   private Vector<Integer> allowedCities; //允许搜索的城市
    
     13:   private float[][] delta; //信息数变化矩阵
    
     14:   private int[][] distance; //距离矩阵
    
     15:   
    
     16:   private float alpha; 
    
     17:   private float beta;
    
     18:   
    
     19:   private int tourLength; //路径长度
    
     20:   private int cityNum; //城市数量
    
     21:   
    
     22:   private int firstCity; //起始城市
    
     23:   private int currentCity; //当前城市
    
     24:   
    
     25:   public Ant(){
    
     26:     cityNum = 30;
    
     27:     tourLength = 0;
    
     28:     
    
     29:   }
    
     30:   
    
     31:   /**
    
     32:    * Constructor of Ant
    
     33:    * @param num 蚂蚁数量
    
     34:    */
    
     35:   public Ant(int num){
    
     36:     cityNum = num;
    
     37:     tourLength = 0;
    
     38:     
    
     39:   }
    
     40:   
    
     41:   /**
    
     42:    * 初始化蚂蚁,随机选择起始位置
    
     43:    * @param distance 距离矩阵
    
     44:    * @param a alpha
    
     45:    * @param b beta
    
     46:    */
    
     47:   public void init(int[][] distance, float a, float b){
    
     48:     alpha = a;
    
     49:     beta = b;
    
     50:     allowedCities = new Vector<Integer>();
    
     51:     tabu = new Vector<Integer>();
    
     52:     this.distance = distance;
    
     53:     delta = new float[cityNum][cityNum];
    
     54:     for (int i = 0; i < cityNum; i++) {
    
     55:       Integer integer = new Integer(i);
    
     56:       allowedCities.add(integer);
    
     57:       for (int j = 0; j < cityNum; j++) {
    
     58:         delta[i][j] = 0.f;
    
     59:       }
    
     60:     }
    
     61:     
    
     62:     Random random = new Random(System.currentTimeMillis());
    
     63:     firstCity = random.nextInt(cityNum);
    
     64:     for (Integer i:allowedCities) {
    
     65:       if (i.intValue() == firstCity) {
    
     66:         allowedCities.remove(i);
    
     67:         break;
    
     68:       }
    
     69:     }
    
     70:     
    
     71:     tabu.add(Integer.valueOf(firstCity));
    
     72:     currentCity = firstCity;
    
     73:   }
    
     74:   
    
     75:   /**
    
     76:    * 选择下一个城市
    
     77:    * @param pheromone 信息素矩阵
    
     78:    */
    
     79:   public void selectNextCity(float[][] pheromone){
    
     80:     float[] p = new float[cityNum];
    
     81:     float sum = 0.0f;
    
     82:     //计算分母部分
    
     83:     for (Integer i:allowedCities) {
    
     84:       sum += Math.pow(pheromone[currentCity][i.intValue()], alpha)*Math.pow(1.0/distance[currentCity][i.intValue()], beta);
    
     85:     }
    
     86:     //计算概率矩阵
    
     87:     for (int i = 0; i < cityNum; i++) {
    
     88:       boolean flag = false;
    
     89:       for (Integer j:allowedCities) {
    
     90:         
    
     91:         if (i == j.intValue()) {
    
     92:           p[i] = (float) (Math.pow(pheromone[currentCity][i], alpha)*Math.pow(1.0/distance[currentCity][i], beta))/sum;
    
     93:           flag = true;
    
     94:           break;
    
     95:         }
    
     96:       }
    
     97:       
    
     98:       if (flag == false) {
    
     99:         p[i] = 0.f;
    
    100:       }
    
    101:     }
    
    102:     
    
    103:     //轮盘赌选择下一个城市
    
    104:     Random random = new Random(System.currentTimeMillis());
    
    105:     float sleectP = random.nextFloat();
    
    106:     int selectCity = 0;
    
    107:     float sum1 = 0.f;
    
    108:     for (int i = 0; i < cityNum; i++) {
    
    109:       sum1 += p[i];
    
    110:       if (sum1 >= sleectP) {
    
    111:         selectCity = i;
    
    112:         break;
    
    113:       }
    
    114:     }
    
    115:     
    
    116:     //从允许选择的城市中去除select city
    
    117:     for (Integer i:allowedCities) {
    
    118:       if (i.intValue() == selectCity) {
    
    119:         allowedCities.remove(i);
    
    120:         break;
    
    121:       }
    
    122:     }
    
    123:     //在禁忌表中添加select city
    
    124:     tabu.add(Integer.valueOf(selectCity));
    
    125:     //将当前城市改为选择的城市
    
    126:     currentCity = selectCity;
    
    127:     
    
    128:   }
    
    129:   
    
    130:   /**
    
    131:    * 计算路径长度
    
    132:    * @return 路径长度
    
    133:    */
    
    134:   private int calculateTourLength(){
    
    135:     int len = 0;
    
    136:     for (int i = 0; i < cityNum; i++) {
    
    137:       len += distance[this.tabu.get(i).intValue()][this.tabu.get(i+1).intValue()];
    
    138:     }
    
    139:     return len;
    
    140:   }
    
    141:   
    
    142:   
    
    143:   
    
    144:   public Vector<Integer> getAllowedCities() {
    
    145:     return allowedCities;
    
    146:   }
    
    147: 
    
    148:   public void setAllowedCities(Vector<Integer> allowedCities) {
    
    149:     this.allowedCities = allowedCities;
    
    150:   }
    
    151: 
    
    152:   public int getTourLength() {
    
    153:     tourLength = calculateTourLength();
    
    154:     return tourLength;
    
    155:   }
    
    156:   public void setTourLength(int tourLength) {
    
    157:     this.tourLength = tourLength;
    
    158:   }
    
    159:   public int getCityNum() {
    
    160:     return cityNum;
    
    161:   }
    
    162:   public void setCityNum(int cityNum) {
    
    163:     this.cityNum = cityNum;
    
    164:   }
    
    165: 
    
    166:   public Vector<Integer> getTabu() {
    
    167:     return tabu;
    
    168:   }
    
    169: 
    
    170:   public void setTabu(Vector<Integer> tabu) {
    
    171:     this.tabu = tabu;
    
    172:   }
    
    173: 
    
    174:   public float[][] getDelta() {
    
    175:     return delta;
    
    176:   }
    
    177: 
    
    178:   public void setDelta(float[][] delta) {
    
    179:     this.delta = delta;
    
    180:   }
    
    181: 
    
    182:   public int getFirstCity() {
    
    183:     return firstCity;
    
    184:   }
    
    185: 
    
    186:   public void setFirstCity(int firstCity) {
    
    187:     this.firstCity = firstCity;
    
    188:   }
    
    189:   
    
    190: }
    
    191: 

    ACO类:

      1: import java.io.BufferedReader;
    
      2: import java.io.FileInputStream;
    
      3: import java.io.IOException;
    
      4: import java.io.InputStreamReader;
    
      5: 
    
      6: /**
    
      7:  * 
    
      8:  * @author BIAO YU
    
      9:  * 
    
     10:  *
    
     11:  */
    
     12: public class ACO {
    
     13: 
    
     14:   private Ant[] ants; //蚂蚁
    
     15:   private int antNum; //蚂蚁数量
    
     16:   private int cityNum; //城市数量
    
     17:   private int MAX_GEN; //运行代数
    
     18:   private float[][] pheromone; //信息素矩阵
    
     19:   private int[][] distance; //距离矩阵
    
     20:   private int bestLength; //最佳长度
    
     21:   private int[] bestTour; //最佳路径
    
     22:   
    
     23:   //三个参数
    
     24:   private float alpha; 
    
     25:   private float beta;
    
     26:   private float rho;
    
     27:   
    
     28:   
    
     29:   public ACO(){
    
     30:     
    
     31:   }
    
     32:   /** constructor of ACO
    
     33:    * @param n 城市数量
    
     34:    * @param m 蚂蚁数量
    
     35:    * @param g 运行代数
    
     36:    * @param a alpha
    
     37:    * @param b beta
    
     38:    * @param r rho
    
     39:    * 
    
     40:   **/
    
     41:   public ACO(int n, int m, int g, float a, float b, float r) {
    
     42:     cityNum = n;
    
     43:     antNum = m;
    
     44:     ants = new Ant[antNum];
    
     45:     MAX_GEN = g;
    
     46:     alpha = a;
    
     47:     beta = b;
    
     48:     rho = r;
    
     49:     
    
     50:   }
    
     51:   
    
     52:   @SuppressWarnings("resource")
    
     53:   /**
    
     54:    * 初始化ACO算法类
    
     55:    * @param filename 数据文件名,该文件存储所有城市节点坐标数据
    
     56:    * @throws IOException
    
     57:    */
    
     58:   private void init(String filename) throws IOException{
    
     59:     //读取数据  
    
     60:         int[] x;  
    
     61:         int[] y;  
    
     62:         String strbuff;  
    
     63:         BufferedReader data = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));  
    
     64:         
    
     65:         distance = new int[cityNum][cityNum];  
    
     66:         x = new int[cityNum];  
    
     67:         y = new int[cityNum];  
    
     68:         for (int i = 0; i < cityNum; i++) {  
    
     69:             strbuff = data.readLine(); 
    
     70:             String[] strcol = strbuff.split("");  
    
     71:             x[i] = Integer.valueOf(strcol[1]);  
    
     72:             y[i] = Integer.valueOf(strcol[2]);  
    
     73:         }  
    
     74:         //计算距离矩阵 ,针对具体问题,距离计算方法也不一样,此处用的是att48作为案例,它有48个城市,距离计算方法为伪欧氏距离,最优值为10628 
    
     75:         for (int i = 0; i < cityNum - 1; i++) {  
    
     76:             distance[i][i] = 0;  //对角线为0
    
     77:             for (int j = i + 1; j < cityNum; j++) {  
    
     78:               double rij = Math.sqrt(((x[i] - x[j]) * (x[i] - x[j])+ (y[i] - y[j]) * (y[i] - y[j]))/10.0);
    
     79:               int tij = (int) Math.round(rij);
    
     80:               if (tij < rij) {
    
     81:                 distance[i][j] = tij + 1;  
    
     82:                     distance[j][i] = distance[i][j];  
    
     83:         }else {
    
     84:           distance[i][j] = tij;  
    
     85:                     distance[j][i] = distance[i][j]; 
    
     86:         }
    
     87:             }  
    
     88:         }  
    
     89:         distance[cityNum - 1][cityNum - 1] = 0;  
    
     90:         
    
     91:         //初始化信息素矩阵  
    
     92:         pheromone=new float[cityNum][cityNum];  
    
     93:         for(int i=0;i<cityNum;i++)  
    
     94:         {  
    
     95:             for(int j=0;j<cityNum;j++){  
    
     96:                 pheromone[i][j]=0.1f;  //初始化为0.1
    
     97:             }  
    
     98:         }  
    
     99:         bestLength=Integer.MAX_VALUE;  
    
    100:         bestTour=new int[cityNum+1];  
    
    101:         //随机放置蚂蚁  
    
    102:         for(int i=0;i<antNum;i++){  
    
    103:             ants[i]=new Ant(cityNum);  
    
    104:             ants[i].init(distance, alpha, beta);  
    
    105:         }  
    
    106:   }
    
    107:   
    
    108:   public void solve(){
    
    109:     
    
    110:     for (int g = 0; g < MAX_GEN; g++) {
    
    111:       for (int i = 0; i < antNum; i++) {
    
    112:         for (int j = 1; j < cityNum; j++) {
    
    113:           ants[i].selectNextCity(pheromone);
    
    114:         }
    
    115:         ants[i].getTabu().add(ants[i].getFirstCity());
    
    116:         if (ants[i].getTourLength() < bestLength) {
    
    117:           bestLength = ants[i].getTourLength();
    
    118:           for (int k = 0; k < cityNum + 1; k++) {
    
    119:             bestTour[k] = ants[i].getTabu().get(k).intValue();
    
    120:           }
    
    121:         }
    
    122:         for (int j = 0; j < cityNum; j++) {
    
    123:           ants[i].getDelta()[ants[i].getTabu().get(j).intValue()][ants[i].getTabu().get(j+1).intValue()] = (float) (1./ants[i].getTourLength());
    
    124:           ants[i].getDelta()[ants[i].getTabu().get(j+1).intValue()][ants[i].getTabu().get(j).intValue()] = (float) (1./ants[i].getTourLength());
    
    125:         }
    
    126:       }
    
    127:       
    
    128:       //更新信息素
    
    129:       updatePheromone();
    
    130:       
    
    131:        //重新初始化蚂蚁
    
    132:           for(int i=0;i<antNum;i++){  
    
    133:              
    
    134:               ants[i].init(distance, alpha, beta);  
    
    135:           }  
    
    136:     }
    
    137:     
    
    138:     //打印最佳结果
    
    139:     printOptimal();
    
    140:   }
    
    141:   
    
    142:   //更新信息素
    
    143:   private void updatePheromone(){
    
    144:     //信息素挥发  
    
    145:         for(int i=0;i<cityNum;i++)  
    
    146:             for(int j=0;j<cityNum;j++)  
    
    147:                 pheromone[i][j]=pheromone[i][j]*(1-rho);  
    
    148:         //信息素更新  
    
    149:         for(int i=0;i<cityNum;i++){  
    
    150:             for(int j=0;j<cityNum;j++){  
    
    151:                 for (int k = 0; k < antNum; k++) {
    
    152:           pheromone[i][j] += ants[k].getDelta()[i][j];
    
    153:         } 
    
    154:             }  
    
    155:         }  
    
    156:   }
    
    157:   
    
    158:   private void printOptimal(){
    
    159:     System.out.println("The optimal length is: " + bestLength);
    
    160:     System.out.println("The optimal tour is: ");
    
    161:     for (int i = 0; i < cityNum + 1; i++) {
    
    162:       System.out.println(bestTour[i]);
    
    163:     }
    
    164:   }
    
    165:   
    
    166:   public Ant[] getAnts() {
    
    167:     return ants;
    
    168:   }
    
    169: 
    
    170:   public void setAnts(Ant[] ants) {
    
    171:     this.ants = ants;
    
    172:   }
    
    173: 
    
    174:   public int getAntNum() {
    
    175:     return antNum;
    
    176:   }
    
    177: 
    
    178:   public void setAntNum(int m) {
    
    179:     this.antNum = m;
    
    180:   }
    
    181: 
    
    182:   public int getCityNum() {
    
    183:     return cityNum;
    
    184:   }
    
    185: 
    
    186:   public void setCityNum(int cityNum) {
    
    187:     this.cityNum = cityNum;
    
    188:   }
    
    189: 
    
    190:   public int getMAX_GEN() {
    
    191:     return MAX_GEN;
    
    192:   }
    
    193: 
    
    194:   public void setMAX_GEN(int mAX_GEN) {
    
    195:     MAX_GEN = mAX_GEN;
    
    196:   }
    
    197: 
    
    198:   public float[][] getPheromone() {
    
    199:     return pheromone;
    
    200:   }
    
    201: 
    
    202:   public void setPheromone(float[][] pheromone) {
    
    203:     this.pheromone = pheromone;
    
    204:   }
    
    205: 
    
    206:   public int[][] getDistance() {
    
    207:     return distance;
    
    208:   }
    
    209: 
    
    210:   public void setDistance(int[][] distance) {
    
    211:     this.distance = distance;
    
    212:   }
    
    213: 
    
    214:   public int getBestLength() {
    
    215:     return bestLength;
    
    216:   }
    
    217: 
    
    218:   public void setBestLength(int bestLength) {
    
    219:     this.bestLength = bestLength;
    
    220:   }
    
    221: 
    
    222:   public int[] getBestTour() {
    
    223:     return bestTour;
    
    224:   }
    
    225: 
    
    226:   public void setBestTour(int[] bestTour) {
    
    227:     this.bestTour = bestTour;
    
    228:   }
    
    229: 
    
    230:   public float getAlpha() {
    
    231:     return alpha;
    
    232:   }
    
    233: 
    
    234:   public void setAlpha(float alpha) {
    
    235:     this.alpha = alpha;
    
    236:   }
    
    237: 
    
    238:   public float getBeta() {
    
    239:     return beta;
    
    240:   }
    
    241: 
    
    242:   public void setBeta(float beta) {
    
    243:     this.beta = beta;
    
    244:   }
    
    245: 
    
    246:   public float getRho() {
    
    247:     return rho;
    
    248:   }
    
    249: 
    
    250:   public void setRho(float rho) {
    
    251:     this.rho = rho;
    
    252:   }
    
    253: 
    
    254: 
    
    255:   /**
    
    256:    * @param args
    
    257:    * @throws IOException 
    
    258:    */
    
    259:   public static void main(String[] args) throws IOException {
    
    260:     ACO aco = new ACO(48, 100, 1000, 1.f, 5.f, 0.5f);
    
    261:     aco.init("c://data.txt");
    
    262:     aco.solve();
    
    263:   }
    
    264: 
    
    265: }
    
    266: 

    5. 总结

          蚁群算法和其它的启发式算法一样,在很多场合都得到了应用,并且取得了很好的结果。但是同样存在着很多的缺点,例如收敛速度慢,容易陷入局部最优,等等。对于这些问题,还需要进一步的研究和探索,另外蚁群算法的数学机理至今还没有得到科学的解释,这也是当前研究的热点和急需解决的问题之一。


    展开全文
  • 尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行为,蚂蚁也不可能从这些解释中获益,但是数学及汁算机方面的专家和工程师却把这种超越生物本身的模型转化成了一项有用的优化和控制算法一蚁群算法,也称...
  • 最近好多人问我蚁群算法最短...他们在研究新型算法的过程中,发现蚁群在寻找食物时,通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标,据此提出了基于信息正反馈原理蚁群算法。 单出口情况: ...

    最近好多人问我蚁群算法最短路径规划如何设置多出口情况,原来2019年美赛D题“拯救卢浮宫”需要用到。本人没有看过美赛的题目,下面给出一些不成熟的代码。
    蚁群算法简介:蚁群算法最早是由Marco Dorigo等人在1991年提出,他们在研究新型算法的过程中,发现蚁群在寻找食物时,通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标,据此提出了基于信息正反馈原理的蚁群算法。

    单出口情况:
    http://www.omegaxyz.com/2018/01/27/aco_routes/
    针对大家问过的问题下面给出解答:
    在这里插入图片描述
    问题1:如何修改目的地(出现minPL(i)=min(PLKPLK);错误)

    出口只需要修改E,其他都不需要改,E是一维,下面的程序会自动解析为横纵坐标(即Ex和Ey不需要修改)
    例如E = MMMM说明是最后一个格子,MMMM-j代表右下角的格子向左平移j个单位,MMMM-iMM,代表右下角的格子向上平移i个单位。
    大家可以试试下面的这些出口
    MMMM, MMMM-19MM-5, MMMM-7MM, MMMM-15MM, MMMM-17
    问题2:如何处理非正方形矩阵

    首先MM作为边长要修改,下面的出口横纵坐标Ex,Ey需要重新解析,相关的画图部分要改,信息素矩阵Tau要修改。
    问题3:G2D函数无法运行的问题

    这里可能是matlab版本问题,为了方便,我将G2D函数直接放在代码的最下面,如果不能运行建议将G2D函数重新新建一个文件,并把main函数中的G2D删去。
    G2D.m

    function D=G2D(G) 
        l=size(G,1); 
        D=zeros(l*l,l*l); 
        for i=1:l 
            for j=1:l 
                if G(i,j)==0 
                    for m=1:l 
                        for n=1:l 
                            if G(m,n)==0 
                                im=abs(i-m);jn=abs(j-n); 
                                if im+jn==1||(im==1&&jn==1) 
                                    D((i-1)*l+j,(m-1)*l+n)=(im+jn)^0.5; 
                                end
                            end 
                        end 
                    end 
                end 
            end 
        end
    end
    

    问题4:对于多出口的情况

    此问题代码需要重构,或者来个简便方法,多线程每个线程一个出口最后一起画图。
    设立一个archive矩阵,里面存储所有的目标点

    Earchive = [MM*MM, MM*MM-19*MM-5, MM*MM-7*MM, MM*MM-15*MM, MM*MM-17];
    

    来个大循环,每次重新运行蚁群算法,最终画图画到一个图上(使用matlab hold on语句)
    声明:以上给出的程序与2019年美赛建模D题具体思路无关。
    更多内容访问 omegaxyz.com
    网站所有代码采用Apache 2.0授权
    网站文章采用知识共享许可协议BY-NC-SA4.0授权
    © 2019 • OmegaXYZ-版权所有 转载请注明出处

    展开全文
  • ACO蚁群算法解决TSP旅行商问题

    万次阅读 2015-04-30 15:31:45
    前言 蚁群算法也是一种利用了大自然规律的启发式算法,与之前学习过的GA遗传算法类似,遗传算法是用了...话题重新回到蚁群算法蚁群算法是一个利用了蚂蚁寻找食物的原理。不知道小时候有没有发现,当一个蚂蚁发现了地
  •     基于蚁群算法的MTSP问题 蚁群算法 一、简介   20世纪50年代中期创立了仿生,人们从生物进化的机理中受到启发。提出许多用以解决复杂优化问题的新方法,如进化规划、进化策略、遗传算法等,这些算法成功...
  • 计算智能--生物智能之蚁群算法

    千次阅读 2018-05-08 17:08:14
    1 蚁群算法原理 通过信息素(会蒸发)来交流 蚂蚁属于群居昆虫,个体行为极其简单,而群体行为却相当复杂。协作能力:一群蚂蚁很容易找到从蚁巢到食物源的最短路径,而单个蚂蚁则不能。自适应能力:例如在蚁群的...
  • 现代优化算法(五): 蚁群算法

    千次阅读 2019-04-29 15:34:46
    组合优化算法系列: 现代优化算法 (一):模拟退火算法 及...现代优化算法(五): 蚁群算法 目录 1 蚁群算法简介 2 解决TSP 问题的蚁群算法描述 人工蚁群算法的求解步骤 3 人工蚁群算法性能的讨论 1 蚁...
  • 蚁群算法(ACO)学习笔记

    千次阅读 多人点赞 2019-08-16 15:26:14
    蚁群算法笔记 #1.蚁群算法简介:
  • 数学建模方法-蚁群算法

    千次阅读 2019-09-26 03:51:40
    跟粒子群算法一样,蚁群算法也是基于对生物行为的研究所受到启发而产生的。它的诞生比粒子群算法还要早3年,在1992年的某一天,一位叫Marco Dorigo的在他的博士论文中提出了蚁群算法,并称其灵感来源于蚂蚁在寻找...
  • 深度学习经典算法 | 蚁群算法解析

    千次阅读 2020-06-28 23:48:44
    蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径问题。根据昆虫家的观察,发现自然界的蚂蚁虽然视觉不发达,但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径,并且能在环境发生变化(如原有路径...
  • 1.1 算法概述生物现象由来行为特征蚁群算法的应用算法特点ACA算法特点补充:启发式算法初始化参数构建模型判断算法是否达到迭代次数 1.什么是蚁群算法? 1.1 算法概述 蚁群算法(Ant Colony Algorithm, ACA)由Marco ...
  • 写在前面 ...遗传算法详解与Python实现在上一篇博客里已经介绍,蚁群算法与遗传算法等仿生进化算法均有共通之处,读者只需要明白透彻其中一种算法的原理和细节,便能触类旁通。因此,今天介绍的是蚁群算
  • 蚁群算法(Ant Colony Algorithm, ACA)简介及其MATLAB实现

    万次阅读 多人点赞 2018-10-09 13:47:25
    目录 算法概述 ACA算法的数学原理 算法步骤 ACA算法特点 ...• 蚁群算法(Ant Colony Algorithm, ACA)由Marco Dorigo于1992年在他的博士论文中首次提出。 • 蚂蚁在寻找食物源时,会在其经过...
  • 蚁群算法路径规划TSP

    千次阅读 2020-01-16 13:55:46
    群蚁算法基本原理 3.群蚁算法的基本流程 4.群蚁算法计算实例 5.TSP问题的群蚁算法C#代码实现 6.资源与参考文献  若干年前读研的时候,学院有一个教授,专门做群蚁算法的,很厉害,偶尔了解了一点点。感觉也是...
  • 蚁群算法、遗传算法、模拟退火算法介绍 穷举法 列举所有可能,然后一个个去,得到最优的结果。如图一,需要从A点一直走到G点,才能知道,F是最高的(最优解)。这种算法得到的最优解肯定是最好的,但也是效率最低的。...
  • 1.1 蚁群算法原理  蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明:一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径,而单只蚂蚁则不能。生物学家经过大量细致观察研究发现,蚂蚁个体...
  • 蚁群算法(ant colony optimization, ACO)

    万次阅读 2013-01-04 11:02:34
    蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 ...
  • 蚁群算法理论

    千次阅读 2017-03-14 20:46:54
    并开始寻求所得结果可接受的启发式算法,以处理大规模实际问题,一些其他学科的新一代优化算法相继出现,如禁忌搜索算法,遗传算法,人工神经网络算法,以及现在研究较多的蚁群算法等。 2.2 群蚁算法的原理  ...
  • 1.1 蚁群算法原理  蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明:一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径,而单只蚂蚁则不能。生物学家经过大量细致观察研究发现,蚂蚁个体...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 570
精华内容 228
关键字:

蚁群算法的生物学原理