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

       Предполагается, что целевая функция генетического синтеза может быть выражена
математической зависимостью от значений двоичных кодов хромосом, участвующих в
синтезе.
      Генетический алгоритм «работает» следующим образом. Создается (случайным
образом генерируется) исходная популяция (ИП) – сообщество свободно скрещивающихся
особей. Генерация ИП предполагает и случайные значения кодов хромосом каждой особи.
Начиная с этой точки, алгоритм может начинать генерировать (репродуцировать) новую
популяцию.
      Репродукция представляет собой целенаправленный (то есть осуществляемый с
учетом характера и вида целевой функкци) процесс отбор для получения потомства с
предпочтительными свойствами от случайно выбранных представителей ИП. Включение в
процесс репродукции процедуры селекции значительно ускоряет синтез искомого решения.
Процесс репродукции является аналогом (моделью) процесса деления родительских
хромосом в соответствии с принципом «выживает сильнейший». В машинных алгоритмах
генетического синтеза выбор (из ИП) пар родительских хромосом для репродукции
потомства может быть сделан с применением датчика случайных чисел.
      По завершении процесса репродукции, к отобранным хромосомам могут быть
применены специальные генетические операторы:
      - кроссовер;
      - мутация;
      - инверсия.
      Порядок применения этих операторов не обязательно таков, как указанно выше.
      Рассмотрим содержание и схематически отобразим действия этих операторов на
примере достаточно «длинных» хромосом, значения генов которых представлены цифрами
двоичной системы счисления, то есть 0 и 1 .
       Кроссовер является наиболее важным генетическим оператором. Он генерирует
новую хромосому, объединяя генетический материал двух родительских хромосом.
Существует несколько вариантов кроссовера. Наиболее простым является одноточечный
кроссовер. В этом варианте просто берутся две хромосомы равной длины, и перерезаются в
случайно выбранной точке. Результирующая хромосома получается из начала одной и
окончания другой родительских хромосом:
      11001↑0101011 ⇒               101010101011
      10101↑0011111 ⇒               110010011111
      Мутация представляет собой случайное изменение хромосомы (обычно простым
изменением значения или состояния одного из битов на альтернативное). Данный оператор,
с одной стороны - позволяет алгоритму более быстро находить локальные экстремумы, а с
другой – пропустив глобальный экстремум, «перескочить» на другой локальный экстремум.
      111001010101 ⇒                111001010100
      Инверсия изменяет порядок следования битов в хромосоме путем их циклической
перестановки (случайное количество раз). Многие модификации генетических алгоритмов
обходятся без инверсии.
      110010101011          ⇒       100110101011
       Последовательность шагов простого генетического алгоритма, включающего
операции репродукции, кроссовера и мутации, может быть следующей.
       Шаг 1. Задаемся числом хромосом исходной популяции - N. Случайным образом
генерируются коды всех N родительских хромосом этой популяции. Параметры генофонда:
все хромосомы (х i , i =1,…,N) кодируются двоичными кодами; целевая функция F({x i })
алгоритма известна и определена на интервале десятичных значений аргументов [0,R].
Задача: сгенерировать получение потомства с максимально возможным значением целевой
функции.
                                                                                  208