Равномерное ранжирование (случайный выбор)

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

  P_s (a_i) =     при 1 ≤ i ≤ µ

              0 при µ ≤ i ≤ N

где µ ≤ N – параметр метода.

Локальный отбор

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

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

  1) Линейное соседство:

На практике рассматривают полную окрестность (вверху показана полная окрестность с расстоянием d=2) и «полуокрестность» с расстоянием d=l).

2)Двумерное - четырехсвязное соседство:

Вверху показан полный крест выделенного элемента с расстоянием d=1, внизу полукрест с расстоянием d=1.

3) Двумерное - восьмисвязное соседство:

Сверху показана "звезда" выделенного элемента с расстоянием d=l, а справа "полузвезда".

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

При наличии отношения соседства, между особями возникает эффект «изоляции расстоянием». Чем меньше соседство, тем больше «изоляция расстояния». Это ограничивает распространение новых решений в популяции.

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

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

В малых и средних популяциях (N<100) для локального отбора|рекомендуется двумерная структура типа полузвезда с расстоянием d = 1.

При большом размере популяции (N>100) лучше использовать большие расстояния d>l и 2-мерные структуры с соседством типа звезда.

 

Отбор на основе усечения

Этот метод не имеет аналогов в естественной эволюции и обычно используется для больших популяций (N>100). При этом отбираемые особиупорядочиваются согласно их значениям целевой функции.  Затем, вкачестве родителей выбираются только лучшие особи. Далее, с равнойвероятностью, среди них случайно выбирают пары, которые производят  потомков.

При этом методе используется параметр - порог отсечения Т (интенсивность отбора), который показывает долю часть популяции, которая отбирается в качестве родителей. Обычно  10% ≤ T ≤ 50%.

Турнирный отбор

Все особи популяции разбиваются на подгруппы размера m с последующим выбором в каждой из них особи с лучшимзначением фитнесс-функции. Параметром этой процедуры является размер тура m, который принимает значения из диапазона 2≤m<N.

Используются два способа выбора: детерминированный и случайный. При детерминированном способе выбор выполняется с вероятностью, равной 1; в то время как при случайном методе выбор осуществляется с вероятностью меньше 1. Чаще всегопопуляция разбиваетсяна подгруппы по 2-3 особи в каждой (m=2,3). Схема турнирной селекции:

 

Турнирный метод может быть использован как при максимизации, так
и при минимизации функции. Кроме этого, он легко распространяется на
задачи многокритериальной оптимизации.