位置: IT常识 - 正文

蚁群算法详解-解决TSP问题(蚁群算法是什么)

编辑:rootadmin
蚁群算法详解-解决TSP问题 文章目录前言一、蚁群算法是什么?算法步骤二、基本原理三、数学模型1、算法中的参数设置2、构建路径轮盘赌例子3、更新信息素浓度代码终止四、代码展示五、参数实际设定1.参数设定的准则2.蚂蚁数量3.信息素因子4.启发函数因子5.信息素挥发因子6. 最大迭代次数7. 组合参数设计策略总结前言

推荐整理分享蚁群算法详解-解决TSP问题(蚁群算法是什么),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:蚁群算法动画演示,蚁群算法详解,蚁群算法简介,蚁群算法简介,蚁群算法详解pdf,蚁群算法详解,蚁群算法详解pdf,蚁群算法详解pdf,内容如对您有帮助,希望把文章链接给更多的朋友!

科研项目中要遇到蚁群 遗传 协同进化 粒子群等一些系列非确定性算法 所以总结一篇自己的学习笔记

一、蚁群算法是什么?

蚁群算法是模仿蚁群的寻食行为,在所有路径中,蚂蚁会随机挑选一个路径前进,等所有路径走完后会留下信息素,随着蚂蚁的增多,信息素的浓度与蚂蚁的数量和路径的长短成正比,蚂蚁更倾向于最短路径前进,此算法具有好的正反馈机制和自组织性。由原理描述可以看出良好的正反馈机制只限于后期,前期由于信息缺乏影响反馈机制的速度。

算法步骤

1、初始化(各个参数): 在计算之初需要对相关的参数进行初始化,如蚂蚁数量m、信息素因子α、启发函数因子β、信息素挥发因子ρ、信息素常数Q、最大迭代次数t等等。

2、构建解空间: 将各个蚂蚁随机地放置于不同的出发点,对每个蚂蚁k(k=1,2,……,m),计算其下一个待访问的城市,直到所有蚂蚁访问完所有的城市。

3、更新信息素: 计算各个蚂蚁经过的路径长度L,记录当前迭代次数中的最优解(最短路径)。同时,对各个城市连接路径上的信息素浓度进行更新。

4、判断是否终止: 若迭代次数小于最大迭代次数则迭代次数加一,清空蚂蚁经过路径的记录表,并返回步骤二;否则终止计算,输出最优解。

二、基本原理

根据信息素来进行判断 蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理,蚂蚁在寻找食物源时,能在其走过的路径上释放一种蚂蚁特有的分泌物–信息素,使得一定范围内的其他蚂蚁能够察觉到并由此影响他们以后的行为。**当一些路径上通过的蚂蚁越来越多时,其留下的信息素也越来越多,以致信息素强度增大,所以蚂蚁选择选该路径的概率也越高,从而更增加了该路径的信息素强度,这种选择过程被称为蚂蚁的自催化行为。**由于其原理是一种正反馈机制,因此,也可将蚂蚁王国理解为所谓的增强型学习系统。

三、数学模型1、算法中的参数设置

2、构建路径

我们知道蚂蚁是根据信息素的浓度来判断所走的路线的,但是事实上,不是说哪条路的信息素浓度高蚂蚁就一定走哪条路,而是走信息素浓度高的路线的概率比较高。那么首先我们就需要知道蚂蚁选择走每个城市的概率,然后通过轮盘赌法(相当于转盘)确定蚂蚁所选择的城市。

轮盘赌

轮盘赌算法来自轮盘赌

某个概率 = 某个因子 除以 所有因子之和 比如一等奖的因子是10,所有因子之和是 100,则一等奖的概率是 10% 学会了轮盘赌算法,让我们回到蚁群算法。 那么现在我们的目标是计算出蚂蚁去下个目的地的因子。因为蚂蚁走过的路上会留下信息素,信息素越高,选择这条路的概率越高,所以假定 因子 = 信息素。在这里,信息素就是一种变量,会在后续的反向传播环节中进行校准。 但是这样会带来一个问题,当第一次迭代完成后,走过的路上留下了信息素,没走过的路上没有信息素,导致之后的蚂蚁会更偏向于之前已经走过的路,而之前已经走过的路不一定是最优路线。 因此我们需要给因子再加一个参数,因为我们的问题是求最短路径,所以我们把两点之间的距离引入进来。从贪心的角度来说,两点之间距离越短,则选择这条路线的概率越大,所以我们乘上距离的倒数。 现在,因子 = 信息素 X (距离的倒数) 因子在受到多个参数影响后,我们希望能够调整各个参数的权重,在之前的人工神经网络中,我们是通过乘法的形式把权重和参数结合,即: 但是在这里我们已经使用了乘法,所以在处理权重时,我们可以使用指数,即: 因子信息素距离 这边使用 alpha 和 beta 分别代表 信息素 和 距离 的权重,这两个值属于常量,调参时可以灵活调整。 在求得每段路程的因子之后,每只蚂蚁使用轮盘赌算法去选择它要去的下个节点,遍历的时候顺便计算走过的路程,毕竟我们要求的就是最短路径。

蚁群算法详解-解决TSP问题(蚁群算法是什么)

蚂蚁k 从i到j的概率公式如下

距离的倒数 蚂蚁选择城市的概率主要由𝜏ij (t)和𝜂ij (𝑡)有关,分母为蚂蚁k可能访问的城市之和(为常数),这样才能使蚂蚁选择各个城市的概率之后为1,符合概率的定义。𝜏ij (t)和𝜂ij (𝑡)上的指数信息素因子ɑ和启发函数因子𝛽只决定了信息素浓度以及启发函数对蚂蚁k从i到j的可能性的贡献程度。

例子

3、更新信息素浓度

根据不同的规则我们可以将蚁群算法分为三种模型——蚁周模型(Ant-Cycle)、蚁量模型(Ant-Quantity)和蚁密模型(Ant-Density)。蚁周模型是完成一次路径循环后,蚂蚁才释放信息素,其利用的是全局信息。蚁量模型和蚁密模型蚂蚁完成一步后就更新路径上的信息素,其利用的是局部信息。本文章使用的是最常见的蚁周模型。 其中Q为信息素常量,Lk表示第k只蚂蚁在本次循环中所走路径的长度。 例:下图为信息素的更新过程,假设初始时各路径信息素浓度为10。

代码终止

蚁群算法中的终止条件:是否达到迭代次数。 一次迭代就是指m只蚂蚁都走完所有的城市,即存在m个搜索路径。 将所有路径进行比较,选择长度最短的路径,做出这一次迭代的可视化结果,更新信息素。并将当前的最短路径与过往的最短路径长度进行对比,同时迭代次数加1。 然后判断当前迭代次数是否等于设置的迭代次数。如果等于则停止迭代,否则进行下一次迭代。

四、代码展示

matlab 代码参考

五、参数实际设定1.参数设定的准则

尽可能在全局上搜索最优解,保证解得最有型 算法尽快手链,以节省寻优时间 尽量反映客观存在的规律,以保证这种仿生算法的真实性

2.蚂蚁数量

一般设置蚂蚁数量为城市数的1.5倍比较稳妥

3.信息素因子

信息素因素a反映蚂蚁在运动过程中所积累的信息量在知道蚁群搜索中的相对重要程度。当a∈[1,4]时,综合求解性能较好

4.启发函数因子

启发函数因子b,反映了启发式信息在知道蚁群搜索过程中的相对重要程度,其大小反映了蚁群巡游过程中小言行、确定性因素的作用强度。b过大是,蚂蚁在某个局部点上选择局优的可能性大。b∈[3,4.5],综合求解性能较好。

5.信息素挥发因子

信息素挥发因子ρ描述信息素的消失水平,而1-ρ则为信息素残留因子。ρ∈[0.2,0.5]时,综合求解能力较好

6. 最大迭代次数

一般去100-500

7. 组合参数设计策略

可按照一下策略来进行参数的组合设计:

确定蚂蚁数目,蚂蚁数目与城市规模之比约为1。5 参数粗调,即调整取值范围较大的a,b以及Q 参数微调,即调整取值范围较小的ρ

总结

蚁群算法有一下特点:

1、从算法的性质而言,蚁群算法是在寻找一个比较好的局部最优解,而不是强调全局最优解 2、开始时算法收敛速度较快,在随后寻优过程中,迭代一定次数后,容易出现停滞现象 3、蚁群算法对TSP及相似问题具有良好的适应性,无论城市规模大还是小,都能进行有效地求解,而且求解速度相对较快 4、蚁群算法解得稳定性较差,及时参数不变,每次执行程序都有可能得到不同界,为此需要多执行几次,已寻找最佳解。 5、蚁群算法中有多个需要设定的参数,而且这些参数对程序又都有一定的影响,所以选择合适的参数组合在算法设计过程中也非常重要。

本文链接地址:https://www.jiuchutong.com/zhishi/297704.html 转载请保留说明!

上一篇:YOLOv5-v6.0学习笔记(yolov5m)

下一篇:ChatGPT角色扮演(【角色扮演】)

  • 苹果怎么给app悬浮窗权限(苹果怎么给app悬浮窗设置)

    苹果怎么给app悬浮窗权限(苹果怎么给app悬浮窗设置)

  • 小米怎么在屏幕调音量(小米怎么在屏幕添加锁屏按键)

    小米怎么在屏幕调音量(小米怎么在屏幕添加锁屏按键)

  • 苹果13什么时候开售(苹果13什么时候发售的)

    苹果13什么时候开售(苹果13什么时候发售的)

  • 电脑桌面文件变大怎么调小(电脑桌面文件变大怎么缩小)

    电脑桌面文件变大怎么调小(电脑桌面文件变大怎么缩小)

  • 微信来源朋友验证消息是从哪里加的(微信来源朋友验证消息是通过什么方式添加的)

    微信来源朋友验证消息是从哪里加的(微信来源朋友验证消息是通过什么方式添加的)

  • 视频帧数怎么调节(视频怎么调画质)

    视频帧数怎么调节(视频怎么调画质)

  • 华为手机怎么弄水印在图片上(华为手机怎么弄出来下边的三个键)

    华为手机怎么弄水印在图片上(华为手机怎么弄出来下边的三个键)

  • fosc是什么频率(fp是什么频率)

    fosc是什么频率(fp是什么频率)

  • 闲鱼上的苹果手机为什么这么便宜(闲鱼上的苹果手机可靠吗)

    闲鱼上的苹果手机为什么这么便宜(闲鱼上的苹果手机可靠吗)

  • 华为nova7怎么调出返回键(华为nova7怎么调时间)

    华为nova7怎么调出返回键(华为nova7怎么调时间)

  • se2无线充电吗(se2无线充电功能)

    se2无线充电吗(se2无线充电功能)

  • 苹果手机主板坏了有必要修吗(苹果手机主板坏了修好了影响使用吗)

    苹果手机主板坏了有必要修吗(苹果手机主板坏了修好了影响使用吗)

  • 单元格设置的基本用途(单元格设置的基本功能)

    单元格设置的基本用途(单元格设置的基本功能)

  • 苹果ios11怎么打开悬浮球(iphone11怎么打特殊符号)

    苹果ios11怎么打开悬浮球(iphone11怎么打特殊符号)

  • 鼠标左边2个键什么用(鼠标左边的2个键有什么作用)

    鼠标左边2个键什么用(鼠标左边的2个键有什么作用)

  • 苹果7plus多重(iphone 7plus重量多少克)

    苹果7plus多重(iphone 7plus重量多少克)

  • 优酷视频可以同时几个人用

    优酷视频可以同时几个人用

  • 魅族怎么样解除root(魅族手机如何解除手机锁定)

    魅族怎么样解除root(魅族手机如何解除手机锁定)

  • 手机摔的开不了机怎么办(手机摔的开不了机了怎么取出数据)

    手机摔的开不了机怎么办(手机摔的开不了机了怎么取出数据)

  • vue视频怎么连续字幕(vue怎么做长视频)

    vue视频怎么连续字幕(vue怎么做长视频)

  • 小米ai音响能不能改昵称(小米ai音响使用技巧)

    小米ai音响能不能改昵称(小米ai音响使用技巧)

  • 快手怎么换播放模式(怎么把快手播放方式换成抖音那样)

    快手怎么换播放模式(怎么把快手播放方式换成抖音那样)

  • a1502是第几年的款(a1502 2015)

    a1502是第几年的款(a1502 2015)

  • 锤子手机开机键在哪(锤子手机开机键失灵修复小技巧)

    锤子手机开机键在哪(锤子手机开机键失灵修复小技巧)

  • ipad顶部怎么显示网速(ipad顶部按钮怎么设置)

    ipad顶部怎么显示网速(ipad顶部按钮怎么设置)

  • windows IIS部署Web网页(iis部署javaweb)

    windows IIS部署Web网页(iis部署javaweb)

  • c语言中fgetc函数的介绍(c语言fgets函数用法stdin)

    c语言中fgetc函数的介绍(c语言fgets函数用法stdin)

  • 纳税人识别号在哪里能查到
  • 增值税纳税义务发生地点的规定
  • 一次性扣除固定资产政策案例
  • 租赁厂房对方不租怎么办
  • 电子汇票提示付款撤销
  • 无形资产登记什么明细账
  • 财务记账之后是否必须审核
  • 房地产企业增值税纳税义务发生时间
  • 研究开发费用加计扣除多少
  • 奖金做预发年底结算缴税怎么做?
  • 预收账款在什么科目核算
  • 公司开给个人的发票有什么用
  • 纳税义务发生时间和纳税期限的关系
  • 长期挂账的其他应收款如何处理
  • 折价股权转让账务处理
  • 外包劳务费用如何计算
  • 17税率改16税率的时间
  • 一万元国债一年多少利息
  • 补缴以前年度税款
  • 暂估成本的会计处理
  • 怎么修改以前年度的账
  • mac如何修改
  • 如何重装系统win7旗舰版
  • win10电脑电源选项怎样设置最好
  • 税收返还会计核算
  • 监狱劳教企业是国企吗
  • phpstrcmp函数
  • 工资薪金所得申报流程
  • html中display none
  • 所有非批扣和所有批扣是什么意思
  • 附加税退税申请理由模板
  • thinkphpcount查询
  • linux suid
  • 深度学习的通道到底是什么?有什么用?(小白可看)
  • phpcms rce
  • 如何在国家税务局增值税纳税申报
  • 税务局规定多久开发票
  • 印花税的征税范围及税率
  • 增值税专用发票丢了怎么补救
  • 5年前开的发票退货可以冲红吗?
  • sse后端向前端推送 前端只能收到 末尾的值
  • 最好最实用的织毛线
  • 固定资产分期付款会计处理?
  • 酒店客房成本计算公式
  • 待抵扣进项税额转出会计分录
  • 固定资产转换为投资性房地产转换日
  • 出口退税账务处理难吗
  • 委托加工如何做会计处理
  • 事业单位开办费与注册资本的关系
  • 海关对旧设备进口规定
  • 费用票可以抵扣多少企业所得税
  • 计提坏账准备不属于企业的或有事项
  • 货运代理服务开票
  • 购进销售产品的会计分录
  • 应收账款坏账准备借贷方向
  • 商业企业可将商品分为哪三类
  • win10exe文件关联修复
  • linux下xhost命令报错:unable to open display的解决办法
  • ubuntu虚拟机apt安装tools
  • centos7(core)
  • 安装centos图形界面
  • ctrl+的作用
  • 如何用dos破解wifi
  • win8笔记本无法更新正在撤销更改
  • 腙基是什么
  • macos安装过程
  • androidstudio手机编程软件
  • Node.js中的construct
  • 批处理脚本怎么写
  • angular scope
  • node.js详解
  • pygame 安装
  • Zero Clipboard js+swf实现的复制功能使用方法
  • jquery操作select元素和option的实例代码
  • jquery过滤选择器案例
  • jquery给输入框赋值
  • js跨域访问页面控件
  • 现行的企业所得税率是多少
  • 香港pcc价格
  • 代理记账公司成本怎样结转的
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设