Выбор индивидов из популяции по фитнес-функции - PullRequest
Новая
       45

Выбор индивидов из популяции по фитнес-функции

6 голосов
/ 09 марта 2011

Я работал над алгоритмом, где мне нужно выбрать n особей из популяции размера k, где k намного больше, чем n.Все люди имеют значение пригодности, поэтому выбор должен способствовать более высоким значениям пригодности.Однако я не хочу просто выбирать лучших русских людей, у худших тоже должен быть шанс.(Естественный отбор)

Итак, я решил найти минимальные и максимальные значения пригодности в популяции.Таким образом, любой человек будет иметь

p = (текущий - мин) / (max - мин)

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

Я также мог бы выполнить более одного прохода до оставшегося размерадоходит до.Но это может во многом способствовать лучшим и сходиться с упомянутым мною наивным методом отбора.

Любое предложение или ссылки на такой процесс отбора?Я мог бы почитать соответствующие статистические методы, если вы можете сослаться на любые.

Спасибо.

1 Ответ

6 голосов
/ 09 марта 2011

Использование Выбор колеса рулетки . Основная идея состоит в том, что вы назначаете область колеса рулетки относительно размера вероятности:

Roulette wheel

Затем вы просто вращаете его n раз, чтобы выбрать нужных вам людей.

Пример реализации в ruby: 

def roulette(population, n)
  probs = population.map { |gene| gene.probability } # TODO: Implement this
  selected = []

  n.times do 
    r, inc = rand * probs.max, 0 # pick a random number and select the  individual 
                     # corresponding to that roulette-wheel area
    population.each_index do |i| 
      if r < (inc += probs[i])
        selected << population[i]
        # make selection not pick sample twice
        population.delete_at i
        probs.delete_at i
        break
      end
    end
  end
  return selected
end

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

...