Like a "crossover" of two lines (1234 & abcd & # 8594; 12cd & ab34)

Question

Develops a genetic algorithm in Java, which, like all of them, requires a crossover of two parent chromosomes. These chromosomes can be quite long, from 30 to 500 (but regardless of their length, they will be the same size, so if the length is 80, then for GA it is still 80).

I thought about development differently, but they all seem very ineffective to me, so I thought I could ask for new, different points of view and suggestions.

For example, one of the ways in which I thought was to convert the string to an array of characters and iterate from the start point to the end of the crossover trap (ie, from s1 & s2[25] to s1 & s2[40] ), copying into the temporary arrays each of the symbols of the array between these points, and then repeats again and replaces them with the symbols of the temporary array of the "partner". But, as I said, it seems that a program that will have about 1000 chromosomes and about 1000 generations will be very slow.

---

Here's an example of what a two-point crossover looks like:

---

There is also a simpler one-line crossover:

---

As I’m not very advanced in Java at all, could you advise me which approach to take, maybe I don’t know the Java function 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

Building a String substring is pretty cheap, as it doesn't involve actually copying the underlying data. You can 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 relying on one that is implicitly created and used for each string concatenation. You just need to set the size to 0 every time.

Answer 3

A 2-point crossover is the same as a repeated 1-point crossover. (assuming that you do not select the same intersection point twice!) With this in mind, it is easy to execute an n-point cross-conversion algorithm, just a loop performs a single-point crossover n times.

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

NWS.