Введение
Отбор — это стадия генетического алгоритма или более общего эволюционного алгоритма, в которой отдельные геномы выбираются из популяции для последующего размножения (например, с использованием оператора кроссовера). Механизмы отбора также используются для выбора кандидатов на решение (индивидов) для следующего поколения. Сохранение лучших индивидуумов в одном поколении без изменений в следующем поколении называется элитаризмом или элитарным отбором. Это успешный (несложный) вариант общего процесса построения новой популяции. Процедура отбора для размножения, используемая на ранней стадии, может быть реализована следующим образом: вычисленные значения пригодности (функция пригодности) нормализуются таким образом, чтобы сумма всех полученных значений пригодности равнялась 1. Вычисляются накопленные нормализованные значения пригодности: накопленное значение пригодности индивида — это сумма его собственного значения пригодности плюс значения пригодности всех предыдущих индивидов; накопленное значение пригодности последнего индивида должно быть 1, иначе произошла ошибка на этапе нормализации. Выбирается случайное число R между 0 и 1. Выбранным индивидом является первый, чей накопленный нормализованный показатель больше или равен R.
Selection is the stage of a genetic algorithm or more general evolutionary algorithm in which individual genomes are chosen from a population for later breeding (e. g., using the crossover operator). Selection mechanisms are also used to choose candidate solutions (individuals) for the next generation. Retaining the best individuals in a generation unchanged in the next generation, is called elitism or elitist selection. It is a successful (slight) variant of the general process of constructing a new population. A selection procedure for breeding used early on may be implemented as follows:
The fitness values that have been computed (fitness function) are normalized, such that the sum of all resulting fitness values equals 1. Accumulated normalized fitness values are computed: the accumulated fitness value of an individual is the sum of its own fitness value plus the fitness values of all the previous individuals; the accumulated fitness of the last individual should be 1, otherwise something went wrong in the normalization step. A random number R between 0 and 1 is chosen. The selected individual is the first one whose accumulated normalized value is greater than or equal to R.
For many problems the above algorithm might be computationally demanding. A simpler and faster alternative uses the so called stochastic acceptance. If this procedure is repeated until there are enough selected individuals, this selection method is called fitness proportionate selection or roulette wheel selection. If instead of a single pointer spun multiple times, there are multiple, equally spaced pointers on a wheel that is spun once, it is called stochastic universal sampling. Repeatedly selecting the best individual of a randomly chosen subset is tournament selection. Taking the best half, third or another proportion of the individuals is truncation selection. There are other selection algorithms that do not consider all individuals for selection, but only those with a fitness value that is higher than a given (arbitrary) constant. Other algorithms select from a restricted pool where only a certain percentage of the individuals are allowed, based on fitness value.
Для многих задач вышеуказанный алгоритм может быть вычислительно затратным. Более простая и быстрая альтернатива использует так называемое стохастическое принятие. Если эта процедура повторяется до тех пор, пока не будет отобрано достаточное количество индивидуумов, этот метод отбора называется пропорциональным отбором по пригодности или отбором методом рулетки. Если вместо одного указателя, вращающегося несколько раз, на колесе, которое вращается один раз, есть несколько равноудаленных указателей, это называется стохастической универсальной выборкой. Повторный выбор лучшего индивида из случайно выбранного подмножества называется турнирным отбором. Отбор лучшей половины, трети или другой пропорции индивидуумов называется усеченным отбором. Существуют и другие алгоритмы отбора, которые не рассматривают всех индивидуумов для отбора, а только тех, у кого значение пригодности выше заданной (произвольной) константы. Другие алгоритмы выбирают из ограниченного пула, где разрешен только определенный процент индивидуумов, основанный на значении пригодности.
Selection is the stage of a genetic algorithm or more general evolutionary algorithm in which individual genomes are chosen from a population for later breeding (e. g., using the crossover operator). Selection mechanisms are also used to choose candidate solutions (individuals) for the next generation. Retaining the best individuals in a generation unchanged in the next generation, is called elitism or elitist selection. It is a successful (slight) variant of the general process of constructing a new population. A selection procedure for breeding used early on may be implemented as follows:
The fitness values that have been computed (fitness function) are normalized, such that the sum of all resulting fitness values equals 1. Accumulated normalized fitness values are computed: the accumulated fitness value of an individual is the sum of its own fitness value plus the fitness values of all the previous individuals; the accumulated fitness of the last individual should be 1, otherwise something went wrong in the normalization step. A random number R between 0 and 1 is chosen. The selected individual is the first one whose accumulated normalized value is greater than or equal to R.
For many problems the above algorithm might be computationally demanding. A simpler and faster alternative uses the so called stochastic acceptance. If this procedure is repeated until there are enough selected individuals, this selection method is called fitness proportionate selection or roulette wheel selection. If instead of a single pointer spun multiple times, there are multiple, equally spaced pointers on a wheel that is spun once, it is called stochastic universal sampling. Repeatedly selecting the best individual of a randomly chosen subset is tournament selection. Taking the best half, third or another proportion of the individuals is truncation selection. There are other selection algorithms that do not consider all individuals for selection, but only those with a fitness value that is higher than a given (arbitrary) constant. Other algorithms select from a restricted pool where only a certain percentage of the individuals are allowed, based on fitness value.
Методы отбора (эволюционный алгоритм)
Перечисленные методы различаются главным образом степенью селективного давления, которое можно задать с помощью параметра стратегии в методе отбора по рангу, описанном ниже. Чем выше селективное давление, тем быстрее популяция сходится к определенному решению, но при этом пространство поиска может быть исследовано недостаточно полно. Подробнее о других методах отбора и дополнительных деталях см.
Выбор колеса рулетки
В отборе методом рулетки вероятность выбора индивида для размножения следующего поколения пропорциональна его приспособленности: чем выше приспособленность, тем больше вероятность выбора этого индивида. Выбор индивидов можно представить как вращение рулетки с количеством карманов, равным числу индивидов в текущем поколении, при этом размеры карманов зависят от вероятности выбора каждого индивида. Вероятность выбора индивида равна , где – приспособленность индивида, а – размер текущего поколения (следует отметить, что одним и тем же индивидом можно быть выбранным несколько раз).
Выбор ранга
При ранговом отборе вероятность выбора не зависит напрямую от приспособленности, а от ранга приспособленности особи в популяции. Это позволяет по-новому взглянуть на большие различия в приспособленности; более того, сами точные значения приспособленности не обязательно должны быть известны, достаточно лишь упорядочить особей по качеству. Часто используется линейный рейтинг, восходящий к Бейкеру. Он позволяет задавать давление отбора параметром , который может принимать значения от 1,0 (отсутствие давления отбора) до 2,0 (высокое давление отбора). Вероятность для ранговой позиции рассчитывается следующим образом:
Помимо настраиваемого давления отбора, преимущество рангового отбора заключается также в том, что оно предоставляет худшим особям шанс на размножение и, следовательно, на улучшение. Это может быть особенно полезно в задачах с ограничениями, поскольку облегчает преодоление ограничения в несколько промежуточных шагов, то есть через последовательность нескольких особей, получивших низкую оценку из-за нарушения ограничений.
Выбор стабильного состояния
В каждом поколении небольшое количество хромосом (удачные, с высокой приспособленностью) отбирается для создания нового потомства. Затем часть (неудачных, с низкой приспособленностью) хромосом удаляется, и на их место помещается новое потомство. Остальная часть популяции переходит в следующее поколение.
Отбор на турнир
Турнирный отбор — это метод выбора особи из популяции особей. Победитель каждого турнира выбирается для скрещивания.
Элитный отбор
Часто для получения лучших результатов используются стратегии с частичным воспроизводством. Один из таких подходов — элитаризм, при котором небольшая доля лучших особей из предыдущего поколения переносится в следующее поколение (без изменений).
Селекция Болцмана
При селекции Болцмана непрерывно изменяющаяся температура управляет скоростью отбора согласно заданному расписанию. Температура изначально высокая, что означает слабое давление отбора. Температура постепенно понижается, что постепенно усиливает давление отбора, позволяя генетическому алгоритму более точно сфокусироваться на оптимальной области пространства поиска, сохраняя при этом необходимый уровень разнообразия.