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.
CodePudding user response：
Try this way :
import numpy as np
import random
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 = [] #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.append([rand1, rand2])
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)
CodePudding user response：
Seeing as the generator of pairs is stateful between calls, I would wrap the functionality inside a class. The instance will store used pairs to ensure we don't repeat anything. Using itertools.combinations we can find all of the possible pairs. We can randomly sample the combinations, and then keep track of all the individuals we used for that round.
class PairGenerator:
def __init__(self):
self.used_pairs = set()
def next_pairs(self, individuals):
"""
Return unique pairs of individuals that haven't been seen before.
In each call, we will look at the history of used_pairs to avoid duplicates.
In each call, each individual may only be used in one pair.
"""
# Find all pairs that could be used. Also ensure data contains no duplicates
possible_pairs = list(itertools.combinations(set(individuals), r=2))
# Keep track of which individuals were used this call.
unused_individuals = set()
# Add randomness when sampling possible pairs
for a, b in random.sample(possible_pairs, len(possible_pairs)):
# Sort the pair to ensure [a, b] collides with [b, a]
if a > b:
a, b = b, a
# Check both the individuals haven't been used in this cycle
if a in unused_individuals or b in unused_individuals:
continue
# Check that the pair has not been seen before.
if (a, b) in self.used_pairs:
continue
# Register pair and individuals before yielding
self.used_pairs.add((a, b))
unused_individuals.add(a)
unused_individuals.add(b)
yield a, b
Example usage
generator = PairGenerator()
individuals = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for i in range(4):
pairs = list(generator.next_pairs(individuals))
print(f"Iteration {i}:")
print(f" {individuals=}")
print(f" {pairs=}")
print(f" used_pairs={len(generator.used_pairs)}")
individuals.append(individuals.pop(0) 10)
Iteration 0:
individuals=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
pairs=[(1, 10), (2, 4), (3, 9), (5, 6), (7, 8)]
used_pairs=5
Iteration 1:
individuals=[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
pairs=[(3, 7), (2, 8), (5, 9), (6, 10), (4, 11)]
used_pairs=10
Iteration 2:
individuals=[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
pairs=[(3, 11), (6, 12), (7, 9), (4, 8), (5, 10)]
used_pairs=15
Iteration 3:
individuals=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
pairs=[(7, 11), (4, 13), (8, 10), (6, 9), (5, 12)]
used_pairs=20
CodePudding user response：
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().