Пт. Мар 1st, 2024

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

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

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

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

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

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

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

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

Мутация заключается в замене некоторого фрагмента программы случайно порожденным символьным выражением.

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

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

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

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

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

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

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

Рис. 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 — валовой национальный продукт.

Ads Blocker Image Powered by Code Help Pro

Обнаружен блокировщик рекламы! Пожалуйста, обратите внимание на эту информацию.

We\'ve detected that you are using AdBlock or some other adblocking software which is preventing the page from fully loading.

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

Пожалуйста, добавьте tehnar.info к вашему белому списку блокирования объявлений или отключите программное обеспечение, блокирующее рекламу.

Powered By
Best Wordpress Adblock Detecting Plugin | CHP Adblock