Выберите случайную выборку из списка с уклоном в Python - PullRequest
Новая
       10

Выберите случайную выборку из списка с уклоном в Python

0 голосов
/ 19 мая 2018

Чтобы подвести итог, я кодирую генетический алгоритм для решения задачи коммивояжера (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]]
...]

После того, как население упорядочено по его пригодности, мне нужноубить половину из них случайным образом, но таким образом, чтобы член был лучше, чем больше шансов на выживание.

  1. Я пытался использовать random.choices() и передача списка с вероятностями вероятности (смещение) в параметр 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%.

  2. Я также пытался использовать np.random.choices() из библиотеки numpy, но для этого требуется, чтобы список, который я передаю , был 1D , и список весов и смещенийдо добавить до 1 .

ЕстьЕсть ли другой способ сделать это?

Ответы [ 4 ]

0 голосов
/ 20 мая 2018

Я бы все равно использовал 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]
0 голосов
/ 19 мая 2018

Выберите один элемент за раз, поместите его в набор, чтобы гарантировать его уникальность, и продолжайте, пока у вас не будет достаточно элементов: 

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))
0 голосов
/ 20 мая 2018

Чтобы не было дубликатов, вы должны использовать случайное перемешивание.Алгоритм называется взвешенным случайным перемешиванием и решается в

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

C ++ версия прямо здесь

C ++.Weighted std :: shuffle

UPDATE: быстрый взвешенный случайный случайный порядок, скопированный с первой ссылки дословно 

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])
0 голосов
/ 19 мая 2018

РЕДАКТИРОВАТЬ: На самом деле, я бы порекомендовал просто использовать следующее: 

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