Как "пересечь" две строки (1234 & abcd -> 12cd & ab34)

Question

Я разрабатываю генетический алгоритм на Java, который, как и все они, требует пересечения двух родительских хромосом.Эти хромосомы могут быть довольно длинными, от 30 до 500 (но какой бы длины они ни имели, все они будут одинакового размера, поэтому, если длина равна 80, в этом прогоне GA будет все 80).

Я думал о том, чтобы развиваться по-разному, но все они кажутся мне очень неэффективными, поэтому я подумал, что могу попросить о новых, разных точках зрения и предложениях.

Например, один из способов, который я думал, былпреобразования строки в массив символов и итерации от начальной точки до конца локуса кроссовера (т. е. от s1 & s2[25] до s1 & s2[40]), копирования во временные массивы каждого из символов массивов между этими точками, а затем повторения ипоменять их местами с символами из временного массива «партнера».Но, как я сказал, похоже, что для программы, которая будет иметь популяцию около 1000 хромосом и около 1000 поколений, будет очень медленно.

---

Вот иллюстрация того, как выглядит двухточечный кроссовер:

---

ТамЭто также более простое кроссовер с одной точкой:

---

Поскольку я не очень продвинут в Java, вы можете дать мне совет, какой подход выбрать, может быть,Я не знаю функцию Java или какой-то алгоритм, который я мог бы реализовать?

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

Построение подстроки строки довольно дешево, поскольку не требует фактического копирования базовых данных. Вы могли бы сделать что-то вроде этого:

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

Возможно, будет быстрее использовать выделенный StringBuilder, а не полагаться на тот, который неявно создается и используется для каждой конкатенации строк. Вам просто нужно каждый раз устанавливать его размер на 0.

Answer 3

2-точечный кроссовер такой же, как повторный 1-точечный кроссовер. (при условии, что вы не выбираете одну и ту же точку пересечения дважды!) Помня об этом, легко сделать алгоритм пересечения n-точек, просто зацикливание n раз, выполняя пересечение в одной точке.

Добавьте это наблюдение к ответу Тедса, и вы сможете сделать вещи простыми и мощными :)

NWS.