Как оценивать лучших потомков лучше, чем с помощью метода выбора рулетки?

Question

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

function roulette(population) 
    local slice = sum_of_fitnesses(population) * math.random() 
    local sum = 0 
    for iter = 1, #population do 
     sum = sum + population[iter].fitness 
     if sum >= slice then 
      return population[iter] 
     end 
    end 
end 

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

Итак, как я могу улучшить свой метод выбора рулетки? Или я должен использовать совершенно другой фитнес-пропорциональный селектор?

Answer 1

В игре есть пара вопросов.

Вы выбираете вероятность индивидуальной репликации в зависимости от ее пригодности, поэтому используемая вами функция фитнеса должна преувеличивать небольшие различия или же незначительное снижение физической формы не так уж плохо. Например, если фитнес упадет с 81 до 80, это изменение, вероятно, находится в пределах шума системы и не будет сильно отличаться от эволюции. Конечно, почти невозможно подняться до очень высокой пригодности, если потребуется серия небольших изменений, потому что избирательное давление просто не будет достаточно сильным.

Способ решения этой проблемы - использовать что-то вроде выбора турнира. В простейшей форме каждый раз, когда вы хотите выбрать другого человека, который должен родиться, вы выбираете случайных людей K (известно и «размер турнира»). Вы вычисляете пригодность каждого человека, и тот, кто имеет наибольшую пригодность, реплицируется. Не имеет значения, если разница в фитнесе составляет 81 против 80 или 10000 против 2, так как она просто занимает максимальную физическую форму.

Теперь встает вопрос: что вам нужно установить K? К можно рассматривать как силу отбора. Если вы установите его на низком уровне (например, K = 2), многие люди с низкой физиологией получат удачу и проскользнут, соревнуясь с другими людьми с низкой физиологической способностью. Вы получите много разнообразия, но очень маленький раздел. С другой стороны, если вы установите K на высокий уровень (скажем, K = 100), вы ВСЕГДА выбираете один из самых высоких показателей в населении, гарантируя, что среднее население приближается к максимуму, но также сдерживая разнообразие населения.

Конкретный компромисс здесь зависит от конкретной проблемы. Я рекомендую попробовать различные варианты (включая ваш оригинальный алгоритм) с несколькими различными проблемами, чтобы увидеть, что происходит. Например, попробуйте проблему all-ones: потенциальные решения - это бит-строки, а фитнес - просто число 1. Если у вас слабый выбор (как в вашем исходном примере, так и с K = 2), вы увидите, что он никогда не попадает в идеальное решение для всех.

Итак, почему бы не всегда использовать высокий K? Хорошо рассмотрим проблему, когда они отрицательны, если они не появляются в блоке из четырех последовательных (или восемь или даже многих), когда они внезапно становятся очень положительными. Такая проблема является «обманчивой», а это значит, что вам нужно исследовать решения, которые выглядят плохо, чтобы найти те, которые хороши. Если вы установите слишком высокий уровень отбора, вы никогда не соберете три из них для этой последней мутации, чтобы дать вам четвертый.

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