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?
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'
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')