Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



Методы генетического программирования были разработаны в начале 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.Модели-потомки, полученные врезультате скрещивания

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


Эта страница нарушает авторские права

allrefrs.ru - 2017 год. Все права принадлежат их авторам!