Генетические алгоритмы

Введение в генетические алгоритмы

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

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

Идею генетических алгоритмов высказал Дж. Холланд в конце шестидесятых - начале семидесятых годов XX века [23]. Он заинтересовался свойствами процессов естественной эволюции (в том числе фактом, что эволюционируют хромосомы, а не сами живые существа). Холланд был уверен в возможности реализовать в виде компьютерной программы алгоритм, решающий сложные задачи так, как это делает природа – путем эволюции.

Генетический алгоритм представляет собой метод решения задач оптимизации в виде процедур поиска, основанных на механизмах естественного отбора и наследования. В них используется эволюционный принцип выживания наиболее приспособленных особей. Они отличаются от традиционных методов оптимизации несколькими базовыми элементами. В частности, генетические алгоритмы:

1) обрабатывают не значения параметров самой задачи, а их закодированную форму;

2) осуществляют поиск решения исходя не из единственной точки, а из их некоторой популяции;

3) используют только целевую функцию, а не ее производные либо иную дополнительную информацию,

4) применяют вероятностные правила выбора.

Перечисленные свойства приводят в результате к устойчивости генетических алгоритмов и их превосходству над другими методами оптимизации.

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

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

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

Хромосомы – это упорядоченные последовательности генов.

Ген – это атомарный элемент генотипа, в частности, хромосомы.

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

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

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

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

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

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

В качестве примера рассмотрим функцию

f (x) = 2 x ²+1

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

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

0000 0001 0010 0011 0100 0101 0110 0111

1000 1001 1010 1011 1100 1101 1110 1111

Это широко известный способ двоичного кодирования, связанный с записью десятичных цифр в двоичной системе счисления. Представленные кодовые последовательности также называются цепями или хромосомами. В рассматриваемом примере они выступают и в роли генотипов. Каждая из хромосом состоит из 4 генов. Значение гена в конкретной позиции называется аллелью, принимающей в данном случае значения 0 или 1. Популяция состоит из особей, выбираемых среди этих 16 хромосом. Примером популяции с численностью, равной 6, может быть, например, множество хромосом {0010, 0101, 0111, 1001, 1100, 1110}, представляющих собой закодированную форму следующих фенотипов: {2, 5, 7, 9, 12, 14}. Функция приспособленности в этом примере задается выражением f (x). Приспособленность отдельных хромосом в популяции определяется значением этой функции для значений х, соответствующих этим хромосомам, т.е. для фенотипов, соответствующих определенным генотипам.

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

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