改进遗传算法进化的演员网络种群强化学习算法

Evolving Actor Network Population Algorithm by Improved Genetic in Reinforcement Learning

摘要: 深度强化学习算法已成功应用于一系列具有挑战性的任务，然而这些方法通常会遇到奖励稀疏的时间信用分配、缺乏有效的探索以及探索经验不足等问题。演化算法是一类受自然进化启发的黑盒优化技术，算法提出了改进的混沌遗传算法以及量子遗传算法分别与强化学习算法结合，首先创建用于进化计算演员网络的总体，并使用梯度下降来更新网络参数，进化种群中的网络，直至算法收敛。算法的适应度度量整合强化学习中事件的回报，一定程度上解决了稀疏奖励条件下的时间信用分配问题；利用种群的方法来生成各种经验训练RL智能体，提高了鲁棒性。在离散和连续的强化学习环境中做了对比实验和消融实验，实验证明本文的算法能收敛到更高的奖励值，且能提高收敛速度。

Abstract: Deep reinforcement learning algorithms have been successfully applied to a range of challenging tasks; however, these methods often encounter problems such as sparse reward time credit allocation, lack of effective exploration, and insufficient exploration experience. Evolutionary algorithm is a type of black box optimization technique inspired by natural evolution. Improved chaotic genetic algorithm and quantum genetic algorithm are proposed to be combined with reinforcement learning algorithm. The algorithm first creates a population for evolutionary computation of actor networks and uses gradient descent to update network parameters, evolving the network in the population until the algorithm converges. The fitness measurement of the algorithm integrates the reward of events in reinforcement learning, which to some extent solves the problem of time credit allocation under sparse reward conditions; The use of population methods to generate various experience trained RL agents has improved robustness. Comparative experiments and ablation experiments were conducted in both discrete and continuous reinforcement learning environments, demonstrating that our algorithm can converge to higher reward values and improve convergence speed.

1. 引言

深度强化学习[1]被认为是结合感知智能和认知智能的有效方法，然而当环境的奖励稀疏时，智能体将行为与回报联系起来是困难的，这被称为时间信用分配问题[2]；其次，充分有效地探索环境且避免陷入局部最优是强化学习的一个关键挑战；最后，深度强化学习需要通过探索收集大量经验样本进行训练，如果探索空间太大，需要花费大量时间来收集所需的样本，而在探索不足时难以收敛，在使用现实世界中的实际机器进行探索的情况下很难执行有效的搜索。目前，一系列进化计算技术已经成为强化学习的有力竞争对手[3]-[5]。混沌遗传算法(Chaos Genetic Algorithm, CGA)利用混沌优化提高了找到全局最优解的概率，尹帅等[6]提出了一种多种群混沌遗传算法，采用混合编码表征决策变量，多种群及精英保留策略使得算法在求解过程中能更为显著地逼近全局最优解。量子遗传算法(Quantum Genetic Algorithm, QGA)使用量子逻辑门来更新单个染色体，可以在搜索空间中并行处理多个解。陈芸芸等[7]考虑在量子遗传算法的基础上引进了一种动态改进量子旋转角策略，并且加入了量子交叉、变异和灾变操作，以改进的量子遗传算法优化BP神经网络的权值和阈值，构建改进的模型。

本文提出了改进的混沌遗传和量子遗传进化演员网络种群的强化学习算法，算法首先创建用于进化计算演员网络的总体，与标准的DDPG结合并使用梯度下降来更新它们的参数，用改进的遗传算法进化种群中的网络，直至收敛。在离散和连续的环境下进行对比实验表明，该算法是卓有成效的。

2. 改进算法的设计与流程

2.1. 改进的量子遗传算法与混沌遗传算法

量子遗传算法是将量子的态矢量表达引入遗传编码的一种遗传算法，QGA通过量子旋转门$\text{U}\left(\delta \theta \right)$ 的更新操作对量子比特进行更新[8]，常见的量子旋转门如下式2.1：

$\left[\begin{array}{c}{\alpha }_{\left(m,n\right)}^{t+1}\\ {\beta }_{\left(m,n\right)}^{t+1}\end{array}\right]=U\left(\delta \theta \right)\left[\begin{array}{c}{\alpha }_{\left(m,n\right)}^t\\ {\beta }_{\left(m,n\right)}^t\end{array}\right]=\left[\begin{array}{cc}\cos \left(\delta \theta \right)& -\sin \left(\delta \theta \right)\\ \sin \left(\delta \theta \right)& \cos \left(\delta \theta \right)\end{array}\right]\left[\begin{array}{c}{\alpha }_{\left(m,n\right)}^t\\ {\beta }_{\left(m,n\right)}^t\end{array}\right]$ (2.1)

量子旋转门通常根据给定的查询表获得值，这种方式不能有效地利用个体适应度信息。为了进行旋转角度值的自适应调整，本文提出了一种改进的量子遗传算法，它可以根据个体适应度值动态调整量子旋转门，本文采用公式2.2确定旋转角的值：

$\begin{array}{c}{\theta }_i=\{\begin{array}{cc}\frac{k_1\left(f_{\max }-f^{\prime }\right)}{f_{\max }-f_{avg}},& f^{\prime }\ge f_{avg}\\ k_2,& f^{\prime }<f_{avg}\end{array}\end{array}$ (2.2)

其中$f_{\max }$ 表示该组的最大适应度值；$f_{avg}$ 表示每一代的平均适应度值；$f^{\prime }$ 表示量子交叉的个体与目标个体之间的较大适应度值；k₁、k₂表示区间$\left[0.001\pi ,0.005\pi \right]$ 之间的随机数，根据k₁、k₂可以自适应地调整旋转角度${\theta }_i$ 。

混沌传算法是基于混沌优化的遗传算法，在混沌遗传算法中，交叉算子在遗传操作中起着核心作用，其主要用于产生新的个体来实现算法的全局搜索能力。作为整个种群的进化过程，交叉概率应该能够随着进化过程逐渐变小，并最终趋向于一个恒定值，这样可以避免算法无法收敛而影响稳定性。为此，本文设计了一个与代数进化相关的交叉概率方程：

$\begin{array}{c}{P}_c=\frac{1}{1+{\text{e}}^{\alpha G}}+0.1\end{array}$ (2.3)

其中，G是代数的演化，$\alpha$ 是一个常数系数，表示交叉概率的曲率变化。

2.2. 改进的演化算法优化强化学习混合算法

图1说明了本文混合算法的双层学习方法，算法的一般流程如下：用随机权重初始化演员网络的总体，用于进化计算。一个额外的演员网络(以下称为$r{l}_{\text{actor}}$ )与评论家网络一起初始化；每个演员网络记录每一代所有任务的奖励。此外，本次探索中采样的样本$\left(s_i,a_i,r_i,s_{i+1}\right)$ 存储在每个任务的重播缓冲区中，这种机

Figure 1. Dual layer learning method of hybrid algorithm

图1. 混合算法的双层学习方法

制使得神经网络通过探索多个参与者来使用无偏样本进行训练，这些样本被DDPG算法用于训练参与者。

在与所有演员网络完成探索后，根据记录的奖励总数计算每个演员的适应度分数，在与环境交互的一集中评估演员群体($r{l}_{\text{actor}}$ 排除在外)，一个选择算子以与他们的相对适应度分数相称的概率选择一部分人口的生存，通过突变和交叉操作对种群中的演员网络进行概率扰动即神经网络的权重(基因)的扰动，以创建下一代参与者。周期性地，$r{l}_{\text{actor}}$ 网络的权重被复制到不断发展的演员网络群体中，这被称为同步。评论家从这个回放缓冲区中随机采样一个批次，并使用梯度下降来更新它的参数，然后，算法使用采样策略梯度来训练$r{l}_{\text{actor}}$ 。

同步的频率控制着从强化学习到进化群体的信息流，这是使进化框架能够直接利用通过梯度下降学到的信息的核心机制。将$r{l}_{\text{actor}}$ 学到的策略注入种群的过程也有助于稳定学习，使其更具鲁棒性。与演化算法只使用粗反馈信号(适应度评分)在事件之间学习不同，本文混合算法是额外学习的从经验集内部获得的奖励，由于适应度分数捕获个体的情景范围回报，使用适应度指标整合整个事件的回报，使得混合算法在一定程度上解决了稀疏奖励条件下的时间信用分配问题，并且对长时间范围具有鲁棒性。

3. 实验与分析

3.1. 两种不同环境下的演化强化实验

图2显示了不采用演化算法的标准DDPG算法[9]、采用改进的量子遗传算法的强化学习算法和采用

Figure 2. Comparative performance in CartPale-v1 environment

图2. CartPole-v1环境下的比较性能

改进的混沌遗传算法的强化学习算法等三种算法的在CartPole-v1环境下的比较性能，该环境中的状态和动作空间均为离散值。本文采用上述三种算法训练200帧，可以看出，改进的混沌遗传算法的强化学习算法在该环境下收敛最快，并且在25帧左右就可以较为平稳的达到了该环境下的最大奖励值500，而改进的量子遗传算法的强化学习算法其在150帧左右逐步收敛到奖励值为300的附近，而标准的DDPG算法在175帧左右收敛到200。在连续的Hopper环境中的三种算法的性能对比见图3，根据图可以得出与Cartpole环境中相似的结论。

Figure 3. Comparative performance in Hopper environment

图3. Hopper环境下的比较性能

标准的DDPG算法表现不佳的原因是由于奖励的欺骗性和稀疏性(智能体必须等待多步才能接收到有用的反馈信号)造成了一个困难的时间信用分配问题，这种问题DDPG无法有效地处理。相比之下，改进的遗传算法结合强化学习算法包含适应度度量的时间信用分配优势，能够更好地解决任务。尽管奖励是稀疏和欺骗性的，混合算法的选择算子为具有高情景范围回报(适应度)的策略提供了选择压力，这使得存储在缓冲区中的状态的分布偏向于具有较高长期回报的状态，从而使算法表现更佳。

3.2. 消融实验

使用消融实验来测试改进的遗传算法中变异操作符和选择操作符的作用，这两种操作符是遗传算法中的核心机制[10]。在Cartpole环境中分别采用完整的时变变异算子的混沌遗传算法、去除变异操作的混沌遗传算法以及去除选择操作的混沌遗传算法与DDPG结合进行训练，每个基准的性能通过使用完整算法获得的最佳分数进行归一化，种群中的演员网络个数为10。下表1和图4为测试的比较结果。

Table 1. Comparison of ablation experiment iteration times and rewards

表1. 消融实验迭代次数与奖励对比

完整算法	去除选择操作算法	去除变异操作算法
(415, 9)	(475, 8.8)	(505, 8.8)
(5327, 141.8)	(3449, 105.4)	(2438, 115.8)
(17,269, 135.6)	(7275, 143.2)	(5150, 142.4)
(30,338, 209)	(13,374, 72.2)	(7574, 124.4)
(79,237, 500)	(37,065, 379.6)	(10,610, 97.8)
(122,996, 482.4)	(90,209, 448)	(13,446, 109.2)
(190,166, 491.2)	(134,127, 269.2)	(17,106, 143.2)
(245,895, 487.8)	(172,517, 329.2)	(22,036, 154.8)
(349,581, 500)	(211,069, 345.6)	(31,209, 263.6)
(408,261, 500)	(252,606, 500)	(50,508, 500)

根据上表的数据推算得知，完整算法在迭代至35,000次左右可以达到最大奖励值的二分之一，而去除选择操作算子和去除变异操作算子的算法达到该奖励值分别为3500次和3100次。至于达到最大奖励值，三种算法分别要迭代400,000次、250,000次、50,000左右。由此可得在训练的初期，选择算子对算法的迭代速度影响微乎其微，而去除变异算子后反而可以加快训练速度。这是由于训练初期，种群的各个个体演员网络处于探索阶段，每个网络所得到的网络权重和参数分布较为均匀，因此选择算子影响很小，去除变异操作能节省运算次数，减轻网络结构。而在Cartpole这种状态空间和动作空间维度较少的环境下，完整的算法在种群演化较少的代数便能达到最大奖励值，但也要付出迭代次数成倍增加的代价。

就种群的更新而言，去除变异算子与选择算子的阉割算法均有损训练性能，其中利用本文提出的完整的演化强化算法在种群更新第20代能达到环境中的最大奖励值，而去除变异算子的演化强化算法需要进化到第25代左右。去除选择算子对算法的影响最大，算法在进化到85代左右才逐步收敛，且训练过程不稳定。因而可以得出选择算子是本文算法的的关键部分，移除选择操作导致在Cartpole环境下的训练性能急速下降。

4. 结论与展望

本文基于改进的变异算子混沌扰动遗传算法以及根据个体适应度值动态调整量子旋转门更新的量子进化算法，分别与标准强化学习算法DDPG结合，提出了一种解决强化学习问题的新的混合算法。首先，算法创建用于进化计算演员网络的总体作为进化种群，它们与标准的DDPG算法结合并使用梯度下降来更新它的参数。其次，用改进的遗传算法进化种群中的网络，直至收敛。算法的适应度度量整合强化学习中事件的回报，将探索偏向于具有较高长期回报的状态，促进探索策略的多样性，一定程度上解决了稀疏奖励下的时间信用分配问题；利用种群的方法来生成各种经验训练智能体，引入冗余以保持稳定性，提高了鲁棒性。在离散和连续的强化学习环境中做了对比实验和消融实验，实验证明本文的算法能收敛到更高的奖励值，且能提高收敛速度，表明了本文优于不采用进化演员网络种群的DDPG算法。通过对

Figure 4. Comparison of ablation experiment iteration times and rewards

图4. 消融实验迭代次数与奖励对比

比实验和消融实验，实验表明，改进的混沌遗传算法表现最佳，同时，遗传算法中的选择操作符对实验的性能改善最为明显。

在未来的工作中，整合更复杂的进化分子机制是一个令人期待的领域。一些例子包括结合更多信息的交叉和突变算子[11]、自适应勘探噪声[12]和显式多样性维护技术[13]等。如基因表达式编程[14]、新颖性搜索[15]或质量多样性[16]等利用了行为特征空间，在大多数研究中，行为特征空间表征了状态或状态–行动轨迹的属性。这些算法的许多实例已经成功地使用了相对简单的手动定义的特征，但一个悬而未决的问题是如何通过无监督学习来学习它们，以及这些学习到的特征将如何影响强化学习方法的动态。