Estoy trabajando en un algoritmo genético en python. En mi problema almaceno individuos en una lista como esa:
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]En cada iteración hay una probabilidad fija de que cada individuo muera y, por lo tanto, será eliminado de la lista.
Además, en cada iteración los individuos se emparejan aleatoriamente, por ejemplo:
[1, 5], [7, 10], [3, 4], [6, 8], [2, 9]y existe cierta probabilidad de que estas parejas tengan un hijo, que se agregará a la lista como el siguiente número (11, 12, etc.)
Cada par puede aparecer solo una vez, por lo que tengo que almacenar cada par y después de elegir dos individuos al azar, verificar si aún no han sido un par.
Me las arreglé para hacer todo eso:
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)pero en algunos casos, después de algunas iteraciones, me quedan al menos 2 elementos, que ya se han emparejado y termino con un bucle infinito:
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 1y así.
¿Hay alguna manera eficiente de verificar en cada iteración si es posible crear nuevos pares y, de no ser así, romper el ciclo while? Por supuesto, puedo hacer combinaciones de elementos que quedan en la lista pop_temp después de cada proceso de reproducción y verificar si alguna de esas combinaciones no está en el conjunto used_pairs , pero con muchas iteraciones y alta probabilidad de reproducción será extremadamente ineficiente, porque habrá miles de elementos en mi lista.
Sugiero usar iterertools.combinations() para generar sus pares. Esto garantizará que ningún elemento se repita en un par. Si necesita seleccionar aleatoriamente de esos pares, puede usar random.sample() .
Sugeriría usar un diccionario para realizar un seguimiento de los emparejamientos. Esto le permitirá revisar sistemáticamente la población y emparejar a los individuos con los candidatos restantes que no han sido emparejados con ese candidato. De esta manera, si no hay más socios elegibles, el individuo simplemente no está emparejado y el ciclo de emparejamiento puede salir eventualmente.
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 (ie 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)Ejecución de muestra:
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]