Выбор только верхнего x% для выбора в генетическом алгоритме

Question

В настоящее время я работаю над StringEvolver , и я не совсем уверен насчет конкретного термина, который может использоваться в GA.

В генетических алгоритмах элитарность относится к той подгруппе населения, которая напрямую продвигается к следующему поколению; исправить?

Но существует ли конкретный термин для использования только, например, верхних 75% текущей популяции для процесса отбора, кроссовера и мутации, а не всей популяции? По сути, как называется эта ставка х%?

Я имею в виду, что вместо использования всей популяции, скажем, в процессе выбора рулетки, я использую только верхний x% (то есть размножаемся только среди лучших x% населения)

---

Причина, по которой я спрашиваю, заключается в том, что я заметил значительные улучшения производительности (более быструю конвергенцию) при использовании, например, верхних 10-25% населения для процессов отбора, кроссовера и мутации для продвижения поколения вместо использования полное население.

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

Тем не менее, существует термин, называемый децимацией.Это когда вы выбрасываете нижние X% вашей популяции перед кроссовером и мутацией.Это обычно не делается каждым поколением.Как правило, вы начнете с невероятно большой популяции, чтобы охватить большее пространство поиска, а затем погасите после X поколений, поскольку ГА часто добиваются наибольшего выигрыша в первые 100 поколений или около того.Затем вы переходите к меньшему, более простому в обращении населению.

Надеюсь, это поможет.