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

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

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

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

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

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

Проиллюстрируем примеры хромосомы и генов для двоичного способа кодирования параметров задачи:

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

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

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

Каждая хромосома может кодировать только один параметр задачи. Но так как в одном генотипе может быть несколько хромосом, то один генотип может закодировать несколько параметров. Например: генотип включает в себя две хромосомы, каждая хромосома состоит из 3 генов, значит, первые 3 гена генотипа кодируют один параметр, а вторые 3 гена – второй параметр. Проиллюстрируем пример генотипа и фенотипа:

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

Аллель – это значение конкретного гена.

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

Локи – это множество позиций генов.

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

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

Это интересно

Смотрите также