如何"交叉"两个字符串(1234&abcd - > 12cd&ab34)

Question

我在Java中开发一种遗传算法,就像所有这些算法一样,需要两条父染色体的交叉.这些染色体可能很长,从30到500不等(但无论它们长度如何,它们都将具有相同的大小,因此如果长度为80,那么GA运行的全部将为80).

我想以不同的方式发展,但他们在我看来都非常低效,所以我想我可能会要求新的,不同的观点和建议.

例如,我想的方式之一是将字符串转换为字符数组和迭代从起点到交叉轨迹(即,从端部的s1 & s2[25]至s1 & s2[40])复制到颞阵列每个阵列的字符的那些点之间和然后再次迭代并使用"伙伴"的时间数组中的字符交换它们.但就像我说的那样,一个拥有大约1000条染色体并且大约1000代的人群的程序似乎非常缓慢.

---

以下是两点交叉的示例:

---

还有一个更简单的点交叉:

---

因为在Java中根本不是很先进,你可以建议我采取什么方法,可能是一个我不知道的Java函数,或者我可以实现的一些算法？

Answer 1

构造String的子字符串非常便宜,因为它不涉及实际复制底层数据.你可以这样做:

String nextS1 = s1.substring(0, halfLength) + s2.substring(halfLength);
String nextS2 = s2.substring(0, halfLength) + s1.substring(halfLength);

使用专用的StringBuilder可能会更快,而不是依赖于隐式创建并用于每个字符串连接的StringBuilder.你只需要每次都将其大小设置为0.

Answer 2

// 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;