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

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 случайных людей (K известно и "размер турнира"). Вы рассчитываете пригодность каждого человека, и тот, кто имеет наивысшую пригодность, воспроизводится. Неважно, будет ли разница в пригодности 81 против 80 или 10000 против 2, так как он просто принимает самую высокую пригодность.

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

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

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

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