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

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

Рассмотрим в отдельности каждый из случаев.

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

При решении задачи максимизации особь тем лучше, чем больше значение её функции приспособленности. Пусть имеем N особей, из которых производим выбор, и соответствующие им значения функции приспособленности Ri, i=(1, N). Для вычисления вероятностей выбора особей по значениям функции приспособленности необходимо использовать следующее выражение:

(1) ,

где

(2)

Следует учесть, что при использовании выражения (1) самая плохая особь никогда не будет выбрана: P = 0.

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

(3) ,

где

(4)

Аналогично предыдущему случаю при использовании выражения (3) особь с наибольшим значением приспособленности никогда не будет выбрана.

Если число особей, из которых производится выбор, небольшое, вероятность выбора худшей из них должна отличаться от нуля. В этом случае имеет смысл задаться минимальной вероятностью выбора худшей особи, исходя из следующих рассуждений. При одинаковых значениях функции приспособленности всех особей вероятности выбора каждой из них должны быть равны и определяются числом самих особей: P = 1/N. Введём понижающий коэффициент (γ), определяющий минимальную вероятность выбора:

(5)

Наиболее часто используемые значения минимальных вероятностей (Pmin) сведены в таблицу.

Зависимость минимальной вероятности выбора из нескольких особей от их количества и значения понижающего коэффициента

Понижающий коэффициент (γ)Количество особей (N)
23456
0,1 0,050 0,033 0,025 0,020 0,017
0,2 0,100 0,067 0,050 0,040 0,033
0,3 0,150 0,100 0,075 0,060 0,050
0,4 0,200 0,133 0,100 0,080 0,067
0,5 0,250 0,167 0,125 0,100 0,083

С учётом вышесказанного, в числитель и знаменатель соотношений (1) и (3) вносится поправка Q, в результате чего они преобразуются к видам (6) и (7) соответственно:

(6) ,
(7)

,

где значения Q рассчитываются по соотношениям (8) и (9) соответственно:

(8) ,
(9)

Ещё один способ перейти к отличной от нуля вероятности выбора худшей особи – принять значения Rmin и Rmax выходящими за пределы диапазона изменения приспособленностей всех особей текущей популяции на некоторую его часть (0 < φ ≤ 0,5). В этом случае соотношения (2) и (4) заменяются на (10) и (11), а формулы для расчёта вероятностей остаются прежними: (1) и (3):

(10) ,
(11)

При решении вопроса о выборе одной из получившихся дочерних особей для включения в новое поколение руководствуются следующими правилами:
– особь выбирается случайным образом;
– особь выбирается случайным образом с вероятностями, пропорциональными улучшению функции приспособленности, рассчитываемыми по соотношениям (1) или (6) – при решении задачи максимизации и (3) или (7) – при решении задачи минимизации;
– выбирается особь с наилучшим значением функции приспособленности.

При выборе особей для исключения из популяции, с учётом используемых эволюционных стратегий, руководствуются следующими правилами:
– все особи выбираются случайным образом;
– все особи выбираются случайным образом с вероятностями, пропорциональными ухудшению функции приспособленности, т. е. для задачи максимизации используют выражения (3) или (7), а для задачи минимизации – (1) или (6);
– выбираются особи с наихудшими значениями функции приспособленности.

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

По материалам учебного пособия:
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.