基于ACO蚁群优化算法的栅格地图避障路线规划matlab仿真

简介: 基于ACO蚁群优化算法的栅格地图避障路线规划matlab仿真

1.算法描述

   蚁群算法是通过对自然界中真实蚂蚁的集体行为的观察,模拟而得到一种仿生优化算法,它具有很好的并行性,分布性.根据蚂蚁群体不同的集体行为特征,蚁群算法可分为受蚂蚁觅食行为启发的模型和受孵化分类启发的模型,受劳动分工和协作运输启发的模型.本文重点研究了前两种蚁群算法模型. 受蚂蚁觅食行为启发的模型又称为蚁群优化算法(ACO),是继模拟退火算法,遗传算法,禁忌搜索等之后又一启发式智能优化算法.目前它已成功应用于求解TSP问题,地图着色,路径车辆调度等优化问题.本文针对蚁群算法收敛时间长,易陷入局部最优的缺点,通过对路径上信息素的更新方式作出动态调整,建立信息素平滑机制,进而使得不同路径上的信息素的更新速度有所不同,从而使改进后算法能够有效地缩短搜索的时间,并能对最终解进行优化,避免过早的陷入局部最优. 聚类是数据挖掘的重要技术之一,它可按照某种规则将数据对象划分为多个类或簇,使同一类的数据对象有较高的相似度,而不同类的数据对象差异较大.       

 算法基本思想:

(1)根据具体问题设置多只蚂蚁,分头并行搜索。

(2)每只蚂蚁完成一次周游后,在行进的路上释放信息素,信息素量与解的质量成正比。

(3)蚂蚁路径的选择根据信息素强度大小(初始信息素量设为相等),同时考虑两点之间的距离,采用随机的局部搜索策略。这使得距离较短的边,其上的信息素量较大,后来的蚂蚁选择该边的概率也较大。

(4)每只蚂蚁只能走合法路线(经过每个城市1次且仅1次),为此设置禁忌表来控制。

(5)所有蚂蚁都搜索完一次就是迭代一次,每迭代一次就对所有的边做一次信息素更新,原来的蚂蚁死掉,新的蚂蚁进行新一轮搜索。

(6)更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。

(7)达到预定的迭代步数,或出现停滞现象(所有蚂蚁都选择同样的路径,解不再变化),则算法结束,以当前最优解作为问题的最优解。

    将各个蚂蚁随机地置于不同的出发地,对每个蚂蚁k ( k = 1 , 2 , ⋯  , m ) ,按照轮盘赌法得到下面的转移概率公式计算其下一个待访问的城市,直到所有蚂蚁访问完所有的城市。

image.png

2.仿真效果预览
matlab2022a仿真结果如下:

image.png
image.png
image.png

3.MATLAB核心程序

for k=1:K
    disp(k);
    for m=1:M
%%     First step: status initialization
        W=S;%set current point as the starting point
        Path=S;%initialize the passing route
        PLkm=0;%initialize the passing length
        TABUkm=ones(1,N);%initialize the forbbiden table
        TABUkm(S)=0;% eliminate this point for it is the starting point
        DD=D;%initialize adjacency matrix
%%     Second Step:Choose the nodes that can step forward
        DW=DD(W,:);
        DW1=find(DW<inf);
        for j=1:length(DW1)
            if TABUkm(DW1(j))==0
                DW(j)=inf;
            end
        end
        LJD=find(DW<inf);% set of points can be selected
        Len_LJD=length(LJD);%number of points can be selected
%%     Colony stop condition:there is no food or go into a impass
        while W~=E&&Len_LJD>=1
%%         Third Step:the method to choose the next step
            PP=zeros(1,Len_LJD);
            for i=1:Len_LJD
                PP(i)=(Tau(W,LJD(i))^Alpha)*(Eta(LJD(i))^Beta);
            end
            PP=PP/(sum(PP));%construct probability distributing
            Pcum=cumsum(PP);
            Select=find(Pcum>=rand);
            to_visit=LJD(Select(1));%the next step node
%%         Fourth Step:status update and record
            Path=[Path,to_visit];%Paths accumulation
            PLkm=PLkm+DD(W,to_visit);%Path length accumulation
            W=to_visit;%move to the next point
            for kk=1:N
                if TABUkm(kk)==0
                    DD(W,kk)=inf;
                    DD(kk,W)=inf;
                end
            end
            TABUkm(W)=0;%eliminate the travelled point in the forbidden table
            DW=DD(W,:);
            DW1=find(DW<inf);
            for j=1:length(DW1)
                if TABUkm(DW1(j))==0
                    DW(j)=inf;
                end
            end
            LJD=find(DW<inf);%set of optional points
            Len_LJD=length(LJD);%number of optional points
        end
%%     Fifth Step:record the pate and length that every ant for every
%%     iteration passes
        ROUTES{k,m}=Path;
        if Path(end)==E
            PL(k,m)=PLkm;
        else
            PL(k,m)=inf;
        end
    end
%%    Sixth Step: update pheromone
    Delta_Tau=zeros(N,N);%initialize updating ammount
    for m=1:M
        if PL(k,m)<inf
            ROUT=ROUTES{k,m};
            TS=length(ROUT)-1;
            PL_km=PL(k,m);
            for s=1:TS
                x=ROUT(s);
                y=ROUT(s+1);
                Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km;
                Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;
            end
        end
    end
    Tau=(1-Rho).*Tau+Delta_Tau;%pheromone evaporates some and accumulates some
end
%% ---------------------------PLOT--------------------------------
plotif=1;%control parameter, determine if plot or not
if plotif==1
    %plot convergence curve
    meanPL=zeros(1,K);
    minPL=zeros(1,K);
    for i=1:K
        PLK=PL(i,:);
        Nonzero=find(PLK<inf);
        PLKPLK=PLK(Nonzero);
        meanPL(i)=mean(PLKPLK);
        minPL(i)=min(PLKPLK);
    end
相关文章
|
1天前
|
算法
基于大爆炸优化算法的PID控制器参数寻优matlab仿真
本研究基于大爆炸优化算法对PID控制器参数进行寻优,并通过Matlab仿真对比优化前后PID控制效果。使用MATLAB2022a实现核心程序,展示了算法迭代过程及最优PID参数的求解。大爆炸优化算法通过模拟宇宙大爆炸和大收缩过程,在搜索空间中迭代寻找全局最优解,特别适用于PID参数优化,提升控制系统性能。
|
1天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
4月前
|
安全
【2023高教社杯】D题 圈养湖羊的空间利用率 问题分析、数学模型及MATLAB代码
本文介绍了2023年高教社杯数学建模竞赛D题的圈养湖羊空间利用率问题,包括问题分析、数学模型建立和MATLAB代码实现,旨在优化养殖场的生产计划和空间利用效率。
205 6
【2023高教社杯】D题 圈养湖羊的空间利用率 问题分析、数学模型及MATLAB代码
|
4月前
|
存储 算法 搜索推荐
【2022年华为杯数学建模】B题 方形件组批优化问题 方案及MATLAB代码实现
本文提供了2022年华为杯数学建模竞赛B题的详细方案和MATLAB代码实现,包括方形件组批优化问题和排样优化问题,以及相关数学模型的建立和求解方法。
131 3
【2022年华为杯数学建模】B题 方形件组批优化问题 方案及MATLAB代码实现
|
4月前
|
数据采集 存储 移动开发
【2023五一杯数学建模】 B题 快递需求分析问题 建模方案及MATLAB实现代码
本文介绍了2023年五一杯数学建模竞赛B题的解题方法,详细阐述了如何通过数学建模和MATLAB编程来分析快递需求、预测运输数量、优化运输成本,并估计固定和非固定需求,提供了完整的建模方案和代码实现。
95 0
【2023五一杯数学建模】 B题 快递需求分析问题 建模方案及MATLAB实现代码
|
7月前
|
数据安全/隐私保护
耐震时程曲线,matlab代码,自定义反应谱与地震波,优化源代码,地震波耐震时程曲线
地震波格式转换、时程转换、峰值调整、规范反应谱、计算反应谱、计算持时、生成人工波、时频域转换、数据滤波、基线校正、Arias截波、傅里叶变换、耐震时程曲线、脉冲波合成与提取、三联反应谱、地震动参数、延性反应谱、地震波缩尺、功率谱密度
基于混合整数规划的微网储能电池容量规划(matlab代码)
基于混合整数规划的微网储能电池容量规划(matlab代码)
|
7月前
|
算法 调度
含多微网租赁共享储能的配电网博弈优化调度(含matlab代码)
含多微网租赁共享储能的配电网博弈优化调度(含matlab代码)
|
7月前
|
Serverless
基于Logistic函数的负荷需求响应(matlab代码)
基于Logistic函数的负荷需求响应(matlab代码)
|
7月前
|
供应链 算法
基于分布式优化的多产消者非合作博弈能量共享(Matlab代码)
基于分布式优化的多产消者非合作博弈能量共享(Matlab代码)