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

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

Уж не знаю почему ГА и ГП разделяют на разные области, но я к ним отношусь как к одному и тому же.

Единственное отличие ГП от ГА состоит в том, что каждая особь в популяции теперь кодирует не числовые характеристики, которые обеспечивают задаче оптимальность, а некоторую "программу", которая решает поставленную проблему.

Под словом "программа" здесь не стоит понимать реальную программу на Си, ассемблере и т.д. Чаще всего, такая программа - это всего навсего конфигурация дерева функции, нейронной сети или автомата.

Алгоритм работает по всем законам ГА, лишь при оценке новой особи происходит "исполнение" программы, а затем оценка её деятельности. Например, в задаче автоматического определения функции хромосома кодирует некоторую сложную, часто многопараметрическую функцию. При оценке происходит расчет закодированной функции на тестовой выборке входных значений, после чего, результаты расчетов сравниваются с тестовыми (экспериментальными) значениями искомой функции на представленной выборке, происходит расчет отклонения текущей функции от искомой, которое используется как оценка особи. Уменьшая отклонение, алгоритм находит неизвестную функцию, представленную тестовой выборкой.

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

Пока что я видел такие направления в представлении программ:

• Деревья поколений - кодируют сложную функцию, представляя её в виде дерева расчета (как при разборе выражений из теории трансляции). Используются при решении задачи автоматического определения функций.
• Нейронные сети - множество связанных однотипных элементов. Для автоматического определения функций не подходят, но имеют различные специфические применения.
• УНС - унифицированные нейронные сети (модель и принципы применения предложены мной в дипломной работе). Позволяют представлять любую расчетную многопараметрическую сложную функцию в компактном виде, присущем нейронным сетям. Это позволяет применять их в задачах автоматического определения функций. Также, обладают всеми качествами нейронных сетей, однако имеют слишком сложную топологию. Обучаются по ГА/ГП или К-Срезу.
• Автоматы - задают последовательность переходов состояний. Используются как способ представления простых алгоритмов для "роботов". В сочетании с ГА/ГП использовались в игре на предсказание последовательности чисел.

Деревья поколений.

В генетическом программировании особи из популяции представляют собой программы. Удобно представлять эти программы в виде деревьев, где функции представлены внутренними узлами, к которым в качестве входных параметров присоединены поддеревья. Листьями такого дерева будут константы, входные параметры задачи или директивные команды программы.

Пример простой программы-дерева:

                                      =
                                      |
                                      +
                                     / \
                                    *   7
                                   / \
                                  x   3

Такое представление программ наглядно и легко реализуемо. Однако, работа с деревьями не всегда удобна при выполнении таких операторов, как кроссинговер и мутация. По сути, необходимо реализовать совершенно новые операторы.

Кроссинговер будет заключаться в подмене одного из поддеревьев первого родителя на какое-либо поддерево второго родителя.

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

Таким образом, использование деревьев влечет за собой несколько проблем: необходимость создания новых операторов мутации и кроссинговера; динамическая длина хромосомы, кодирующей дерево.

Терминальный алфавит, функциональный базис и их свойства.

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

Второй шаг заключается в определении функционального множества, элементы которого должны использоваться для генерации математических выражений. Каждая компьютерная программа (то есть, анализируемое дерево, математическое выражение) является композицией функций от множества функций F и терминалов из терминального множества T (в случае программ-функций это константы и переменные).

Множество возможных внутренних узлов (не листовых), используемых в деревьях синтаксического анализа, используемых в генетическом программировании, называется функциональным множеством:

                             F={f1,f2,..,fn}

Каждая функция из функционального множества характеризуется арностью - количеством входящих параметров.

Множество листовых узлов в деревьях синтаксического анализа, представляющих программы в генетическом программировании, называются терминальным множеством:

                             T={t1,t2,..,tm}

Функциональное и терминальное множества могут быть объединены в однородную группу С, при условии, что терминалы рассматриваются как функции с нулевой арностью:

                                 C=F U T

Пространством поиска генетического программирования является множество всех возможных рекурсивных композиций функций множества C.

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

Множества F и T должны обладать свойствами замыкания и достаточности.

ЗАМЫКАНИЕ требует, чтобы каждая функция из множества F была способна принять аргументом любые значения и типы данных, которые могут быть возвращены любой функцией из множества C. Это предупреждает ошибки во время выполнения программ, полученных генетическим программированием. Для обеспечения условия замкнутости можно использовать защиту операций - принудительное приведение поступающих данных к диапазону, определяемому конкретной операцией. Например, операцию извлечения корня можно защитить от появления отрицательного аргумента принудительным расчетом модуля от этого аргумента. Альтернативой защите может быть автоматическое исправление ошибок в программе или применение штрафов за ошибки.

ДОСТАТОЧНОСТЬ требует, чтобы функции из множества C были способны выразить решение поставленной задачи, то есть, чтобы решение принадлежало множеству всех возможных рекурсивных композиций функций из C. Однако доказать, что выбранное множество C достаточно, возможно лишь в редких случаях. Поэтому, при выборе этого множества, как и при выборе основных операций генетического алгоритма, приходится полагаться лишь на интуицию и экспериментальный опыт.

---

Назад | Оглавление | Далее

Оставить комментарий

Комментарий: можно использовать BB-коды Максимальная длина комментария - 4000 символов.	CodeNet ВКонтакте Facebook Twitter Google Яндекс Чтобы оставить комментарий, необходимо авторизоваться. Можно ввести логин и пароль, или авторизоваться через социальные сети.

Комментарии