Методы селекции

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

(4.16)

e(ch,) = p_s(ch,) ■ N

Рис. 4.9. Графическое представление схем для целочисленных значений х от О до 31, закодированных в форме 5-битовых двоичных последовательностей дл? оптимизации функции f(x) = 2х² + 1 (примеры 4.5, а также 4.8 и 4.11).

где N- количество хромосом ch/, /= 1,2,..., N в популяции, a p_s(ch,) - вероятность селекции хромосомы ch/, рассчитываемая по формуле (4.3). Строго говоря, количество копий данной особи в родительском пуле равно целой части от e(ch,). При использовании формул (4 3) и (4.16) необходимо обращать внимание на то, что e(ch,) = F(ch;)/F,

4.8. Модификации классического

алгоритма

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

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

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

N особей популяции Р(к)

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

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

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

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

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

1 "наилучшая особь"

1 "наилучшая особь"

Родительский пул M(k);N особей

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

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

а 4. Генетические алгорип

4.8. Модификации классического генегг,

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

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

Дата добавления: 2015-06-04