Cross-over is failing binary encoded string

Question

I am implementing Genetic Algorithm (GA). There are 43 numbers [Ambulance Locations] to choose from (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39) , I choose 3 places since I have 3 ambulances.

I can only put my ambulance in 3 locations among 1-39 locations (Restriction).

A chromosome sample: [000010000000000000100000000000100000000]. This represents that I want to put my Ambulance on the 5th, 19th, and 31 positions. The bits against positions 5th, 19th, and 31 are 1 and rest positions are 0. In other words, I am turning on 5-bit, 19-bit, and 31-bit.

Let's say

Parent1 (111000000000000000000000000000000000000) 

and

Parent2 (000000000000000000000000000000000000111)

After a cross-over, I am getting this:

('111000000000000000000000000000000000111', '000000000000000000000000000000000000000')

In the first off-spring, I have six 1's and in the second off-spring, I have Zero 1's. These generated off-springs are illegal for me since I need off-springs string with three 1's only.

I am using one-point cross-over. This is my code:

from typing import Union
import random

Parent 1 ="111000000000000000000000000000000000000"
Parent 2 ="000000000000000000000000000000000000111"


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:]

crossover(Cs1,Cs2)

What can be a good approach to perform cross-over while keeping3 bits among 1-39 bits?

Answer 1

IIUC, you want to mix the two parents randomly, keeping exactly 3 '1's?

You can get the indices of the 1s in each parent and select them randomly:

import random

Parent1 ="111000000000000000000000000000000000000"
Parent2 ="000000000000000000000000000000000000111"

def indices(s):
    return {i for i,c in enumerate(s) if c=='1'}

def crossover(p1, p2, k=3):

    idx = set(random.sample(list(indices(p1) | indices(p2)), k=k))

    return ''.join('1' if i in idx else '0' for i in range(len(p1)))

out = crossover(Parent1, Parent2, k=Parent1.count('1'))
# '110000000000000000000000000000000000100'

If you want to give more weight to a position that is 1 in both strings, you can modify the above to use a Counter in place of a set:

import random
from collections import Counter

Parent1 ="111000000000000000000000000000000000000"
Parent2 ="000000000000000000000000000000000000111"

def indices(s):
    return Counter(i for i,c in enumerate(s) if c=='1')

def crossover(p1, p2, k=3):

    # count the number of 1 per position
    pool = indices(p1) | indices(p2)
    
    # randomly select indices
    # using the counts as weights
    idx = set(random.sample(list(pool),
                            counts=pool.values(),
                            k=k))

    return ''.join('1' if i in idx else '0' for i in range(len(p1)))

out = crossover(Parent1, Parent2, k=Parent1.count('1'))
# '010000000000000000000000000000000000101'

shuffle the bits between two offsprings:

using set operations

import random

def indices(s):
    return {i for i,c in enumerate(s) if c=='1'}

def crossover(p1, p2):
    # get positions of 1s for each string
    idx1 = indices(p1)
    idx2 = indices(p2)
    
    # positions that are different in both strings
    differ = idx1.symmetric_difference(idx2)
    # identical positions
    common = idx1&idx2
    
    # pick half of the different positions randomly
    select = set(random.sample(list(differ), k=len(differ)//2))
    
    # offspring 1 get those positions + the common ones
    select1 = select | common
    # offstring 2 gets the other positions + the common ones
    select2 = (differ-select) | common
    
    # make strings from the selected positions for each offspring
    out1 = ''.join('1' if i in select1 else '0' for i in range(len(p1)))
    out2 = ''.join('1' if i in select2 else '0' for i in range(len(p1)))
    
    return out1, out2
    
crossover(Parent1, Parent2)

example output:

('101000000000000000000000000000000000001',
 '010000000000000000000000000000000000110')