通过神经网络和/或强化学习提升我的GA

Question

正如我在之前的问题中提到的,我正在写一个迷宫求解应用程序,以帮助我学习更多的理论CS科目,经过一些麻烦,我有一个遗传算法工作,可以发展一组规则(由布尔值处理)按顺序通过迷宫找到一个好的解决方案.

话虽这么说,GA本身还可以,但我想用神经网络来加强它,即使我没有神经网络的真正工作知识(没有正式的理论CS教育).在对该主题进行了一些阅读后,我发现可以使用神经网络来训练基因组以改善结果.假设我有一个基因组(一组基因),比如

1 0 0 1 0 1 0 1 0 1 1 1 0 0...

我如何使用神经网络(我假设MLP？)来训练和改善我的基因组？

除此之外,因为我对神经网络一无所知,我一直在研究使用我的迷宫矩阵(二维数组)来实现某种形式的强化学习,尽管我对以下算法想要的东西有点困惑:

(来自http://people.revoledu.com/kardi/tutorial/ReinforcementLearning/Q-Learning-Algorithm.htm)

1.  Set parameter , and environment reward matrix R
   2. Initialize matrix Q as zero matrix
   3. For each episode:
          * Select random initial state
          * Do while not reach goal state
                o Select one among all possible actions for the current state
                o Using this possible action, consider to go to the next state
                o Get maximum Q value of this next state based on all possible actions
                o Compute
                o Set the next state as the current state

  End Do

  End For 

对我来说最大的问题是实现奖励矩阵R和Q矩阵究竟是什么,并获得Q值.我为我的迷宫使用多维数组,并为每次移动使用枚举状态.如何在Q-Learning算法中使用它？

如果有人可以通过解释我需要做什么来帮助实现以下内容,最好是在Java中,尽管C#也会很好,可能有一些源代码示例,我们将不胜感激.

Answer 1

正如一些评论中指出的那样，您的问题确实涉及大量的背景知识和主题，而这些背景知识和主题在 stackoverflow 上几乎无法雄辩地涵盖。但是，我们在这里可以尝试建议解决您的问题的方法。

首先：你的 GA 是做什么的？我看到一组二进制值；这些是什么？我认为它们是：

• bad：一系列“右转”和“左转”指令。为什么这样不好？因为你基本上是在随机地、强力地尝试解决你的问题。你不是在进化基因型：你是在完善随机猜测。
• 更好：每个基因（基因组中的位置）代表将在表型中表达的特征。基因组和表型之间不应该存在一对一的映射！

让我举个例子：我们的大脑中有 10^13 个左右的神经元。但我们只有大约 10^9 个基因（是的，这不是一个确切的值，请耐心等待）。这告诉我们什么？我们的基因型并不编码每个神经元。我们的基因组编码蛋白质，然后这些蛋白质将构成我们身体的组成部分。

因此，进化通过选择表型特征直接作用于基因型。如果我每只手都有 6 个手指，如果这会让我成为一个更好的程序员，让我有更多的孩子，因为我在生活中更成功，那么我的基因型将被进化选择，因为它包含以下能力：给我一个更健康的身体（是的，这里有一个双关语，考虑到这里大多数人的平均极客与可重复性比率）。

现在，想想你的 G​​A：你想要实现什么目标？您确定不断发展的规则会有帮助吗？换句话说——你在迷宫中会表现如何？对你有帮助的最成功的事情是什么：拥有不同的身体，还是拥有正确的逃生之路的记忆？也许您可能想重新考虑您的基因型并让它编码记忆能力。也许可以在基因型中编码可以存储多少数据，以及代理访问数据的速度有多快，然后根据他们走出迷宫的速度来衡量适应性。另一种（较弱的）方法可能是对代理用来决定去哪里的规则进行编码。最重要的信息是，对特征进行编码，一旦表达出来，就可以通过适应度来选择。

现在，谈谈神经网络问题。要记住的一件事是，神经网络是过滤器。他们收到输入。对其执行操作并返回输出。这个输出是什么？也许你只需要区分真/假条件；例如，一旦你将迷宫地图输入神经网络，它就可以告诉你是否可以走出迷宫。你会怎么做这样的事？您需要对数据进行正确编码。

这是神经网络的关键点：您的输入数据必须正确编码。通常人们会对其进行标准化，也许对其进行缩放，也许您可​​以对其应用西格玛函数以避免值太大或太小；这些是处理错误测量和性能的细节。您现在需要了解什么是神经网络，以及不能用它做什么。

现在解决你的问题。您提到您也想使用神经网络：怎么样，

• 使用神经网络来指导代理，以及
• 使用遗传算法来进化神经网络参数？

改写如下：

• 假设您有一个机器人：您的神经网络正在控制左右轮，并且作为输入，它接收下一堵墙的距离以及它到目前为止已经行驶了多少距离（这只是一个例子）
• 你首先生成一个随机基因型
• 将基因型转化为表型：第一个基因是网络敏感性；第二个基因编码学习率；第三个基因......依此类推
• 现在您已经有了神经网络，请运行模拟
• 看看它的表现如何
• 生成第二个随机基因型，进化第二个神经网络
• 看看第二个人的表现如何
• 获得最好的个体，然后要么突变其基因型，要么与失败者重新组合
• 重复

这里有一篇关于这个问题的优秀读物： Inman Harvey Microbial GA。

我希望我能为您提供有关此类问题的一些见解。神经网络和遗传算法并不是解决所有问题的灵丹妙药。在某些方面它们可以做很多事情，但在另一些方面它们只是错误的工具。（仍然！）取决于我们来获得最好的，为此我们必须很好地理解它们。

玩得开心！很高兴知道这些事情，让日常生活变得更有趣:)