4.3. Основные понятия генетических алгоритмов

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

Популяция - это конечное множество особей.

Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированным в них множествами параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска (search points). В некоторых работах особи называются организмами.

Хромосомы (другие названия - цепочки или кодовые последовательности) - это упорядоченные последовательности генов.

Ген (также называемый свойством, знаком или детектором) - это атомарный элемент генотипа, в частности, хромосомы.

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

Фенотип - это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска).

Аллель - это значение конкретного гена, также определяемое как значение свойства или вариант свойства.

Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов - это локи.

Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функционирование генетических алгоритмов и должна иметь точное и корректное определение. В задачах оптимизации функция приспособленности, как правило, оптимизируется (точнее говоря, максимизируется) и называется целевой функцией. В задачах минимизации целевая функция преобразуется, и проблема сводится к максимизации. В теории управления функция приспособленности может принимать вид функции погрешности, а в теории игр - стоимостной функции. На каждой итерации генетического алгоритма приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляющих множество потенциальных решений проблемы, например, задачи оптимизации.

Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков».

Пример 4.1

Рассмотрим функцию

                      (4.1)

и допустим, что  принимает целые значения из интервала от 0 до 15. Задача оптимизации этой функции заключается в перемещении по пространству, состоящему из 16 точек со значениями для обнаружения той точки, в которой функция принимает максимальное (или минимальное) значение.

В этом случае в качестве параметра задачи выступает переменная . Множество  составляет пространство поиска и одновременно - множество потенциальных решений задачи. Каждое из 16 чисел, принадлежащих к этому множеству, называется точкой пространства поиска, решением, значением параметра, фенотипом. Следует отметить, что решение, оптимизирующее функцию, называется наилучшим или оптимальным решением. Значения параметра  от 0 до 15 можно закодировать следующим образом:

0000    0001    0010    0011    0100    0101    0110    0111

1000    1001    1010    1011    1100    1101    1110    1111

Это широко известный способ двоичного кодирования, связанный с записью десятичных цифр в двоичной системе. Представленные кодовые последовательности также называются цепями или хромосомами. В рассматриваемом примере они выступают и в роли генотипов. Каждая из хромосом состоит из 4 генов (иначе можно сказать, что двоичные последовательности состоят из 4 битов). Значение гена в конкретной позиции называется аллелью, принимающей в данном случае значения 0 или 1. Популяция состоит из особей, выбираемых среди этих 16 хромосом. Примером популяции с численностью, равной 6, может быть, например, множество хромосом , представляющих собой закодированную форму следующих фенотипов: . Функция приспособленности в этом примере задается выражением (4.1). Приспособленность отдельных хромосом в популяции определяется значением этой функции для значений , соответствующих этим хромосомам, т.е. для фенотипов, соответствующих определенным генотипам.

Пример 4.2

Рассмотрим следующий пример постановки оптимизационной задачи. Для системы, изображенной на рис. 4.1, следует найти

,

где .

Рис. 4.1. Схема оптимизационной двухпараметрической системы.

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

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

Таблица 4.1. Популяция особей (для примера 4.2)

Первые 10 генов каждого генотипа соответствуют параметру , а последние 10 генов - параметру . Таким образом, длина хромосом равна 20.

Способ кодирования значений параметров  и  в виде хромосом будет подробно изложен в разд. 4.6.

Пример 4.3

Рассмотрим нейронную сеть, представленную на рис. 4.2, для которой необходимо подобрать оптимальные веса , , , , ,  и , , , минимизирующих значение погрешности

.

Рис. 4.2. Нейронная сеть, реализующая операцию XOR.

Это сеть, реализующая систему XOR, поэтому значения  и , а также  для  принимают значения, приведенные в табл. 2.1. В качестве параметров рассматриваемой задачи выступают перечисленные выше веса, т.е. задача имеет 9 параметров. В данном примере набор из этих 9 параметров определяет точку пространства поиска и, следовательно, представляет собой возможное решение. Допустим, что веса могут принимать значения из интервала . Тогда каждая хромосома будет комбинацией из 9 двоичных последовательностей, кодирующих конкретные веса. Это, очевидно, и есть генотипы. Соответствующие им фенотипы представлены значениями отдельных весов, т.е. множествами соответствующих действительных чисел из интервала .

В приведенных примерах (4.1 - 4.3) хромосомы и генотипы обозначают одно и то же - фенотипы особей популяции, закодированные в форме упорядоченных последовательностей генов со значениями (аллелями), равными 0 или 1.

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

Длина хромосом зависит от условий задачи (см. разд. 4.6). Следует заметить, что в естественных организмах хромосома может состоять из нескольких сотен и даже тысяч генов. У человека имеется около 100 000 генов, хотя их точное количество до сих пор неизвестно.