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

ГЕНЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В генетическом программировании (ГП) в качестве особи выступает программа, представленная в определенном формате, которая решает некоторую задачу. В качестве фитнесс-функции достаточно часто выступают функции ошибки (рассогласования, невязки в различной метрике). ГП работает с генетическим материалом переменной длины, что требует нестандартной формы представления генома и соответствующих генетических операторов. Функциональное и терминальное множества Терминальное множество включает в себя: 1) внешние входы в программу; 2) используемые в программе константы; 3) функции, которые не имеют аргументов. Функциональное множество может состоять из операторов: - булевы функции И, ИЛИ, НЕ и т.п.; - арифметические функции сложения, вычитания, умножения, деления; - трансцендентные функции (тригонометрические, логарифмические); - функции присваивания значения переменным (a:=2); - условные операторы (if then, else: case или switch операторы ветвления); - операторы переходов (go to, jump, call- вызов функции); - операторы цикла (while do, repeat until, for do); - подпрограммы и функции. Структуры для представления программ Наиболее распространенными структурами для представления особей (потенциальных решений проблемы) являются: 1) древовидное представление; 2) линейная структура; 3) графоподобная структура. Древовидное представление / d ген оти п * e a + b c Древовидное представление формулы d/e-a*(b+c). Линейные структуры Каждая особь (программа) представлена последовательностью переменной длины операторов некоторого упрощенного языка программирования (например, Си). void int u double v[8] { … v[0]=v[5]+75; v[7]=v[0]-69; if (v[1]>0) if (v[4]>21) v[4]=v[2]*v[1]; v[2]=v[5]+v[4]; v[6]=v[4]-4; v[1]=sin(v[6]); if(v[0]>v[1]) v[5]=v[7]+115; if(v[1]<=v[6]) v[1]=sin(v[7]); } Графоподобные структуры Здесь каждая особь – программа представляется в виде графа. Вершина графа представляет линейный участок программы. Она имеет 2 части – собственно линейную программу и узел ветвления. - линейная программа - узел ветвления - узел графа -ребро графа Представление программы в виде графа Инициализация начальной популяции Данный этап в ГП является не таким простым, как в классическом ГА, где генерация случайных двоичных строк не представляет особых проблем. Это связано с различной сложностью особей и их структурой. Естественно методы инициализации начальной популяции различны для разных форм представления программ. Одним из важнейших параметров в ГП является максимально возможный размер (сложность) программы. Инициализация древовидных структур Для деревьев в качестве меры сложности используется максимальная глубина (иногда высота) дерева или общее число узлов в дереве. Глубиной узла называется минимальное число узлов, которые необходимо пройти от корня дерева к этому узлу. Максимальной глубиной дерева Dm называется максимально возможная глубина в дереве для терминального символа (листа) Инициализация древовидных структур выполняется путем случайного выбора функциональных и терминальных символов при заданной максимальной глубине дерева. Пусть для определенности выбраны следующее терминальное T={a,b,c,d,e} и функциональное F={+,-,*,%} множества, где % означает деление нацело. Применяются два основных метода: 1) полная (full) и 2) растущая (grow) инициализация [5]. а) полная б) растушая Деревья, генерируемые при инициализации разными методами. Инициализация линейных структур В этом случае процесс инициализации выполняется совершенно по-другому. Прежде всего, особь – программа разбивается на следующие четыре части: 1) Заголовок; 2) тело; 3) «подвал»; 4) выход (возврат). Из них только тело программы генерируется с помощью эволюции, остальные части программы используются стандартные и заготавливаются заранее. Алгоритм инициализации можно сформулировать следующим образом: 1) Выбор случайной длины из заданного диапазона; 2) Копирование заготовленного заголовка; 3) Инициализация и пополнение собственно операторов в программу пока не достигнута длина, определенная в пункте 1. Операторы выбираются случайно, сначала тип, затем переменная или константа из заданного диапазона; 4) Копирование в конец программы заготовленного «подвал»: 5) Копирование в конец программы заготовленных операторов выхода. Кроссинговер в генетическом программировании Выполнение кроссиновера на древовидных структурах Для древообразной формы представления используются следующие три основные оператора кроссинговера (ОК): а) узловой ОК; б) кроссинговер поддеревьев; в) смешанный. В узловом операторе кроссинговера выбираются два родителя (два дерева) и узлы в этих деревьях. Первый родитель называется доминантом, второй – рецессивом. Узлы в деревьях могут быть разного типа. Поэтому сначала необходимо убедиться, что выбранные узлы у родителей являются взаимозаменяемыми. Если узел во втором родителе не соответствует типу узла первого родителя, то случайным образом выбирается другой узел во втором родителе, который опять подлежит проверке на предмет совместимости. Далее производится обмен узлов. Рассмотрим ОК на следующем примере, представленном на рис.7.7 для 3 2 x  x  x  y родительских особей: 4 , 2  y z y Родители + + * * / 3 Х * Х 4 + У * У / Х Х У Z 2 Потомки + + * * / 3 Х + 4 Х Х * У У / Х * 2 Z У Узловой кроссинговер. В кроссинговере поддеревьев родители обмениваются не узлами, а определяемыми ими поддеревьями. Оператор выполняется следующим образом: 1. Выбираются родители (один – доминантный, другой – рецессивный). Далее необходимо убедиться, что выбранные узлы взаимозаменяемы, т.е. принадлежат одному типу. Иначе, как и в предыдущем случае в рецессивном дереве выбирается другой узел с последующей проверкой. 2. Затем производится обмен поддеревьев, которые определены этими узлами. 3. Вычисляется размер ожидаемых потомков. Если ожидаемый размер (сложность потомка) не превышает заданный порог, такой обмен ветвями запоминается. Этот тип ОК является основным. При этом под размером (под)дерева понимается, как и ранее, либо его высота, либо число его вершин . На рис. показан пример выполнения этого ОК. Родители + * + % + a % d c e 1 * 3 2 4 b Потомки + * + % 1 2 d % e + a * c b 3 4 При смешанном операторе кроссинговера для некоторых узлов выполняется узловой ОК, а для других - кроссиновер поддеревьев. Отметим, что выполнение кроссинговера на древовидных структурах выполняется достаточно просто с помощью S-выражений, что показано в таблице Например, кроссинговер поддеревьев сводится к обмену «скобками», которые здесь соответствуют поддеревьям. Родители Потомки (-(ab)c) ( - (- ( + d e) f) c ) (  (- ( + d e) f ) g) (  ( a b) g) Кроссинговер на линейных структурах Скрещивание на линейных структурах выполняется достаточно просто. Здесь у родителей выполняется обмен линейными сегментами, как это показано на рис.7.9. Родитель 1 Родитель 2 Потомок 1 Потомок 2 Выполнение кроссинговера для графоподобных структур Кроссинговер комбинирует генетический материал из двух родительских программ путем обмена некоторых частей программ. ОК для этой модели может быть реализован двумя способами. Первый способ похож на кроссиновер поддеревьев, который определен на древообразных структурах путем обмена поддеревьев. Здесь обмен производится подграфами, как это показано на рис.7.10. Родитель 1 Родитель 2 Потомок 1 Потомок 2 Кроссинговер на графоподобных структурах. При этом в каждой особи - родителе выбирается случайным образом множество смежных узлов и производится обмен 2-х подграфов между этими подграфами. Второй тип кроссинговера выполняет линейный ОК. Здесь для каждого родителя выбирается линейный сегмент (в одном узле графа), начинающийся со случайной позиции данного сегмента и имеющий случайную длину. Далее, как обычно, производится обмен этими линейными сегментами. Если размер хотя бы одного потомка превышает некоторый порог, то результаты ОК аннулируются и выполняется обмен равными сегментами меньшей длины. Обычно линейный ОК выполняется в вероятностью Pl  0.1. Пример выполнения этого ОК представлен на рис.7.11. Родители Потомки Как правило, в процессе эволюции используются ОК обоих типов. В целом ОК выполняется следующим образом: 1. Выбор точки скрещивания P1 , P2 в обоих родителях. 2. Выбор с заданной вероятностью типа ОК ( для 1-го типа с вероятностью PG , для 2- го с вероятностью1- PG ). Если выбран 1-й тип то переход на п.3, иначе на п.4. 3. Если размер потомка не превышает порог, то выполнить ОК 1-го типа, переход на п.5. 4. Если размер потомка не превышает порог, то выполнить ОК 2-го типа. 5.Конец. Мутация в генетическом программировании Выполнение мутации на древовидных структурах Для деревьев используются следующие операторы мутации (ОМ): а) узловая; б) усекающая; в) растущая. Узловая мутация выполняется следующим образом:  выбрать случайным образом узел, подлежащий мутации, определить его тип;  случайно выбрать из соответствующего множества вариантов узлов отличный от рассматриваемого узел;  поменять исходный узел на выбранный. Усекающая мутация производится так:  определяется или выбирается узел;  случайным образом выбирается терминальный символ из заданного множества;  обрезается ветвь узла мутации;  вместо обрезанной ветви помещается выбранный терминальный символ. На рис. показан пример выполнения усекающей мутации. (a+b)/c*d*e b/c*d*e * * % c + a b % * d e b * c d e Растущая мутация выполняется следующим образом:  определяется узел мутации;  если узел нетерминальный то необходимо отсечь ветви исходящие из него, иначе выбрать другой узел.  вычислить размер (сложность) остатка дерева;  вместо отсеченного дерева вырастить случайным образом новое дерево так, чтобы размер нового построенного дерева не превышал заданный порог. Это очень мощный оператор, который обладает большими возможностями. На рис. представлен пример выполнения этого оператора. 1 * ( d  e) 2 * * / 1 + 2 / d e + + c a d e b Рис. Растущая мутация. Для примера на рис.7.14 представлен результат выполнения мутации - перестановки 1 (аргументов) для дерева, представляющего выражение 2 * (d  e) . * * / 1 / + 2 d e 1 + 2 e d Фитнесс-функция в генетическом программировании В ГП фитнесс-функция обычно определяет меру близости между реальными требуемыми di yi и выходными значениями (например, при использовании ГП в символьной регрессии). Поэтому в качестве фитнесс-функции часто используется абсолютная или квадратичная ошибка. В этом случае фитнесс-функция использует обучающее множество данных, на котором выполняется обучение системы. С помощью фитнесс-функции в процессе обучения реализуется обратная связь, которая показывает, насколько хорошо данная особь-программа реализует необходимую функцию на обучающем множестве. «Непрерывной» (continuous) фитнесс-функцией называют функцию вычисления фитнесс-значений, в которой малое улучшение в обучении программы вызывает малые улучшения измеряемых фитнесс-значений и большие улучшения в обучении связаны соответственно с большими изменениями (в сторону улучшения) фитнесс-значений. «Стандартизованой» фитнесс-функцией называют преобразованную фитнессфункцию, которая лучшим особям приписывает нулевое значение. «Нормализованной» фитнесс-функцией называют преобразованную фитнесс- функцию, которая для всех особей дает значения в интервале (0,1). Рассмотрим следующий пример с обучающей выборкой, представленной табл. № Вход x Выход d 1 1 2 2 2 6 3 4 20 4 7 56 5 9 90 Каждая строка таблицы определяет один элемент (x,y) обучающей выборки. Необходимо в процессе эволюции построить программу (или формулу в случае символьной регрессии), которая для каждого входного значения x вычисляет необходимое (в соответствии с табл.) значение y реализовать функцию f ( x)  x 2  x (фактически нам необходимо ). Рассмотрим в качестве фитнесс-функции ошибку в метрике абсолютных значений, n f a   yi  d i i 1 где суммирование выполняется по обучающей выборке. Эта фитнесс- функция соответствует первому определению «непрерывной» поскольку чем ближе значения yi к di, тем меньше значение фитнесс-функции. Данная фитнесс-функция является также стандартизованной, так как случае для идеального решения дает нулевое значение. Часто в качестве фитнесс-функции также используют квадратичную ошибку n f s    y i  d i 2 i 1 . Следующая таблица показывает различие для этих двух фитнесс-функций в том случае, если на некотором (промежуточном) этапе в качестве особи оценивается (плохо 2 обученная) программа, реализующая функцию f ( x)  x . № Вход x Выход d Выход y Ошибка Ошибка fa fs 1 1 2 1 1 2 2 2 6 4 2 4 3 4 20 16 4 16 4 7 56 49 7 49 5 9 90 81 9 81 23 151 Общая ошибка Подобный подход применяется также во многих других задачах, где используются следующие фитнесс-функции: 1) число правильно отображаемых пикселов в задачах обработки изображений; 2) число столкновений робота со стенами при обучении обхода препятствия; 3) число правильно классифицируемых примеров в задачах классификации; 4) ошибка между реальными и ожидаемыми значениями в задачах прогнозирования; 5) приз победителя в игровых задачах; 6) количество «пищи», найденной агентом, в многоагентных системах («искусственная жизнь» и т.п.) Естественно разработано множество фитнесс-функций других типов, их вид существенно зависит от исследуемой проблемы, а применение ГП не ограничивается задачами символьной регрессии. В некоторых случаях, кроме близости решений учитываются и другие критерии, например, длина или время выполнения программы. многокритериальных фитнесс-функциях. В этом случае говорят о Интроны Программы, построенные с помощью методов ГП, имеют тенденцию к накоплению интронов – ненужных и непригодных участков кода. Например: NOT NOT x , (AND (ORXX)), (+… (-XX)), (+X0), (*X1), (*(DIV XX)), (MOVE_LEFT MOVE_RIGHT), (IF (2=1) . . . ), A:=A. Таких фрагментов в программе возникает достаточно много (их количество может достигать 60%), и обнаружение и удаление интронов представляет серьезную проблему в ГП. Разработаны специальные методы для их устранения. Общий алгоритм генетического программирования Таким образом, для решения задачи с помощью ГП необходимо выполнить описанные выше предварительные этапы: 1) Определить терминальное множество; 2) Определить функциональное множество; 3) Определить фитнесс-функцию; 4) Определить значения параметров, такие как мощность популяции, максимальный размер особи, вероятности кроссинговера и мутации, способ отбора родителей, критерий окончания эволюции (например, максимальное число поколений) и т.п. После этого можно разрабатывать непосредственно сам эволюционный алгоритм, реализующий ГП для конкретной задачи. Как и в случае ГА здесь также возможны различные подходы, параллельные ГА). которые рассмотрены в разделах 4-5 (модификации и Например, решение задачи на основе ГП можно представить следующей последовательностью действий. 1) установка параметров эволюции; 2) инициализация начальной популяции; 3) t:=0; 4) оценка особей, входящих в популяцию; 5) t:=t+1; 6) отбор родителей; 7) создание потомков выбранных пар родителей – выполнение оператора кроссинговера; 8) мутация новых особей; 9) расширение популяции новыми порожденными особями; 10) сокращение расширенной популяции до исходного размера; 11) если критерий останова алгоритма выполнен, то выбор лучшей особи в конечной популяции – результат работы алгоритма. Иначе переход на шаг 4. Символьная регрессия Этот раздел является одним из важнейших приложений ГП. Данный термин подчеркивает то, что здесь объектом поиска является символьное описание модели, в отличие от множества коэффициентов в стандартных методах регрессии. Задача регрессии может быть определена на основе множества значений входных независимых переменных x и зависимой выходной переменной y. Целью поиска является апроксимация y с помощью переменных x и коэффициентов w следующим образом y  f ( x, w)   , где  представляет шум (ошибку). В стандартних методах регресии вид функции f предполагается известным, например, в линейной регресии f ( x, w)  w0  w1 x1  ... wn x n . Здесь коэффициенты wi обычно находятся методом наименьших квадратов. Как уже отмечалось, символьная регрессия на основе ГП не использует некоторую заранее предопределенную форму функции Здесь функция эволюционным f ( x, w) методом терминального множеств. представляется с древовидной использованием структурой определенного и f ( x, w) . строится функционального и В качестве фитнесс-функции обычно используется квадратичная ошибка, которая оценивает качество решения и обеспечивает обратную связь при поиске решения. Для определенности обозначим функции множества, зависящие от одной переменной через h1,…, hk и функции от двух переменных как g1,…, gl. В этой нотации функция f ( x, w) представляется в виде суперпозиции функций hi , gj, и например, может иметь следующий вид f ( x, w)  h1 ( g 2 ( g1 ( x3 , w1 ), h2 ( x1 ))) . Далее рассмотрим детально пример использования символьной регрессии из для апроксимации данных, представленных в табл. Необходимо найти функцию f(x), которая апроксимирует с заданной точностью эти «экспериментальные» данные № Вход x Выход y 1 0.000 0.000 2 0.100 0.005 3 0.200 0.020 4 0.300 0.045 5 0.400 0.080 6 0.500 0.125 7 0.600 0.180 8 0.700 0.245 9 0.800 0.320 10 0.900 0.405 Для решения задачи определим в соответствии с вышесказанным: 1. Терминальное множество: переменная x и константы в диапазоне [-5,5]; 2. Функциональное множество: арифметические функции +, - , * , % (защищенное деление). 3. Фитнесс-функция – стандартизованная на основе корня квадратного средней квадратичной ошибки. 4. Параметры: мощность популяции, методы инициализации популяции и отбора родителей, значения вероятностей кроссинговера и мутации. Koza ввел следующую удобную и «прозрачную» форму для перечисления параметров , которая представлена в следующей таблице. Параметры Значения Цель: Эволюция функции, апроксимируюшей данные Табл.7.6 Терминальное множество Переменная x, Функциональное множество ADD, SUB, MUL, DIV Целые от –5 до +5 Мощность популяции: Вероятность кросинговера: Вероятность мутации: Отбор родителей: Максимальное число поколений: 600 0.90 0.05 турнирный с мощностью тура 4 100 Максимальная глубина после кроссинговера: 200 Максимальная глубина мутации: 4 Метод инициализации: Растущая Далее приведем некоторые полученные экспериментальные данные результатов эволюции для различных запусков программ. В начальной популяции после инициализации лучшая особь представлена деревом которая реализует (не минимальным образом !) функцию f 0 ( x)  x . 3 В последующих рисунках представлены лучшие особи последующих поколений. x f ( x )  1 Здесь в первом поколении лучшая особь реализует 6  3x и соответствующее дерево сильно избыточно. % Х - 4,0 % Х Х Рис. Лучшая особь в поколении 0 f 0 ( x)  x . 3 % * -1.0 % % + x % * 5.0 % 1.0 * 0.0 -1.0 x x -1.0 4.0 x * x -3.0 * x + 4.0 -1.0 * 1.0 -2.0 x f ( x )  Рис. Лучшая особь поколения 1 1 6  3x . % Х - + _ _ + + Sub 1 1.0 % -4.0 * + y + X -4.0 % _ 3.0 2.0 * X + X -4.0 _ X 1.0 X Рис.. Лучшая особь поколения 2. % * - % + x - 1.0 x % % 4.0 - % 0.0 * * - 5.0 - -1.0 x * x * % 2.0 x - 1.0 2.0 * - - * x - 1.0 x x x - 3.0 * x + * 4.0 - 1.0 1.0 - 2.0 Рис. Лучшая особь поколения 3. В четвертом поколении получена лучшая особь f 3 ( x)  x2 , 2 которая дает оптимальное решение в простейшей форме. % * х 2,0 х Рис. Лучшая особь поколения 4 f 3 ( x)  x2 2 . Следует отметить, что мощность популяций используемых в ГП на порядок выше, чем в классических ГА, а число поколений, как правило, меньше. Применение ГП в качестве символьной регрессии является важным для многих технических задач (например, в гидро- и аэро-динамике), но далеко не единственным. Интересным примером является машинный вывод третьего закона Кеплера на основе символьной регрессии. Итак, есть экспериментальные данные, которые связывают радиус и период обращения планет солнечной системы, которые представлены в табл.6.12 (в астрономических единицах). Таблица 6.12 Планета Радиус - r Период - p Меркурий 0,387 0,24 Венера 0,723 0,62 Земля 1,000 1,000 Марс 1,524 1,88 Юпитер 5,203 11,86 Сатурн 9,569 29,46 Уран 19,309 84,01 Нептун 30,284 164,79 Плутон 39,781 247,69 Напомним, что согласно закону Кеплера, период обращения планеты пропорционален корню квадратному из третьей степени радиуса орбиты планеты (чаще используется формулировка P  (r ) 3 , r3  c ). P2 где r – радиус орбиты На рис.6.20 представлено полученное с помощью символьной регрессии дерево, которое представляет закон Кеплера. Рис. Дерево, представляющее третий закон Кеплера Параметры Значения Цель: Вывод третьего закона Кеплера, апроксимируюшей данные табл.6.12 Терминальное множество Переменная r (расстояние от солнца в астрономических единицах) Функциональное множество +, - , * ,^ , sqrt, sin, cos Фитнесс-функция Сумма абсолютных значений разности между реальным периодом и даваемым текущей формулой Мощность популяции: 500 Вероятность кросинговера: 0.80 Вероятность мутации: 0.05 Максимальное число поколений: 50 ПРИМЕНЕНИЕ ГП ДЛЯ ЗАДАЧИ ПРОГНОЗИРОВАНИЯ СТОИМОСТИ РАЗРАБОТКИ ПРОГРАММНОЙ СИСТЕМЫ Напомним, что основным методом оценки стоимости разрабатываемых программных систем является методика СОСОМО, ядром которой является следующая формула , Где DL представляет сложность разрабатываемого ПО в килостроках, А значения коэффициентов a и b зависят от типа и сложности проекта. Типичные значения этих коэффициентов для различных проектов представлены в следующей таблице. Ранее мы рассмотрели применение генетического алгоритма к решению задачи поиска оптимальных значений коэффициентов a и b , которые минимизируют некоторую ошибку (различие) медлу реальными и модельными значениями. Математический аппарат генетического программирования позволяет обобщить рассматриваемую задачу и искать не только значения коэффициентов a и b, но и другие формулы. Рассматриваемая задача относится к задачам символьной регрессии. Фактически, ГП позволяет решать задачи не только параметричекого, но и структурного синтеза. Напомним, что для решения этой задачи, прежде всего, необходима обучающая выборка. Часто в качестве обучающей выборки используются различные подмножества проектов НАСА, на основе которых разработана методика СОСОМО, например, представленное в следующей таблице. Здесь во втором столбце представлена сложность ПО в килостроках, в третье столбце –оценка используемой методики, и в последнем – реальная (измеренная) стоимость проекта в человекамесяцах. Напомним, что в ГП потенциальное решение (в данном случае формула) представляется древовидной структурой. Например, формула Представляется в виде следующего дерева Процесс искусственной эволюции представлен на следующем рисунке Для того, чтобы применить ГП к решению нашей задачи – оценки стоимости проекта по заданным значениям входных параметров сложности и используемой методики необходимо , прежде всего: -определить терминальное и функционально множество; - определить фитнесс-функцию для данной задачи; - задать критерий окончания процесса искусственной эволюции; - задать управляющие параметры ГП (мощность популяции, вероятности кроссинговера, мутации и т.п….). В качестве фитнесс-функции используют меру ошибки между реальными E (заданными в обучающей выборке) и модельными значениями Ê (получаемых согласно выведенным формулам модели). Например, для этого часто применяется среднее значение относительной ошибки Или вариабельность (дисперсия) Кроме этого, можно использовать и длугие меры, рассмотренные ранее в разделе оценки стоимости с помощью ГА. В следующей таблице показаны некотрые используемые параметры ГП. В качестве обучающего множества используется подмножество из 13 проектов, представленных ранее в таблице. Данные остальных проектов используются в каяестве тестового множества для оценки качества построенной модели. Эсперименты В результате экспериментов применения ГП для решения данной задачи с использованием языка искусственного интеллекта Lisp построены различные модели: 1) без учета методики МЕ; 2) с учетом методики МЕ. Одна из простейших моделей в виде Lisp-программы показана ниже Она соответствует следующей формуле В следующей таблице показаны значения используемых параметров ГП Ниже на рисунке показан процесс сходимости ГП при выводе простейших формул без учета методики МЕ для различных мощностей (числа особей) популяции Следующая таблица показывает реальные и модельные значения оценок стоимостей проектов Аналогичные эксперименты проведены для более продвинутых моделей с учетом методики МЕ. При этом использовались следующие параметры ГП. Ниже на рисунке показан процесс сходимости ГП при выводе простейших формул с учетом методики МЕ для различных мощностей (числа особей) популяции Следующая таблица показывает реальные и модельные значения оценок стоимостей проектов с учетом методики МЕ Следует отметить, что учет метоки МЕ позволяет повысить качество модели, что подтверждают следующая таблица. Наконец, следующая таблица показывает, что ГП дает одни из лучших результатов (сравнимые с применением нечетких моделей) – более качественные модели оценки стоимости проектов на текущий момент. Заметим, что метод роевого интеллекта (PSO) дает тоже неполохие результаты, но все же уступает ГП.