Python实现带偏置无重复列表抽样（TSP遗传算法场景）

针对你在TSP遗传算法里的种群筛选需求——要从按适应度排序后的种群里淘汰一半，同时让高适应度个体有更高存活概率，我给你几个实用的解决方案，能完美避开你之前遇到的重复选择问题：

这个方法的核心是每次选中个体后就从候选池中移除，彻底避免重复选择。因为你的种群已经按路径长度（适应度）从高到低排好序，我们可以直接用路径距离的倒数作为权重（距离越短，权重越大，存活概率越高），也可以用排名相关的权重。

import random

def select_survivors(population, survival_rate=0.5):
    # 复制原种群，避免修改原始数据
    candidate_pool = population.copy()
    survivors = []
    num_survive = int(len(population) * survival_rate)
    
    for _ in range(num_survive):
        # 计算权重：用路径距离的倒数，保证短路径（高适应度）权重更高
        weights = [1 / path[1][0] for path in candidate_pool]
        # 随机选择1个个体
        selected = random.choices(candidate_pool, weights=weights, k=1)[0]
        survivors.append(selected)
        # 从候选池移除已选个体，防止重复
        candidate_pool.remove(selected)
    
    return survivors

如果你的种群规模很大，用列表的remove()方法效率偏低，你可以改用索引操作来优化：

import random

def select_survivors(population, survival_rate=0.5):
    num_individuals = len(population)
    num_survive = int(num_individuals * survival_rate)
    # 生成所有个体的索引
    candidate_indices = list(range(num_individuals))
    survivors = []
    
    for _ in range(num_survive):
        # 根据索引获取对应的距离，计算权重
        weights = [1 / population[i][1][0] for i in candidate_indices]
        # 选择一个索引
        selected_idx = random.choices(candidate_indices, weights=weights, k=1)[0]
        survivors.append(population[selected_idx])
        # 移除已选索引
        candidate_indices.remove(selected_idx)
    
    return survivors

numpy的np.random.choice()支持无放回抽样（设置replace=False），刚好解决你之前遇到的重复问题。因为你的种群已经按适应度排序，我们可以直接给每个个体分配和排名挂钩的权重——排名越靠前（适应度越高），权重越大，这样存活概率自然更高。

import numpy as np

def select_survivors(population, survival_rate=0.5):
    num_individuals = len(population)
    num_survive = int(num_individuals * survival_rate)
    
    # 生成排名权重：第1名（索引0）权重为num_individuals，第2名为num_individuals-1，依此类推
    rank_weights = np.arange(num_individuals, 0, -1)
    # 归一化权重（numpy不强制要求总和为1，但归一化后更直观）
    normalized_weights = rank_weights / rank_weights.sum()
    
    # 无放回选择指定数量的索引
    selected_indices = np.random.choice(num_individuals, size=num_survive, replace=False, p=normalized_weights)
    # 根据索引提取存活个体
    survivors = [population[i] for i in selected_indices]
    
    return survivors

如果你想让高适应度个体的存活概率提升更明显，可以把权重改成非线性的，比如平方权重：

rank_weights = np.arange(num_individuals, 0, -1) ** 2
normalized_weights = rank_weights / rank_weights.sum()

这样前几名个体的权重占比会大幅提升，存活概率更高。

锦标赛选择是遗传算法里常用的选择策略，你可以给高适应度个体更高的入选锦标赛的概率，或者直接利用已排序的种群特性，让前N个个体有更高的被选中概率：

import random

def select_survivors(population, survival_rate=0.5, tournament_size=3):
    num_individuals = len(population)
    num_survive = int(num_individuals * survival_rate)
    survivors = []
    
    for _ in range(num_survive):
        # 给前半部分个体更高的入选概率（比如2倍权重）
        weights = [2 if i < num_individuals//2 else 1 for i in range(num_individuals)]
        # 随机选择锦标赛选手
        tournament_candidates = random.choices(population, weights=weights, k=tournament_size)
        # 选择锦标赛里适应度最高的（路径最短的）
        tournament_candidates.sort(key=lambda x: x[1][0])
        survivors.append(tournament_candidates[0])
    
    return survivors

这个方法的优势是实现简单，而且能保证高适应度个体更容易被选中，同时也能引入一定的随机性。

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