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

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

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

Д. Коза в своих исследованиях по генетическому программированию применяет язык LISP, обладающий всеми необходимыми для синтеза структур генетического программирования свойствами:

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

•    обработка данных в LISP-программе сводится к объединению, делению и перегруппировке информации;

•    LISP-выражения представляются древовидной структурой (рис. 4.22), форма и величина которой может динамически изменяться.

Язык LISP имеет свои недостатки, и применение генетического программирования нельзя связывать лишь с LISP-программированием. Следуя

Д. Коза, сформулируем следующие стартовые условия для генетического программирования [98]:

•    установка множества проблемно-ориентированных переменных и констант (terminal set);

•    установка множества проблемно-ориентированных элементарных функций (function set);

•    определение экстремальных ЦФ;

•    установка параметров моделей эволюций;

•    определение критерия остановки моделирования эволюции и правил декодирования результатов эволюции.

Поскольку основой моделирования эволюции в генетическом программировании являются элементы множеств terminal set и function set, то, в этом смысле, выбор пользователем языка программирования будет в дальнейшем определять вид получаемых решений. Что касается определения ЦФ, параметров эволюции и критериев остановки процесса моделирования, то они совпадают с аналогичными этапами в других типах ГА.

В качестве элементов function sets могут фигурировать следующие [130]:

•    арифметические операции (например, +, —, *);

•    математические функции (например, sin, cos);

•    булевы операции (например, if-tlien-else);

•    циклы (например, for, do-imtil);

•    некоторые специальные функции для быстрого поиска хороших решений.

Элементами множества terminal set являются константы и переменные,

среди которых особое значение имеют так называемые случайные константы, с коротким временем «жизни». Речь идет о булевых константах, принимающих значения из множества {true, false}, а также вещественных константах, принимающих значение на отрезке [—1,000; 1,000] с шагом 0,001. Множества function set и terminal set должны быть достаточными для нахождения решения задачи, а любая функция должна быть корректно выполнимой при любых допустимых аргументах.

Для эффективности генетического программирования форма ЦФ имеет большое значение. Общепризнанным способом оценки качества ЦФ является такой показатель, как среднеквадратичная ошибка (чем она меньше, тем лучше программа). Иногда используется критерий «выигрыша», согласно которому выигрыш определяется в зависимости от степени близости к корректному значению ЦФ. ЦФ в генетическом программировании обозначают через Fro. На практике используется стандартное значение Fst. Обозначим через а\ некоторую программу из популяции размером Np. Тогда стандартное значение ЦФ определяется как

а юстируемое значение ЦФ равно FjU(ai) = 1/(1 + Fst(a,i)).

Интервал изменения Fju(&i) равен (0,1). Размер популяции Np в генетическом программировании обычно составляет несколько тысяч программ. Для максимального числа генераций £тах рекомендации отсутствуют. Д. Коза в своих экспериментах использует значение £тах = 51 [98].

Рассмотрим подробнее процедуру генетического программирования.

1.   Инициализация. На этом этапе стохастически генерируется популяция Р, состоящая из Np древовидных программ, причем корневой вершиной дерева всегда является функция, аргументы которой выбираются случайно из множеств function set или terminal set. Концевыми вершинами дерева должны быть переменные или константы, в противном случае процесс генерации необходимо рекурсивно продолжить. Если структура дерева становится сложной, то заранее устанавливается максимальная высота дерева, равная числу ребер дерева, которое содержит самый длинный путь от корневой вершины до некоторой концевой вершины. В экспериментах Д. Коза максимальная высота дерева колеблется от шести для популяции Р° до 17 в более поздних популяциях Р1. Для обеспечения многообразия популяции Р° в ходе инициализации Д. Коза предлагает применить способ, согласно которому деревья разной высоты генерируются с одинаковой частотой. Правда, способ не лишен недостатка, связанного с не совсем случайным характером генерируемых деревьев [98].

2.   Оценка решений. На втором этапе оценивается ЦФ каждой программы в Р° указанным выше способом. Поскольку все программы выбраны случайно, то большинство из них будут иметь ЦФ далекую от лучшего решения, поэтому в качестве оценки можно взять разницу между лучшим и худшим значением ЦФ в популяции Р° .

3.   Генерация новой популяции. Этот этап принято разделять на следующие под этапы.

3.1. Выбор операторов генетического программирования. Основными операторами здесь являются репродукция и кроссинговер, применяемые с вероятностью Р(ОР) и Р(ОК) соответственно, причем Р(ОР) + + Р(ОК)=1 (чаще всего Р(ОР) = 0,1, Р(ОК) = 0,9).

3.2. Селекция и рекомбинация. Данный этап моделирования выполняется по схемам, аналогичным ГА [88-92].

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

4.   Проверка критерия остановки. Процедура генетического программирования является итерационной, и критерии ее остановки аналогичны критериям для обычных ГА.

В качестве примера, иллюстрирующего рассмотренную процедуру, возьмем проблему двух параллелепипедов. Пусть два параллелепипеда задаются шестью независимыми переменными Li, Bi, Hi, L2, B2, H2 и одной зависимой переменной D (рис. 4.24).

В табл. 4.1 представлены 10 различных вариантов исходных значений для шести независимых переменных, а также разность объемов D = = Li *Bi *Ні — L2 *62 *Н2. Пусть для получения корректных значений величины D установлены следующие стартовые условия: terminal set Т = = {Li, Вь Нь Ь2, В2, Н2}; function set F = {+,—,*,/}; F указывает абсолютную ошибку определяемую разностью между действительным значением D и тем значением, которое получается программно; Fst = Fro; выигрыш определяется числом случаев, когда сравниваемые величины D различаются менее, чем на 0,01; Np = 4000; программа останавливается, если число выигрышей равно 10, либо £тах = 51.

 

В результате моделирования эволюции для популяции Р° лучшая ЦФ имела значение 783, что соответствует следующей форме:

или

Видно, что в данном выражении отсутствует переменная Нз и оно не соответствует корректному решению. Далее, лучшие ЦФ в популяциях Р\—Pq имели следующие значения: 778, 510, 138, 117, 53, 51. Лучшая программа на восьмом этапе эволюции дала значение ЦФ, равное 4,44, что соответствовало LISP-выражению следующего вида:

или, в упрощенном виде,

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

или

Рассмотрим перспективные направления исследований в области генетического программирования [130]. К ним прежде всего следует отнести работы по так называемым автоматически определяемым функциям (ADF), идея которых состоит в повышении эффективности генетического программирования за счет модульного построения программ, состоящих из главной программы и ADF-модулей, генерируемых в ходе моделирования эволюции. При этом до начала эволюции ориентировочно определяется архитектура программы, число ADF-модулей и параметры (аргументы) ADF. На рис. 4.25 представлена общая структура LISP-программы, состоящей из главной программы и двух модулей ADF0 и ADF1.

Все типы вершин данной структуры имеют свой номер, причем вершины с номерами от 1 до 6 являются инвариантами по отношению к генетическому программированию в отличие от вершин с номерами 7, 8, 9. Общая LISP-функция progn определяет по следовательно (слева направо) каждый свой аргумент. Каждая подпрограмма декларируется как функция defun. Список аргументов включает отдельные локальные переменные, которые определяются при вызове ADF. Наконец, задание values-функции главной программы завершает установку общей программы progn. Настройка ADF (их число, аргументы и т.п.) зависит от решаемой задачи, имеющихся вычислительных ресурсов и предварительного опыта. Отметим также необходимость типизации вершин дерева, иначе при выполнении оператора кроссинговера могут быть синтезированы синтаксически некорректные решения. Это связано с применением в генетическом программировании

с ADF модифицированной формы ОК, исключающего появление некорректных решений.

Вернемся к ранее рассмотренной проблеме двух параллелепипедов и приведем результаты моделирования эволюции с использованием ADF. Определим, что число ADF равно единице (ADF0), а число аргументов равно трем (ARGO, ARG1, ARG2). Тогда множества terminal set и function set для главной программы, соответственно равны { Li, Ві, Hi, L2, В2, Н2 } и {+, —, *, %, ADF0}, а множества terminal set и function set для ADFO имеют, соответственно, вид {ARGO, ARG1, ARG2} и {+, —, *, %}. Лучшая из 4000 случайно сгенерированных программ популяции Р° имела значение ЦФ, равное 1142, что соответствовало следующему LISР-выражению:

или

которое не соответствует корректному решению.

После 6 генераций значение ЦФ улучшилось с 1101 до 96, причем лучшая программа имела вид

или

В следующей популяции Р7 лучшая программа имела ЦФ, также равную 96, однако решение было другим. Наконец, на 13-й генерации была получена корректная программа

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

Проблема проверки на четность пяти имеет следующую формулировку. Пусть булева функция, зависящая от пяти аргументов (Do, Di, D2, D3, D4) принимает значение true, если четное число аргументов (включая нуль) принимают значение true, в противном случае булева функция принимает значение false (константа, обозначающая список, в котором нет ни одного элемента); 32 возможных комбинации аргументов служат основой для оценки генетического программирования с ADF и без ADF.

Для генетического программирования без ADF устанавливаются следующие начальные условия и параметры эволюции: terminal set T={Dq, Di, D2, D3, D4}; function set F = {AND, OR, NAND, NOR}; ЦФ определяется числом совпадений значений исходной функции со значениями, выдаваемыми генетическим программированием; Fst = 32 — Fro; N = 16000; программа останавливается, если число совпадений равно 32.

Аналогичные условия и параметры устанавливаются также для генетте скош программирования с ADF. Отличие генетического программирования с ADF от генетического программирования без ADF состоит в следующем: архитектура программы включает главную программу и две ADF (ADF0 и ADF1), каждая из которых содержит 4 параметра, причем ADF1 может включать функцию ADFO; terminal set главной программы совпадает с множеством Т в генетическом программировании без ADF; function set главной программы равно {ADF1, ADFO, AND, OR, NAND, NOR}; terminal set для ADF1 равно {ARGO, ARG1, ARG2, ARG3}; function set для ADF1 равно {ADFO, AND, OR, NAND, NOR}; terminal set для ADFO равно {ARGO, ARG1, ARG2, ARG3}; function set для ADFO равно {AND, OR, NAND, NOR}.

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

В [131], исследуя решения различной длины, получаемые с помощью генетического программирования, обратили внимание на так называемый эффект «компрессионного давления», которым обладают решения с малой структурной сложностью. Программы, генерируемые по методу генетического программирования, могут содержать «лишние» блоки, не влияющие на функциональные возможности программы и на значение ее ЦФ. В генетике это соответствует понятию интрона, который является нечувствительным к кроссиншверу [6,7]. С учетом этого в [131] вводится понятие эффективной сложности, величина которой равна величине структурной (абсолютной) сложности программы за вычетом величины интронов, содержащихся в программе. Принято считать, что применение ОК носит деструктивный характер, если ЦФ ухудшается.

Следовательно, для программы с относительно большим значением структурной сложности, но содержащей много интронов, опасность деструктивного воздействия кроссинговера уменьшается. С учетом этого, а также принимая во внимание фундаментальную теорему ГА [88], приведем следующие рассуждения. Обозначим через СЦщ) эффективную сложность программы сіі = (г = 1, 2,..., Np), через Са(щ) — абсолютную сложность программы щ, через Ps(OK) — вероятность выживания решения после применения ОК, а через Р^(ОК) — вероятность того, что применение ОК приведет к деструктивному эффекту, причем Р^(ОК) = 0, если ОК проводится с интроном. Пусть F(ai) — значение ЦФ программы щ, F(t) — среднее значение ЦФ всех программ в популяции Р1. Если применяется пропорциональная селекция, то нижняя оценка Аі(і + 1) «доли» программы щ в популяции Р^+1) примерно равна

Выражение в скобках представляет собой определение эффективной ЦФ:

которая соответствует вкладу программы щ в следующую популяцию P(t+1). Отсюда следует, что репродуктивные шансы некоторой программы щ тем выше, чем меньше отношение между эффективной и абсолютной сложностью программы. Достигнуть этого можно двумя путями.

Первый заключается в увеличении абсолютной сложности путем добавления интронов, второй — в поиске простых решений. Эмпирические данные, полученные в [131], подтверждают приведенные выше соображения:

•    на ранних этапах эволюции среднее значение ЦФ от популяции к популяции изменяется сильно, в то время как FQ изменяется относительно медленно, а репродуктивные свойства некоторой программы зависят прежде всего от ее ЦФ;

•    затем темп изменения ЦФ уменьшается, однако начинает расти соотношение между эффективной и абсолютной сложностью, «компрессионное давление» возрастает, и FQ уменьшается;

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

Теоретически обоснованное и эмпирически наблюдаемое явление «компрессии» ведет к преждевременной сходимости генетических программ к субоптимальным решениям. В [131] предлагается ввести внешнее управление этим процессом с помощью некоторого коэффициента D, пропорционального абсолютной сложности программы. С учетом этого выражение для Fq принимает вид

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

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