Сформулируйте стратегию селекции генетических алгоритмов.

Основанный на принципе колеса рулетки метод селекции, представленный в разд. 4.4 и продемонстрированный в примерах 4.4 и 4.5, считается для генетических алгоритмов основным методом отбора особей для родительской популяции с целью последующего их преобразования генетическими операторами, такими как скрещивание и мутация. Несмотря на случайный характер процедуры селекции, родительские особи выбираются пропорционально значениям их функций приспособленности, т.е. согласно вероятности селекции, определяемой по формуле (4.3). Каждая особь получает в родительском пуле такое количество своих копий, какое устанавливается выражением

, (4.16)

где - количество хромосом , в популяции, а - вероятность селекции хромосомы , рассчитываемая по формуле (4.3). Строго говоря, количество копий данной особи в родительском пуле равно целой части от . При использовании формул (4.3) и (4.16) необходимо обращать внимание на то, что , где - среднее значение функции приспособленности в популяции. Очевидно, что метод рулетки можно применять тогда, когда значения функции приспособленности положительны. Этот метод может использоваться только в задачах максимизации функции (но не минимизации).

Очевидно, что проблему минимизации можно легко свести к задаче максимизации функции и обратно. В некоторых реализациях генетического алгоритма метод рулетки применяется для поиска минимума функции (а не максимума). Это результат соответствующего преобразования, выполняемого программным путем для удобства пользователей, поскольку в большинстве прикладных задач решается проблема минимизации (например, затрат, расстояния, погрешности и т.п.). В качестве примера такой реализации можно назвать программу FlexTool [48]. Однако возможность применения метода рулетки всего лишь для одного класса задач, т.е. только для максимизации (или только для минимизации) можно считать его несомненным недостатком. Другая слабая сторона этого метода заключается в том, что особи с очень малым значением функции приспособленности слишком быстро исключаются из популяции, что может привести к преждевременной сходимости генетического алгоритма. Для предотвращения такого эффекта применяется масштабирование функции приспособленности (п. 4.8.5).

С учетом отмеченных недостатков метода рулетки созданы и используются альтернативные алгоритмы селекции. Один из них называется турнирным методом (tournament selection). Наряду с методом рулетки и ранговым методом он применяется как один из основных алгоритмов селекции в программе FlexTool. Представим эти методы подробнее.

При турнирной селекции все особи популяции разбиваются на подгруппы с последующим выбором в каждой из них особи с наилучшей приспособленностью. Различаются два способа такого выбора: детерминированный выбор (deterministic tournament selection) и случайный выбор (stochastic tournament selection). Детерминированный выбор осуществляется с вероятностью, равной 1, а случайный выбор - с вероятностью, меньшей 1. Подгруппы могут иметь произвольный размер, но чаще всего популяция разделяется на подгруппы по 2 - 3 особи в каждой.

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

На рис. 4.10 представлена схема, которая иллюстрирует метод турнирной селекции для подгрупп, состоящих из двух особей. Такую схему легко обобщить на подгруппы большего размера. Это одно из возможных приложений рассматриваемого алгоритма селекции (оно используется в программе FlexTool [48]).

Рис. 4.10. Схема турнирной селекции для подгрупп, состоящих из двух особей.

При ранговой селекции (ranking selection) особи популяции ранжируются по значениям их функции приспособленности. Это можно представить себе как отсортированный список особей, упорядоченных по направлению от наиболее приспособленных к наименее приспособленным (или наоборот), в котором каждой особи приписывается число, определяющее ее место в списке и называемое рангом (rank). Количество копий каждой особи, введенных в родительскую популяцию, рассчитывается по априорно заданной функции в зависимости от ранга особи. Пример такой функции показан на рис. 4.11.

Рис. 4.11. Пример функции, определяющей зависимость количества копий особи в родительском пуле от его ранга при ранговой селекции.

Достоинство рангового метода заключается в возможности его применения как для максимизации, так и для минимизации функции.

Он также не требует масштабирования из-за проблемы преждевременной сходимости, актуальной для метода рулетки.

Существуют различные варианты алгоритмов селекции [4,15]. Представленные ранее методы (рулетки, турнирный и ранговый) применяются чаще всего. Другие методы представляют собой либо их модификации, либо комбинации - например, метода рулетки с турнирным методом, когда пары родительских хромосом выбираются случайным образом, после чего из каждой пары выбирается хромосома с наибольшим значением функции приспособленности. Большинство методов селекции основано на формулах (4.3) и (4.16), по которым рассчитывается вероятность селекции и количество копий, вводимых в родительский пул. В так называемом детерминированном методе каждая особь получает число копий, равное целой части от , после чего популяция упорядочивается в соответствии с дробной частью , а остальные хромосомы, необходимые для пополнения новой популяции, последовательно выбираются из верхней части сформированного таким образом списка. В другом методе (называемом случайным) дробные части рассматриваются как вероятности успеха по Бернулли и, например, хромосома , для которой , получает одну копию гарантированно и еще одну - с вероятностью 0,5. В еще одном методе для устранения расхождения между расчетным значением и количеством копий хромосом , выбираемым по методу рулетки, производится модификация путем увеличения или уменьшения его значения для каждой хромосомы, выбранной для скрещивания и/или мутации.

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

Селекция в ГА

§ Селекция - это оператор, посредством которого индивиды (т.е. хромосомы) выбираются для спаривания и порождения потомков

§ Для имитации естественной селекции индивиды с более высокой пригодностью должны выбираться с большей вероятностью

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

§ Большинство схем селекций, используемых в ГА, создают промежуточную популяцию и затем выбирают из нее случайным образом пары индивидов для скрещивания

§ Предположения:

1. Мера Q качества решения (целевая функция) задачи известна

2. Она должна быть максимизирована

3. Она должна быть всегда положительной

4. Мы рассматриваем меру Q качества индивида как его пригодность

Дата добавления: 2015-11-14