Введение в эволюционное моделирование. Каширина И.Л. - 8 стр.

                                          8
                                Оценка особей популяции
      Чтобы оптимизировать какую-либо структуру с использованием ГА,
нужно задать меру качества для каждого индивида в пространстве поиска.
Для этой цели используется функция приспособленности. В задачах мак-
симизации целевая функция часто сама выступает в качестве функции при-
способленности (например, как в рассмотренном ранее двумерном примере);
для задач минимизации целевую функцию следует инвертировать. Если ре-
шаемая задача имеет ограничения, выполнение которых невозможно кон-
тролировать алгоритмически, то функция приспособленности, как правило,
включает также штрафы за невыполнение ограничений (они уменьшают ее
значение).
                           Отбор (селекция)
     На каждом шаге эволюции с помощью вероятностного оператора се-
лекции (отбора) выбираются два решения-родителя для их последующего
скрещивания. Среди операторов селекции наиболее распространенными яв-
ляются два вероятностных оператора пропорциональной и турнирной се-
лекции. В некоторых случаях также применяется отбор усечением.
Пропорциональный отбор (Proportional selection)
     При пропорциональной селекции вероятность на k-м шаге выбрать ре-
шение i в качестве одного из родителей задается формулой:
                    f (i )
P{i − выбрано} =            ,    в предположении, что f (i) > 0 для всех i   Ik
                   ∑ f ( j)
                   j∈I k

(здесь Ik –популяция на k-м шаге).
      Простейший пропорциональный отбор � � рулетка � �           отбирает
особей с помощью n "запусков" рулетки. Колесо рулетки содержит по од-
ному сектору для каждого i-го члена популяции. Размер i-го сектора пропор-
ционален соответствующей величине P(i). При таком отборе члены популя-
ции с более высокой приспособленностью с большей вероятностью будут
чаще выбираться, чем особи с низкой приспособленностью.
Турнирный отбор (Tournament selection)
      Турнирный отбор может быть описан следующим образом: из популя-
ции, содержащей m строк (особей), выбирается случайным образом t строк и
лучшая строка записывается в промежуточный массив (между выбранными
строками проводится турнир). Эта операция повторяется m раз. Строки в по-
лученном промежуточном массиве затем используются для скрещивания
(также случайным образом). Размер группы строк, отбираемых для турнира,
часто равен 2. В этом случае говорят о двоичном/парном турнире. Вообще
же t называется численностью турнира.
Отбор усечением (Truncation selection)