Терминальный алфавит, функциональный базис и их свойства.
Yuri Burger

Первый главный шаг в подготовке использования генетического программирования должен идентифицировать множество терминалов. Набор терминалов, наряду с набором функций, представляет собой компоненты, из которых будет создаваться компьютерная программа для полного или частичного решения проблемы.
Второй шаг заключается в определении функционального множества, элементы которого должны использоваться для генерации математических выражений. Каждая компьютерная программа (то есть, анализируемое дерево, математическое выражение) является композицией функций от множества функций F и терминалов из терминального множества T (в случае программ-функций это константы и переменные).
Множество возможных внутренних узлов (не листовых), используемых в деревьях синтаксического анализа, используемых в генетическом программировании, называется функциональным множеством:

                             F={f1,f2,..,fn}

                             T={t1,t2,..,tm}

                                 C=F U T

В генетическом программировании особи из популяции представляют собой программы. Удобно представлять эти программы в виде деревьев, где функции представлены внутренними узлами, к которым в качестве входных параметров присоединены поддеревья. Листьями такого дерева будут константы, входные параметры задачи или директивные команды программы.

    Пример простой программы-дерева:

                                      =
                                      |
                                      +
                                     / \
                                    *   7
                                   / \
                                  x   3

Вопервых, давайте посмотрим на природу кроссинговера. Тривиальный кроссинговер генерирует новое решение на основании двух имеющихся. Новое решение он получает комбинируя части готовых решений. Тоесть, кроссинговер суть есть комбинирующий механизм. Исходным материалом для него служат генотипы имеющихся решений. Это означает, что число различных решений, которые могут быть получены кроссинговером при использовании одной и той же пары готовых решений, ограничено. Соответственно, пространство, которое ГА может покрыть используя лишь кроссинговер, жестко зависит от генофонда популяции. Чем разнообразнее генотипы решений популяции, тем больше пространство покрытия. Теперь, если вспомнить что при обнаружении локального оптимума, соответствующий ему генотип стремится занять все позиции в популяции, становится понятным почему ГА "сходится", тоесть перестает генерировать новые решения.

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

Функция Растригина. Число переменных 2. Максимумов - 96 локальных, 4 глобальных.

    #define PI 3.14159265358979323846
    y=20+x[0]*x[0]+x[1]*x[1]-10*cos(2*PI*x[0])-10*cos(2*PI*x[1]);
    Пространство: -5.12<=x[t]<=5.12
    Максимум: F(4.52299,4.52299)  =80.7065
              F(-4.52299,4.52299) =80.7065
              F(4.52299,-4.52299) =80.7065
              F(-4.52299,-4.52299)=80.7065

    y=1/(((x[0]*x[0]+x[1]*x[1])/200)-cos(x[0])*cos(x[1]/sqrt(2))+2);
    Пространство: -20<=x[t]<=20
    Максимум: F(0,0)=1

    #define PI 3.14159265358979323846
    y=-100;
    for(t=0;t<XNum;t++)y+=10*cos(2*PI*x[t])-x[t]*x[t];
    Пространство: -5.12<=x[t]<=5.12
    Максимум: F(0,..,0)=0

АДАПТАЦИЯ - Любое изменение в структуре или функции организма, которое позволяет ему выживать во внешней среде.
АЛЛЕЛИ - Возможные значения генов.
ГА - Генетический алгоритм. Интеллектуальное исследование произвольного поиска. [Reeves, 1993]. Представлен Holland 1975.
ГА МОДЕЛЬ ОСТРОВА (IMGA) - Популяция ГА разделена в несколько подсовокупностей, каждая из которых беспорядочно инициализирована и выполняет независимый последовательный ГА на собственной подпопуляции. Иногда, пригодные ветви решений мигрируют между подсовокупностями. [Например. Levine 1994].
ГЕНЫ - Переменные в хромосоме.
ГЕНЕТИЧЕСКИЙ ДРЕЙФ - Члены популяции сходятся к некоторой отметке пространства решения вне оптимума из-за накопления стохастических ошибок.
ГЕНОТИП - Фактическая структура. Кодированная хромосома.
ГП - Генетическое программирование. Прикладные программы использующие принципы эволюционной адаптации к конструкции процедурного кода. [Koza 1992]
ДИПЛОИД - В каждом участке хромосомы имеется пара генов. Это позволяет сохраняться долгосрочной памяти.
КГА - Компактный ГА (CGA). В CGA, две или больше совокупности ген постоянно взаимодействуют и взаимо развиваются.
КРОССИНГОВЕР - Обмен отрезками хромосом родителей. В диапазоне от 75 до 95% появляются самые лучшие особи.
ЛОКУС - Позиция гена в хромосоме.
МУТАЦИЯ - Произвольная модификация хромосомы.
СИНАПС - Вход нейрона.
СХЕМА (шемма) - Подмножество подобных хромосом, содержащих модель значений гена.
СХОДИМОСТЬ - Прогрессия к увеличивающейся однородности. Ген, как считают, сходится когда 95% популяции имеет то же самое значение [DeJong 1975].
УНС - Унифицированная нейронная сеть.
ФИТНЕС-ФУНКЦИЯ - Значение являющееся целевым функциональным значением решения. Оно также называется функцией оценки или функцией цели в проблемах оптимизации.
ФЕНОТИП - Физическое выражение структуры. Декодированный набор ген.
ХРОМОСОМА - Составляющий вектор, строка, или решение.

1. Д.-Э.Бэстенс, В. .М. Ван Ден Берг, Д. Вуд. .Hейронные сети и финансовые рынки.., Москва, научное издательство .ТВП., 1997.
2. Галушкин А. И. .Hейрокомпьютеры и их применение. Книга 1. Теория нейронных сетей.. Москва, Издательское предприятие редакции журнала .Радиотехника., 2000.
3. Тейво Кохонен, Гвидо Дебок .Анализ финансовых данных с помощью самоорганизующихся карт., Москва, издательский дом .Альпина., 2001.
4. Ф.Уоссерман. .Hейрокомпьютерная техника., Москва, издательство .Мир., 1992.
5. Шумский C. A. .Hейрокомпьютинг и его применение в экономике и бизнесе., Москва, издательство МИФИ, 1998.
6. А. И. Змитрович Интеллектуальные информационные системы. - Минск.: HТООО "Тетра Системс", 1997. - 368с.
7. В. В. Корнеев, А. Ф. Гарев, С.В. Васютин, В.В. Райх Базы данных. Интеллектуальная обработка информации. - М.: "Hолидж", 2000. - 352с.