Python遗传算法中如何实现列表元素无重复配对并避免无限循环

优化方案1：概率阈值终止法（性能最优，推荐） #

该方案无复杂全量校验逻辑，额外开销极低，完全适配数千甚至更大规模的种群场景：

• 原理：如果当前种群仍有未使用的配对，连续多次随机抽样都命中已用配对的概率会随重试次数增加指数级降低，当连续失败次数达到阈值时，可判定已无可用配对，直接终止循环即可，实际使用中误判概率几乎为0。
• 阈值建议：动态设置为2 * len(pop_temp)即可，种群规模越大可适当调高阈值。

首先优化已配对存储逻辑，将无序对统一存为排序后的元组，减少查询次数：

# 存配对时统一排序，仅需查询一次
used_pairs.add(tuple(sorted((rand1, rand2))))
# 查询时也先排序再判断是否存在
if tuple(sorted((rand1, rand2))) not in used_pairs:

修改后的while循环逻辑如下：

pop_temp = pop_start.copy()
max_retry = 2 * len(pop_temp)  # 动态适配当前种群大小的重试阈值
fail_count = 0
while len(pop_temp) > 1:
    if fail_count >= max_retry:
        # 连续多次未匹配到可用配对，判定无剩余可用配对，终止循环
        break
    idx1, idx2 = random.sample(range(0, len(pop_temp)), 2) 
    rand1, rand2 = pop_temp[idx1], pop_temp[idx2] 
    print("Found pair: ", rand1, rand2)
    
    pair = tuple(sorted((rand1, rand2)))
    if pair not in used_pairs:
        fail_count = 0  # 匹配成功，重置失败计数器
        for i in sorted([idx1, idx2], reverse=True):
            pop_temp.pop(i)
        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)
    else:
        fail_count += 1  # 匹配失败，计数器累加

优化方案2：100%准确校验法（适合零误判要求的场景） #

如果需要完全准确的判断是否存在可用配对，可以通过维护个体维度的已配对字典实现，开销远低于生成所有组合：

• 为每个个体维护已配对集合：used_partners = defaultdict(set)，每次配对成功后互相把对方加入自己的集合：used_partners[rand1].add(rand2); used_partners[rand2].add(rand1)
• 可用配对校验逻辑如下，几千规模种群的校验时间复杂度仅为O(n)，完全可接受：

def has_available_pair(pop_temp, used_partners):
    pop_set = set(pop_temp)
    for ind in pop_temp:
        # 只要有一个个体存在未配对的同种群其他个体，就存在可用配对
        if len(used_partners[ind] & pop_set) < len(pop_temp) - 1:
            return True
    return False

在while循环开头调用该函数，如果返回False直接break即可。

内容的提问来源于stack exchange，提问作者MKorona