c - 遗传算法使用哪种编码？

Question

我想用 C 编写一个遗传算法来优化 10 个变量（x1 到 x10）的函数。但是我无法弄清楚我应该使用哪种编码。我经常看到示例中使用了二进制编码，但在我的例子中，变量可以取实值。此外，对于这些类型的问题，值编码是一个不错的选择吗？

Answer 1

对于真正有价值的问题，我建议尝试 CMA-ES 或其他 ES 变体。CMA-ES 无疑是实值问题的当前最先进技术。它旨在快速找到多维问题的良好解决方案。Hansen 的页面上有可用的实现。HeuristicLab的工作中还有一个 C# 实现. 进化策略是专门为实值优化问题设计的算法。它们与遗传算法非常相似（两者都是在同一时间发明的，但在不同的地方）。主要区别在于，对于 ES，主要驱动因素是突变，它具有对突变强度的巧妙适应。没有这种适应，（局部）最优值就不能及时定位。CMA-ES 易于配置，它所需要的只是初始标准偏差和可选的总体规模（否则有一个公式可以根据问题规模来估计这一点）。

当然也可以应用遗传算法，但是您必须使用一些特定的运算符，这些运算符只能以非常小的程度改变变量。例如，有来自 Mühlenbein 的育种者遗传算法。然而，一般而言，遗传算法更适合需要正确组合事物的问题。例如，背包问题中要包括哪些项目，或者哪些功能和终端要结合到一个公式中（遗传编程）。更少的问题，你需要为某事找到正确的价值。虽然当然有遗传算法的变体来解决这些问题，但请寻找实数编码遗传算法（RCGA 或 RGA）。

另一种适用于实值问题的算法是粒子群优化，但我认为它更难配置。我将从SPSO-2011开始，即 2011年标准 PSO。

如果您的问题包含整数变量，则选择变得更加困难。当变量是离散的时，进化策略表现不佳，因为整数变量的适应方案不同。遗传算法再次成为有趣的首选算法。

Answer 2

当两个非常接近最优的答案组合起来会使其他答案非常接近最优时，最好使用遗传算法。纯二进制编码的问题在于，如果您不检查交叉点，您最终会得到两个答案，这可能与原始答案没有太大关系。

也就是说，只有当您的变量数量非常少并且变量中的数据量很大时，这才是真正的问题。至于选择编码，它更像是一门艺术而不是一门科学，这取决于你的问题。我建议使用适合您想要的精度的编码。使用 10 个变量，无论您如何编码，都不会出错，一个 8 位 ASCII 编码器可能工作得很好。

希望有帮助。