Choose a random sample from a list with bias in Python

Question

To give a little background, I am coding a genetic algorithm to solve the Traveling Salesman Problem (TSP). In my population, I have an ordered list of paths from shortest to longest (fittest to least fit), and their respective distances, like this:

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]]
...]

After the population is ordered by their fitness, I need to kill half of them randomly, but in such a fashion that the fitter the member, the better their chance of surviving.

1. I've tried using random.choices() and passing a list with chances of probability (bias) into the weights parameter, and my desired size of half the original population as k like this:

   # 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)
   

   The problem with the code above is that it produces duplicates in my list, and it's very messy to get rid of them and keep the population size at 50%.

2. I've also tried using the np.random.choices() from the numpy library, but it requires the list that I am passing to be 1D, and the list of weights and biases to add up to 1.

Is there any other way to do this?

Answer 1

I would still use np.random.choice(). Solve the first problem by asking np.random.choice() to choose the index of the path rather than the path itself. Solve the second problem by scaling the weights so they sum to 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]

Answer 2

EDIT: Actually, I would recommend to just use the following:

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

Answer 3

Choose one element at a time, put it into a set to guarantee it's unique, and continue until you have enough elements:

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 4

For no duplicates you have to use random shuffle. Algorithm is called weighted random shuffle, and is solved in

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

C++ version is right here

C++. Weighted std::shuffle

UPDATE: Fast weighted random shuffle copied from first link verbatim

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])