基于扩展分类器系统（XCS）的雾云物联网资源分配

### 基于扩展分类器系统（XCS）的雾云物联网资源分配 #### 1. LCS 不同模型概述 强化学习（RL）和遗传算法（GA）相互结合，催生出了强大的学习分类器系统（LCS）。多年来，LCS 发展出了多种不同版本，以适应不同的概率需求。以下是几种常见的 LCS 模型： | 模型名称 | 特点 | | ---- | ---- | | 零级分类器（ZCS） | 分类器的适应度取决于执行该分类器所获得的累积奖励。累积奖励越大，适应度越高；奖励少的分类器可能会被删除。 | | 扩展分类器系统（XCS） | 分类器的适应度基于奖励预测的准确性，而非奖励值本身。每一代存活下来的分类器是那些奖励预测准确的，而非奖励值高的。 | | 预期分类器系统（ACS） | 分类器表示为 <条件, 动作, 效果>，效果组件反映动作的影响和结果，是基于模型的 RL 架构。 | | 监督分类器系统（UCS） | 专为分类和数据挖掘等阶段性问题设计，采用监督学习，在大空间问题中能有效泛化和进行一致的知识表示。 | | 函数逼近的 XCS（XCSF） | 以函数逼近为导向，条件部分接受实值输入，使用递归最小二乘法等线性逼近技术计算奖励预测。 | #### 2. 准确性为基础的扩展学习分类器系统（XCS） XCS 由 Wilson 在 1995 年提出，它能为给定问题进化出准确且高度泛化的分类器。其关键特点是不仅能得出最优的输入 - 输出映射，还能生成解释该映射的最小分类器（规则）集合，这使其区别于其他机器学习算法。 ##### 2.1 XCS 的术语和参数 - **情况（Situation）**：通过检测器从环境接收的感官输入，是一串固定长度的比特序列，通常表示为 σ(t) ϵ {0,1}L。 - **场景（Scenario）**：一系列情况，XCS 算法会针对这些情况执行适当动作以最大化奖励。 - **动作（Action）**：XCS 算法针对情况执行的输出，用 α(t) ϵ A 表示，A 是有序动作列表。 - **RL 问题**：分为单步问题（阶段性）和多步问题（连续性）。单步问题中，动作对后续状态无影响；多步问题中，当前状态受前一时刻动作影响，且并非每个状态 - 动作对都能获得奖励。 - **分类器/规则（Classifier/Rule）**：XCS 维护一组表示环境状态的分类器，每个分类器 “cl” 是一个元组，包含条件、动作、预测等属性，具体如下表： | 属性 | 描述 | | ---- | ---- | | c | 条件 c ϵ {0, 1, #}L，指定传感器输入，即情况 | | a | 动作 a ϵ {a1, a2, a3, ………….. an}，列举动作列表，即输出 | | p | 预测估计 p 是采取动作预期的回报 | | ε | 奖励预测误差，是目标预测与现有预测的差值 | | f | 分类器的适应度 | | exp | 经验，表示分类器成为动作集成员的次数 | | ts | 时间戳，规定上次调用 GA 的时间步 | | as | 动作集 [A] 的大小，分类器所属的动作集 | | n | 表示分类器被有经验的分类器包含的次数 | - **种群集（Population Set）**：在时间 “t” 时，集合 [P] 中所有规则或分类器的集合，“N” 表示种群的最大大小。 - **匹配集（Match Set）**：每个时间步，种群 [P] 中与当前情况（输入）匹配的分类器组成的集合 [M]。 - **预测数组（Prediction Array）**：为匹配集中的每个可能动作计算适应度加权预测平均值，并存储在预测数组中