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

-1

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

来源

2013-04-22 vjain27

不知道这会有所帮助，但你可以存储编码时真的很有帮助二进制补码形式的数字 – jg943 2013-04-22 22:45:39

编码[-n，n]和[0,2n]之间的区别是什么？我想这不应该是...... – sashkello 2013-04-22 22:53:00

C会为你做字节编码，我期望。 – flup 2013-04-22 23:11:38

user1765444的回答很有意义......我刚刚读了sashkello的建议（使用偏移二进制将消除与GA内签名的int进行绑定）。做交叉和变异等等会很容易 - 使用shashkello's和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福格尔现代启发式”试图了解的问题等等:)

来源

2013-04-22 23:25:37 Jimbo

感谢您的解释。但就编码而言，我应该生成从0到2n的数字，然后在解码时从它们中减去n？ – vjain27 2013-04-23 01:08:21

我可能会去2n实施。然后你在处理未签名的同时进行稍微更友好的位操作。例如。如果您右移一个签名数量的结果可能不会很好定义（http://stackoverflow.com/questions/7622/shift-operator-in-c） – Jimbo 2013-04-23 06:23:11

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

回答

相关问题