Agent联盟
多智能体系统源于工业控制从集中式、总线式到智能控制的演进。它把控制系统中的传输路由、执行单元和控制单元都升级为独立的 Agent,每个 Agent 有自己的判断,通过网络结成联盟,以协作方式完成整体的控制和执行任务,并借助联盟求解快速协调、生成工作联盟。
主题对照
比较 MDP、Q-learning/Sarsa/DQN 等单体强化学习方法,以及多智能体的集中训练分布式执行、联合动作分解、博弈矩阵与均衡学习、群体智能算法。
多智能体系统源于工业控制从集中式、总线式到智能控制的演进。它把控制系统中的传输路由、执行单元和控制单元都升级为独立的 Agent,每个 Agent 有自己的判断,通过网络结成联盟,以协作方式完成整体的控制和执行任务,并借助联盟求解快速协调、生成工作联盟。
分布式求解有两种方式。分布式问题求解先规划一个全局问题,各子系统分担任务协作计算,最后归并出结果,HLA 属于这一类。多智能体系统中每个 Agent 独立、整体分散,它们通过协作、协商、协调解决问题,但不做总体归纳,每个 Agent 都是自治的,有自己的目标和决策方式。
马尔可夫决策过程(MDP)是智能体决策和强化学习的基础模型,由状态集、动作集、状态转移概率和回报组成。智能体在某状态选择动作后按概率转到下一状态,每一步都有回报。强化学习根据环境给出的延时回报判断策略好坏,并用值函数衡量策略的长期影响,而不只看单步收益。
MADDPG 采用集中训练、分布式执行:训练时每个智能体都有 Critic 和 Actor,Critic 使用全局信息,包括其他智能体的观测和动作,从而估计它们的策略;执行时只用 Actor,只依赖本智能体的局部观测。因为 Critic 知道所有智能体的动作,环境对它是稳定的。各智能体有独立的奖励函数,可形成合作、对抗或混合关系。
Q-learning 用 Q 表记录每个状态下每个动作的期望奖励,运行时只要找到当前状态所在的行,选期望最大的动作即可,在迷宫这类小状态空间里简单有效。但状态和动作的数量一多,Q 表的查询和维护就会变得很慢,于是 DQN 改用神经网络等近似函数来估算值函数。
Q-learning 是 off-policy 算法,更新时用下一状态中回报最大的动作的 Q 值;Sarsa 是 on-policy 算法,去掉取最大值这一步,用下一状态实际选择的动作来计算 Q 值。Sarsa(λ) 进一步在获得奖励时回溯更新前 λ 步:λ=0 就是单步更新的 Sarsa,λ=1 则更新整个回合中奖励之前的所有步。
DQN 用神经网络近似 Q 函数,以替代状态和动作过多时无法使用的 Q 表。除了 Q 网络,DQN 还增加一个 target Q 网络专门计算目标值:它与 Q 网络结构和初始权重相同,但 Q 网络每一步都更新,target Q 网络隔一段时间才同步一次,让计算目标值所用的参数在一段时间内保持不变。
群体智能算法源于 Holland 1975 年提出的遗传算法,框架大致相同:输入初始种群和环境,设定群体规模、迭代次数和社会参数;每一轮计算个体与环境的适应值,个体自我适应、更新参数,再通过博弈和竞争生成下一代子种群;满足终止条件时结束迭代,从个体到子种群再到社会化地逐步更新策略。
博弈矩阵有两条定理。第一定理:信息完全对等的两人零和博弈,每个玩家都有最佳纯策略,最小最大值等于最大最小值。但在信息隐藏的博弈中,如猜硬币,两者不相等,不存在纯策略解。第二定理:信息隐藏的两人零和博弈总存在一个最佳混合策略,即按一定概率随机选择纯策略。
WoLF 的意思是“赢了慢学、输了快学”:先比较当前策略积累的预期奖励是否高于纳什均衡下的评价值,以判断输赢。WoLF-PHC 设两个学习速率,胜利时用较小的速率,失败时用较大的速率,让失败的智能体更快调整、追上胜利者,从而加速收敛到纳什均衡。
学习自动机让智能体在未知环境中自动适应:根据环境对自身行为的响应,更新自己各个动作的概率分布,逐步学到最优策略。它是完全分散式的算法,只考虑自身行为和环境回报,完全不理会其他智能体。线性回报-无为、线性回报-惩罚等变体在一定条件下可以收敛到纳什均衡。
多个智能体联合行动时,Q 函数的联合动作空间随智能体数量指数增长,传统 Q-learning 不再适用;其他智能体的策略又在不断变化,难以收敛。QMix 用集中式学习把联合动作值分解为各智能体的局部 Q 值,并约束二者单调一致,于是各智能体贪心选出的局部最优动作就对应全局最优,计算量只随智能体数量线性增长。
让多个智能体各自用 DDPG 训练时,每个智能体的策略都在变化,彼此面对的环境就不稳定。MADDPG 的做法是汇总各智能体的子策略,形成中央评判网络:每个智能体的训练方式与 DDPG 类似,但它的 Critic 输入除了自己的状态和动作,还包括其他智能体的数据,从而得到稳定的评价。
游戏 AI 最常用的是有限状态机,复杂场景下需要分层管理,形成分层有限状态机:切换时先进入高层状态,再进入底层状态。书中在这一结构上对不同层应用强化学习,用 DDPG 神经网络在分层状态机中做决策,形成多行为决策引擎,让智能体行为更有变化,并能在复杂场景中快速反应。
IFEPSO-SA 是粒子群优化(PSO)与模拟退火的混合,两处改造各管一件事:
熵作用于种群如何移动,退火作用于候选是否保留;结合后的效果仍须按具体问题检验。
人工雨滴算法(ARA)把降雨循环映射为随机优化搜索,分为雨滴形成、雨滴碰撞、雨滴流动、雨滴池更新和水汽更新五个阶段。它模仿的自然过程是:水汽聚集凝结成雨滴,雨滴落地碰撞成许多小雨滴,小雨滴受重力流向海拔低处,部分再蒸发成水汽回到大气,循环往复。在最小化问题里,“海拔”对应目标函数值,流向低处即寻找目标值更小的位置。
这个阶段框架给自然现象与算法过程建立对应关系,但只列出阶段名称并不等于掌握各阶段的更新规则;具体算子见 [[雨滴质心构造主搜索点]]、[[飞溅扰动兼顾全局与局部搜索]] 和 [[雨滴池与择优更新保留搜索进展]]。
结构图:
flowchart TD
A[雨滴形成] --> B[雨滴碰撞]
B --> C[雨滴流动]
C --> D[雨滴池更新]
D --> E[水汽更新]
E --> A
ARA把 N 个 D 维水汽向量视为一代候选解(第 G 代第 i 个记作 Vaporᵢ),并将它们各维坐标的平均值组成雨滴位置:Raindrop 的第 j 维 = (1/N)·Σᵢ vaporᵢ,ⱼ,即水汽种群的几何中心。这模仿水汽不断吸收周围水汽而凝成雨滴。
示例(补充):N=3、D=2,水汽为 (1,4)、(3,2)、(5,6),雨滴位置为 ((1+3+5)/3, (4+2+6)/3)=(3,4)。
群体中心把多个候选压缩成一个后续扰动的起点;它代表种群整体位置,不等于其中目标值最好的解——上例中 (3,4) 与三个水汽都不重合,目标值也可能不如其中某个,因此还需单独保留个体评价。
ARA的扰动分三步:
飞溅负责大范围覆盖,流动负责局部改进。正文方向向量(式 13-7)的符号与下标有疑点,因此这里只保留可由文字确认的机制。
结构图:
flowchart TD
A[雨滴位置] --> B[随机扰动一个维度]
B --> C[碰撞并产生拟正态小雨滴]
C --> D[雨滴池位置提供低值引导]
D --> E[最多流动MNF次]
E --> F[形成局部搜索候选]
ARA分别维护两个集合:
前者提供局部引导记忆,后者筛选总体候选。两者职责不同:RP 超容时是随机删除而非按优劣淘汰,不能误写成只保留最优者的全局精英档案。
结构图:
flowchart TD
A[流动后的候选] --> B[本代最优位置加入雨滴池]
B --> C{雨滴池是否超过N?}
C -- 是 --> D[随机删除冗余粒子]
C -- 否 --> E[保留雨滴池]
D --> E
F[新小雨滴] --> G[与旧水汽合并]
G --> H[按目标值选择前N个]
H --> I[形成下一代水汽]
智能水滴算法用路径泥土量和路径长度共同影响下一节点的选择概率,并为泥土变量设置上下限,避免某段路径信息变化过快而使搜索过早集中。它与 [[选城概率融合信息素与距离]] 都组合了历史路径信息和距离启发,但泥土更新属于水滴算法机制,不能直接套用蚁群的信息素更新规则。
选择倾向上(补充教学示例,非书中数据;原文未给具体公式):
| 路段特征 | 对下一节点概率的影响 |
|---|---|
| 泥土少、路程短 | 更容易被选 |
| 泥土多、路程长 | 更不容易被选 |
| 泥土已碰到上/下限 | 该段信息不再剧烈变,降低过早盯住少数路 |
泥土少/路短更像“已有水流冲刷且近”的河道;上限下限管的是变化速度,不是把某条路永久删掉。
智能水滴的旁域更新不只改动单条路径上的泥土量,而把整条河道的信息纳入更新,使其他水滴到达目标节点的概率也受影响。它扩大了节点选择所共享的路径反馈范围;原文未给更新公式和参数,不能据此复原算子或断言性能提升。它扩展的是 [[IWD按泥土和路径长度选节点]] 的泥土更新环节。
经典 PSO 用当前位置和速度更新粒子;本节的 QPSO 保留评价、局部最好解与全局最好解的迭代框架,把位置更新改成围绕吸引子的概率采样,不再显式更新速度。这里的“量子”指借波函数构造的搜索分布;书中给的是模拟采样算法,不能由名称推断量子硬件或普遍加速。
| 经典 PSO | 本节 QPSO | |
|---|---|---|
| 状态 | 位置 + 速度 | 只有位置 |
| 产生新解 | 先更新速度,再沿速度走一步 | 按波函数导出的概率模型采样 |
| 其余 | 比较适应度,更新个体/全局最好 | 相同框架 |
吸引子和特征长度如何进入采样式,见 [[吸引子与长度控制采样]]。
一维 δ 势井模型把吸引子 p 作为位置分布中心,把特征长度 L 作为扩散尺度。书中给出的密度 Q(y)=e^(−2|y|/L)/L 对应采样 x=p±(L/2)ln(1/u),u 为 (0,1) 均匀数,正负号各半。吸引子和 L 的构造影响探索范围。书中间步骤与 L 的符号推导有不一致,公式用于实现前须独立复核。
演算(补充教学示例,非书中数据):取 p=0、L=2、u=1/e≈0.368,则 (L/2)ln(1/u)=1×1=1,故 x=±1。L 越大,同样的 u 会把样本推得离 p 更远。p 与 L 由个体最好、全局最好等量更新,见 [[平均最优位置调节采样半径]]。
本节 QPSO 在每维从个体最好位置与群体最好位置之间随机取吸引点 p,再计算全部粒子个体最好位置的均值 C(平均最优位置)。新位置围绕 p 随机生成,步幅随收缩扩张参数 α 及当前位置到 C 的距离改变。评价后更新个体和群体最好解,再继续采样。粒子没有速度向量。原文变量与式号有排版疑点,应用时应核对原论文的更新式。
示例(补充教学示例,非书中数据):一维两粒子,个体最好 P₁=2、P₂=6,则 C=(2+6)/2=4。某粒子取 φ=0.5、Pᵢ=2、G=6,吸引点 p=0.5×2+0.5×6=4。新位置在 p 附近抽样,离 C 越远、α 越大,步子越大。C 把“群体个体最好的平均”引进采样半径,而不是只用当前全局最好 G。
QPSO 每轮借个体最好和群体最好位置引导新样本;若群体反复向同一批较优位置靠拢,分布可能收缩,多峰目标上的其他区域便难再探索。这解释早熟风险,也说明为何需关注多样性。是否真的早熟取决于目标景观、吸引点和收缩参数;书中“不可避免”及“全局搜索远优于 PSO”均未给普遍证明。
协同 QPSO 要比较某粒子的第 d 维时,先固定其他维的背景值,仅替换第 d 维,再重算完整目标函数;这样同一背景下可比较各候选分量对目标值的影响,避免只按整条向量的分数丢弃有用分量。贡献依赖背景和变量耦合,不能把单次替换结果当成该维的固有质量。文字称用全局最好 g 作背景,但随后算式实际代入了另一个体。
书中三维例子:误差 f(X)=‖X−A‖²,A=(20,20,20),越小越好。g=(18,3,15)→f=318;X₁=(5,15,13)→f=299;X₂=(20,7,5)→f=394。无协作时因 299 会用整条 X₁ 替换 g,X₂ 被丢,尽管 X₂ 的第一维 20 已是最优分量。
按书中写出的三个函数值,背景实际是 X₁ 而非所称的 g:
| 替换 | 向量 | f |
|---|---|---|
| X₂ 的第 1 维 | (20,15,13) | 74 |
| X₂ 的第 2 维 | (5,7,13) | 443 |
| X₂ 的第 3 维 | (5,15,5) | 475 |
只有第一维变好,于是新的 g 取 (20,15,13)。这些平方和可由 A=(20,20,20) 直接核算,是书中数据;背景向量应取 g 还是 X₁,原文不一致,实现时须自行选定并保持前后一致。
ICQPSO 对一个粒子多次采样后,先把适应度最好的候选复制为“背景向量”(逐维试换时的基准解),再拿其余候选的每一维逐个试换:只替换这一维,重算完整目标值;变好就保留,变差就恢复,然后试下一维。
示例(补充,最小化 f=x₁²+x₂²+x₃²):
| 步骤 | 背景向量 | f |
|---|---|---|
| 最好候选 X1 作背景 | (1,2,0) | 5 |
| 换入 X2=(3,0,3) 第 1 维 | (3,2,0) | 13,恢复 |
| 换入第 2 维 | (1,0,0) | 1,保留 |
| 换入第 3 维 | (1,0,3) | 10,恢复 |
X2 整体 f=18 很差,但它的第 2 维让背景从 5 降到 1,这就是协同要利用的“局部有益分量”。代价是每试一维就多评价一次:书中每轮采样 5 次,其余 4 个候选在 D 维问题上每粒子每轮多 4D 次评价。结果还依赖试换顺序与当前背景,效果不能由流程本身保证。
量子粒子群算法先用概率分布描述粒子位置,再用一个随机数经蒙特卡洛反变换取得一个确定位置,供目标函数评价;本节把这一步称为单次“坍塌”。反变换的做法是取 0 到 1 之间的均匀随机数 u,代入 x = p ± (L/2)·ln(1/u):p 是粒子被吸引的中心位置,L 控制分布宽度。演示:取 p=0、L=2,u=0.5 时 x≈±0.69,u=0.1 时 x≈±2.30——u 越小,位置离 p 越远。使用多个不同的 u 得到多个候选位置,就是多次坍塌。它在实现上是重复抽样,增加候选也增加评价成本,不表示在量子硬件上反复测量。候选如何取舍见 [[多次采样以计算成本换候选选择]]。
MOQPSO(多次坍塌-正交交叉的量子粒子群算法)将 [[多次坍塌是重复位置抽样]] 与 [[正交交叉按表重组片段]] 连在一轮更新中:每个粒子先由 Q 次抽样得到 Q 个位置,再按正交表组合片段得到 M 个新候选,以目标函数评价后选本轮最好位置,并与个体及群体历史最优比较。这样保留了多个样本的片段信息,但 Q、M 越大,目标评价也越多。流程本身不能证明书中“概率 1 收敛”或普遍性能优势。
结构图:
flowchart TD
A[当前粒子及历史最优] --> B[重复抽样Q个位置]
B --> C[按正交表重组片段]
C --> D[生成M个候选]
D --> E[评价并取本轮最好]
E --> F[更新个体最优]
F --> G[更新群体最优]
G --> H{终止条件}
H -- 否 --> B
H -- 是 --> I[输出群体最优]
MOQPSO(多次坍塌-正交交叉量子粒子群)在多数测试函数上取得较低的平均最优适应度,但优势并非普遍。对照组是标准粒子群 PSO 和量子粒子群 QPSO;所有函数都求最小值,数值越小越好,负数也一样(−76 比 −74.5 更小、更好)。
| 函数 | MOQPSO | 对照 | 更好者 |
|---|---|---|---|
| f2 | 8.1004 | QPSO 28.7138 | MOQPSO |
| f6 | −74.5436 | QPSO −76.0704 | QPSO |
| f9 | −0.2234 | PSO、QPSO 均 −0.2399 | 对照 |
多次采样与正交交叉还增加目标评价次数,迭代数相同不能证明计算效率更高。
点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。
来源书籍
分布式人工智能与多智能体类
书籍类型:工程实践
清单覆盖 7/7
35 张卡片
来源书籍
算法与数据结构类。按全文与现有卡核对七项;“已覆盖”表示保留了本书实际展开的部分,不表示穷尽该领域。
书籍类型:经典原理
清单覆盖 6/7
367 张卡片
主题索引
MDP 与 Q-learning/Sarsa/DQN 的单体学习路径,多智能体的集中训练分布式执行、联合动作分解、博弈矩阵与均衡学习,以及群体智能算法与强化学习在反馈来源上的差别。
与 4 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 3 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 3 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;来自相同书籍;属于相同分类