【经典算法】有趣的算法之---蚁群算法梳理
every blog every motto: You can do more than you think.
0. 前言
蚁群算法记录
1. 简介
蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。经过20多年的发展,蚁群算法在理论以及应用研究上已经得到巨大的进步。
蚂蚁在寻找食物的过程中往往是随机选择路径的,但它们能感知当前地面上的信息素浓度,并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放,是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短,单位时间内经过该路径的蚂蚁多,所以信息素的积累速度比较长路径快。因此,当后续蚂蚁在路口时,就能感知先前蚂蚁留下的信息,并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发,最终所有的蚂蚁都在最优路径上行进。
2. TSP问题
蚁群算法最早用来求解TSP问题,并且表现出了很大的优越性,因为它分布式特性,鲁棒性强并且容易与其它算法结合,但是同时也存在这收敛速度慢,容易陷入局部最优(local optimal)等缺点。
TSP问题(Travel Salesperson Problem,即旅行商问题或者称为中国邮递员问题),是一种NP-hard问题,此类问题用一般的算法是很难得到最优解的,所以一般需要借助一些启发式算法求解,例如遗传算法(GA),蚁群算法(ACO),微粒群算法(PSO)等等。
TSP问题(旅行商问题)是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次 然后回到出发城市,并要求所走的路程最短。
由上述蚂蚁找食物模式演变来的算法,即是蚁群算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。
蚁群算法应用广泛,如旅行商问题(traveling salesman problem,简称TSP)、指派问题、Job-shop调度问题、车辆路径问题(vehicle routing problem)、图着色问题(graph coloring problem)和网络路由问题(network routing problem)等等。
3. 原理
设整个蚂蚁群体数量为m,城市数量为n,城市i和j之间的相互距离为 d i j d_{ij} dij,t时刻城市i与城市j路径上的信息浓度为 τ i j ( t ) \tau_{ij}(t) τij(t),初始时刻,各城市间连接路径上的信息浓度相同,不妨设 τ ( 0 ) = τ 0 \tau(0)=\tau_0 τ(0)=τ0
3.1 转移概率
蚂蚁k根据各城市间连接路径上的信息素浓度决定其下一个访问的城市,设 P i j k ( t ) P^k_{ij}(t) Pijk(t)表示t时刻蚂蚁k从城市i到城市j的概率,计算公式如下:
P i j k = { [ τ i j ] α ⋅ [ η i j ( t ) ] β ∑ s ∈ a l l o w k [ τ i s ( t ) ] β ⋅ [ η i s ( t ) ] β , s ∈ a l l o w k 0 , s ∉ a l l o w k \LARGE P^k_{ij}=\left\{ \begin{matrix} {\big [\tau_{ij}\big]^{\alpha} ·\big [\eta_{ij}(t)\big ]^{\beta} \over \sum\limits_{s \in allow_k}\big [\tau_{is}(t) \big ]^{\beta} · \big [\eta_{is}(t) \big]^{\beta}} &, s \in allow_k \\ 0 &, s \notin allow_k \end{matrix} \right. Pijk=⎩
相关文章:

【经典算法】有趣的算法之---蚁群算法梳理
every blog every motto: You can do more than you think. 0. 前言 蚁群算法记录 1. 简介 蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性…...

第八届视觉、图像与信号处理国际会议(ICVISP 2024) | Ei, Scopus双检索
会议简介 Brief Introduction 2024年第八届视觉、图像与信号处理国际会议(ICVISP 2024) 会议时间:2024年12月27日-29日 召开地点:中国西双版纳 大会官网:ICVISP 2024-2024 8th International Conference on Vision, Image and Signal Process…...

《HelloGitHub》第 93 期
兴趣是最好的老师,HelloGitHub 让你对编程感兴趣! 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等,涵盖多种编程语言 Python、Java、Go、C/C、Swift...让你在短时间内…...

JAVA B/S架构智慧工地源码,PC后台管理端、APP移动端
智慧工地系统充分利用计算机技术、互联网、物联网、云计算、大数据等新一代信息技术,以PC端,移动端,设备端三位一体的管控方式为企业现场工程管理提供了先进的技术手段。让劳务、设备、物料、安全、环境、能源、资料、计划、质量、视频监控等…...

【adb】--- win10 配置 adb环境 超详细 (持续更新中)
在编程的艺术世界里,代码和灵感需要寻找到最佳的交融点,才能打造出令人为之惊叹的作品。而在这座秋知叶i博客的殿堂里,我们将共同追寻这种完美结合,为未来的世界留下属于我们的独特印记。 【adb】--- win10 配置 adb环境 超详细 &…...
SQL注入安全漏洞详解
1. SQL注入的原理: SQL注入的攻击行为是通过用户可控参数中注入了SQL语法,改变原有SQL结构,以下两种情况可以造成SQL注入: 1.使用字符串拼接的方式构造SQL语句 2.未对用户可控参数进行严格的过滤,便把参数内容拼接到…...
数据结构与算法教程,数据结构C语言版教程!(第一部分、数据结构快速入门,数据结构基础详解)四
第一部分、数据结构快速入门,数据结构基础详解 数据结构基础,主要研究数据存储的方式。 本章作为数据结构的入门课程,主要让读者明白,数据结构到底是什么,常用的数据存储结构有哪些,数据结构和算法之间到底…...

mac安装k8s环境
安装kubectl brew install kubectl 确认一下安装的版本 kubectl version --client 如果想在本地运行kubernetes 需要安装minikube brew install minikube 需要注意安装minikube需要本地的docker服务是启动的 启动 默认连接的是google的仓库 minikube start 指定阿…...

HarmonyOS4.0系列——04、@Styles、@Extend、@Extend事件以及多态样式stateStyles
Styles、Extend、Extend事件以及多态样式stateStyles Styles 通用样式 类似于css中的class 语法一:内部样式 放在struct内 Styles commonStyle(){.backgroundColor(Color.Pink).padding(20px)}语法二:外部样式 Styles function commonStyle() {.backg…...
C++项目之酒店客房管理系统架构——设计模式应用场景详解(下)
5. 迭代器模式(Iterator Pattern):用于遍历客房列表。通过定义一个迭代器接口,可以遍历客房列表并访问每个客房的属性和状态。 代码中,Iterator是抽象迭代器,定义了迭代器的基本操作,包括判断是否还有下一项和获取下一项的方法。RoomIterator是具体迭代器,实现了具体的…...

RabbitMQ消息存储JSON格式反序列化
如果发送消息消息体为实体类对象数据,交换机接收消息经由路由键发送给队列。需要实现数据反序列化操作。实现JSON格式的反序列化操作 Rabbitmq的反序列化接口 MessageConverter,它的实现类有 Jackson2JsonMessageConverter的反序列化实现类,…...
Java解决统计有序矩阵中的负数问题
Java解决统计有序矩阵中的负数问题 01 题目 给你一个 m * n 的矩阵 grid,矩阵中的元素无论是按行还是按列,都以非递增顺序排列。 请你统计并返回 grid 中 负数 的数目。 示例 1: 输入:grid [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-…...

【算法与数据结构】435、LeetCode无重叠区间
文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析:思路和【算法与数据结构】452、LeetCode用最少数量的箭引爆气球类似,也是排序找重叠区间。…...
【开题报告】基于SpringBoot的茶文化宣传网站设计与实现
1.研究背景和意义 1.1研究背景 茶文化是中国传统文化的重要组成部分,具有悠久的历史和丰富的内涵。茶文化不仅是一种饮食文化,更是一种生活方式和精神追求。然而,在当今快节奏的生活中,茶文化逐渐被人们所忽视。为了加强对茶文化…...

用通俗易懂的方式讲解大模型:基于 Langchain 和 ChatChat 部署本地知识库问答系统
之前写了一篇文章介绍基于 LangChain 和 ChatGLM 打造自有知识库问答系统,最近该项目更新了0.2新版本,这个版本与之前的版本差别很大,底层的架构发生了很大的变化。 该项目最早是基于 ChatGLM 这个 LLM(大语言模型)来…...

YOLO训练results.csv文件可视化(原模型与改进模型对比可视化)
一、单独一个文件可视化(源码对应utils文件夹下的plots.py文件的plot_results类) from pathlib import Path import matplotlib.pyplot as plt import pandas as pd def plot_results(fileruns/train/exp9/results.csv, dir):# Plot training results.c…...

uni-appcss语法
锋哥原创的uni-app视频教程: 2023版uniapp从入门到上天视频教程(Java后端无废话版),火爆更新中..._哔哩哔哩_bilibili2023版uniapp从入门到上天视频教程(Java后端无废话版),火爆更新中...共计23条视频,包括:第1讲 uni…...

java在线票务系统(选座)Myeclipse开发mysql数据库web结构java编程计算机网页项目
一、源码特点 java servlet 在线票务系统(选座)管理系统是一套完善的java web信息管理系统 系统采用serlvetdaobean(mvc模式),对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要…...

Python 简易图形界面库easygui 对话框大全(续)
目录 EasyGUI库 主要特点 使用场景 对话框样式 10. 文件打开框 fileopenbox 11. 文件保存框 filesavebox 12. 目录打开框 diropenbox 13. 索引对话框 indexbox 14. 例外报告框 exceptionbox 15. 代码文本框 codebox 16. 密码输入框 passwordbox 17. 多重文本框 mul…...

电容器50ZLH56MEFC6.3X11
电容器 常用电子元器件类型 50ZLH56MEFC6.3X11 文章目录 电容器前言一、电容器二、50ZLH56MEFC6.3X11总结前言 电容器在电子电路中有许多重要的应用,如滤波、耦合、储能、定时等。不同类型的电容器具有不同的性能特点,例如电容量、工作电压、频率响应等。在选择和使用电容…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...

python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...

倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
Python的__call__ 方法
在 Python 中,__call__ 是一个特殊的魔术方法(magic method),它允许一个类的实例像函数一样被调用。当你在一个对象后面加上 () 并执行时(例如 obj()),Python 会自动调用该对象的 __call__ 方法…...

运行vue项目报错 errors and 0 warnings potentially fixable with the `--fix` option.
报错 找到package.json文件 找到这个修改成 "lint": "eslint --fix --ext .js,.vue src" 为elsint有配置结尾换行符,最后运行:npm run lint --fix...
Electron简介(附电子书学习资料)
一、什么是Electron? Electron 是一个由 GitHub 开发的 开源框架,允许开发者使用 Web技术(HTML、CSS、JavaScript) 构建跨平台的桌面应用程序(Windows、macOS、Linux)。它将 Chromium浏览器内核 和 Node.j…...