如何“交叉”两个字符串(1234&abcd – > 12cd&ab34)
我正在开发一种Java中的遗传算法,就像所有这些算法一样,它需要两条父染色体的交叉。 这些染色体可以很长,从30到500不等(但无论它们长度如何,它们都将具有相同的大小,因此如果长度为80,则GA运行中的全部将为80)。
我想以不同的方式发展,但他们在我看来都非常低效,所以我想我可能会要求新的,不同的观点和建议。
例如,我认为的方法之一是将字符串转换为字符数组并从交叉轨迹的起点到终点迭代(即从s1 & s2[25]
到s1 & s2[40]
)复制将这些点之间的每个数组字符转换为时间数组,然后再次迭代并使用“伙伴”的时间数组中的字符交换它们。 但就像我说的那样,一个拥有大约1000条染色体并且大约1000代的人群的计划似乎非常缓慢。
以下是两点交叉的图示:
还有一个更简单的点交叉:
因为在Java中根本不是很先进,你可以建议我采取什么方法,可能是一个我不知道的Java函数,或者我可以实现的一些算法?
// chromosomes String s1; String s2; // crossovers String c1; String c2; Random r = new Random(); // get 2 random indices int ind1 = r.nextInt(s1.length()); int ind2 = r.nextInt(s1.length()); // make sure ind2 > ind1... leaving this part out; // break both strings into parts like in your picture String s1part1 = s1.substring(0, ind1); String s1part2 = s1.substring(ind1, ind2); String s1part3 = s1.substring(ind2); String s2part1 = s2.substring(0, ind1); String s2part2 = s2.substring(ind1, ind2); String s2part3 = s2.substring(ind2); // combine the parts c1 = s1part1 + s2part2 + s1part3; c2 = s2part1 + s1part2 + s2part3;
构造String的子字符串非常便宜,因为它不涉及实际复制底层数据。 你可以这样做:
String nextS1 = s1.substring(0, halfLength) + s2.substring(halfLength); String nextS2 = s2.substring(0, halfLength) + s1.substring(halfLength);
使用专用的StringBuilder可能会更快,而不是依赖于隐式创建并用于每个字符串连接的StringBuilder。 你只需要每次都将其大小设置为0。
2点交叉与重复1点交叉相同。 (假设你没有选择相同的交叉点两次!)记住这一点很容易做一个n点交叉算法,只需循环n次执行单点交叉。
将此观察添加到Teds答案,您可以保持简单和强大:)
NWS。