Способы отбора особей

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

Почти для всех методов отбора существуют модификации, связанные с принципиальной возможностью (невозможностью) одной и той же особи входить в пул скрещивания несколько раз, — их называют соответственно алгоритмы с замещением и без:

• • в алгоритмах с замещением после перемещения особи в пул скрещивания в исходной популяции ее замещают еще одной такой же особью, что ей дает возможность попасть в пул более одного раза;
• • в алгоритмах без замещения одна и та же особь может отбираться в пул скрещивания только единожды, так как в исходной популяции после отбора ее «не замещают».

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

Примером отбора, сравнивающего особей напрямую, является турнирный отбор. Как и турнирный метод ранжирования, данный метод работает с небольшими поднаборами особей из популяции:

• 1) из популяции случайно отбирается набор особей X_sef,
• 2) в наборе X_se/ производятся сравнения особей с последующим определением доминирующих;
• 3) доминирующие особи добавляются в пул скрещивания, после чего при необходимости повторяется пункт 1.

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

Рис. 2.30. График зависимости вероятности (пР (1у = ли)) того, что особь, выигравшая турнирный отбор (/j), обладает рангом ли, где и — размер популяции; t = (1, 2, 3, 5, 8) — величина используемого поднабора В качестве примера алгоритма отбора, опирающегося на предварительно подготовленные значения приспособленности особей, но при этом вносящего элемент случайности, рассмотрим алгоритм рулетки (пропорциональный алгоритм). В данном алгоритме вероятность попадания особи в пул скрещивания пропорциональна значению приспособленности особи, отнесенному к сумме значений приспособленностей всех особей:

Если исходная популяция проранжирована, то имеет смысл использовать алгоритмы с полиномной зависимостью вероятности выбора особи от ее ранга:

где Рг (/ = k) — вероятность выбора особи с рангом k; d — степень многочлена, задающего зависимость вероятности выбора от ранга особи; a_t — коэффициенты задающего многочлена.

Рассмотрим простую реализацию подобного алгоритма:

• 1) генерируем случайную равномерно распределенную величину в границах интервала [0, 1);
• 2) полученное значение возводим в степень р, где р > 0 отражает характер и крутизну зависимости вероятности отбора от ранга особи;
• 3) возведенную в степень случайную величину умножаем на размер популяции, что дает нам ранг выбираемой особи;
• 4) при необходимости повторяем пункт 1.

Характер зависимости вероятности выбора особи от ее ранга и используемого коэффициента р приведен на рис. 2.31. Очевидно, что при р < 1 предпочтение отдается особям с более низким рангом, а при р > 1 — наоборот.

Рис. 231. Характер зависимости вероятности отбора особи (Pr (/ = k)) с рангом k для разных показателей степени (1 /р).

———1;———-2;———0,5;——3;…- 0,333 333 333;—4; —…- 0,25.

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

• 1) имеется популяция особей Х_рор, в которой каждая особь имеет оценки приспособленности согласно каждому из критериев f_i множества критериев F, по которым ведется оптимизация. Из этой популяции нам нужно составить пул скрещивания X_set;
• 2) берем оценки приспособленности особей согласно одному из критериев /?,
• 3) используя оценки приспособленности, с помощью пропорциональной схемы отбираем |X_S, J / F особей;
• 4) повторяем пункт 2 для следующего критерия, пока не переберем все критерии из F;
• 5) итоговая популяция X_sei составляется путем объединения особей, отобранных по каждому из критериев.

Наконец, алгоритмы отбора также могут учитывать «нишевой» фактор для сохранения разнообразия в популяции. Так, алгоритм NPGA (нишевой Парето-генетический алгоритм) помимо турнирной схемы отбора учитывает предварительно рассчитанные для особей «нишевые» числа:

• 1) из популяции Х_рор отбираются две особи-кандидага;
• 2) обе особи сравниваются со случайным набором особей Х_ш;
• 3) если в ходе сравнений с тестовым набором доминирующей оказалась только одна из особей-кандидатов, то она отбирается в пул скрещивания

sel'

• 4) если обе особи оказались либо доминирующими, либо не доминирующими в тестовом наборе, то отбирается особь с менее заполненной нишей;
• 5) пункт 1 повторяется до заполнения X_set.

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