Представление данных в генах |
|
Для решения некоторой задачи с помощью ГА её данные необходимо представить в виде генов особи. Для этого прежде всего необходимо определить какие параметры задачи необходимо настроить. Например, если мы пытаемся аппроксимировать с помощью ГА набор точек функцией вида f(x) = A*exp(k*x), где А, k - константы, х - независимая переменная, то в качестве параметров будут выступать А и k, т.к. от их значения зависит вид и поведение функции. Итак, имеем два параметра и, следовательно, два гена. Следующий шаг - это выбор числа разрядов в каждом гене. Здесь необходимо учитывать, что с одной стороны, чем больше разрядов, тем лучше, т.к. выше точность и т.д., но с другой - большое число разрядов влечет увеличение времени поиска решения (сходимости). Стоит отметить, что с ростом числа параметров (в некоторых задачах они исчисляются сотнями) "лишние" разряды сказываются все сильнее и сильнее. Поэтому необходимо найти компромисс между точностью и скоростью. Возьмем для задачи аппроксимации 16-разрядные гены, при этом параметры будут изменяться от -32,768 до 32,767 с шагом в 0,001. Данные числа получены, исходя из того, что 16-разрядное число может принимать одно из 216= 65536 значений от 0 до 65535. Если предположить, что 0 будет в середине этого интервала, причем каждое значение разделится затем на 1000, то получим интервал изменения параметров и шаг изменения. После того, как выбраны параметры, их число и разрядность, необходимо решить, как непосредственно записывать данные. Можно использовать обычное кодирование, когда 1011=10112=1110, либо коды Грея, когда 1011=11102= 1410. Несмотря на то, что коды Грея влекут неизбежное кодирование/декодирование данных, они позволяют избежать некоторых проблем, которые появляются в результате обычного кодирования. Могу лишь сказать, что преимущество кода Грея в том, что если два числа различаются на 1, то и их двоичные коды различаются только на один разряд, а в двоичных кодах не все так просто. Стоит отметить, что кодировать и декодировать в коды Грея довольно удобно, описать это можно так: сначала копируется самый старший разряд, затем:
Здесь, G[i] - i-й разряд кода Грея, а B[i] - i-й разряд бинарного кода. Например, последовательность чисел от 0 до 7 в двоичном коде: {000, 001, 010, 011, 100, 101, 110, 111}, а в кодах Грея: {000, 001, 011, 010, 110, 111, 101, 100}. Итак, теперь заданы все необходимые характеристики генов, остается только представить все это на каком-нибудь языке программирования. Например, на С++ одна особь с хромосомой из двух 16-разрядных генов может "выглядеть" так:
Последний пример на первый взгляд кажется как минимум странным: зачем для задания одного бита использовать целый байт? Однако бывают случаи, когда используются небинарные алфавиты, т.е. каждый разряд может принимать не 2 различных значения "0" или "1", а больше, например, "1", "2", "4", "8". Как раз для таких ситуаций последний пример и удобен. В дальнейшем речь будет идти только о бинарном алфавите. Кроме того, в последнем способе легче использовать коды Грея. Для того чтобы задать популяцию из 50 особей, можно поступить одним из следующих способов:
Следует также отметить, что в задаче аппроксимации, взятой в качестве примера, в процессе "эволюции" будут учавствовать все гены особи, т.е. генетические операторы будут применяться к каждому гену. Однако, это не всегда необходимо, например, рассмотрим задачу компоновки, т.е. когда на некоторой известной поверхности требуется разместить N элементов разной площади так, чтобы они не накладывались друг на друга. Для простоты будем считать, что все элементы имеют прямоугольную форму. Настраиваемыми (оптимизируемыми) параметрами будут координаты каждого элемента, т.е. каждая хромосома будет содержать два гена, соответствующие координатам левого верхнего угла элемента. Но помимо этого необходимо знать, какой элемент представляет данная особь. Для этого необходимо добавить в набор генов особи ещё один ген, содержащий номер элемента. При этом нам нужно сохранить значение этого гена неизменным в течении всего процесса поиска решения. Таким образом, получаем особь с тремя генами, два из которых обрабатываются генетическими операторами, а один нет. Помимо рассмотренных задач аппроксимации и компоновки можно привести варианты кодирования для некоторых других задач:
И напоследок, разрядность генов необязательно должна быть фиксированной, многие современные алгоритмы самостоятельно подстраивают число разрядов для каждого гена в зависимости от промежуточных результатов поиска решения. Источники:
|