Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
2. Основные понятия генетических алгоритмов: популяция, особь, хромосома, ген, генотип, фенотип, аллель, локус, функция приспособленности. Кодирование хромосом.
Основные понятия генетических алгоритмов
При описании генетических алгоритмов используются определения, заимствованные из генетики. Например, речь идет о популяции особей, а в качестве базовых понятий применяются ген, хромосома, генотип, фенотип, аллель. Также используются соответствующие этим терминам определения из технического лексикона, в частности, цепь, двоичная последовательность, структура.
Популяция - это конечное множество особей.
Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированными в них множествами параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска (search points). В некоторых работах особи называются организмами.
Хромосомы (другие названия - цепочки или кодовые последовательности) - это упорядоченные последовательности генов.
Ген (также называемый свойством, знаком или детектором) - это атомарный элемент генотипа, в частности, хромосомы.
Генотип или структура - это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы либо единичные хромосомы (в довольно распространенном случае, когда генотип состоит из одной хромосомы).
Фенотип - это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска).
Аллель - это значение конкретного гена, также определяемое как значение свойства или вариант свойства.
Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов - это локи (локусы).
Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функционирование генетических алгоритмов и должна иметь точное и корректное определение. В задачах оптимизации функция приспособленности, как правило, оптимизируется (точнее говоря, максимизируется) и называется целевой функцией. В задачах минимизации целевая функция преобразуется, и проблема сводится к максимизации. В теории управления функция приспособленности может принимать вид функции погрешности, а в теории игр - стоимостной функции. На каждой итерации генетического алгоритма приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляющих множество потенциальных решений проблемы, например, задачи оптимизации.
Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков».
Кодирование хромосом
Рассмотрим функцию
f(x) = 2x2+1
и допустим, что х принимает целые значения из интервала от 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 генов (иначе можно сказать, что двоичные последовательности состоят из 4 битов). Значение гена в конкретной позиции называется аллелью, принимающей в данном случае значения 0 или 1. Популяция состоит из особей, выбираемых среди этих 16 хромосом. Примером популяции с численностью, равной 6, может быть, например, множество хромосом {0010, 0101, 0111, 1001, 1100, 1110}, представляющих собой закодированную форму следующих фенотипов: {2, 5, 7, 9, 12, 14}. Функция приспособленности в этом примере задается формулой условия. Приспособленность отдельных хромосом в популяции определяется значением этой функции для значений х, соответствующих этим хромосомам, т.е. для фенотипов, соответствующих определенным генотипам.
В приведенном примере хромосомы и генотипы обозначают одно и то же - фенотипы особей популяции, закодированные в форме упорядоченных последовательностей генов со значениями (аллелями), равными 0 или 1.
В генетике генотип задает генетическую структуру особи, которая может включать более одной хромосомы. Например, клетки человека содержат 46 хромосом. В генетических алгоритмах генотип определяется аналогичным образом, однако чаще всего он состоит всего из одной хромосомы, которая и выступает в роли особи популяции. Причем «сложная» или составная хромосома может содержать несколько кодируемых параметров.
Длина хромосом зависит от условий задачи. Следует заметить, что в естественных организмах хромосома может состоять из нескольких сотен и тысяч генов. В настоящее время предполагается, что у человека имеется около 20000-25000 генов.