从具有 Python 偏差的列表中选择一个随机样本

Question

为了提供一点背景知识，我正在编写一个遗传算法来解决 Traveling Salesman Problem (TSP)。在我的人口中，我有一个从最短到最长（最适合到最不适合）的有序路径列表，以及它们各自的距离，如下所示：

population = [
[[a, b, c, d], [10.12]],
[[b, c, a, d], [11.33]],
[[d, a, c, b], [11.5]],
[[b, a, d, c], [12.07]]
...]

人口按适应度排序后，我需要随机杀死其中一半，但以这种方式，成员越健康，他们生存的机会就越大。

我试过使用 random.choices() 并将概率为 (bias) 的列表传递给 weights 参数，和我想要的原始人口的一半大小 k 像这样：
```
# returns something like [0.99, 0.75, 0.65, 0.22...]
bias_weights = [x / len(population) for x in range(len(population))]

random.choices(population, weights=bias_weights, k=len(population) / 2)
```
上面代码的问题是它在我的列表中产生了重复项，删除它们并将人口规模保持在 50% 是非常混乱的。
我也尝试过使用 numpy 库中的 np.random.choices()，但它要求我传递的列表 是一维的，以及 的权重和偏差列表加起来为 1。

还有其他方法吗？

Answer 1

编辑：实际上，我建议只使用以下内容：

while <variable> not in <list>:
    <list>.append(<variable>)

Answer 2

一次选择一个元素，将其放入集合中以保证其唯一性，然后继续直到元素足够：

bias_weights = [x / len(population) for x in range(len(population))]

chosen = set()

while size(chosen) < len(population) // 2:
    chosen.add(random.choices(population, weights=bias_weights, k=1))

Answer 3

为了不重复，您必须使用随机洗牌。算法称为加权随机洗牌，并在

中解决

http://nicky.vanforeest.com/probability/weightedRandomShuffling/weighted.html

C++ 版本在这里

更新：从第一个link逐字复制的快速加权随机洗牌

from random import random
from bisect import bisect_right
import numpy as np

def weighted_shuffle(a,w):
    r = np.empty_like(a)
    cumWeights = np.cumsum(w)
    for i in range(len(a)):
         rnd = random() * cumWeights[-1]
         j = bisect_right(cumWeights,rnd)
         #j = np.searchsorted(cumWeights, rnd, side='right')
         r[i]=a[j]
         cumWeights[j:] -= w[j]
    return r

a = np.arange(1,1000)
w = np.arange(1,1000)
r = weighted_shuffle(a,w)
print(r[:2])

Answer 4

我仍然会使用 np.random.choice()。通过要求 np.random.choice() 选择路径的 index 而不是路径本身来解决第一个问题。通过缩放权重来解决第二个问题，使它们总和为 1。

import numpy as np

a, b, c, d = 1, 2, 3, 4

population = [
[[a, b, c, d], [10.12]],
[[b, c, a, d], [11.33]],
[[d, a, c, b], [11.5]],
[[b, a, d, c], [12.07]]
]

# Build probability array
bias_weights = [x / len(population) for x in range(len(population))]
prob = np.array(bias_weights) / np.sum(bias_weights)

# Get random integers between 0 and len(prob)-1, drawn according to prob
sample_size = 2
choice_indices = np.random.choice(len(prob), size=sample_size, replace=False, p=prob)

# Get corresponding paths
paths = [population[i][0] for i in choice_indices]

从具有 Python 偏差的列表中选择一个随机样本

Choose a random sample from a list with bias in Python

python

random

numpy

traveling-salesman

genetic-algorithm