Символьная модель простого га
Цель в оптимизации с помощью ГА состоит в том, чтобы найти лучшее возможное решение или решения задачи по одному или нескольким критериям. Чтобы реализовать генетический алгоритм нужно сначала выбрать подходящую структуру для представления этих решений. В постановке задачи поиска, экземпляр этой структуры данных представляет точку в пространстве поиска всех возможных решений.
Структура данных генетического алгоритма состоит из одной или большее количество хромосом (обычно из одной). Как правило, хромосома - это битовая строка, так что термин строка часто заменяет понятие "хромосома". В принципе, ГА не ограничены бинарным представление. Известны другие реализации, построенные исключительно на векторах вещественных чисел (L. Davis, 1991b; Eshelman и Schaffer, 1993; Goldberg, 1991a, 1991b). Несмотря на то, что для многих реальных задач, видимо, больше подходят строки переменной длины, в настоящее время структуры фиксированной длины наиболее распространены и изучены. Пока и мы ограничимся только структурам, которые являются одиночными строками по l бит.
Каждая хромосома (строка) представляет собой конкатенацию ряда подкомпонентов называемых генами. Гены располагаются в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген – бит, локус - его позиция в строке, и аллель - его значение (0 или 1). Биологический термин "генотип" относится к полной генетической модели особи и соответствует структуре в ГА. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров. Чрезвычайно простой, но иллюстративный пример – задача максимизации следующей функции двух переменных:
f (x1, x2) = exp(x1x2), где 0 < x1< 1 и 0 < x2 < 1.
Обычно, методика кодирования реальных переменных x1 и x2 состоит в их преобразовании в двоичные целочисленные строки достаточной длины – достаточной для того, чтобы обеспечить желаемую точность. Предположим, что 10-разрядное кодирование достаточно и для x1, и x2. Установить соответствие между генотипом и фенотипом закодированных особей можно, разделив соответствующее двоичное целое число – на 210-1. Например, 0000000000 соответствует 0/1023 или 0, тогда как 1111111111 соответствует 1023/1023 или 1. Оптимизируемая структура данных – 20-битная строка, представляющая конкатенацию кодировок x1 и x2. Переменная x1 размещается в крайних левых 10-разрядах, тогда как x2 размещается в правой части генотипа особи (20-битовой строке). Генотип – точка в 20-мерном хеммининговом пространстве, исследуемом ГА. Фенотип – точка в двумерном пространстве параметров.
Чтобы оптимизировать структуру, используя ГА, нужно задать некоторую меру качества для каждой структуры в пространстве поиска. Для этой цели используется функция приспособленности. В функциональной максимизации, целевая функция часто сама выступает в качестве функции приспособленности (например наш двумерный пример); для задач минимизации, целевую функцию следует инвертировать и сместить затем в область положительных значений.