c - 遗传算法二进制编码负整数

Question

我正在尝试实现遗传算法以最大化 n 个整数变量 x1..xn 的函数，其中每个变量都属于范围 [-n, n]。我正在考虑使用二进制编码来表示染色体，但我不确定如何编码负整数。我已经搜索了很长时间，但我还没有遇到二进制编码的通用公式。对于遗传算法，在 [-n,n] 范围内编码整数的最常见方法是什么？我希望交叉和突变具有更少的复杂性（更少的条件检查）。如果对于初始种群，而不是生成 -n 和 n 之间的数字，而是生成从 0 到 2n 的数字并将它们编码为二进制，然后在解码时，我每次减去 n（对于每个后续代），它会起作用吗？

Answer 1

user1765444 的回答很有意义......我刚刚阅读了 sashkello 的建议（使用偏移二进制文件将消除在 GA 内使用带符号整数的麻烦）。那样做交叉和变异等会很容易 - 使用 shashkello 和 user1765444 的答案的组合。问题是如果您的数据类型的宽度大于您的范围，那么交叉可能会产生无效的子代。

假设 int32 具有您需要的宽度。然后是 int32 数组 [n]。您知道有 32n 位，因此您可能会在随机 m 处取一个交叉点，其中 m >=0 且 m < 32n。您知道位 m 出现在数组 [m/n] 中，位位置 m%n 从 msb 开始（想象数组只是一个长二进制字符串）。

然后说你有 2 个父母 int32 parent1[n] 和 int32 parent2[n]。类似于下面的伪代码？在这个交叉中，为了交叉，字符串只是一个二进制字符串（即符号位被视为另一个位）......

免责声明：对不起，下面的代码是粗略的，未编译的，所以可能包含错误......只是一个想法！

int child1[n];
uint32 m = rand_like_func(); // random cross over point, a bit position
                             // in the binary string of length n*32;
uint32 arraySlotForCrossOvr = (uint32)(m / n);
uint32 bitInSlotForCrossOvr = 31 - m % n;
uint32 maskForCrossOvrP2 = (1 << bitInSlotForCrossOvr) - 1;
uint32 maskForCrossOvrP1 = ~maskForCrossOvrP2;

// crossover to create child 1
memcpy(child1, parent1, arraySlotForCrossOvr);
child1[arraySlotForCrossOvr] = 
    (int32)( ((uint32)parent1[arraySlotForCrossOvr] & maskForCrossOverP1) |
             ((uint32)parent2[arraySlotForCrossOvr] & maskForCrossOvrP2) )
memcpy(
    child1, 
    parent2 + arraySlotForCrossOvr + 1, 
    total_num_slots - arraySlotForCrossOvr);

然后您可能必须检测超出范围的孩子，或者让超出范围的孩子在下一轮中得分为零。也许您可以通过一些智能来增加交叉，例如将无效值限制为最接近的有效值等？

希望有帮助吗？

此外，我发现“如何解决它：Z. Michalewicz 和 D Fogel 的现代启发式”在尝试理解问题的编码等时非常有用：)