Генетическое программирование

6.2.3. Графоподобные структуры

Эта форма представления разработана для задач, которые не могут быть решены методами, которые используют рассмотренные выше модели программ. Данный подход использует более выразительную модель для представления программы [7]. Поэтому данный подход позволяет эффективно решать многие задачи, которые нельзя было решить с помощью предыдущих методов.

Сначала рассмотрим типичную блок-схему программы написанной вручную, которая представлена в качестве примера на рис.6.3.

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

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

Реализация линейных подструктур использует список операторов Си (или другого языка программирования, в том числе и ассемблера) переменной длины, которые оперируют с переменными или константами и полученные значения присваиваются переменным (например, $$a = b + 1.33$$). После выполнения программы вычисленное значение запоминается в "выходные" переменные. Функция ветвления также является оператором Си, который оперирует с теми же переменными, что и линейная программа, но этот оператор только читает значения этих переменных.Таблица 6.2 содержит множество операторов ветвления, которые могут быть использованы в данной модели.

На рис.6.4 представлен детально узел графа, соответствующий некоторой части линейной программы.

Данная модель, как и предыдущая, использует при выполнении программы глобальную память. Графоподобные структуры позволяют расширить класс задач, которые могут быть решены с помощью ГП, так как являются более общими по сравнению с первыми двумя и допускают эффективную реализацию [7].

Известен другой способ применения структур графов в ГП, называемый PADO [5]. Здесь каждая программа представляется ориентированным графом, содержащим узлы, индексированную память для входных переменных и стек, как показано на рис.6.5. В произвольном ориентированном графе каждый узел может иметь N исходящих дуг.

Эта структура не просто показывает потоки информации и управление ходом выполнения программы. Узел в графе соответствует сегменту программы и имеет две части: "действие" и "ветвление". Часть "действие" содержит константы и функцию, которая выполняется при достижении данного узла в процессе интерпретации программы. Данные передаются между узлами через стек. Часть "действие" получает данные из (верхушки) стека и после выполнения соответствующей функции передает преобразованные данные снова в стек. После того выполняется "ветвление", которое определяет ветвь следующего выполняемого узла на основании данных стека, памяти или специальных констант ветвления. Очевидно, что в процессе интерпретации необязательно посещаются все вершины графа. Каждая программа имеет две специальных вершины "старт" и "конец" и кроме этого может содержать некоторые специальные узлы типа "вызов подпрограммы". Поскольку граф может содержать обратные связи, то вершина "конец" при интерпретации на некоторых входных данных может быть недостижимой вследствие "зацикливания". Поэтому необходимо контролировать и ограничивать время выполнения программы.

6.2.4. Другие формы представления программ.

Кроме рассмотренных трех форм представления, в настоящее время предложены многочисленные модификации и обобщения ГП, в которых разработаны различные формы представления особей и определены на них соответствующие генетические операторы кроссинговера и мутации. В табл.6.3 приведены основные структуры, используемые в настоящее время в ГП [8].

В работе [9] для представления программ введены более сложные структуры в узлы дерева. Этот подход основан на хорошо известном методе группового учета аргументов (МГУА) Ивахненко, который широко используется при решении многих задач. При этом внутренние узлы дерева соответствуют полиномам второго порядка, которые используются в МГУА. Далее на указанных древовидных структурах определяются генетические операторы кроссинговера и мутации. При этом обычно используется локальный поиск и замена функций – процедура "переразметки", которая применяется для нахождения оптимальных значений параметров при заданной структуре. При определении фитнесс-функции здесь часто используют кратный (множественный) регрессионный анализ. Иногда используются и другие меры, например, сложность особи (к примеру, минимальная длина) или их комбинация.

Клеточное кодирование [10] также использует структуру графов, которые широко используются в компьютерных науках (для описания электрических цепей, нейронных сетей, конечных автоматов и т.п.), и поэтому область применения такого представления достаточно широкая (в частности, структурный синтез). Основная идея заключается в том, что фенотип отделяется от генотипа, который основан на древовидной структуре. С другой стороны фенотип представляется структурой (возможно циклического) графа. Генотип представляется грамматическим деревом (разбора), использующим правила грамматического вывода. При этом используются древовидные грамматики, в которых при грамматическом выводе нетерминальный символ заменяется соответствующим деревом. Эти операции выполняются параллельно подобно $$L$$-системам [11]. Клеточное кодирование позволяет определить модули, которые последовательно могут применяться в различных участках грамматического дерева.

Генетическое программирование на основе формальных грамматик предложено в работе [12]. Здесь используется очень общая форма ГП, которая основана на использовании теории формальных языков и грамматик. В процессе эволюции особей применяются контекстно-свободные грамматики, что позволяет преодолеть некоторые ограничения в теоретическом плане, характерные для классического ГП. Применение КС-грамматик гарантирует синтаксическую корректность потомков в процессе эволюции и позволяет определить простые и эффективные генетические операторы. Кроссинговер выполняется следующим образом. Случайным образом выбирается нетерминальный символ в грамматическом дереве первого родителя и затем производится поиск этого же нетерминала во втором родителе. Если во втором родителе этого нетерминала нет, то оператор не выполняется. Иначе производится обмен поддеревьев, соответствующих нетерминальным символам. Мутация выполняется путем "выращивания" грамматического дерева из случайным образом выбранного нетерминального символа. В дальнейших работах авторы допускают изменение продукций КС-грамматики в процессе эволюции для вывода лучших правил. Известны также работы, в которых используются и более общие контекстно-зависимые грамматики.

В работах [8,11] определено понятие $$L$$-систем, которые первоначально были разработаны для моделирования структур биологических формаций или, в более общем контексте, развивающихся процессов. В этом подходе замена нетерминальных символов при "выращивании деревьев" выполняется параллельно. Это позволяет развиваться различным ветвям независимо друг от друга, как это имеет место в реальных сложных процессах. При этом целью эволюции является генерация $$L$$-системы, множество продукций которой позволяет решать поставленную задачу. Таким образом, здесь в качестве особи выступает вся $$L$$-система. Каждая $$L$$-система оценивается после вывода грамматического дерева. Следует отметить, что такие особи не могут изменяться произвольным образом, а развиваются согласно правилам мета-грамматики.

Интересным является применение в ГП методов нечеткой (fuzzy) логики [9]. В частности, нечеткая логика может использоваться в адаптивном ГП для подстройки таких параметров как вероятности кроссинговера и мутации в процессе эволюции, что позволяет повысить эффективность. При этом используется коэволюция правил нечеткого контроллера, который управляет параметрами ГП.

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

6.3. Инициализация начальной популяции

Данный этап в ГП является не таким простым, как в классическом ГА, где генерация случайных двоичных строк не представляет особых проблем. Это связано с различной сложностью особей и их структурой. Естественно методы инициализации начальной популяции различны для разных форм представления программ. Одним из важнейших параметров в ГП является максимально возможный размер (сложность) программы.

6.3.1. Инициализация древовидных структур

Для деревьев в качестве меры сложности используется максимальная глубина (иногда называется высота) дерева или общее число узлов в дереве. Глубиной узла называется минимальное число узлов, которые необходимо пройти от корня дерева к этому узлу. Максимальной глубиной дерева $$D_m$$ называется максимально возможная глубина в дереве для терминального символа (листа). Если арность каждого узла равна двум, то общее число узлов не превышает $$2^{D_m}$$, которое также используется в качестве меры сложности.

Инициализация древовидных структур выполняется путем случайного выбора функциональных и терминальных символов при заданной максимальной глубине дерева. Пусть для определенности выбраны следующее терминальное $$T=\{a,b,c,d,e\}$$ и функциональное $$F=\{+,-,*,\% \}$$ множества, где $$\%$$ означает деление нацело. Применяются два основных метода: 1) полная (full) и 2) растущая (grow) инициализация [2].

В полном методе при генерации дерева, пока не достигнута максимальная глубина, допускается выбор только функциональных символов, а на последнем уровне (максимальной глубины) выбираются только терминальные символы. Например, на рис.6.6 а) представлено дерево с $$D_m=3$$.

В растущей инициализации генерируются нерегулярные деревья с различной глубиной листьев вследствие случайного на каждом шаге выбора функционального или терминального символа. Здесь при выборе терминального символа рост дерева прекращается по текущей ветви и поэтому дерево имеет нерегулярную структуру.

Например, для $$D_m=3$$ при растущей инициализации для указанных функциональных и терминальных символов могут быть построены деревья, приведенные на рис.6.6 б).

При использовании первого метода начальная популяция содержит однородное множество структур, что способствует вырождению генетического материала (и преждевременной сходимости к локальным экстремумам). Поэтому на практике часто эти два метода используют одновременно следующим образом. Начальная популяция генерируется так, чтобы в нее входили деревья с разной максимальной длиной примерно поровну (для нашего примера $$D_m=1, D_m=2, D_m=3, D_m=4$$). Для каждой глубины первая половина деревьев генерируется полным методом, а вторая – растущей инициализацией.

6.3.2. Инициализация линейных структур

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

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

6.4. Кроссинговер в генетическом программировании

В начальной популяции особи (потенциальные решения), как правило, имеют низкие (плохие) значения фитнесс-функции. В процессе эволюции с помощью генетических операторов популяция развивается и значения фитнесс-функции улучшаются. В ГП используются те же, что и в ГА, генетические операторы кроссинговера, мутации и репродукции. Отметим, что в терминах машинного обучения они соответствуют операторам поиска решения. Далее мы рассмотрим выполнение генетических операторов на ранее определенных структурах.

6.4.1. Выполнение кроссинговера на древовидных структурах

Для древообразной формы представления используются следующие три основные операторы кроссинговера (ОК):

В узловом операторе кроссинговера выбираются два родителя (два дерева) и узлы в этих деревьях. Первый родитель называется доминантом, второй – рецессивом. Узлы в деревьях могут быть разного типа. Поэтому сначала необходимо убедиться, что выбранные узлы у родителей являются взаимозаменяемыми. Если узел во втором родителе не соответствует типу узла первого родителя, то случайным образом выбирается другой узел во втором родителе, который опять подлежит проверке на предмет совместимости. Далее производится обмен узлов.

Рассмотрим ОК на следующем примере, представленном на рис.6.7 для родительских особей:$$\frac{3}{4}*x^2+x*y,\ \frac{x}{2}+y+z*y$$

В кроссинговере поддеревьев родители обмениваются не узлами, а определяемыми ими поддеревьями. Оператор выполняется следующим образом:

Этот тип ОК является основным. При этом под размером (под)дерева понимается, как и ранее, либо его высота, либо число его вершин.

При смешанном операторе кроссинговера для некоторых узлов выполняется узловой ОК, а для других - кроссинговер поддеревьев.

Отметим, что выполнение кроссинговера на древовидных структурах выполняется достаточно просто с помощью $$S$$-выражений, что показано в таблице 6.4. Например, кроссинговер поддеревьев сводится к обмену "скобками", которые здесь соответствуют поддеревьям.

В таблице 6.5 приведены типовые операторы кроссинговера для древовидных структур[3,8].

6.4.2. Кроссинговер на линейных структурах

Скрещивание на линейных структурах выполняется достаточно просто. Здесь у родителей выполняется обмен линейными сегментами, как это показано на рис.6.9.

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

6.4.3. Выполнение кроссинговера для графоподобных структур

Кроссинговер комбинирует генетический материал из двух родительских программ путем обмена некоторых частей программ. ОК для этой модели может быть реализован двумя способами.

Первый способ похож на кроссинговер поддеревьев, который определен на древообразных структурах путем обмена поддеревьев. Здесь обмен производится подграфами, как это показано на рис.6.10.

При этом в каждой особи-родителе выбирается случайным образом множество смежных узлов и производится обмен двух подграфов между этими подграфами.

Второй тип кроссинговера выполняет линейный ОК. Здесь для каждого родителя выбирается линейный сегмент (в одном узле графа), начинающийся со случайной позиции данного сегмента и имеющий случайную длину. Далее, как обычно, производится обмен этими линейными сегментами. Если размер хотя бы одного потомка превышает некоторый порог, то результаты ОК аннулируются и выполняется обмен равными сегментами меньшей длины.

Обычно линейный ОК выполняется в вероятностью $$P_i=0,1$$. Пример выполнения этого ОК представлен на рис.6.11. Как правило, в процессе эволюции используются ОК обоих типов. В целом ОК выполняется следующим образом:

6.5. Мутация в генетическом программировании

После выполнения кроссинговера с заданной малой вероятностью $$P_c$$ выполняется мутация для выбранной одной особи-программы.

6.5.1. Выполнение мутации на древовидных структурах

Для деревьев используются следующие операторы мутации (ОМ):

Узловая мутация выполняется следующим образом:

Усекающая мутация производится так:

На рис.6.12 показан пример выполнения усекающей мутации.

Растущая мутация выполняется следующим образом:

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

В настоящее время для древовидных структур в ГП разработаны различные типы мутаций, которые производят различные изменения и представлены в табл.6.6 [5].

Для примера на рис.6.14 представлен результат выполнения мутации - перестановки (аргументов) для дерева, представляющего выражение $$\frac{1}{2}*(d+e)$$.

6.5.2. Выполнение мутации на линейных структурах

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

Мутация констант выполняется путем стандартного отклонения от текущего значения $$P=P+\delta\cdot h_m$$, где $$P$$-текущее значение, $$1\le\delta\le 1$$-случайное число и $$h_m$$–шаг мутации. При этом вероятность мутации обычно убывает по мере удаления от начала процесса.

6.5.3. Выполнение мутации на графоподобных структурах

В этом случае оператор мутации случайным образом выбирает множество узлов и изменяет либо узел линейной программы, либо узел ветвления, либо число исходящих из условного оператора ветвей. То есть ОМ не строит новые линейные последовательности. Измененная ОМ программа помещается назад в популяцию.

6.6. Фитнесс-функция в генетическом программировании

В отличие от генетических алгоритмов, где часто при поиске экстремумов в качестве фитнесс-функции используется исходная целевая функция, в ГП фитнесс-функция обычно определяет меру близости между реальными $$y_i$$ и требуемыми $$d_i$$ выходными значениями (например, при использовании ГП в имвольной регрессии ). Поэтому в качестве фитнесс-функции часто используется абсолютная или квадратичная ошибка.

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

"Непрерывной" (continuous) фитнесс-функцией называют [5] функцию вычисления фитнесс-значений, в которой малое улучшение в обучении программы вызывает малые улучшения измеряемых фитнесс-значений и большие улучшения в обучении связаны соответственно с большими изменениями (в сторону улучшения) фитнесс-значений. В [5] отмечается, что такая "непрерывность" является важным свойством, так как позволяет ГП итеративно улучшать программы в процессе эволюции.

"Стандартизованой" [5] фитнесс-функцией называют преобразованную фитнесс-функцию, которая лучшим особям приписывает нулевое значение.

"Нормализованной" [5] фитнесс-функцией называют преобразованную фитнесс-функцию, которая для всех особей дает значения в интервале (0,1).

Рассмотрим следующий пример [5] с обучающей выборкой, представленной табл.6.7. Каждая строка таблицы определяет один элемент $$(x,y)$$ обучающей выборки. Необходимо в процессе эволюции построить программу (или формулу в случае символьной регрессии), которая для каждого входного значения x вычисляет необходимое (в соответствии с табл.6.5) значение y (фактически нам необходимо реализовать функцию $$f(x)=x^2+x$$).

Рассмотрим в качестве фитнесс-функции ошибку в метрике абсолютных значений $$f_a=\sum_{i=1}^n |y_i-d_i|$$, где суммирование выполняется по обучающей выборке. Эта фитнесс-функция соответствует первому определению "непрерывной", поскольку чем ближе значения $$y_i$$ к $$d_i$$, тем меньше значение фитнесс-функции. Приведенная фитнесс-функция является также стандартизованной, так как в случае идеального решения дает нулевое значение.

Часто в качестве фитнесс-функции также используют квадратичную ошибку $$f_s=\sum_{i=1}^n (y_i-d_i)^2$$.Таблица 6.8 показывает различие для этих двух фитнесс-функций в том случае, если на некотором (промежуточном) этапе в качестве особи оценивается (плохо обученная) программа, реализующая функцию $$f(x)=x^2$$.

Мы рассмотрели использование в качестве фитнесс-функции ошибки в двух метриках, которые характерны для применения ГП в качестве символьной регрессии, что будет детальнее рассмотрено в разделе 6.8.

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

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

6.7. Интроны

Программы, построенные с помощью методов ГП, имеют тенденцию к накоплению интронов – ненужных и непригодных участков кода

Например:

(NOT(NOT x)) ,
(AND (ORXX)),
(+… (-XX)),
(+X0),
(*X1),
(*(DIV XX)),
(MOVE_LEFT MOVE_RIGHT),
(IF (2=1) . . . ),
A:=A.

Таких фрагментов в программе возникает достаточно много (их количество может достигать 60%), и обнаружение и удаление интронов представляет серьезную проблему в ГП. Разработаны специальные методы для их устранения. Интересно отметить, что в живой природе интронов также достаточно много (в частности, на генном уровне существуют "лишние" участки ДНК).

6.8. Общий алгоритм генетического программирования

Таким образом, для решения задачи с помощью ГП необходимо выполнить описанные выше предварительные этапы:

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

Например, решение задачи на основе ГП можно представить следующей последовательностью действий:

Следует отметить, что в ГП достаточно часто применяется асинхронный ГА, рассмотренный в разделе 4.6.

6.9. Символьная регрессия

Этот раздел является одним из важнейших приложений ГП. Данный термин подчеркивает то, что здесь объектом поиска является символьное описание модели, в отличие от множества коэффициентов в стандартных методах. Этот подход существенно отличается от других методов регрессии и использования нейросетей прямого распространения, где структура (и сложность) модели предполагается известной и фактически необходимо найти только ее коэффициенты. В случае символьной регрессии вид и сложность функции заранее неизвестны и могут изменяться в процессе поиска.

Задача регрессии может быть определена на основе множества значений входных независимых переменных $$x$$ и зависимой выходной переменной $$y$$. Целью поиска является аппроксимация $$y$$ с помощью переменных $$x$$ и коэффициентов $$w$$ следующим образом $$y=f(x,w)+\varepsilon$$, где $$\varepsilon$$ представляет шум (ошибку).

В стандартних методах регресии вид функции $$f$$ предполагается известным, например, в линейной регресии - $$f(x,w)=w_0+w_1x_1+\dots +w_nx_n$$. Здесь коэффициенты $$w_i$$ обычно находятся методом наименьших квадратов. В нелинейных методах, например с использованием нейронных сетей прямого распространения, функция имеет вид $$f(x,w)=w_0\cdot g(w_hx)$$. Здесь коэффициенты $$w_0$$ и $$w_h$$ представляют синаптические веса нейронной сети выходного и скрытых слоев соответственно.

Как уже отмечалось, символьная регрессия на основе ГП не использует некоторую заранее предопределенную форму функции $$f(x,w)$$. Здесь функция $$f(x,w)$$ представляется древовидной структурой и строится эволюционным методом с использованием определенного функционального и терминального множеств. В качестве фитнесс-функции обычно используется квадратичная ошибка, которая оценивает качество решения и обеспечивает обратную связь при поиске решения. Для определенности обозначим функции множества, зависящие от одной переменной через $$h_1,\dots,h_k$$ и функции от двух переменных как $$g_1,\dots,g_l$$. В этой нотации функция $$f(x,w)$$ представляется в виде суперпозиции функций $$h_i,g_j$$, и например, может иметь следующий вид: $$f(x,w)=h_1(g_2(g_1(x_3,w_1),h_2(x_1)))$$.

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

Далее рассмотрим детально пример использования символьной регрессии из [5] для аппроксимации данных, представленных в табл.6.9. Необходимо найти функцию $$f(x)$$, которая аппроксимирует с заданной точностью эти "экспериментальные" данные. Для решения задачи определим в соответствии с вышесказанным:

Терминальное множество: переменная x и константы в диапазоне [-5,5];

Функциональное множество: арифметические функции $$+, - , * , \%$$ (защищенное деление).

Koza [2] ввел следующую удобную и "прозрачную" форму для перечисления параметров, которая представлена в табл.6.10.

Далее приведем некоторые полученные экспериментальные данные результатов эволюции для различных запусков программ из [5]. В начальной популяции после инициализации лучшая особь представлена деревом рис.6.15, которая реализует (не минимальным образом !) функцию $$f_0(x)=\frac{x}{3}$$.В последующих рисунках рис.6.16,рис.6.17,рис.6.18,рис.6.19,рис.6.20 представлены лучшие особи последующих поколений. Здесь в первом поколении лучшая особь реализует $$f_1(x)=\frac{x}{6-3x}$$.В последующих рисунках рис.6.16,рис.6.17,рис.6.18,рис.6.19,рис.6.20 представлены лучшие особи последующих поколений. Здесь в первом поколении лучшая особь реализует $$f_1(x)=\frac{x}{6-3x}$$ и соответствующее дерево рис.6.16 сильно избыточно.

Аналогично во втором поколении лучшая особь реализует функцию $$f_2(x)=\frac{x}{x(x-4)-1+\frac{4}{x}-\frac{\frac{9(x+1)}{5x}+x}{6-3x}}$$ и дерево тоже сильно избыточно. Наконец в третьем поколении получена лучшая особь $$f_3(x)=\frac{x^2}{2}$$, которая дает оптимальное решение в простейшей форме.

В табл.6.11 для сравнения представлены значения функций лучших особей первых поколений (0-3).Отметим, что была выполнена еще одна итерация (4-е поколение). На рис.6.19 представлена лучшая особь четвертого поколения, которая также реализует функцию $$f_4(x)=\frac{x^2}{2}$$, но избыточность соответствующего дерева выросла. Конечно, для данного примера можно было использовать и классические методы регрессии, но он носит чисто иллюстративный характер.

Интересным примером является машинный вывод третьего закона Кеплера на основе символьной регрессии. Итак, есть экспериментальные данные, которые связывают радиус и период обращения планет солнечной системы, которые представлены в табл.6.12 (в астрономических единицах). Напомним, что согласно закону Кеплера, период обращения планеты пропорционален корню квадратному из третьей степени радиуса орбиты $$P=\sqrt{(r)^3}$$, где $$r$$ – радиус орбиты планеты (чаще используется формулировка $$\frac{r^3}{P^2}=c$$). Для решения этой задачи с помощью символьной регрессии возможные параметры представлены в табл.6.13. На рис.6.20 представлено полученное с помощью символьной регрессии дерево, которое представляет закон Кеплера.

Во многих работах [2,5] приведены результаты для более сложных зависимостей, но они требуют для представления результатов большого объема.

Следует отметить, что мощность популяций используемых в ГП на порядок выше, чем в классических ГА, а число поколений, как правило, меньше. Применение ГП в качестве символьной регрессии является важным для многих технических задач (например, в гидро- и аэродинамике), но далеко не единственным.

Как показано выше, символьная регрессия может использоваться для получения эмпирических зависимостей на основе экспериментальных данных. Она широко применяется в эконометрике при решении задач моделирования и прогнозирования. Кроме этого, символьная регрессия с успехом применяется в символьных вычислениях, включая символьное дифференцирование и интегрирование, решение дифференциальных и интегральных уравнений в символьном виде и т.п.[2].

6.10 Модульное построение программ в генетическом программировани

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

Одним из самых перспективных направлений повышения эффективности ГП является использование модульного принципа, в котором идентифицируются некоторые функциональные единицы программы, которые оформляются по определенным стандартам и сохраняются для дальнейшего использования.

Модулем называют последовательность (соседних) операторов программы, ограниченную некоторыми окаймляющими элементами, который имеет общий идентификатор. Модуль должен обладать, по крайней мере, следующими свойствами:

Модульный принцип является средством инкапсуляции блоков кода. Такие блоки оформляются в виде подпрограмм, которые затем могут многократно использоваться в главной программе или включаться в другие подпрограммы. Это позволяет существенно уменьшить сложность программы за счет оформления часто используемых идентичных участков кода в виде подпрограмм. Отметим, что меньшая сложность (длина) программ способствуют их "выживанию" в процессе эволюционного поиска. В ГП используется различная техника для реализации модульного принципа. Самыми известными методами являются автоматически определяемые функции (АОФ) (automatically defined functions –ADF), которые введены в [2] и детально исследованы во многих работах [2,5].

ADF построены по аналогии с функциями языка LISP. Поэтому программа, содержащая ADF, также представляется древовидной структурой, но при этом дерево состоит из двух частей (поддеревьев):

Эти два поддерева соответствуют структуре программы на языке программирования высокого уровня, подобном С++, Паскаль и т.п., где главная программа (тело) сопровождается "объявлениями", где описаны соответствующие функции. Отметим, что обе указанные компоненты должны участвовать в эволюции, которая в этом случае производит программу, построенную в соответствии с модульным принципом.

На рис.6.21 корень дерева"программа" соответствует программе в целом и объединяет ее различные части. Узел "определение" является корневым для поддерева, содержащего описание функции ADF0. В случае необходимости использования нескольких функций каждой из них необходимо выделить соответствующее поддерево ADF для описания функции.

Левая ветвь, исходящая из узла "определение", содержит имя функции (ADF0), которое включается в функциональное множество главной программы и используется для вызова соответствующей функции. Справа от узла имени расположен узел, представляющий список аргументов данной функции. Этот список определяет имена входных переменных аргументов функции. Эти имена входят в терминальное множество тела соответствующей функции. Этот подход аналогичен определению функции в С++ или Паскале, где необходимо дать имя функции и определить входные переменные вместе с описанием тела функции. Следует отметить, что использование рекурсии, как правило, не допускается вследствие значительных трудностей реализации.

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

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

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

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

Кроме ADF в ГП применяются и другие методы модульного построения программ [5]. К ним относится использование автоматически определяемых макросов (automatically defined macros), автоматическое определение циклов do while, until и рекурсии, применение сложных и абстрактных типов данных и т.д. С одной стороны они позволяют получать более компактные программы, но с другой их применение существенно осложняет сам процесс их построения.

Контрольные вопросы

Упражнения

Краткие итоги: