Кроссовер со строковыми кодированными хромосомами

ОП вопрос

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

Предоставленное решение является динамическим и будет работать для хромосом любой длины с любым количеством перевернутых битов (1).

import random
from typing import Union
def crossover(cs1: str, cs2: str) -> Union[str, str]:
    if len(cs1) != len(cs2):
        raise Exception("Candidate solutions input are of different length.")
    # get the flipped bits in each string
    cs1_bits = [index for index, gene in enumerate(cs1) if gene == "1"]
    cs2_bits = [index for index, gene in enumerate(cs2) if gene == "1"]
    if len(cs1_bits) != len(cs2_bits):
        raise Exception("Candidate solutions input have different number of flipped bits.")
    index: int = random.randint(0, len(cs1_bits))
    sol1_bits, sol2_bits = cs1_bits[:index] + cs2_bits[index:], cs2_bits[:index] + cs1_bits[index:]
    output_1 = ""
    output_2 = ""
    for i in range(len(cs1)):
        if i in sol1_bits:
            output_1 += "1"
        else:
            output_1 += "0"
        if i in sol2_bits:
            output_2 += "1"
        else:
            output_2 += "0"
    return output_1, output_2

Пример ввода/вывода для решения OP.

# Input
"111000000000000000000000000000000000000", "000000000000000000000000000000000000111"
# Output
'110000000000000000000000000000000000001', '001000000000000000000000000000000000110'

Как выполнить стандартный кроссовер

Вы выполняете кроссовер в генетическом алгоритме, выбирая случайный индекс по длине числа значений, в вашем случае вы выберете значение от 0 до 38 (39 вариантов).

Затем вы разделите оба входа и соедините переднюю часть cs1 с задней частью cs2 и наоборот.

from typing import Union
import random
def crossover(cs1: str, cs2: str) -> Union[str, str]:
    index: int = random.randint(0, len(cs1))
    return cs1[:index] + cs2[index:], cs2[:index] + cs1[index:]

Если у вас есть значения:

cs1 = "111000000000000000000000000000000000000"
cs2 = "000000000000000000000000000000000000111"

Кроссинговер с индексом 1 вернет:

output_1 = "100000000000000000000000000000000000111"
output_2 = "011000000000000000000000000000000000000"

Кроссинговер с индексом 5 вернет:

output_1 = "111000000000000000000000000000000000111"
output_2 = "000000000000000000000000000000000000000"