Creating a genetic algorithm crossover function for 1:1 maps

Question

I am trying to implement a crossover function for a genetic algorithm. V is a set of nodes. Just consider each node a unique string. $V_M$ and $V_F$ are each a set of nodes with no element in common. $V_M$ and $V_F$ are of the same size. Each member of the population consists of a $1:1$ mapping $f:V_M \rightarrow V_F$.

What is a reasonable way to implement a crossover function in this case?

I implement this in Python with the $1:1$ mappings being dictionaries from $V_M$ to $V_F$. A Python solution would be nice but is not necessary. A generic solution or a solution in another language would be fine, too.

I can implement single-point crossover like this:

# Crossover function
def crossover(parent1, parent2):
    # Single - point crossover
    f_values = list(parent1.values())
    random_values = random.sample(f_values, 2)
    value_1 = random_values[0]
    key_1_1 = get_key_by_value(parent1, value_1)
    value_2 = random_values[1]
    key_1_2 = get_key_by_value(parent1, value_2)
    key_2_1 = get_key_by_value(parent2, value_1)
    key_2_2 = get_key_by_value(parent2, value_2)
child1 = parent1.copy()
child1[key_1_1] = value_2
child1[key_1_2] = value_1
child2 = parent2.copy()
child2[key_2_1] = value_2
child2[key_2_2] = value_1

return child1, child2

I imagine I can implement multi-point crossover similarly.

But how can I implement uniform crossover or blend crossover?

score 0 · Answer 1 · answered Jan 04 '25 at 05:43

In uniform crossover genetic operator, each value of the key-value pair of the offspring's dictionary is randomly selected from either parent with a 50% probability.

In uniform crossover, typically, each bit is chosen from either parent with equal probability... In a uniform crossover, we don’t divide the chromosome into segments, rather we treat each gene separately. In this, we essentially flip a coin for each chromosome to decide whether or not it will be included in the off-spring.

Therefore you just need to code up a fair coin flip at each position to decide whether to swap the value of the two parents or not to generate the two offsprings. Example python code is shown below.

import random
def uniform_crossover(parent1, parent2):
    if len(parent1) != len(parent2):
        raise ValueError("Parents must have the same number of genes.")
child1 = {}
child2 = {}

for key in parent1.keys():
    if random.randint(0, 1) == 0:
        child1[key] = parent1[key]
        child2[key] = parent2[key]
    else:
        child1[key] = parent2[key]
        child2[key] = parent1[key]

return child1, child2

One example result is expected as:

# Example usage
parent1 = {'A': 1, 'B': 0, 'C': 1, 'D': 1, 'E': 0}
parent2 = {'A': 1, 'B': 1, 'C': 0, 'D': 0, 'E': 1}
child1, child2 = uniform_crossover(parent1, parent2)
print(child1)
print(child2)
{'A': 1, 'B': 1, 'C': 1, 'D': 1, 'E': 1}
{'A': 1, 'B': 0, 'C': 0, 'D': 0, 'E': 0}

In blend-$a$ crossover BLX-a) genetic operator applicable only for real-valued parents' attributes, we choose a uniform random real number from $a$-scaled interval $[\min(x_i^{(t)},y_i^{(t)})-ad_i, \max(x_i^{(t)},y_i^{(t)})+ad_i]$ for each offspring, where $x_i^{(t)},y_i^{(t)}$ are $1:1$ mapped parents' attributes, $d_i=|x_i^{(t)}-y_i^{(t)}|$, and $a$ is a positive real parameter. Example python code is shown below.

def blx_a_crossover(parent1, parent2, alpha):
    if len(parent1) != len(parent2):
        raise ValueError("Parents must have the same number of genes.")
child1 = {}
child2 = {}

for key in parent1.keys():
    x = parent1[key]
    y = parent2[key]        
    d = abs(x - y)        
    lower_bound = min(x, y) - alpha * d
    upper_bound = max(x, y) + alpha * d   
    child1[key] = round(random.uniform(lower_bound, upper_bound), 2)
    child2[key] = round(random.uniform(lower_bound, upper_bound), 2)

return child1, child2

One example result is expected as:

parent1 = {'a': 1.0, 'b': 2.0, 'c': 3.0}
parent2 = {'a': 4.0, 'b': 5.0, 'c': 6.0}
child1, child2 = blx_a_crossover(parent1, parent2, alpha=0.5)
print("Parent 1:", parent1)
print("Parent 2:", parent2)
print("child1:", child1)
print("child2:", child2)
Parent 1: {'a': 1.0, 'b': 2.0, 'c': 3.0}
Parent 2: {'a': 4.0, 'b': 5.0, 'c': 6.0}
child1: {'a': 4.87, 'b': 5.76, 'c': 3.19}
child2: {'a': 3.44, 'b': 1.18, 'c': 3.49}
```

score 0 · Accepted Answer · answered Jan 05 '25 at 19:29

def crossover(parent1, parent2):
    crossover_key = random.choice(list(parent1.keys()))  # Randomly select a crossover key
    child1 = {key: parent1[key] for key in parent1 if key < crossover_key}
    child1.update({key: parent2[key] for key in parent2 if key >= crossover_key})
    child2 = {key: parent2[key] for key in parent2 if key < crossover_key}
    child2.update({key: parent1[key] for key in parent1 if key >= crossover_key})

    return child1, child2

Creating a genetic algorithm crossover function for 1:1 maps

2 Answers2