首页 > 其他分享 >人工智能基础笔记 · Part C 群体智能和强化学习

人工智能基础笔记 · Part C 群体智能和强化学习

时间:2023-12-09 11:33:05浏览次数:32  
标签:蚂蚁 人工智能 路径 通信 信息 个体 Part Agents 笔记

C6 群体智能

核心思路 :大自然中的一些社会系统尽管由简单的个体组成,却表现出智能的集体行为。称 Agents 为“智能体”。

对问题的智能解决方案,自然地涌现于这些个体的自组织交流之中。整个系统的行为是自下而上的,遵循简单规则的简单 Agents 生成复杂的结构/行为,且 Agents 不遵循某个领导者的命令。

通信特征:不能全局交换信息,只能局部交换信息。

基本概念

Boid Rules

  • 分离(Separation)

    • 避免与邻近同伴太接近。这条规则使得每个个体避免与附近的其他个体碰撞,维持一定的距离。
  • 对齐(Alignment):

    • 与邻近同伴保持相同的移动方向。个体会调整自己的方向和速度,以匹配周围个体的平均方向和速度。
  • 聚集(Cohesion):

    • 向邻近同伴的平均位置移动。这使得个体趋向于向群体的中心移动,促进群体的聚集。

基本构成

  • Agents 智能体

    • Interact with the world and with each other (either directly or indirectly)
  • Simple behaviours 简单的行为

    • e.g. ants, termites, bees, wasps
  • Communication 通信

    • How agents interact with each other. e.g. pheromones of ants

总结来看,个体 Agents 的简单行为 + Agents 群体之间的通信 = 群体 Agents 的复杂涌现行为。

基本特点

  • 分布式,没有中央控制或数据源 Distributed, no central control or data source。

  • 有限的通信。Limited communication。

  • 没有(显式的)环境模型。No (explicit) model of the environment。

  • 对环境存在感知。Perception of environment (sensing)。

  • 对环境变化做出反应的能力。Ability to react to environment changes。

往往采取如下思路来抽象出一种算法来:

通信 Communication

基本的通信思路

  • 计算机通信

在计算机科学中,通信可以通过共享内存或消息传递来实现。共享内存涉及多个处理单元共享相同的内存空间,而消息传递则涉及通过发送和接收消息进行通信。

  • 群体智能中的通信

在群体智能系统中,通信不仅仅是简单的信息传递,而是意味着相互作用。环境提供了一个计算基础设施,其中 Agents 之间发生相互作用。这个基础设施包括 Agents 之间通信的协议以及 Agents 相互作用的协议。

  • 低级通信

涉及简单信号和痕迹的传递,通常是一些基本的信息传递形式。

  • 高级通信

涉及认知 Agents ,通常被视为有意图的系统,更复杂,更灵活。

  • 直接通信 vs. 间接通信

直接通信是指 Agents 之间直接的信息传递,而间接通信可能涉及其他媒介或者通过环境中介来实现。

间接通信

类似 Share Memory 的形式。个体的消息均发送到 Blackboard。

直接通信

这一部分需要做到一个 Actor Language,每个 Actor 接收到一个消息后会做一系列动作。

Speech Acts

言语行为有三个方面:

  • Locution(言词)= 说话者的物理表达。

  • Illocution(言外之意)= 说话者的意图含义(履行性的)。

  • Prelocution(言后之果)= 由言词引起的动作。

也有不少模型在研究这个问题。shared languages,有 KIF, KQML, DAML。service models 的 DAML-S 等。

蚁群算法 ACO

Ant Colony Optimization。基于间接通信和信息素。

简单来说,一只孤立的蚂蚁会随机移动,但当它发现信息素踪迹时,这只蚂蚁很可能会决定跟随该踪迹。这个概率取决于信息素的浓度。

同时,一只寻找食物的蚂蚁会在其路线上沉积信息素。当它找到食物来源(目标)时,它会返回巢穴以加强其踪迹。因此,其他蚂蚁更有可能开始追踪这条踪迹,从而在其上释放更多的信息素。蚂蚁在每条走过的路径上都会留下信息素。如果一条路径比另一条短,那么蚂蚁会更快地在这条路径上往返,并且因此在较短的时间内留下更多的信息素。

这个过程就像一个正反馈循环系统,因为路径上的信息素强度越高,蚂蚁开始穿过它的可能性就越高。

解决 TSP 问题

设第 \(k\) 只蚂蚁在 \(t\) 时刻位于点 \(i\) 上,那么它会等概率地向邻居走:

\[\begin{aligned} p_{i j}^k(t)& = \begin{cases}\frac{\left[\tau_{i j}(t)\right]^\alpha\left[\eta_{i j}(t)\right]^\beta}{\sum_{l \in N_i^k(t)}\left[\tau_{i l}(t)\right]^\alpha\left[\eta_{i l}(t)\right]^\beta}, & j \in N_i^k(t) \\ 0, & j \notin N_i^k(t)\end{cases}\\ \tau_{i j}(t+1)& =(1-\rho) \cdot \tau_{i j}(t)+\Delta \tau_{i j}(t) \\ \Delta \tau_{i j}(t)& =\sum_{k=1}^m \Delta \tau_{i j}^k(t) \\ \Delta \tau_{i j}^k(t)& = \begin{cases}Q / L^k, \text { 第 } k \text { 只蚂蚁在本次遍历中经过路径 } c_i-c_j \\ 0, \text { 其他 }\end{cases} \end{aligned} \]

其中 Q 是信息素总量,L 是总的路径的长度。这个的意思是,我们每次加信息素是以路径为单位加的(从起点回到起点,TSP)。

另外,\(\tau_{ij}\) 是 \(i \to j\) 这条边的信息素,\(\eta_{i j}\) 可以是边权也可以是某种启发式的长度,\(p_{ij}\) 是走 \(i\to j\) 的概率,上角标 \(k\) 表示第 \(k\) 只蚂蚁,\(N_i\) 是 \(i\) 的邻居集合。

大概就这样:

解决 JSSP 问题

Btw,蚁群算法也可以来解决 Job Shop Scheduling (JSSP),即作业车间调度问题。

转化成图问题即可:

这样一来就还是 TSP 问题了。

一些扩展

接下来是一些基于启发式思路的优化。

1. Elitist Strategy for Ant Systems (EAS)

EAS 特别强调了最佳解决方案的重要性。在EAS中,不仅是所有蚂蚁在其路径上留下信息素,而且历史上找到的最佳路径会获得额外的信息素强化。这意味着最佳路径上的信息素浓度会比其他路径更高,从而更有可能被后续的蚂蚁选择。

特点:

  • 强化历史最佳路径。

  • 加速向最优解的收敛。

  • 增加了算法对于最佳解的搜索强度。

2. Rank-based Ant System (ASRank)

ASRank 根据蚂蚁找到的路径质量对蚂蚁进行排名。在这个系统中,只有排名靠前的蚂蚁(例如,最好的几条路径)被允许在其路径上留下信息素。这样,信息素的更新更加集中于高质量的解决方案。

特点:

  • 排名制度减少了信息素的过度分散。

  • 专注于更有效的路径。

  • 提高了算法的收敛速度和解决方案的质量。

3. MAX-MIN Ant System (MMAS)

MMAS 是一种特别设计来避免过早收敛和探索解空间边界的 ACO 方法。因为 ACO 本身追求快速收敛。在 MMAS 中,信息素的浓度被限制在一个最大值和一个最小值之间。这种限制防止了任何一条路径变得过于“显著”,从而保持了算法的探索能力。相当于是有上下界的蚁群算法。

特点:

  • 信息素浓度有上下限制。

  • 避免过早收敛和探索的不足。

  • 保持了算法的多样性和探索能力。

4. Ant Colony System (ACS)

ACS 是 ACO 的一个高效版本,它引入了局部信息素更新规则和更强的全局更新规则。在 ACS 中,蚂蚁在构建路径时进行局部信息素更新,减少了当前路径上的信息素浓度,鼓励其他蚂蚁探索新路径。而全局更新只由生成最优解的蚂蚁执行,强化了最优路径。

特点:

  • 结合局部和全局信息素更新机制。

  • 强化最优解,同时保持探索新路径的激励。

  • 在快速收敛和多样性探索之间取得了良好的平衡。

粒子群算法 Particle Swarm Optimization (PSO)

PSO 的优先:简单高效。

参考鸟群的模式,“群体”被定义为移动个体的明显无组织的集合(群体)。这些个体倾向于聚集在一起,而每个个体似乎都在随机方向移动。而群体行为的同步性被认为是鸟类努力保持自己与邻居之间最佳距离的函数(避免碰撞,但方向和目标仍和群体一致)。而一个体的移动,往往是根据邻居的移动轨迹来的。

具体而言,是可以在搜索过程中,某个粒子搜索到了较优的路径,即可以把这个路径通信给其他粒子。

基本流程

1. 群体初始化

  • 在PSO中,解决方案的候选群体(称为“粒子”)通过随机分配位置和速度来初始化。这些粒子在问题的解空间中移动,解空间可以被想象为一个高维的“超空间”。
  • 每个粒子代表了解空间中的一个潜在解决方案,其位置代表了解决方案的候选点。

** 2. 个体历史最佳(pBest)、全局最佳(gBest)和局部最佳(lBest)**

  • 每个粒子都会跟踪它在超空间中遇到的“最佳”位置,即它所找到的具有最高适应度(或最优解)的位置。
  • “pBest”(personal best),代表了个体粒子在迄今为止的搜索过程中的最佳成就。
  • “gBest”(global best)是整个粒子群中找到的最优解。
  • 在某些 PSO 变体中,还会使用“lBest”(local best),它代表了粒子在一个定义好的邻域内找到的最佳解。

3. 随机加速和移动

  • 在每个时间步,粒子会根据自己的 pBest 和 gBest(或 lBest)的位置来随机地调整其速度和方向。这意味着粒子会“飞向”它自己的最佳位置和整个群体的最佳位置。
  • 这种行为模仿了鸟群或鱼群的社会行为,其中个体通过观察和模仿其他个体来改进自己的行为。

细节

\[\begin{aligned} &v_{i k}^{t+1}=\omega v_{i k}^t+c_1 \xi\left(p_{i k}^t-x_{i k}^t\right)+c_2 \eta\left(p_{g k}^t-x_{i k}^t\right), k=1,2, \cdots, d\\ &x_{i k}^{t+1}=x_{i k}^t+v_{i k}^{t+1}, k=1,2, \cdots, d \end{aligned} \]

关心的实际上是位置和速度。\(k\) 表示的是维度,\(i\) 表示当前粒子,\(t\) 表示当前时间。\(\left(p_{i k}^t-x_{i k}^t\right)\) 是当前位置离 IBest 的距离,\(\left(p_{g k}^t-x_{i k}^t\right)\) 是当前位置和 gBest 的距离。

另外,\(c_1\) 和 \(c_2\) 是 \(>0\) 的参数,\(\eta\) 和 \(\xi\) 是随机函数,\(w\) 是某种惯性权重。这些都是可调的。

C7 强化学习

标签:蚂蚁,人工智能,路径,通信,信息,个体,Part,Agents,笔记
From: https://www.cnblogs.com/pks-t/p/17890701.html

相关文章

  • 2023衡山论坛 医学大数据与人工智能前沿论坛 2023.11.20-12
    中国抗癌协会肿瘤标志专业委员会南华大学附属第一医院南华大学计算机学院 湖南省生物医学工程协会 湖南省生物信息学会哈尔滨工业大学生命科学与技术学院   湖南省生物医学工程学会是由湖南省从事生物医学工程学科活动的科技工作者和有志于促进生物医学工程领域......
  • 读程序员的README笔记05_日志、监控与配置
    1. 行为准则2. 日志分级2.1. 日志框架设有日志级别,它可以让运维人员根据重要性过滤消息2.2. 编程语言有精良的日志类库,让运维人员对要记录的内容和时间有更多的控制2.3. TRACE2.3.1. 一个极其精细的日志级别2.3.2. 对特定的包或类开放2.3.3. 在开发阶段之外很少......
  • [学习笔记]分层图最短路
    分层图的概念分层图最短路,听名字就知道他和其他最短路不一样,实际也确实如此,可以解决一些普通最短路无法解决的问题。比如有\(n\)个点\(m\)条带权无向边,可以将\(k\)条边进行某些操作,然后求出从\(1\)到\(n\)的最短路,此时即可使用分层图。例题例题1P4568[JLOI2011]......
  • CSS笔记
    1.CSS选择器是用于选取HTML文档中的元素的一种方式。常见的选择器包括:元素选择器:通过元素的标签名来选取元素,例如p、div等。类选择器:通过元素的class属性来选取元素,使用.符号加上类名,例如.my-class。ID选择器:通过元素的id属性来选取元素,使用#符号加上id值,例如#my-id。属性选......
  • JavaScript笔记
    JavaScript的组成:     1.数据类型:JavaScript有8种基本数据类型,包括Undefined、Null、Boolean、Number、String、BigInt、Symbol和Object。变量:在JavaScript中,可以使用var、let或const关键字声明变量。函数:JavaScript中的函数是一种可重用的代码块,可以使用fun......
  • 软件构造笔记
    今天软件构造考试结束了,这门课真的上的听玄幻的主要通过对ppt的整理得到的笔记格式是word里的格式,有原件和ppt,但是不方便直接发  有重构的书pdf软件构造前言l 推荐书目代码大全 代码整洁之道  重构改善既有代码设计l 主要都是ppt里的  合肥工业大学张高峰......
  • 【CCFCSP】2209真题笔记
    -1.如此编码分析daisuki代数题了,直接无脑套公式子任务有提示,记得参考测试数据:1532767222222222222222预期结果:111111111111111AC:#include<iostream>usingnamespacestd;constintmaxn=25;intn,m,tmp;inta[maxn],b[maxn];......
  • 第二周阅读笔记|人月神话
    9.23阅读了贵族专制、民主政治和系统设计我发现这个作者写的还是蛮通俗易懂的,而且有点引经据典的味道,读着还蛮津津有味的。功能,而非简洁,总是被用来衡量设计人员工作的出色程度。这是错的,任何事情我们都应该从他的实用性出发,拒绝假大空。因此,易用性实际上需要设计的一致性和概念......
  • HTML笔记
    1.什么是HTMl:HTML(HyperTextMarkupLanguage)是一种用于创建网页的标准标记语言。它使用一系列标签来定义网页的结构、内容和样式。HTML文档由一系列的元素组成,这些元素包括标题、段落、链接、图片、列表等。通过使用HTML标签,开发者可以创建出具有交互性和动态效果的网页。2.HTML......
  • 二分——acwing算法基础课笔记
    个人笔记,欢迎补充、指正。此次完全以个人理解来写。整数二分 整数二分有两种,分别是找左边界和找右边界。 寻找符合要求的左边界:绿色点intbsearch_1(intl,intr){while(l<r){intmid=l+r>>1;//对应下界,最左if(check(mid))r=......