Отбор (генетический алгоритм) - Selection (genetic algorithm)

Отбор - это этап генетического алгоритма, на котором отдельные геномы выбираются из популяции для последующего разведения (с использованием оператора кроссовера ).

Общая процедура выбора может быть реализована следующим образом:

Функция пригодности оценивается для каждого человека, предоставляя значения пригодности, которые затем нормализуются. Нормализация означает деление значения пригодности каждого человека на сумму всех значений приспособленности, так что сумма всех результирующих значений приспособленности равна 1.
Вычисляются накопленные нормализованные значения пригодности: накопленное значение приспособленности индивидуума представляет собой сумму его собственного значения приспособленности плюс значения приспособленности всех предыдущих индивидуумов; совокупная приспособленность последнего человека должна быть равна 1, иначе на этапе нормализации что-то пошло не так.
Выбрано случайное число R от 0 до 1.
Выбран индивидуум является первым , чья накопленное нормализованное значение больше или равно R .

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

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

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

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

Методы отбора (генетический алгоритм)

Выбор колеса рулетки

При выборе колеса рулетки вероятность выбора особи для разведения следующего поколения пропорциональна ее приспособленности, чем лучше приспособленность, тем выше вероятность того, что эта особь будет выбрана. Выбор индивидов можно представить как вращение рулетки, в которой столько же карманов, сколько есть индивидов в нынешнем поколении, с размерами, зависящими от их вероятности. Вероятность выбора индивидуума равна , где - приспособленность, а - размер текущего поколения (обратите внимание, что в этом методе одного человека можно нарисовать несколько раз). ${\ displaystyle i}$ ${\ displaystyle p_ {i} = {\ frac {f_ {i}} {\ Sigma _ {j = 1} ^ {N} f_ {j}}}}$ ${\ displaystyle f_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle N}$

Выбор ранга

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

Выбор устойчивого состояния

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

В каждом поколении отбирается несколько (хороших - с высокой приспособленностью) хромосом для создания нового потомства. Затем удаляются некоторые (плохие - с низкой приспособленностью) хромосомы и на их место помещается новое потомство. Остальная часть населения доживает до нового поколения.

Выбор турнира

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

Выбор элитарности

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

Выбор Больцмана

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

Languages

In other projects

Отбор (генетический алгоритм) - Selection (genetic algorithm)

СОДЕРЖАНИЕ