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

Представление данных в генах

Для решения некоторой задачи с помощью ГА её данные необходимо представить в виде генов особи. Для этого прежде всего необходимо определить какие параметры задачи необходимо настроить. Например, если мы пытаемся аппроксимировать с помощью ГА набор точек функцией вида f(x) = A*exp(k*x), где А, k - константы, х - независимая переменная, то в качестве параметров будут выступать А и k, т.к. от их значения зависит вид и поведение функции. Итак, имеем два параметра и, следовательно, два гена.

Следующий шаг - это выбор числа разрядов в каждом гене. Здесь необходимо учитывать, что с одной стороны, чем больше разрядов, тем лучше, т.к. выше точность и т.д., но с другой - большое число разрядов влечет увеличение времени поиска решения (сходимости). Стоит отметить, что с ростом числа параметров (в некоторых задачах они исчисляются сотнями) "лишние" разряды сказываются все сильнее и сильнее. Поэтому необходимо найти компромисс между точностью и скоростью. Возьмем для задачи аппроксимации 16-разрядные гены, при этом параметры будут изменяться от -32,768 до 32,767 с шагом в 0,001. Данные числа получены, исходя из того, что 16-разрядное число может принимать одно из 2¹⁶= 65536 значений от 0 до 65535. Если предположить, что 0 будет в середине этого интервала, причем каждое значение разделится затем на 1000, то получим интервал изменения параметров и шаг изменения.

После того, как выбраны параметры, их число и разрядность, необходимо решить, как непосредственно записывать данные. Можно использовать обычное кодирование, когда 1011=1011₂=11₁₀, либо коды Грея, когда 1011=1110₂= 14₁₀. Несмотря на то, что коды Грея влекут неизбежное кодирование/декодирование данных, они позволяют избежать некоторых проблем, которые появляются в результате обычного кодирования. Могу лишь сказать, что преимущество кода Грея в том, что если два числа различаются на 1, то и их двоичные коды различаются только на один разряд, а в двоичных кодах не все так просто. Я не использовал коды Грея (лень, однако ;)), поэтому данная проблема мне знакома и я в своё время её решил, может быть не самым оптимальным способом, но довольно эффективным. Если интересно как, то пишите. Стоит отметить, что кодировать и декодировать в коды Грея довольно удобно, описать это можно так: сначала копируется самый старший разряд, затем:

Из двоичного кода в код Грея: G[i] = XOR(B[i+1], B[i])

Из кода Грея в двоичный код: B[i] = XOR(B[i+1], G[i])

Здесь, 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-разрядных генов может "выглядеть" так:

short int Individual[2];

class Individual {
  short int Genes[2];
};

unsigned char Individual [32];

Последний пример на первый взгляд кажется как минимум странным: зачем для задания одного бита использовать целый байт? Однако бывают случаи, когда используются небинарные алфавиты, т.е. каждый разряд может принимать не 2 различных значения "0" или "1", а больше, например, "1", "2", "4", "8". Как раз для таких ситуаций последний пример и удобен. В дальнейшем речь будет идти только о бинарном алфавите. Кроме того, в последнем способе легче использовать коды Грея. Для того чтобы задать популяцию из 50 особей, можно поступить одним из следующих способов:

short int Population[50][2];

class Population {
  Individual Inds[50];
};

unsigned char Population[50][32];

Следует также отметить, что в задаче аппроксимации, взятой в качестве примера, в процессе "эволюции" будут учавствовать все гены особи, т.е. генетические операторы будут применяться к каждому гену. Однако, это не всегда необходимо, например, рассмотрим задачу компоновки, т.е. когда на некоторой известной поверхности требуется разместить N элементов разной площади так, чтобы они не накладывались друг на друга. Для простоты будем считать, что все элементы имеют прямоугольную форму. Настраиваемыми (оптимизируемыми) параметрами будут координаты каждого элемента, т.е. каждая хромосома будет содержать два гена, соответствующие координатам левого верхнего угла элемента. Но помимо этого необходимо знать, какой элемент представляет данная особь. Для этого необходимо добавить в набор генов особи ещё один ген, содержащий номер элемента. При этом нам нужно сохранить значение этого гена неизменным в течении всего процесса поиска решения. Таким образом, получаем особь с тремя генами, два из которых обрабатываются генетическими операторами, а один нет.

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

Оптимизация функций: гены - независимые переменные;
Настройка весов искусственной нейронной сети: гены - синаптические веса нейронов;
Искусственная жизнь (Artificial Life): гены - характеристики особи (сила, скорость, и т.д.), также должны быть неизменные гены, обозначающие тип особи (растение или животное);
Задача о кратчайшем пути: гены - пункты передвижения. Вся хромосома целиком представляет из себя маршрут из начальной точки в конечную, причем не всегда существующий.

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

Источники:

Heitkoetter, Joerg and Beasley, David, eds. (2001) "The Hitch-Hiker's Guide to Evolutionary Computation: A list of Frequently Asked Questions (FAQ)", USENET: comp.ai.genetic. Available via anonymous FTP from rtfm.mit.edu/pub/usenet/news.answers/ai-faq/genetic/ About 110 pages.

Made by Qwerty. 2003.