【经典算法】有趣的算法之---蚁群算法梳理
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总结前言 电容器在电子电路中有许多重要的应用,如滤波、耦合、储能、定时等。不同类型的电容器具有不同的性能特点,例如电容量、工作电压、频率响应等。在选择和使用电容…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...

练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...