遗传算法

Question

我正在尝试实现一个遗传算法，它将计算Rastrigin functon的最小值，但我遇到了一些问题。

我需要将染色体表示为二进制字符串，并且由于Rastrigin函数以数字列表作为参数，如何将染色体解码为数字列表？

Rastrigin还希望列表中的元素是-5.12<=x(i)<=5.12，如果当我生成染色体时，它会产生不在该间隔内的数字，会发生什么？

Answer 1

您正在寻求实现一个遗传算法。您的实现应该适用于任何通用最小化(或最大化)问题，而不仅仅是Rastrigin函数。您可以决定实现二进制编码的GA或实数编码的GA。两者都有自己的用途和利基应用。但对你来说，我建议实现一个真正的编码GA。根据你关于如何处理的问题，如果生成的变量值在-5.12:5.12之外，实数编码的GA和二进制编码的GA将以不同的方式处理它们。

在开始实现自己的版本之前，有一个参考代码总是很好的。如果你正在寻找一个C实现，实验室的source section有一个实数编码的GA实现，它被我们和其他人广泛用于我们的研究工作。我建议您试用它，并尝试那里给出的一些简单优化问题。

Pyevolve是一个用于遗传算法和遗传编程的Python库。

现在，我们已经讨论了实现的东西，你的GA理解清楚了吗？如果没有，请参考这个tutorial，它从优化的角度介绍了GA。请注意，二进制编码遗传算法的交叉和变异解释不会自动转换为实数编码遗传算法。真正的编码遗传算法有它自己的复杂性，你需要时间阅读一些论文并理解它们。不着急，但只要全心全意努力，你就能轻松上手。

Answer 2

为什么需要将染色体表示为二进制字符串？您可以编写使用其他类型的进化算法。你可以使用一个数字列表。

至于限制值，在生成种群的初始成员时，请确保随机数在所需的范围内。限制您的变异操作符，以避免产生超出此范围的值(您可以只截断此范围之外的值，也可以让它们绕回)。

如果您真的必须使用二进制字符串，请看一下Gray Code，这是一种用二进制编码数值的方法，使它们更容易发生突变。

Answer 3

将实值问题的解决方案编码为位串并不是真正可行的方法。当你以位串的形式获取数字时，你就是在使用定点数字来表示数字。一旦你的算法接近最优，达到定点编码的精度，它就不会有进一步的进展。你可以使用更多的位，但是你会有更慢的收敛速度。在实践中，在严重的问题上，这种方法比处理浮点值的合格算法慢几个数量级。

使用浮点数将允许您更接近最优值，例如1e-10，同时使用典型的64位数字。此外，现代进化算法在优化过程中采用自适应策略来调整变异步长。与固定的变异步骤相比，这种机制允许更快的收敛速度。看看典型的进化优化器在Rastrigin函数上实现了什么：http://coco.gforge.inria.fr/doku.php?id=bbob-2010