Is there a way to aviod picking two same parents in genetic aglorithm?

Question

I'm working on selection of two parents in GA, and the problem is that when I implemented the ' tournament_selection' function, it always returns two identical parents.

The initial population is:

num_emitter_coefficients = 782
sol_per_pop_1=1
sol_per_pop_2=3
sol_per_pop=sol_per_pop_1+sol_per_pop_2   

pop_size_1 = [sol_per_pop_1, num_emitter_coefficients]
pop_size_2 = [sol_per_pop_2, num_emitter_coefficients]

initial_population_1 = np.random.uniform(low=0.0, high=0.0, size=pop_size_1)
initial_population_2 = np.random.uniform(low=0.0, high=0.0, size=pop_size_2)

for row in initial_population_2:
    locations_used_in_this_row = 0
    while locations_used_in_this_row != 5:
        column = np.random.randint(num_emitter_coefficients)
        if row[column] == 0.0:
            row[column] = np.random.rand()*10
            locations_used_in_this_row += 1

population=np.vstack([initial_population_1, initial_population_2])
print('Population: ',population)

Assuming that each individual's score is:

[44,56,63,34]

And in my project, the higher score each individual is , the lower fitness each individual has. The function of selection of parents is shown below:

def tournament_selection(population, scores, k=4):
    first_pick = np.random.randint(0,len(population))  
    for second_pick in np.random.randint(0,len(population),k-1):
        if scores[second_pick] < scores[first_pick]:
            winner = second_pick
        else:
            winner = first_pick
    return population[winner,:]

When I implemented the function,

for i in range(0, len(population),2):
    parent_1 = tournament_selection(population, scores)
    parent_2 = tournament_selection(population, scores)

it always returned two identical parents. Could you please tell me how to aviod this problem?

Maybe if I can exclude 'winner' from the population list, the problem of picking two same parents can be fixed, but I don't know how to achieve it with code, could you please give me ideas? Thanks a lot in advance.

Answer 1

I think list comprehension is your answer without any more information (I know genetic analyses can get cumbersome).

I've added list comprehension at the start of your function to filter out previous winners from your main list. Bear in mind that the .index() will only select the first occurrence within the list, so if you have long lists with possible duplicates you will need another way to

import numpy as np

num_emitter_coefficients = 782
sol_per_pop_1=1
sol_per_pop_2=3
sol_per_pop=sol_per_pop_1+sol_per_pop_2   

pop_size_1 = [sol_per_pop_1, num_emitter_coefficients]
pop_size_2 = [sol_per_pop_2, num_emitter_coefficients]

initial_population_1 = np.random.uniform(low=0.0, high=0.0, size=pop_size_1)
initial_population_2 = np.random.uniform(low=0.0, high=0.0, size=pop_size_2)

for row in initial_population_2:
    locations_used_in_this_row = 0
    while locations_used_in_this_row != 5:
        column = np.random.randint(num_emitter_coefficients)
        if row[column] == 0.0:
            row[column] = np.random.rand()*10
            locations_used_in_this_row += 1

population=np.vstack([initial_population_1, initial_population_2]).tolist()

prevwinner = []

scores = [44,56,63,34]

def tournament_selection(population, scores, k=4):
    # filter previous winners out
    selectable_parents = [nonwinner for nonwinner in population if nonwinner not in prevwinner]
    if len(selectable_parents) > 1:
        first_pick, second_pick = np.random.randint(len(selectable_parents), size=2)
        first_pick_score = scores[population.index(selectable_parents[first_pick])]
        while second_pick == first_pick:
            second_pick = np.random.randint(0,len(selectable_parents))
        second_pick_score = scores[population.index(selectable_parents[second_pick])]
        if second_pick_score < first_pick_score:
            winner = second_pick
            loser = first_pick
        else:
            winner = first_pick
            loser = second_pick

        # append winner to prevwinner list
        prevwinner.append(population[population.index(selectable_parents[winner])])
        prevwinner.append(population[population.index(selectable_parents[loser])])
        return population[population.index(selectable_parents[winner])], population[population.index(selectable_parents[loser])]
    else: 
        # there is one parent left
        return selectable_parents[0]

for i in range(0, len(population),2):
    parent_1, parent_2 = tournament_selection(population, scores)
    print('parent_1: ', np.unique(np.array(parent_1)))
    print('parent_2: ', np.unique(np.array(parent_2)))

Answer 2

Instead of randomly selecting from the population twice, you should use np.random.choice with replace=False instead.

But seemingly random.choice in numpy only supports 1-D arrays, so you'll have to use the size argument in np.random.randint. See Numpy: Get random set of rows from 2D array

import numpy as np

population= [[0., 1., 0., 0., 0., 0.],
             [0., 0., 0., 0., 1., 0.],
             [0., 0., 1., 0., 0., 0.],
             [0., 0., 0., 1., 0., 0.]]

parent_1, parent_2 = np.random.randint(len(population), size=2)