基于改进型遗传算法的强化学习特征选择方法_张坤.pdf

191计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering1 引言近年来，强化学习算法正广泛应用在电力分配、网络通信、机器人控制领域，其基本原理是通过智能体与环境不断的交互产生评价性的反馈信号，并利用反馈信号不断改善智能体的策略，最终使智能体能够自主学习到适应环境的最优策略1-4，在与环境的互动过程中，选择何种特征作为模型输入是一个关键问题，特征选择不当不仅会导致算法性能下降，在实际问题中，也会导致更多的成本。无用的特征反而会干扰算法判断，因此必须非常慎重地选择状态特征。目前，对于特征选择方面的研究主要包括三类：基于特征子集评价策略的特征选择算法5-6、基于搜索策略的特征选择算法7-9、基于不同监督信息的特征选择方法10-12。其中基于搜索策略的特征选择算法分为全局最优搜索策略、随机搜索策略以及序列搜索策略的特征选择算法。由于强化学习算法特征之间具有非线性关系，而且适应度函数计算耗时长，因此本文使用能兼顾效果和效率的基于随机搜索策略的特征选择方法。2 基本思路本文提出一种基于改进型遗传算法，使用 PPO 算法作为适应度函数的特征选择方法，其中染色体为各特征的序列串，使用改进型遗传算法在特征空间进行搜索，将当前个体的特征作为 PPO 算法的输入特征与环境进行互动，进而得出当前个体综合得分作为适应度值。由于强化学习算法训练时间较长，因此为了加速特征的选择，需要提前截断训练过程，同时保证对特征有效性进行一定程度的选择，综合以上因此，设计了本文算法，伪代码如下：算法 1 本文算法伪代码输入：17 种特征 f1,f2,f17超参数：种群数量 N 最大迭代次数 T 交叉概率 Pc 突变概率 Pm输出：最优染色体序列 C1 Q1初始化，数量为 N2 使用适应度函数 F 对 Q1进行评价，得到 F(Q1,1)2 循环 t=2，3，T 3 根据适应度选择父代染色体4 根据 Pc交叉染色体5 根据 Pm突变染色体6 更新种群7 使用 F 对 Qt进行评价，得到 F(Qt,t)8 对每个染色体的适应度进行标记9 结束10 返回 最优染色体序列 CF(Q,t)为采用 PPO 算法的适应度评价函数，本文使用种群迭代次数 t 作为 PPO 算法训练的次数，具体流程如下：算法 2 评价函数伪代码输入：染色体序列 Q 种群迭代次数 t超参数：minibatch size M actor number N horizon H输出：染色体序列适应度 F(Q,t)1 初始化模型参数;3 循环 iteration=1，2，t4 循环 actor=1，2，N5 使用参数 与环境交互 H 次6 计算 Advantage 的估计，7 结束8 从 NH 个样本中，选择 M 次样本，其中 MNH，对 进行更新9 old10 结束11 使用训练好的 和 Q 进行测试，并返回适应度值 F(Q,t)本文主要完成以下工作：（1）针对自回避行走问题中的寻路任务设计了 17 种特征，包含感知特征、方位特征、状态特征、时间序列特征等。（2）针对强化学习模型收敛速度慢的缺点，改进了遗传算法适应度函数，添加了准确和效率的平衡参数，加快了训练速度。基于改进型遗传算法的强化学习特征选择方法张坤1姚媛2蔡宇3（1.海军大连舰艇学院 辽宁省大连市 116000 2.63751 部队 陕西省西安市 710038）（3.31455 部队 辽宁省沈阳市 110000）摘要：本文针对强化学习的特征选择过程中存在的组合爆炸问题，提出了基于改进型遗传算法的特征选择方法，并以自回避行走问题中的寻路任务进行有效性验证。首先针对自回避行走任务环境设计了 17 种独立特征，而后设计了渐进式的遗传算法并改进了适应度函数，最后进行了对比实验。实验结果表明，该方法在不降低算法性能的条件下，特征数量减少了 70.59%，适应度提高了 23.98%，是一种行之有效的特征选择方法。关键词：自回避行走；近端策略优化；遗传算法192计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering（3）通过将遗传算法应用在强化学习特征选择任务中，在不降低算法效果的基础上，将 17 种特征缩减为 5 种特征，减少了 70.59%的特征数量，适应度提高了 23.98%。3 具体方法3.1 场景构建自回避行走（self-avoiding walk，简称 SAW）指在一些格点内行走的路径，它们不重复经过任何一个点。本文使用贪吃蛇游戏作为算法运行场景，该游戏是自回避行走的一个特例，游戏过程中由 agent 控制一条蛇的移动方向，并试图通过到达随机出现的目标点来增加自己的长度，同时使游戏变得越来越困难。游戏结束方式有 3 种分别为蛇撞到自己或屏幕边界、距离上一次到达目标点超过 25 步或者蛇身填充满屏幕。3.2 特征工程本文使用 5*5 格子的贪吃蛇游戏环境，初始条件下蛇的长度为 1，每次到达目标位置后蛇的长度增加 1，并随机生成下一个目标点的位置。在一轮游戏当中，有效元素包括蛇头、蛇身、蛇尾、目标点、空白点、边界 6 种。在不考虑元素相关性条件下，特征空间为 65*5，因此如何有效的表示这6 种元素是本文讨论的重点。本文共设计了 17 种状态特征，下面分别进行描述。3.2.1 感知特征感知特征表征环境的态势，有 2 个分别为 3 方向元素特征和 8 方向元素特征。3 方向元素特征指以蛇头为中心探测前、左、右一格距离内是否为自身或者边界，如果有为 1，没有为 0，长度为 3，如图 1(a)所示。8方向元素特征指以蛇头为中心，分别探测前、左前，左、左后，后，右后，右，右前 8 个方向直线上是否有边界、蛇身或蛇尾、目标点，其值为 1/N，其中 N 为距离元素的距离，没有元素值为 0，长度为 24，如图 1(b)所示。3.2.2 方位特征方位特征表征目标或者蛇尾的方位，共 5 个分别为目标方位、蛇尾方位、目标角度、目标相对方位、目标绝对方位。目标方位特征检测目标点相对于头部的位置，以头部为中心，分为 4 个象限和 2 条坐标轴共 6 个位置，使用 onehot 编码，长度为 6。蛇尾方位与目标方位类似，只不过检测蛇尾相对于蛇头的位置，其余一致。目标角度检测目标相对蛇头的角度，公式为：R/360，其中 R 为目标角度，特征长度为 1，如图 1(c)。3.2.3 状态特征状态特征表征 agent 自身的状态，共 3 个分别为自身方向、填充度、上步动作。自身方向特征使用 1 维向量表示，检测头部方向，分为上下左右四个方向，使用 onehot 编码，长度为 4，如图 1(d)。3.2.4 标量时间序列特征该特征将当前态势特征 S0和上一步态势特征 S-1叠加后生成新的特征，一同输入给下一步计算，对于向量特征，将S-1直接添加在 S0的尾部，特征尺寸为原特征的 2 倍。3.2.5 S0矩阵特征该类特征用矩阵的方式以蛇头作为中心描述 S0时刻的态势，分为灰度特征、RGB 特征，6 层分解特征。灰度特征将蛇头、蛇身、蛇尾、目标点、空白点和边界表示在一个值为0至1的一维实数矩阵上，其中蛇头、蛇身、蛇尾值为0.7，目标点值为 1，边界值为 0.4，其余值为 0，可以配合动态中心使用，特征尺寸为(sizex*sizey*1)，如图 2(a)(b)所示。RGB 特征将 6 种元素表示在一个值为 0 至 1 的三维实数矩阵上，其中不同部位使用不同的矩阵值，特征尺寸为图 1：特征示意图 1图 2：特征示意图 2图 3：特征示意图 3(a)(a)(a)(b)(b)(b)(c)(c)(c)(d)(d)(d)193计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering(sizex*sizey*3)，如图 2(c)(d)所示。6 层分解特征将蛇头、蛇身、蛇尾、目标点和边界表示在一个值为 0 至 1 的六维实数矩阵上，其中不同部位使用不同的矩阵值，保证在不同部位保持描绘在不同层上，如图 3图 4：最优适应度曲线图 5：特征数量曲线194计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering所示。3.2.6 S-1矩阵特征该类特征用矩阵的方式以蛇头作为中心描述 S-1时刻的态势，同样分为灰度特征、RGB 特征，6 层分解特征 3 类，其余与 S0矩阵特征一致。3.3 遗传算法的改进在本文使用的硬件环境下，使用 PPO 算法进行 10000轮训练需要约 30 分钟，则按照每次种群数量为 20 计算，每代计算需要 10 小时，如果进行 20 轮计算，需要 200 小时，这显然是无法接受的，因此针对强化学习算法收敛速度慢和缩减特征的目标，设计了如下适应度函数：fitness=Nc(t)+Mc （1）其中 Nc(t)表示当前参数 C 进行 t 次训练获得的平均抵达次数，Mc表示当前参数 C 的特征数量，这样可以保证训练前期更快的获得评价结果，后期获得更准确的评价结果。根据任务本身的难度，调节 参数，从而对特征数量和算法表现进行平衡，获得适应当前任务的算法参数。本文 设置为 12.5，设置为 0.5。本文染色体编码长度为 17，对应于是否使用 17 个特征，形如 0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,1，如果对应位为 1，则使用特征，如果对应位为 0，则相应特征位置输入全 0，这样可以保证 PPO 算法使用的网络结构稳定，排除因网络结构引起的性能变化。4 结果分析本文共进行了 20 轮改进型遗传算法的训练，初始染色体为 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1，最优染色体为 1,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0，具体的特征为（8 方向元素特征，3方向元素特征，目标角度，S0时刻 RGB 特征，S0时刻 6 层分解特征），每轮的最优适应度曲线如图 4 所示，每轮的特征数量如图 5 所示。经过 20 轮训练后，得到可能的最优个体后，进行 20000轮训练，并与使用全部特征的个体进行对比，训练结果如图6 所示。观察可知，最优染色体每轮平均抵达次数为 23.25425，使用全部特征的染色体每轮平均抵达次数为 23.5964，优化过的染色比原版染色体有 1.47%的性能差距，这可以理解为算法的性能误差，但使用的特征数量减少了 70.59%，最优染色体适应度为 29.25425，比初始染色体适应度提高了23.98%。5 结语本文提出了一种基于改进型遗传算法的强化算法特征选择方法，将自回避行走中的寻路任务作为测试环境，设计了图 6：最优染色体对比曲线195数据库系统设计Database System Design电子技术与软件工程Electronic Technology&Software Engineering17 种特征，经过试验后发现，本文方法能够有效缩减特征数量，同时不降低算法性能，是一种行之有效的方法。但观察最优值可以发现，5 个最优特征有一定相关性，可能是一个局部最优值，下一步将继续研究如何利用特征相关性进一步提升算法表现。参考文献1 张佳鹏,李琳,朱叶.基于强化学习的无人驾驶车辆行为决策方法研究进展 J.电子科技,2021,34(5):6.2 王姝静.电子商务平台个性化推荐强化学习算法研究J.中外企业家,2020(9):1.3 贺嘉璠,汪慢,方峰,等.深度强化学习技术在智能空战中的运用 J.指挥信息系统与技术,2021,12(5):8.4 孙辉辉,胡春鹤,张军国.移动机器人运动规划中的深度强化学习方法 J.控制与决策,2021