MATLAB实现蚁群算法栅格路径优化

news/2024/9/23 3:09:44/

蚁群算法是一种模拟自然界中蚂蚁觅食行为的优化算法,常用于解决路径规划问题。在栅格路径优化中,蚁群算法可以帮助找到从起点到终点的最优路径。以下是蚁群算法栅格路径优化的基本流程步骤:

  1. 初始化参数

    (1)设置蚂蚁数量(popsize)、信息素挥发系数(ρ)、信息素增强系数(Q)、最大迭代次数、信息素重要程度因子(α)、启发函数重要程度因子(β)。
    (2)初始化信息素矩阵,设置为一个相同的较小正值,避让0.01。
    (3)定义栅格地图,包括障碍物、可行走区域等。
  2. 蚂蚁路径选择

    (1)每只蚂蚁从起点开始,根据转移概率公式选择下一个要移动的栅格。转移概率基于当前栅格与相邻栅格之间的信息素浓度和启发式信息,表达式如下:

    (1)式表示蚂蚁在t时刻由城市i选择城市j的概率。α是信息素在概率计算中的权重,它的值越大,信息素在蚂蚁选择下一个要到的城市中起到的作用越大。β是启发因子(在路径问题中常以d的倒数来表示)在概率计算中所占的权重,它的值越大,启发因子在蚂蚁选择城市的过程中所起的作用越大,allowed是不在蚂蚁禁忌表中的城市集合(在栅格问题中就是非障碍物和未走过的栅格的节点编号集)。

    (2)更新所选路径上的信息素浓度,通常包括信息素的挥发和增加:

    \tau_{ij}(t+1)=\rho\tau_{ij}(t)+\Delta \tau_{ij}(t,t+1)
    其中\tau_{ij}(t+1)表示在t+1次迭代时边ij上的信息素. ρ是信息素维持因子, 1-ρ是信息素挥发因子.\Delta \tau_{ij}(t,t+1)是所有蚂蚁在边ij上所释放的信息素的总和:\Delta\tau_{ij}(t,t+1)=\sum_{k=1}^{m}\Delta\tau_{ij}^{k}(t,t+1)

  3. 计算路径长度

    当所有蚂蚁都完成一次路径搜索后,计算每只蚂蚁所走路径的总长度。
  4. 更新信息素

    根据每只蚂蚁的路径长度和设定的规则,更新栅格地图上的信息素浓度。优质路径上的信息素会得到增强,而劣质路径上的信息素会逐渐挥发减少。
     
  5. 迭代优化

    重复步骤2至4,进行多次迭代,直到达到最大迭代次数或满足其他停止条件。
  6. 选择最优路径

    在所有蚂蚁走过的路径中,选择长度最短(或成本最低)的路径作为最优路径。
  7. 输出结果

    输出最优路径及其长度。

流程图如下:

算法的关键在于邻近节点集的概念和数据设计

首先对整个场景进行栅格化, 并依次编号,如下表所示

7

8

9

4

5

6

1

2

3

然后构造一个cell变量nearcell或者一个邻接指示矩阵E

nearcell{1,1}=[2,4,5];

nearcell{2,1}=[1,3,4,5,6];

nearcell{3,1}=[2,5,6];

对于每一个i都有nearcell{i,1}=nearmat

nearmat是与节点i相邻的节点编号集合, 当然这个不能人工一个一个设定, 必须采用代码来自动设定, 根据栅格的特点, 我们可以用代码实现 ,其原理为:
对于任何一个栅格中的节点(如节点5),其周边有8个邻近节点(如果是在边界,则代码在后面进行了边界约束),其行号和列号与节点的行列号是有规律的,因此可以采用代码进行设置。具体实现如nearfun函数所示。

有了nearcell,那么就可以很简单的使用蚁群算法进行路径规划了,当然有可能走死胡同,这个就必须再设计一个回滚函数,走了死胡同就回滚。

部分MATLAB主程序如下:


clc;close all;clear all;warning off;%清除变量
rand('seed', 100);
randn('seed', 100);
format long g;xmin=0;
xmax=100;
ymin=0;
ymax=100;nx=10;% 划分数
ny=10;% 划分数
dx=(xmax-xmin)/nx;
dy=(ymax-ymin)/ny;
[nodetable,XY,nodnumber]=nodetabelfun(nx,ny,dx,dy);% 计算节点表格
XY(:,1)=XY(:,1)+xmin;
XY(:,2)=XY(:,2)+ymin;
gamma=0.2;
bocktable=bocktablefun(nodnumber,gamma);nodeset= find(bocktable==1);
title1='栅格模型';
drawshelf(XY,dx,dy,nodeset,title1);% 绘图[neartable,E,G]=nearfun(nodetable,nodnumber,nx,ny,bocktable);% 计算节点邻接表格nodenumber=size(XY,1);
dmat=distancetable(XY,E);
startnodeID=1;% 起点
targetnodeID=20;% 终点maxgen=50;% 迭代次数
popsize=10;  % 蚂蚁数量alpha=2; % 信息素重要程度因子
beta=3; % 启发函数重要程度因子
rho=0.1; % 信息素挥发因子
Q=1;tic;
Eta=0.01*ones(nodenumber,nodenumber);
tocL=length(targetnodeID);
Ttable02=topo_table(E);tracemat=zeros(maxgen,2);
Tau = ones(nodenumber,nodenumber);  % 信息素矩阵初始化
gen = 1;                            % 迭代次数初值tic;
wait_hand = waitbar(0,'running...', 'tag', 'TMWWaitbar');
while gen<=maxgen% 多次循环ACOChrom=zeros(popsize,nodenumber);for i=1:popsize% 每个蚂蚁循环Ttable01=Ttable02;route=startnodeID;state=1;number_dem=targetnodeID;while state~=0curr_node=route(end);curr_topolopy=Ttable01(curr_node).topolopy;n=length(route);for k=1:nendP=P/sum(P);Pc=cumsum(P);target_index=find(Pc >= rand);next_node=curr_topolopy(target_index(1));route=[route next_node];else[state,route,Ttable01]=getroutefun(route,Ttable01,state,curr_node);endif route(end)==number_demstate=0;endendL1=length(route);ACOChrom(i,1:L1)=route;endcost= decodingFun(ACOChrom,popsize,dmat);% 计算目标函数[costu,inputps]=mapminmax(cost',100,200);costu=costu';% 记录结果[v1,index1]=min(cost);if gen==1bestlong001=v1;bestroute=ACOChrom(index1,:);endif bestlong001>v1;bestlong001=v1;bestroute=ACOChrom(index1,:);endtracemat(gen,1)=bestlong001;tracemat(gen,2)=mean(cost);Tau=updatetaufun(rho,Q,nodenumber,popsize,ACOChrom,costu,Tau);% 更新信息素gen=gen+1;waitbar(gen/maxgen,wait_hand);
end
delete(wait_hand);
toc% 输出结果
disp('蚁群算法得到的最优路径');
bestroute=bestroute(bestroute>0)% 绘图
title1='蚁群算法得到的路径';
startnodeID=bestroute;
drawshelf2(XY,dx,dy,nodeset,startnodeID,title1)figure;
plot(tracemat(:,1),'r-','linewidth',1);
legend({'最优值'},'fontname','宋体');
xlabel('迭代次数','fontname','宋体');
ylabel('目标函数','fontname','宋体');
title('蚁群算法迭代曲线','fontname','宋体');

程序结果:

时间已过 0.000757 秒。
时间已过 3.196282 秒。
蚁群算法得到的最优路径

bestroute =

     1    11    22    13     4     5     6     7     8    19    20

>> 


http://www.ppmy.cn/news/1435906.html

相关文章

常用的MQ有哪些?

1. 背景 最近有新同事接触了项目中使用的RocketMQ&#xff0c;问了一个问题&#xff1a;MQ有哪几种&#xff1f;基于此&#xff0c;本文介绍一下目前市面上常用的消息队列&#xff08;MQ&#xff09;有哪些。 2. 五种主流消息队列&#xff08;MQ&#xff09; 2.1 RocketMQ …

Ansible 中的copy 复制模块应用详解

作者主页&#xff1a;点击&#xff01; Ansible专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月25日13点40分 Ansible 中的 copy 模块用于将文件或目录从本地计算机或远程主机复制到远程主机上的特定位置。它是一个功能强大的模块&#xff0c;可用于各种文…

【C++】从零开始认识泛型编程 — 模版

送给大家一句话&#xff1a; 尽管眼下十分艰难&#xff0c;可日后这段经历说不定就会开花结果。总有一天我们都会成为别人的回忆&#xff0c;所以尽力让它美好吧。 – 岩井俊二 &#xff3c;&#xff3c;\ ⱶ˝୧(๑ ⁼̴̀ᐜ⁼̴́๑)૭兯 //&#xff0f;&#xff0f; &#…

获取公募基金持仓【数据分析系列博文】

摘要 从指定网址获取公募基金持仓数据&#xff0c;快速解析并存储数据。 &#xff08;该博文针对自由学习者获取数据&#xff1b;而在投顾、基金、证券等公司&#xff0c;通常有Wind、聚源、通联等厂商采购的数据&#xff09; 1. 导入必要的库&#xff1a; pandas 用于数据处理…

rust - 捕获全局panic并记录进程退出日志

本文提供了捕获全局panic并记录进程退出日志的方法。 1. 使用 panic::set_hook 注册异常处理 use human_panic::setup_panic; use log::error; use std::{boxed::Box, panic};fn hook(panic_info: &panic::PanicInfo) {if cfg!(debug_assertions) {let err_message form…

vulfocus靶场redis 未授权访问漏洞之CNVD-2015-07557

目标系统的权限不够redis用户无法写计划任务和公钥&#xff0c;而且也没有开放ssh端口。 主从复制getshell&#xff0c;写入恶意的so文件达到执行系统命令的目的。 github上有一键可以利用的脚本 https://github.com/n0b0dyCN/redis-rogue-server.git 利用条件&#xff1a;需…

Linux Shell字符串截取#与%使用

背景Jenkins需要解析gerrit的commit message中特殊字段的值&#xff0c;比如Depend-On&#xff1a;字段的值 比如commit msg内容如下&#xff1a;用变量msg表示 1. # 号截取, 截取指定字符保留右边的字符串&#xff0c;删除左边的部分。分为#和##两种 1.1 # 号截取&#xff0c…

AI雷达智能名片小程序源码系统 销售名片+企业商城+公司动态 带安装代码包以及安装部署教程

数字化时代的快速发展&#xff0c;小程序已经成为了企业展示自身形象、推广产品和服务的重要工具。其中&#xff0c;AI雷达智能名片小程序源码系统以其强大的功能和灵活的定制性受到了广大企业的青睐。该系统集销售名片、企业商城、公司动态等功能于一体&#xff0c;不仅提升了…