6

我正在尝试实现一个遗传算法来计算Rastrigin 函数的最小值，但我遇到了一些问题。
我需要将染色体表示为二进制字符串，并且 Rastrigin 的函数将数字列表作为参数，如何将染色体解码为数字列表？
Rastrigin 还希望列表中的元素为 -5.12<=x(i)<=5.12 如果我生成染色体时会产生不在该区间内的数字，会发生什么情况？

4

5 回答 5

7

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

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

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

现在，我们已经谈到了实现的东西，你对 GA 的理解清楚了吗？如果没有，请参考这篇教程，它从优化的角度介绍了 GA。请注意，二进制编码 GA 的交叉和变异的解释不会自动转移到实编码 GA。Real coded GA 有其自身的复杂性，您需要时间阅读一些论文并理解它们。不用着急，但只要全力以赴，您应该能够轻松上手。

于 2010-02-02T06:22:14.903 回答
3

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

至于限制值，当您生成人口的初始成员时，请确保随机数在您需要的范围内。限制您的变异运算符以避免产生超出此范围的值（您可以截断超出此范围的值，也可以让它们环绕）。

如果您真的必须使用二进制字符串，请查看Gray Code，这是一种将数值编码为二进制的方式，使它们更易于变化。

于 2010-02-01T20:39:45.103 回答
1

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

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

于 2011-11-15T12:43:49.607 回答
0

我假设您正在使用 C 编程。整数（C 语言的 int）可以打包为 4 字节/字符（32 位）的数组。所以如果你的数组是

char* chrom_as_bytes=(...)

您可以通过转换为 int* 来获得第 i 个值

int ith=3;
value=((int*)chrom_as_bytes)[ith];

如果一个值不在 -5.12<x<5.12 的范围内，那么你的 fitness 函数应该返回一个非常糟糕的值，并且进化中的这一步应该在下一代被丢弃。

另请参阅Wikipedia中的文章。

于 2010-02-01T20:39:23.233 回答
0

如果您有兴趣，我已经使用 Pyevolve 完成了一个实现：http://pyevolve.sourceforge.net/examples.html#example-7-the-rastringin-function 抱歉 名称中的拼写错误。

于 2010-03-08T18:18:08.860 回答