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

Методы генетического программирования были разработаны в начале 1990-х гг. Дж. Козой. Генетическое программи­рование — это способ создания компьютерных программ для за­дач с неизвестным алгоритмом решения.

Технология генетического программирования включает cледующие этапы.

Этап 1. Формирование множества терминалов, множества примитивных функций, синтаксических правил и критериев оценки создаваемых программ.

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

Этап 3. Каждая программа выполняется, а результаты ее ра­боты оцениваются с помощью fitness function (целевой функции).

Этап 4. Формируется новая популяция программ, в которую сгенерированные программы могут попасть с вероятностью, про­порциональной значению целевой функции.

Этап 5. Реализуются генетические операторы репродукции, скрещивания и мутации. В результате репродукции осуществля­ется копирование уже созданных программ с хорошими значени­ями целевой функции. Оператор скрещивания создает новые программы путем комбинирования фрагментов существующих программ.

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

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

Эти выражения можно представить в виде деревьев (рис. 6.9). В процессе эволюции на уровне поддеревьев осуществляется ре­комбинация и получаются потомки (рис. 6.10).

Первый из этих потомков представляет собой реализацию операции исключаю­щего ИЛИ:

Результатом применения оператора мутации является замена части дерева другим выражением, сгенерированным случайным образом. Точка мутации также выбирается случайно.

Идеи генетического программирования положены в основу программ, которые называются симуляторами «искусственной жизни». В работе Дж. Козы приводится следующий пример подобной программы. На тороидальной сетке размером 32×32, в 89 ячейках помещается «пища». Существуют некие препятствия, мешающие «насекомым» добраться до «пищи». «Насекомые» по­падают на сетку из одной точки, и каждое движется согласно ко­мандам своей программы. В начальной популяции эти програм­мы формируются случайным образом из операторов, которые проверяют наличие препятствий и предписывают движение пря­мо, влево или вправо.

Рис. 6.10. Потомки от скрещивания родителей на уровне поддеревьев

Задается время жизни популяции (400 шагов). Цена каждой программы определяется числом шагов, кото­рые необходимо совершить, чтобы обойти все ячейки с «пищей». Каждая следующая популяция формируется из предыдущей с по­мощью генетических операторов репродукции, скрещивания и мутации с учетом ценности программ предыдущей популяции. Решение для популяции из 4000 «насекомых» было найдено за 20 итераций.

Последователи Дж. Козы исследовали в своих работах возмож­ность использования ГП для синтеза сложных автоматов, а также для структурной идентификации динамических систем.

В примере построения экономической балансовой модели поставлена цель уточнения эконометрического уравнения обмена, связывающего уровень цен, валовой национальный про­дукт (ВНП), запас денег и скорость оборота денег в экономике.

В качестве терминалов здесь используются следующие пере­менные: ВНП82 — уровень ВНП за 1982 г.; GD — дефлятор ВНП (выходная переменная модели), нормализованный к единице для 1982 г.; FM- ежемесячная величина запаса денег. Приведенные переменные являются функциями времени. Их значения опреде­ляются на основе статистических данных в виде временных ря­дов. Кроме того, используется множество обобщенных констант действительного типа R.

Для обработки переменных предусмотрены следующие опе­рации: сложение (+); вычитание (-); умножение (*); защищенное деление (%), результатом которого является единица при попыт­ке разделить на 0; защищенное логарифмирование (RLOG), даю­щее 1 при нулевом значении аргумента; вычисление экспоненты (ЕХР).

Грубая оценка пригодности сгенерированных уравнений вы­числяется как сумма квадратов отклонений расчетных значений от фактических в заданных экспериментальных точках:

Значение  масштабируется в целях получения нормиро­ванной оценки пригодностикоторая изменяется на интервале [0, 1] и позволяет перейти к задаче максимизации. На основе  вычисляется относительная нормированная оценка пригодности которая имеет более высокие значения для лучших членов популяции и обладает свойством допускающим вероятностную интерпритацию.

Критерием окончания процесса эволюции является достиже­ние заданного числа генераций (50) или достижение наилучшего значения целевой функции. Численность популяции была при­нята равной 500. В процессе генерации новых поколений скре­щивание проводилось на 9Q% численности популяции, т.е. из каждого поколения выбиралось 225 пар родителей с вероятнос­тью, равной относительной оценке их пригодности. Кроме того, для каждой новой популяции осуществлялась репродукция 10% лучших представителей поколения.

Генерируемые модели (программы) удобно представить в ви­де древовидных структур (рис. 6.11).

Рис. 6.11. Древовидное представление компьютерных моделей, отобранных для скрещивания: а — родитель 1; б — родитель 2

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

Рис. 6.12. Модели-потомки, полученные в результате скрещивания

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

Используя статистические данные за 30 лет (заметим, что в примере исследовалась экономика США в период с 1959 по 1988 г.), генетический алгоритм за 50 последовательных генера­ций выдал наилучшее решение которое хорошо согласуется с известным эконометрическим уравнением обмена где Р — уровень цен; М — запасы денежной массы; V— скорость обращения денег в экономике; Q — валовой национальный продукт.