蚁群算法最短路径规划多出口情况及问题答疑

r囧r小猫 2022-03-21 12:08 427阅读 0赞

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

**单出口情况：**  
[http://www.omegaxyz.com/2018/01/27/aco\_routes/][http_www.omegaxyz.com_2018_01_27_aco_routes]  
**针对大家问过的问题下面给出解答：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70]  
**问题1：如何修改目的地（出现minPL(i)=min(PLKPLK);错误）**

出口只需要修改E，其他都不需要改，E是一维，下面的程序会自动解析为横纵坐标（即Ex和Ey不需要修改）  
例如E = MM*MM说明是最后一个格子，MM*MM-j代表右下角的格子向左平移j个单位，MM*MM-i*MM，代表右下角的格子向上平移i个单位。  
大家可以试试下面的这些出口  
MM*MM, MM*MM-19*MM-5, MM*MM-7*MM, MM*MM-15*MM, MM*MM-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];

[http_www.omegaxyz.com_2018_01_27_aco_routes]: http://www.omegaxyz.com/2018/01/27/aco_routes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70]: /images/20220321/86fc1d7c16ef4e8eba4a29f1abf89ed3.png
[omegaxyz.com]: http://omegaxyz.com