I am working on a genetic algorithm in python. In my problem I store individuals in a list like that:
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
In every iteration there is some fixed probability that each individual will die, and therefore it will be deleted from the list.
What is more, in every iteration individuals pair up randomly, for example:
[1, 5], [7, 10], [3, 4], [6, 8], [2, 9]
and there is some probability that these pairs will have a child, which will be added to the list as the next number (11, 12 etc.)
Each pair may appear only once, so I have to store each pair and after choosing randomly two individuals, check if they haven't been a pair already.
I managed to do all of that:
reproducing_prob = 0.1 #probability of reproduction
death_prob = 0.1 #probability of death
pop_size = 10 #starting population size
pop_start = list(range(1, pop_size+1))
used_pairs = set() #storing pairs that already appeared
new_creature = 10
for day in range(10):
print("\nDay ", day)
print("Population: ", pop_start)
dead_creatures = []
for creature in pop_start: #iterating through whole list to check if creatures die
death = np.random.uniform(0,1)
if death < death_prob:
print("Dead: ", creature)
dead_creatures.append(creature)
pop_start = [creature for creature in pop_start if creature not in dead_creatures]
pop_temp = pop_start.copy()
while len(pop_temp) > 1: #looping through list until there aren't enough elements to pair them up
idx1, idx2 = random.sample(range(0, len(pop_temp)), 2)
rand1, rand2 = pop_temp[idx1], pop_temp[idx2]
print("Found pair: ", rand1, rand2)
if ((rand1, rand2) not in used_pairs) and ((rand2, rand1) not in used_pairs): #check if random pair hasn't been already used
for i in sorted([idx1, idx2], reverse=True):
pop_temp.pop(i)
pair = rand1, rand2
used_pairs.add(pair)
reproducing = np.random.uniform(0,1)
if reproducing < reproducing_prob:
pop_size += 1
new_creature += 1
print("New creature! ", new_creature)
pop_start.append(new_creature)
but in some cases, after a few iterations I have at least 2 elements left, that have already been paired up and I end up with an infinite loop:
Day 0
Population: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Found pair: 10 3
Found pair: 7 5
New creature! 11
Found pair: 8 2
Found pair: 9 1
Found pair: 6 4
Day 1
Population: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Dead: 8
Found pair: 6 10
Found pair: 1 11
Found pair: 4 5
Found pair: 2 9
Found pair: 3 7
Day 2
Population: [1, 2, 3, 4, 5, 6, 7, 9, 10, 11]
Dead: 6
Found pair: 5 11
Found pair: 10 1
Found pair: 3 2
Found pair: 9 7
Day 3
Population: [1, 2, 3, 4, 5, 7, 9, 10, 11]
Found pair: 11 9
Found pair: 4 7
Found pair: 5 10
Found pair: 2 1
Day 4
Population: [1, 2, 3, 4, 5, 7, 9, 10, 11]
Dead: 10
Found pair: 5 3
New creature! 12
Found pair: 2 7
Found pair: 9 1
Found pair: 4 9
Found pair: 1 11
Found pair: 11 1
Found pair: 1 11
Found pair: 11 1
and so on.
Is there any efficient way to check in every iteration if it is possible to create any new pairs, and if not, break the while loop? Of course, I can make combinations of elements left in pop_temp list after every reproduction process and check if any of those combinations aren't in used_pairs set, but with many iterations and high reproduction probability it's going to be extremely inefficient, because there will be thousands of elements in my list.