Генетическое программирование и компьютерный синтез математических выражений

Проблемы компьютерного синтеза программ стали одним из направлений искусственного интеллекта примерно в конце 50-х годов. Интерес исследователей к данной проблематике резко возрос благодаря работам Дж. Коза, посвященным генетическому программированию [6] и направленным на решение задач автоматического синтеза программ на основе обучающих данных путем индуктивного вывода.

Хромосомы или математические выражения, которые автоматически генерируются с помощью генетических операторов, являются компьютерными программами различной величины и сложности. Программы состоят из функций, переменных и констант. Исходная популяция P (0) хромосом в ГП образуется стохастически и состоит из программ, которые включают в себя элементы множества проблемно-ориентированных элементарных функций (function set: +,, Ї, *, %, sin, сos, log, or, and, for, do-until и пр., а также любая другая функция из предметной области задачи), проблемно-ориентированные переменные и константы (terminal set: ephemeral random — константы регрессионных функций с коротким временем жизни; T, Nil— булевы константы; вещественные константы принимающие значение на отрезке [-1.000; 1.000] с шагом 0.001). Множества function set и terminal set являются основой для эволюционного синтеза программы, способной наилучшим образом решать поставленную задачу. Одновременно устанавливаются правила выбора элементов из указанных множеств в пространстве всех потенциально синтезируемых программ, структура которых имеет древовидную форму.

Первоначально в исследованиях по ГП применялся язык LISP, обладающий всеми необходимыми для синтеза ГП-структур свойствами, однако в настоящее время наряду с LISP используются языки C, Smalltalk, C++.

Стартовыми условиями для ГП являются установка множеств terminal set и function set; определение подходящего вида функции соответствия (fitness-function); установка параметров эволюции; определение критерия останова моделирования эволюции и правил декодирования результатов эволюции.

Способом оценки качества функции соответствия в ГП является среднеквадратичная ошибка (чем она меньше, тем лучше программа) или критерий «выигрыша», согласно которому выигрыш определяется в зависимости от степени близости к корректному значению математического выражения. Размер популяции м в ГП обычно составляет несколько тысяч программ. Для максимального числа генераций t_max используется значение t_max=51.

Рассмотрим подробнее процедуру ГП.

• 1. Инициализация. На этом этапе стохастически генерируется популяция P (0), состоящая из µ древовидных программ, причем корневой вершиной дерева всегда является функция, аргументы которой выбираются случайно из множеств function set или terminal set. Концевыми вершинами дерева должны быть переменные или константы, в противном случае процесс генерации необходимо рекурсивно продолжить. Если структура дерева становится сложной, то заранее устанавливается максимальная высота дерева, равная числу ребер дерева, которое содержит самый длинный путь от корневой вершины до некоторой концевой вершины. В экспериментах обычно максимальная высота дерева колеблется от шести для популяции P (0) до 17 в более поздних популяциях P (t).
• 2. Оценка решений. Оценивается целевая функция каждой программы в P (0). Поскольку все программы выбраны случайно, то большинство из них могут иметь значение целевой функции далекое от лучшего решения, поэтому в качестве оценки можно взять разницу между лучшим и худшим значением функции в популяции P (0).
• 3. Генерация новой популяции и селекция. Основными операторами ГП являются рекомбинация (кроссинговер) и репродукция, селекция и репликация, выполняемые по схемам, аналогичным генетическим алгоритмам [7]. Если к некоторой программе применяют оператор репродукции, то эта программа копируется в новую популяцию. Для проведения кроссинговера выбираются две родительские хромосомы (программы), случайным образом определяются точки кроссинговера и путем обмена образуются два потомка. При программной реализации на языке LISP кроссинговер сводится к обмену списками между двумя программами при сохранении синтаксической корректности вновь получаемых программ.
• 4. Проверка критерия остановки. Процедура ГП является итерационной, критерии останова аналогичны критериям для генетических алгоритмов.

Проиллюстрируем рассмотренную процедуру на примере вычисления разности объемов двух параллелепипедов. Пусть два параллелепипеда задаются шестью независимыми переменными L₁, B₁, H₁, L₂, B₂, H₂ и одной зависимой переменной D. Для получения корректных значений величины D установим следующие стартовые условия:

terminal set: ={ L₁, B₁, H₁, L₂, B₂, H₂};

function set: ={+,-,*,%};

функция соответствия указывает абсолютную ошибку, определяемую разностью между корректным значением D и тем значением, которое получается программно;

выигрыш определяется числом случаев, когда сравниваемые величины D различаются менее, чем на 0.01;

м=4000;

программа останавливается, если число выигрышей равно 10, либо t_max=51.

В табл. 1 представлены 10 различных вариантов исходных значений для шести независимых переменных, а также разность объемов D= L_1*B_1*H₁-L_2*B_2*H₂.

Таблица 1 Исходные данные для вычисления разности объемов двух параллелепипедов

В результате моделирования эволюции для популяции P (0) лучшее значение D=783, что соответствовало следующему выражению:

(*(Ї(ЇB₁L₂)(ЇB₂H₁))(+(ЇH₁H₁)(*H₁L₁))) или H₁L₁(B₁+H₁ЇB₂ЇL₂).

Видно, что в данном математическом выражении отсутствует переменная H₂ и оно мало похоже на корректное решение. Далее, лучшие значения D в популяциях P (1)-P (6) имели значения 778, 510, 138, 117, 53, 51 соответственно. Лучшая программа на восьмом этапе эволюции дала значение D, равное 4.44, что соответствовало LISP-выражению следующего вида: программирование генетический компьютерный.

(Ї(Ї(*(*B₁H₁)L₁)(*(*L₂H₂)B₂))(%(+B₁L₁)(Ї(ЇL₁B₂)(+(+B₂L₂)(*L₂B₂))))).

или B₁H₁L₁ЇB₂H₂L₂Ї(B₁+L₁)/(L₁Ї2B₂ЇL₂ЇL₂B₂).

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

(Ї(*(*B₁H₁)L₁)(*(*L₂H₂)B₂)) или L₁B₁H₁ЇL₂B₂H₂.

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

Эксперименты с использованием ADF для ранее рассмотренной задачи о параллелепипедах показали что с точки зрения вычислительной трудоемкости и структурной сложности преимущество за ГП без ADF.

Однако имеется целый ряд задач, свидетельствующих об обратном. Рассмотрим одну из них, связанную с проверкой на четность. Пусть булева функция, зависящая от пяти аргументов (D₀, D₁, D₂, D₃, D₄), принимает значение T, если четное число аргументов принимают значение «истина», в противном случае, булева функция принимает значение Nil (константа, обозначающая список, в котором нет ни одного элемента); 32 возможных комбинации аргументов служат основой для оценки ГП с ADF и без ADF.

Для ГП без ADF и с ADF устанавливаются одинаковые стартовые условия и параметры эволюции: функция соответствия определяется числом совпадений значений исходной функции со значениями, выдаваемыми ГП; м=16 000; программа останавливается, если число совпадений равно 32.

Результаты моделирования однозначно свидетельствуют о преимуществе ГП с ADF как по структурной сложности решений, так и по вычислительной трудоемкости.

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

Авторы [8], исследуя решения различной длины, получаемые с помощью ГП, обратили внимание на так называемый эффект «компрессионного давления», которым обладают решения с малой структурной сложностью. Программы, генерируемые по методу ГП, как уже отмечалось выше, зачастую содержат «лишние» блоки, не влияющие на функциональные возможности программы и на целевую функцию. В генетике это соответствует понятию интрона, который является нечувствительным к кроссинговеру. Принято считать, что применение кроссинговера носит деструктивный характер, если целевая функция ухудшается. Следовательно, для программы с относительно большим значением структурной сложности, но содержащей много интронов, опасность деструктивного воздействия кроссинговера заметно уменьшается. С учетом этого, а также принимая во внимание известную Schema-теорему Дж. Холланда, приведем следующую последовательность рассуждений.

Обозначим через С_е(а_i) эффективную сложность программы a_i (i=1,2,…м), через С_a (a_i) абсолютную сложность программы а_i, через p_c — вероятность применения кроссинговера, а через p_d -вероятность того, что применение кроссинговера приведет к деструктивному эффекту, причем p_d=0, если кроссинговер проводится с интроном. Пусть Ф (a_i) — значение функции соответствия программы a_i; Ц (a_i) — среднее значение функций соответствия всех программ в популяции P (t). Если применяется пропорциональная селекция, то нижняя оценка A_i(t+1) «доли» программы a_i в популяции P (t+1) примерно равна.

A_i(t+1)? A_i(t)· Ц (a_i)/[Ц (t)]·(1Їp_c·С_е(а_i)·p_di/ С_a (a_i)) = A_i(t)·? Ц (a_i)Їp_c· Ц (a_i) С_е(а_i)· p_di/ С_a (a_i) ?,.

где выражение в скобках представляет собой функцию Ц_e(a_i) эффективной сложности программы:

Ц_e(a_i) = Ц (a_i)Їp_c· Ц (a_i) С_е(а_i)· p_di/ С_a (a_i),.

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

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

на ранних этапах эволюции среднее значение целевой функции от популяции к популяции изменяется очень сильно, в то время как Ф_e изменяется относительно медленно;

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

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

Теоретически обоснованное и эмпирически наблюдаемое явление «компрессии» таит в себе опасность преждевременной сходимости ГП к субоптимальным решениям.

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