How to "crossover" two strings (1234 & abcd -> 12cd & ab34)

Question

Am developing a genetic algorithm in Java, that like all of them, requires the crossover of two parent chromosomes. These chromosomes can be quite long, anywhere from 30 to 500 (but whatever length they have, they will all be the same size, so if the length is 80, in that GA run all will be 80).

I thought of developing in different ways but they all just seem to me like very inefficient, so I thought I might ask for new, different points of view and suggestions.

For example, one of the ways I thought was of converting the string to an array of characters and iterating from the start point to the end of the crossover locus (ie from s1 & s2[25] to s1 & s2[40]) copying into temporal arrays each of the arrays characters between those points and then iterating again and swapping them with the characters from the temporal array of the "partner". But like I said it seems like for a program that will have a population of about 1000 chromosomes and with around 1000 generations will be extremely slow.

---

Here is an illustration of what two-point crossover looks like:

---

There is also the easier one point crossover:

---

As am not very advanced at all in Java could you advice me on what approach to take, maybe a Java function am unaware of, or some algorithm that I could implement?

Answer 1

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

Answer 2

Constructing a substring of a String is pretty cheap, since it does not involve actually copying the underlying data. You could do something like this:

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

It might be faster to use a dedicated StringBuilder rather than rely on the one that is implicitly created and used for each string concatenation. You'd just need to set its size to 0 each time through.

Answer 3

2 point crossover is the same as repeated 1 point crossover. (assuming you dont pick the same crossover point twice!) Keeping this in mind it is easy to do an n-point crossover algorithm, just loop n times performing single point crossover.

Add this observation to Teds answer and you can keep things simple and powerful :)

NWS.