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

Методы генетического программирования были разработаны в начале 1990-х гг. Дж. Козой. Генетическое программи­рование — это способ создания компьютерных программ для за­дач с неизвестным алгоритмом решения. Объектом эволюции яв­ляется программа, а популяция содержит множество различных программ. Совершенствование объекта осуществляется на осно­ве отбора в соответствии с определенной функцией ценности (fit­ness function). Программы строятся из блоков, которые представ­ляют собой примитивные функции и терминалы. В качестве при­митивных функций обычно рассматриваются арифметические и логические операции, математические функции и функции спе­циального вида, характерные для класса решаемых задач. Мно­жество терминалов содержит разнообразные данные, не создава­емые программой. Цель состоит в построении наилучшей про­граммы в пространстве программ, которые могут быть составле­ны из заданных функций и терминалов с учетом определенных правил синтаксиса.

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

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

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

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

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

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

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

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

Эти выражения можно представить в виде деревьев (рис.9), когда в процессе эволюции на уровне поддеревьев осуществляется ре­комбинация и получаются потомки (рис. 10). Первый из этих потомков представляет собой реализациюоперации исключаю­щего ИЛИ:

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

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

Рис.9. Представление символьных выражений языка LISP в виде деревьев

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

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

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

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

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

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

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

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

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