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.
I suggest using iterertools.combinations() to generate your pairs. This will guarantee that no element will repeat in a pair. If you need to randomly select from those pairs, you can use random.sample().
I would suggest using a dictionary to keep track of pairings. This will allow you to systematically go through the population and pair individuals with remaining candidates that have not been paired with that one. This way, if there are no more eligible partners, the individual is simply not paired and the pairing loop can eventually exit.
import random
from collections import defaultdict
reproducing_prob = 0.1 #probability of reproduction
death_prob = 0.1 #probability of death
pop_size = 10 #starting population size
population = list(range(1, pop_size+1))
next_id = pop_size+1
paired = defaultdict(set) # {creature:set of paired creatures}
for day in range(10):
print("Day",day)
print(" population",population)
deaths = {c for c in population if random.random()<death_prob}
print(" deaths:",deaths or None)
population = [c for c in population if c not in deaths] # remove deads
singles = random.sample(population,len(population)) # randomizes pairs
while singles: # systematically consume list
a = singles.pop(0) # remove first individual
b = next((c for c in singles if c not in paired[a]),0)
if not b: continue # no eligible candidate (i.e. no pairing)
print(" pair",(a,b))
singles.remove(b) # remove paired individual
paired[a].add(b) # track pairs
paired[b].add(a) # in both order
if random.random()<reproducing_prob: # reproduce ?
print(" NewCreature!",next_id)
population.append(next_id) # add individual
next_id += 1 # unique numbering
print("Final Population:",population)
Sample Run:
Day 0
population [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
deaths: {4}
pair (8, 1)
NewCreature! 11
pair (6, 7)
pair (2, 10)
pair (3, 5)
Day 1
population [1, 2, 3, 5, 6, 7, 8, 9, 10, 11]
deaths: None
pair (7, 11)
pair (1, 10)
NewCreature! 12
pair (9, 2)
pair (8, 5)
NewCreature! 13
pair (6, 3)
Day 2
population [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13]
deaths: {9, 3, 5}
pair (12, 7)
pair (13, 1)
pair (10, 8)
pair (11, 2)
Day 3
population [1, 2, 6, 7, 8, 10, 11, 12, 13]
deaths: {11, 13}
pair (10, 7)
pair (8, 2)
pair (1, 12)
Day 4
population [1, 2, 6, 7, 8, 10, 12]
deaths: {8, 1, 12}
pair (10, 6)
pair (2, 7)
Day 5
population [2, 6, 7, 10]
deaths: None
pair (6, 2)
Day 6
population [2, 6, 7, 10]
deaths: None
Day 7
population [2, 6, 7, 10]
deaths: None
Day 8
population [2, 6, 7, 10]
deaths: None
Day 9
population [2, 6, 7, 10]
deaths: None
Final Population: [2, 6, 7, 10]