我正在使用Python编写遗传算法。在我的问题中,我将个体存储在一个列表中,如下所示:
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
每次迭代中,每个个体都有一定的固定概率死亡,因此它将从列表中删除。
此外,在每次迭代中,个体会随机配对,例如:
[1, 5], [7, 10], [3, 4], [6, 8], [2, 9]
有一定的概率这些配对会有孩子,然后将孩子添加到列表中作为下一个数字(11,12等)。
每对只能出现一次,所以我必须存储每对,并在随机选择两个人之后检查他们是否已经成为一对。
我成功地完成了所有这些操作:
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)
但在某些情况下,经过几次迭代后,我至少还剩下2个已经配对的元素,最终导致无限循环:
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
等等其他的事情。
有没有一种有效的方式,在每次迭代中检查是否可以创建任何新的对,如果不行,则退出while循环?当然,我可以在每次繁殖过程后将剩余的元素组合在pop_temp
列表中,并检查这些组合中是否有任何一个不在used_pairs
集合中,但是随着许多迭代和高繁殖概率,这将变得极其低效,因为我的列表中将有成千上万个元素。