При данном виде отбора сначала подсчитывается присособленность каждой особи f_i. После этого находят среднюю приспособленность в популяции f_ср как среднее арифметическое значений приспособленности всех особей. Затем для каждой особи вычисляется отношение f_i/f_ср. Если это отношение больше 1, то особь считается хорошо приспособленной и допускается к скрещиванию, в противном случае особь, скорее всего, останется "за бортом". Например, если дробь равна 2.36, то данная особь имеет двойной шанс на скрещивание и будет иметь вероятность равную 0.36 третьего скрещивания. Если же приспособленность равна 0.54, то особь примет участие в единственном скрещивании с вероятностью 0.54.

Реализовать это можно, например, так (сам не пробовал, но читал в тьюториале Уитли). Пусть имеется массив двоичных строк (популяция) и дополнительный массив для особей допущенных к скрещиванию. Определим для каждой особи популяции значение описанного выше отношения. Далее, будем записывать строки в промежуточный массив согласно следующему правилу: возьмем целую часть понятно-какого-отношения и ровно столько раз запишем данную строку во вспомогательный массив, после этого с помощью случайной величины (СВ) определим, будем ли мы записывать данную строку ещё раз: если СВ больше дробной части отношения, то "да", если нет, то "нет". В дальнейшем, особи для скрещивания выбираются только из промежуточного массива случайным образом, так что, если строка присутствует в нем в нескольких экземплярах, то у нее больше шансов "наследить" в истории ;). Для уже рассмотренных примеров с числами 2.36 и 0.51 ситуация будет выглядеть следующим образом: первая строка запишется в промежуточный массив два раза и с вероятностью 0.36 запишется в третьй раз. Вторая же строка имеет вероятность равную 0.51 того, что она вообще будет присутствовать во вспомогательном массиве.

Данная стратегия отбора знаменита тем, что именно для неё создана классическая теорема шим (вот откуда там дробь).

Турнирный отбор может быть описан следующим образом: из популяции, содержащей N строк, выбирается случайным образом t строк и лучшая строка записывается в промежуточный массив (между выбранными строками проводится турнир). Эта операция повторяется N раз. Строки в полученном промежуточном массиве затем используются для скрещивания (также случайным образом). Размер группы строк, отбираемых для турнира часто равен 2. В этом случае говорят о двоичном/парном турнире (binary tournament). Вообще же t называется численностью турнира (tournament size). Чем больше турнир, тем более жесткий вариант селекции, т.е. тем меньше шансов у особей, "кому за, или кто просто плохо".

Преимуществом данной стратегии является то, что она не требует дополнительных вычислений и упорядочивания строк в популяции по возрастанию приспособленности. Также, на мой взгляд, такой вариант селекции ближе к реальности, т.к. успешность той или иной особи во многом определяется ее окружением, насколько оно лучше или хуже ее. А иначе получилось бы, что бац! появился где-нибудь в Бразилии супер-таракан, а в России все усатые собратья тараканьи взяли (тоже бац!) и вымерли, от осознания своей неприспособленности. ;)

Данная стратегия использует отсортированную по возрастанию популяцию. Число особей для скрещивания выбирается в соответствии с порогом TО[0; 1]. Порог определяет какая доля особей, начиная с самой первой (=самой приспособленной) будет принимать участие в отборе. В принципе, порог можно задать и числом больше 1, тогда он будет просто равен числу особей из текущей популяции, допущенных к отбору. Среди особей, попавших "под порог" случайным образом N раз выбирается самая везучая и записывается в промежуточный массив, из которого затем выбираются особи непосредственно для скрещивания.

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

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

Стратегии формирования нового поколения

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

1. Новые особи (потомки) занимают места своих родителей. После чего наступает следующий этап, в котором потомки оцениваются, отбираются, дают потомство и уступают место своим "детям". Написал, и аж самому грустно стало, до чего все невесело и уныло ;).
2. Создается промежуточная популяция, которая включает в себя как родителей, так и их потомков. Члены этой популяции оцениваются, а затем из них выбираются N самых лучших, которые и войдут в следующее поколение.

Если вы знакомы с эволюционными стратегиями, то с этими способами вы уже встречались. Что из этих двух вариантов лучше - выбирать вам. На мой взгляд второй вариант практичнее (т.к. не позволяет заменять приспособленных родителей на "неизвестно кого"), но тут может быть больше проблем с преждевременной сходимостью, чем в первом варианте. К тому же он требует сортировки массива размером (как минимум) 2*N.

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

Принцип "элитизма"

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

Использование "элитизма" позволяет не потерять хорошее промежуточное решение, но, в то же время, из-за этого алгоритм может "застрять" в локальном экстремуме. Однако, мой скромный опыт позволяет сделать вывод, что в большинстве случаев "элитизм" нисколько не вредит поиску решения, и главное - это предоставить алгоритму возможность анализировать разные строки из пространства поиска. Помните про спайс и да прибудет с вами великая сила :))).

Подробнее об элитизме можно прочитать здесь

Источники:

1. Tobias Blickle and Lothar Thiele "A Comparison of Selection Schemes used in Genetic Algorithm", 1995, 2 Edition.

2. Darrel Whitley "A Genetic Algorithm Tutorial", 1993.

3. Д.И.Батищев, С.А.Исаев Оптимизация многоэкстремальных функций с помощью генетических алгоритмов./Межвузовский сборник научных трудов "Высокие технологии в технике, медицине и образовании", Воронеж, ВГТУ, 1997г, стр.4-17.