Интеллектуальные информационные системы. Дубровин А.Д. - 174 стр.

      Примечание: на основании данных об интервале десятичных значений аргументов, на
котором определена целевая функция, сразу же определяется минимальное значение
величины z - числа разрядов двоичного кода (то есть, числа генов) каждой хромосомы
исходной популяции - по условию 2 z ≥ R.
      Шаг 2. Положить П=1 (открыт счетчик числа генерируемых популяций).
      Шаг 3. Случайным образом выбирается пара родительских хромосом (из N
сгенерированных в исходной популяции) для скрещивания (кроссовера). Этот выбор может
быть и не совсем случаен, ибо, зная вид целевой функции, иногда можно сориентировать
выбор на те хромосомы, которые характеризуются (в сочетании) максимальным значением
ЦФ (то есть показывают наилучшую жизнеспособность). Допустим, выбор, тем или иным
способом, сделан и победителями оказались хромосомы ( х i и х j ).
      Шаг 4. Формируем генотип потомка П-й популяции. Для этого вычисляется
вероятность проведения операции кроссовера над выбранными хромосомами (i,j). Эти
вероятности вычисляются по формуле
                                    F ( xi )
                              pi = N
                                   ∑ F ( xi )
                                   i =1
       После этого, опять же с помощью датчика случайных чисел, определяется потомок,
который будет объявлен родоначальником П-й популяции; запоминается его код (х i ) и
номер (индекс i).
       Шаг 5. Над кодом родоначальника П-й популяции, допустим это будет хромосома с
индексом ( j ), совершаются операции инверсии и (или) мутации и полученный в результате
этих операций новый код генотипа и его индекс запоминаются соответственно под
значениями (х j ) и ( j ).
       Шаг 6. Заменяем в П-й популяции старый код хромосомы с индексом ( j ) на новый,
полученный после инверсии и мутации ( если они проводились).
       Шаг 7. Вычисляем значение целевой функции П-й популяции с учетом всех
проведенных операций и вычисляем среднюю жизнеспособность всей популяции.
       Шаг 8. Если обнаружены признаки (симптомы) инцухта или совершено
запланированное число сгенерированных популяций, то алгоритм заканчивает «работу»,
иначе – положить П = П + 1 и перейти к шагу 3.
       Рассмотрим пример применения описанного генетического алгоритма для
                                                                                    N
максимизации целевой функции (ЦФ) на множестве аргументов {х i }: F({х i }) =   ∑   i =1
                                                                                           (2x i +1),

где N – число аргументов, которыми должны быть случайным образом сгенерированные
коды четырех (N=4) хромосом. ЦФ определена на десятичных значениях аргументов в
интервале [0,14]. Это значит, что длина кода хромосом (z) должна быть равна четырем битам
( по условию 2 z ≤15 ) и, что немаловажно, - в данном процессе недопустимо «участие»
хромосомы с десятичным значением кода более 14 или с двоичным кодом более (1 1 1 0).
Допустим, что получены следующие коды хромосом исходной популяции: 0101, 1010, 1101,
0011. Им соответствуют десятичные значения: 5, 6, 9, 3. Как видим, условия определения
ЦФ удовлетворены. Составим таблицу для записи результатов вычислительных и
генетических операций, отражающих «работу» алгоритма (табл.7.5.2-1).
                                                                      Таблица 7.5.2-1
  индекс     двоичный      десятичное F(x i ) =              ожидаемое    округленное
хромосомы        код        значение    2x i + 1   F ( x i ) число копий  (реальное)
   (i)       хромосомы        кода                N          хромосомы число копий
                           хромосомы             ∑ F ( xi ) в будущем хромосомы
                                                i =1
   1          0101           5            11    0,22      0,22*N=0,88           1

                                                                                                209