4.3. Основные понятия генетических алгоритмовПри описании генетических алгоритмов используются определения, заимствованные из генетики. Например, речь идет о популяции особей, а в качестве базовых понятий применяются ген, хромосома, генотип, фенотип, аллель. Также используются соответствующие этим терминам определения из технического лексикона, в частности, цепь, двоичная последовательность, структура. Популяция - это конечное множество особей. Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированным в них множествами параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска (search points). В некоторых работах особи называются организмами. Хромосомы (другие названия - цепочки или кодовые последовательности) - это упорядоченные последовательности генов. Ген (также называемый свойством, знаком или детектором) - это атомарный элемент генотипа, в частности, хромосомы. Генотип или структура - это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы либо единичные хромосомы (в довольно распространенном случае, когда генотип состоит из одной хромосомы). Фенотип - это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска). Аллель - это значение конкретного гена, также определяемое как значение свойства или вариант свойства. Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов - это локи. Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функционирование генетических алгоритмов и должна иметь точное и корректное определение. В задачах оптимизации функция приспособленности, как правило, оптимизируется (точнее говоря, максимизируется) и называется целевой функцией. В задачах минимизации целевая функция преобразуется, и проблема сводится к максимизации. В теории управления функция приспособленности может принимать вид функции погрешности, а в теории игр - стоимостной функции. На каждой итерации генетического алгоритма приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляющих множество потенциальных решений проблемы, например, задачи оптимизации. Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков». Пример 4.1 Рассмотрим функцию
и допустим, что В этом случае в качестве параметра задачи выступает переменная 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Это широко известный способ двоичного кодирования, связанный с записью десятичных цифр в двоичной системе. Представленные кодовые последовательности также называются цепями или хромосомами. В рассматриваемом примере они выступают и в роли генотипов. Каждая из хромосом состоит из 4 генов (иначе можно сказать, что двоичные последовательности состоят из 4 битов). Значение гена в конкретной позиции называется аллелью, принимающей в данном случае значения 0 или 1. Популяция состоит из особей, выбираемых среди этих 16 хромосом. Примером популяции с численностью, равной 6, может быть, например, множество хромосом Пример 4.2 Рассмотрим следующий пример постановки оптимизационной задачи. Для системы, изображенной на рис. 4.1, следует найти
где Рис. 4.1. Схема оптимизационной двухпараметрической системы. В роли параметров этой задачи выступают Допустим, что Таблица 4.1. Популяция особей (для примера 4.2)
Первые 10 генов каждого генотипа соответствуют параметру Способ кодирования значений параметров Пример 4.3 Рассмотрим нейронную сеть, представленную на рис. 4.2, для которой необходимо подобрать оптимальные веса
Рис. 4.2. Нейронная сеть, реализующая операцию XOR. Это сеть, реализующая систему XOR, поэтому значения В приведенных примерах (4.1 - 4.3) хромосомы и генотипы обозначают одно и то же - фенотипы особей популяции, закодированные в форме упорядоченных последовательностей генов со значениями (аллелями), равными 0 или 1. В генетике генотип задает генетическую структуру особи, которая может включать более одной хромосомы. Например, клетки человека содержат 46 хромосом. В генетических алгоритмах генотип определяется аналогичным образом, однако чаще всего он состоит всего из одной хромосомы, которая и выступает в роли особи популяции. Длина хромосом зависит от условий задачи (см. разд. 4.6). Следует заметить, что в естественных организмах хромосома может состоять из нескольких сотен и даже тысяч генов. У человека имеется около 100 000 генов, хотя их точное количество до сих пор неизвестно.
|