强化学习与遗传算法

之前看混沌理论的时候看到了遗传算法，之后又了解到了强化学习。当时这两个一直搞不太懂，总感觉都是选好的不要不好的。而且作为一个搞安全的，AI方面真的是不太行。就算之前把西瓜书给草草的过了一遍，但对于一些理论的文章还是看着头大。

昨天一整天没学习，晚上良心发现，在睡前就看了一些强化学习和遗传算法相关的知识，终于搞懂了。

理论的东西我看着头大，就按我理解的写了。

强化学习（Reinforcement Learning）

强化学习是机器学习的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。让计算机实现从一开始完全随机的进行操作，通过不断地尝试，从错误中学习，最后找到规律，学会了达到目的的方法。这就是一个完整的强化学习过程。让计算机在不断的尝试中更新自己的行为，从而一步步学习如何操自己的行为得到高分。

它主要包含四个元素，Agent、环境状态、行动、奖励，强化学习的目标就是获得最多的累计奖励。

让我们想象一下比赛现场：

计算机有一位虚拟的裁判，这个裁判他不会告诉你如何行动，如何做决定，他为你做的事只有给你的行为打分，最开始，计算机完全不知道该怎么做，行为完全是随机的，那计算机应该以什么形式学习这些现有的资源，或者说怎么样只从分数中学习到我应该怎样做决定呢？很简单，只需要记住那些高分，低分对应的行为，下次用同样的行为拿高分, 并避免低分的行为.

计算机就是 Agent，他试图通过采取行动来操纵环境，并且从一个状态转变到另一个状态，当他完成任务时给高分(奖励)，但是当他没完成任务时，给低分(无奖励)。这也是强化学习的核心思想。所以强化学习具有分数导向性。

（说实话，我觉得根据奖惩得分判断选择策略有一种博弈论的意思，查了一下，果然如此）

最近，深度强化学习貌似还挺火的。

遗传算法（Genetic Algorithm）

遗传算法我还是从BBC的混沌理论纪录片里了解的，当时它模拟生物进化来让算法得到一个非常优秀的结果让我印象深刻。

按我的理解就是，达尔文进化理论的物竞天择适者生存。通过计算机来自动控制进化，每次迭代选择当前种群中的一个最优的个体，个体种群内控制随机变异，最优的个体进入下一次迭代，如此往复就是一个生物进化的过程，不过此时变成了得到了最适合当前情况的一个解。可以说遗传算法就是一个鉴生物界自然选择和自然遗传机制的随机化搜索算法得到（近似）最优解的过程。

这里有一个介绍的挺容易理解的：

从前在海岸边有一群扇贝在悠哉游哉地生活繁衍着。它们自然是衣食不愁，连房子也有了着落。它们担忧的只有一件事：每隔一段时间，总有一个人来挖走它们之中的一部分。当然啦，挖回去干什么这大家都知道。但扇贝们不知道的是，这人的家族图腾是Firefox的图标，所以他总是选择那些贝壳花纹长得比较不像Firefox图标的扇贝。

这种状况持续了好几十万代。大家应该也猜到扇贝们身上发生什么事情了：它们的贝壳上都印着很像Firefox图标的图案。

可能有些读者会说：你这不是糊弄我们么，Firefox才有多少年历史，你就搞了个几十万代的扇贝？

确有其事，但是这些扇贝不是真实的，它们在我电脑的内存里边生活。它们是一个遗传算法程序的一部分，这个程序的目的就是用100个半透明三角形把Firefox的图标尽可能像地画出来。

什么是遗传算法呢？

简单地说，遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化，从而得到问题的一个近似解。

在二十世纪五十年代，生物学家已经知道基因在自然演化过程中的作用了，而他们也希望能在新出现的计算机上模拟这个过程，用以尝试定量研究基因与进化之间的关系。这就是遗传算法的滥觞。后来，有人将其用于解决优化问题，于是就产生了遗传算法。

那么，具体来说，在计算机里边是怎么模拟进化过程的呢？

我们还是以开头提到的程序为例。

首先，我们知道，生物个体长什么样子很大程度上是由染色体上的基因决定的。同样，如果我们把100个半透明三角形组成的东西看成一个生物个体的话（为了说话方便，称为扇贝吧），我们也可以说它的样子是由这些三角形的具体位置和颜色决定的。所以，我们可以把一个一个的半透明三角形看作是这些扇贝的“基因”。而组成扇贝的这100个基因就组成了每个扇贝个体的“染色体”（chromosome）。

从下面的图可以大约看出来这些基因是怎么决定扇贝的样子的（为了观看方便，我们只画出其中五个三角形）：

然后，扇贝们除了生活，当然还要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体，而在这个程序里边我们当然也这么办：选择两个原有的扇贝，然后从这两个扇贝的染色体中随机选取一共100个基因组成新个体的染色体。如图所示：（仍然是将扇贝看成是五个三角形组成的）

为了产生新的基因，使基因的种类更多样化，在组合的时候，新的扇贝的基因有一定的概率发生变异。也就是说，其中的一个透明三角形的位置或者颜色会随机改变，如图（仍然是五个三角形……我偷工减料……）：

其次，为了使扇贝的样子向Firefox图标靠近，我们要给它们加上一点选择压力，就是文章开头故事中提到的那个人的行动：在每一代把最不像Firefox的扇贝淘汰出去，同时也给新的个体留下生存的空间。怎么评价这个扇贝像不像Firefox呢？最直接的方法就是一个一个像素比较，颜色相差得越多就越不像。这个评价的函数叫做“适应函数”，它负责评价一个个体到底有多适应我们的要求。

在淘汰的过程中，为了便于编程，我们通常会在淘汰旧个体和产生新个体的数目上进行适当的调整，使种群的大小保持不变。淘汰的作用就是使适应我们要求的个体存在的时间更长，从而达到选择的目的。

最后，在自然界中，种群的演化是一个无休止的过程，但程序总要停下来给出一个结果。那么，什么时候终止演化输出结果呢？这就要订立一个终止条件，满足这个条件的话程序就输出当前最好的结果并停止。最简单的终止条件就是，如果种群经过了很多代（这里的“很多”是一个需要设定的参数）之后仍然没有显著改变适应性的变异的话，我们就停止并输出结果。我们就用这个终止条件。

好了，现在是万事俱备只欠东风了。定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码之后，只需要随机产生一个适当大小的种群，然后让它这样一代代的繁衍、变异和淘汰下去，到最后终止我们就会获得一个惊喜的结果：（这回是完整的了，图片下的数字表示这个扇贝是第几代中最好的）