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

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

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

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

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

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

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

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

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

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

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

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

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

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

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