Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


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, следует найти

,

где .

120.jpg

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

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

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

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

Генотипы

Фенотипы

00000000000000000000

–25,00

–25,00

10100010010011001011

6,72

–15,08

01101000101111010010

–4,57

22,8.

11011010011110000111

17,67

19,13

00011011000000010001

–19,72

–24,17

00110000101011111010

–15,52

12,24

11111111111111111111

25,00

25,00

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

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

Пример 4.3

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

.

121.jpg

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

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

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

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

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

 



<< ПредыдущаяОглавлениеСледующая >>