Блог

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

 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
  

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

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

Здесь возникает пара проблем.

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

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

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

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

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

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