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.

You set "winner" repeatedly in the for-loop (throwing away the previous value) but you only read it once after the loop (with its last value). — Michael Butscher, Sep 08 '21 at 01:12

Lachlan · Accepted Answer · 2021-09-08T11:50:41.230

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

edited Sep 08 '21 at 11:50

answered Sep 08 '21 at 01:17

Lachlan

360
5
14

Thanks for your reply. But when I run your code, it returned one error:AttributeError: 'numpy.ndarray' object has no attribute 'index'. Could you please tell me how to fix it? – Zzyy Sep 08 '21 at 02:05
code works fine at my end, I would suggest your code is using a np array where mine has lists. you can convert numpy arrays to lists with np.array.tolist(). @alvas answer below is a neater way of getting the two parents, you can substitute the parent selection lines in my code with their answer, but select from the 'selectable_parents' list. – Lachlan Sep 08 '21 at 02:14
I created population using numpy, maybe the AttributeError is casued by it. I followed your advice and tried to convert population array to list with the code:first_pick_score=scores[population.tolist().index(selected_parents[first_pick])],but it returned a ValueError:The truth value of an array with more than one element is ambiguous.Use a.any() or a.all(). So I changed the code to first_pick_score=scores[population.all().tolist().index(selected_parents[first_pick])], it returned a AttributeError: 'bool' object has no attribute 'index'. Could you please give me some ideas? – Zzyy Sep 08 '21 at 02:37
you need to convert your equivalent of `population` and `scores` arrays to lists. (and this is also why you post a full example) – Lachlan Sep 08 '21 at 05:25
Thanks for you patience! scores is a list and population is an array. And I converted population array into list using population_1=population.tolist(), but it always returned ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all() – Zzyy Sep 08 '21 at 10:10
are you feeding it `population_1` now then? the error msg is still saying its an array. – Lachlan Sep 08 '21 at 10:18
I have edited how I created population, could you please have a look and help me find out how to fix this problem? now when I added all() to population_1, it returned AttributeError: 'list' object has no attribute 'all'. – Zzyy Sep 08 '21 at 10:26
using your additional code at the top, if I change the line where you assign `population` to `population=np.vstack([initial_population_1, initial_population_2]).tolist()` and run my example code above there are no issues at my end. This creates a list of 4 lists, and the code handles this. – Lachlan Sep 08 '21 at 11:20
It works! But for the code for i in range(0, len(population),2), finally,it will return two parent_1s and two parent_2s. How to ensure those four parents are diiferent from each other? – Zzyy Sep 08 '21 at 11:31
I was about to let you know that based on your initial question, you only wanted to not select the 'winner' in future draws, so the loser is not omitted from the list and is available for selection again. Also, do you want to pick the lowest score as the winner, as that is what you have. Based on your comment, I assume that you want to pull a random pair out, and assign the 'winner' as parent_1 and the loser as parent_2? – Lachlan Sep 08 '21 at 11:35
I want to select parents with lowest score and second lowest score. – Zzyy Sep 08 '21 at 11:49
Apologies, I did not index the return lists. I have edited the code answer to show full example with fixed return indexing. – Lachlan Sep 08 '21 at 11:54
Can I ask one more question? what does the code:selectable_parents = [nonwinner for nonwinner in population if nonwinner not in prevwinner] mean? – Zzyy Sep 08 '21 at 12:00
that is the list comprehension - the main solution to your problem of omitting previous parents from the list. Read more [here](https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions) – Lachlan Sep 08 '21 at 22:46

score 0 · Answer 2 · answered Sep 08 '21 at 01:57

0

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)

answered Sep 08 '21 at 01:57

alvas

115,346
109
446
738

Thanks for your reply and could you please specify your code of selecting two parents? I am new to GA and I didn't full understand your code. – Zzyy Sep 08 '21 at 02:47
The `size=2` specifies how many parents you want to select. And the `len(population)` is the total no. of rows. – alvas Sep 08 '21 at 03:54
1

So you mean I don't need tournament_selection function and just directly pick two parents using np.random.randint with size=2? – Zzyy Sep 08 '21 at 10:12

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

2 Answers2