遗传算法
我正在尝试实现一种遗传算法，该算法将计算 Rastrigin 函数的最小值 我遇到了一些问题。
我需要将染色体表示为二进制字符串，并且 Rastrigin 函数将数字列表作为参数，如何将染色体解码为数字列表？
另外 Rastrigin 希望列表中的元素为 -5.12<=x(i)<=5.12 如果当我生成染色体时它将产生不在该区间内的数字，会发生什么？
I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues.
I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of numbers?
Also the Rastrigin's wants the elements in the list to be -5.12<=x(i)<=5.12 what happens if when i generate the chromosome it will produce number not in that interval?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您正在寻求实施遗传算法。您的实现应该适用于任何通用的最小化（或最大化）问题，而不仅仅是 Rastrigin 函数。您可以决定实现二进制编码 GA 或实数编码 GA。两者都有自己的用途和利基应用。但对于你来说，我建议实现一个真实编码的遗传算法。根据您关于该怎么做的问题，如果生成的变量值超出 [-5.12:5.12]，实数编码的 GA 和二进制编码的 GA 将以不同的方式处理它们。
在开始实现自己的版本之前，拥有参考代码总是好的。如果您正在寻找 C 实现，实验室的源代码部分有一个 Real编码 GA 实现，被我们和其他人广泛用于我们的研究工作。我建议您使用它并尝试其中给出的一些简单的优化问题。
Pyevolve 是一个用于遗传算法和遗传编程的 Python 库。
现在，我们已经讨论了实现方面的内容，您对 GA 的理解清楚了吗？如果没有，请参考这个教程，其中介绍了 GA优化的角度。请注意，二进制编码 GA 的交叉和变异的解释不会自动转移到真实编码 GA。真正的编码遗传算法有其自身的复杂性，您需要时间阅读一些论文并理解它们。不着急，但只要全力以赴，您应该能够轻松上手。
You are looking to implement a Genetic Algorithm. Your implementation should be such that it works for any generic minimization (or maximization) problem, and not only the Rastrigin function. You may decide to implement a binary coded GA or a Real coded GA. Both has its own uses and niche applications. But for you, i would suggest to implement a Real coded GA. As per your question regarding what to do, if the generated variable values are outside of [-5.12:5.12], a Real coded GA and binary coded GA will handle them differently.
Having a reference code is always good before you start implementing your own version. If you are looking for a C implementation, the source section of lab has a Real Coded GA implementation, which is widely used by us and others for our research work. I would suggest you to play with it and try out some of the simple optimization problems given there.
Pyevolve is a Python library for Genetic Algorithms and Genetic Programming.
Now, that we have talked about the implementation stuff, is your GA understanding clear? If not, please refer to this tutorial, which introduces GA from a optimization point of view. Please note that the explanation of crossover and mutation for a Binary Coded GA do not automagically transfer to a Real Coded GA. Real coded GA has its own intricacies, which you will need time to read some papers and understand them. No hurries, but with full time effort you should be able to get going easily.
为什么需要将染色体表示为二进制字符串？您可以编写使用其他类型的进化算法。您可以使用数字列表。
至于限制值，当您生成总体的初始成员时，请确保随机数在您需要的范围内。限制突变运算符以避免产生超出此范围的值（您可以仅截断超出此范围的值，也可以让它们环绕）。
如果您确实必须使用二进制字符串，请查看 格雷码，它是一种以二进制编码数值的方法，使它们更容易发生突变。
Why do you need to represent the chromosome as a binary string? You can write evolutionary algorithms that use other types. You could use a list of numbers.
As for restricting the values, when you generate the initial members of the population ensure that the random numbers are within the range that you need. Restrict your mutation operator to avoid producing values outside of this range (you could either just truncate values that are outside this range, or you could have them wrap around).
If you really have to use a binary string, take a look at Gray Code, which is a way of encoding numeric values in binary making them more amenable to mutations.
将实值问题的解决方案编码为位串并不是真正的正确方法。当您将数字作为位字符串时，您将使用定点数来表示数字。一旦您的算法接近最佳值，达到定点编码的精度，它将不再有进一步的进展。您可以使用更多位，但收敛速度会变慢。实际上，在解决严重问题时，这种方法比处理浮点值的有效算法慢几个数量级。
使用浮点数可以让您更接近最佳值，例如 1e-10，同时使用典型的 64 位数字。此外，现代进化算法在优化过程中使用自适应方案来调整突变步长。与固定突变步骤相比，这种机制可以实现更快的收敛速度。看看这个，看看典型的进化优化器在 Rastrigin 函数上实现了什么：http:// /coco.gforge.inria.fr/doku.php?id=bbob-2010
Coding solutions of a real-valued problems as a bit-string is not really the way to go. When you got numbers as bit strings, you are using fixed-point numbers to represent the numbers. Once your algorithm will be close to the optimum, up to the precision of your fixed point encoding, it will do no further progress. You can use either more bits, but then you will have slower convergence. In practice, on serious problems, such an approach is several orders magnitude slower than a competent algorithm working on floating point values.
Use floating point numbers would allow you to go much closer to the optimum, say 1e-10, while using your typical 64 bits numbers. Moreover, modern evolutionary algorithm use adaptive scheme to adjust the mutation step during the optimization. Such mechanism allow for greater convergence speed, compared to a fixed mutation step. Checkout this to see what typical evolutionary optimizers achieve on the Rastrigin function : http://coco.gforge.inria.fr/doku.php?id=bbob-2010
我假设您正在使用 C 进行编程。整数（C 语言中的 int）可以打包为 4 个字节/字符（32 位）的数组。
因此，如果你的数组是
你可以通过转换为 int* 来获取第 i 个值，
如果一个值不在 -5.12
另请参阅维基百科中的文章。
I assume you're programming in C. Integers (int for the C language) can be packed as an array of 4 bytes/char (32 bits).
so if your array is
your can get the i-th value by casting to int*
if a value is not in the range -5.12<x<5.12 than, your fiteness function should return a very bad value and this step in the evolution should be discarded at the next generation.
See also the article in Wikipedia.
如果您有兴趣，我已经使用 Pyevolve 完成了一个实现：
http://pyevolve.sourceforge.net/examples.html#示例 7-rastringin 函数
抱歉，名称中有拼写错误。
If you're interested, I've done an implementation using Pyevolve:
http://pyevolve.sourceforge.net/examples.html#example-7-the-rastringin-function
Sorry for the typo in the name.