logo标签列表

遗传算法

mathematical-optimizationgenetic-algorithm
6
我正在尝试实现一个遗传算法，用于计算Rastrigin函数的最小值，但是我遇到了一些问题。
我需要将染色体表示为二进制字符串，而由于Rastrigin函数需要将数字列表作为参数，因此如何将染色体解码为数字列表呢？
此外，Rastrigin希望列表中的元素为-5.12 <= x(i) <= 5.12，如果生成的染色体产生不在该区间内的数字会怎样呢？
5个回答
7
你希望实现一种遗传算法。你的实现应该适用于任何通用的最小化（或最大化）问题，而不仅仅是Rastrigin函数。你可以决定实现二进制编码GA或实数编码GA。两者都有其自己的用途和细分应用。但对于你来说，我建议你实现一个实数编码GA。关于如果生成的变量值超出[-5.12:5.12]应该怎么办的问题，实数编码GA和二进制编码GA会以不同的方式处理它们。
在开始实现自己的版本之前，拥有参考代码总是很好的。如果你正在寻找C实现，实验室的源代码部分有一个广泛用于我们和其他人研究工作的实数编码GA实现。我建议你玩一下它，并尝试解决其中一些简单的优化问题。 Pyevolve是一个用于遗传算法和遗传编程的Python库。
现在，我们已经讨论了实现相关的内容，你对GA的理解清晰了吗？如果不清楚，请参考tutorial，该教程从优化的角度介绍了GA。请注意，针对二进制编码的GA的交叉和变异的解释并不能自动转移到实数编码的GA。实数编码的GA有其自身的复杂性，您需要花时间阅读一些论文并理解它们。不要着急，但只要全力以赴，您应该能够轻松上手。
3
为什么需要将染色体表示为二进制字符串？您可以编写使用其他类型的进化算法。您可以使用数字列表。
至于限制值，当您生成人口的初始成员时，请确保随机数在所需范围内。限制变异运算符以避免产生超出此范围的值（您可以截断超出此范围的值，或者使它们环绕）。
如果您确实需要使用二进制字符串，请查看格雷码，这是一种将数字值编码为二进制的方法，使其更易于突变。
处理约束（例如将值限制在某些范围内），使用包装或截断很可能会破坏优化，因为它基本上添加了强噪声...罚款方案（向适应度添加与约束违规成比例的罚款）将使事情更加优雅。如果您真的不想有任何违规行为，您可以重新采样，即重试突变，直到生成的个体不违反任何约束为止。 - Monkey
1
将实值问题的编码解决方案作为位串并不是正确的方法。当您使用数字作为位串时，您正在使用定点数来表示数字。一旦您的算法接近最优解，达到了定点编码的精度，它就不会再有进展了。您可以使用更多的位数，但这样会导致收敛速度变慢。在实践中，对于严重的问题，这种方法比使用浮点值的有效算法慢几个数量级。
使用浮点数可以让您在使用典型的64位数字的情况下更接近最优解，例如1e-10。此外，现代进化算法使用自适应方案来调整优化过程中的突变步骤。与固定突变步骤相比，这种机制可以提高收敛速度。请查看此链接以了解Rastrigin函数上典型进化优化器的表现：http://coco.gforge.inria.fr/doku.php?id=bbob-2010
0

我假设你正在使用C语言进行编程。整数（C语言中的int）可以被打包成一个由4个字节/字符（32位）组成的数组。 因此，如果你的数组是

char* chrom_as_bytes=(...)

你可以通过将其转换为int*来获取第i个值

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

如果一个值不在范围-5.12
另请参阅维基百科中的文章。
在遗传算法中，当给定参数值的一段范围时，通常的做法（依我之见）是在初始种群中就要注意，即确保我的初始种群包含符合分配范围的变量。在交叉和变异操作期间，如果超过了范围，那么有多种处理方式。您所建议的是“惩罚”方法，对吧？ - user59634
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接