Исходный URL: http://www.codenet.ru/progr/alg/Smart/Genetic-Programming.php
Генетическое программирование
Что такое генетическое программирование?
Уж не знаю почему ГА и ГП разделяют на разные области, но я к ним
отношусь как к одному и тому же.
Единственное отличие ГП от ГА состоит в том, что каждая особь в
популяции теперь кодирует не числовые характеристики, которые обеспечивают
задаче оптимальность, а некоторую "программу", которая решает поставленную
проблему.
Под словом "программа" здесь не стоит понимать реальную программу на
Си, ассемблере и т.д. Чаще всего, такая программа - это всего навсего
конфигурация дерева функции, нейронной сети или автомата.
Алгоритм работает по всем законам ГА, лишь при оценке новой особи
происходит "исполнение" программы, а затем оценка её деятельности.
Например, в задаче автоматического определения функции хромосома кодирует
некоторую сложную, часто многопараметрическую функцию. При оценке
происходит расчет закодированной функции на тестовой выборке входных
значений, после чего, результаты расчетов сравниваются с тестовыми
(экспериментальными) значениями искомой функции на представленной выборке,
происходит расчет отклонения текущей функции от искомой, которое
используется как оценка особи. Уменьшая отклонение, алгоритм находит
неизвестную функцию, представленную тестовой выборкой.
В принципе, возможно создание и реальной программы на некотором простом
языке (вроде ассемблера). Но тогда возникает проблема исполнения такой
программы (чтоб не подвисла) и оценки результата.
Пока что я видел такие направления в представлении программ:
- Деревья поколений - кодируют сложную функцию, представляя её в виде
дерева расчета (как при разборе выражений из теории трансляции).
Используются при решении задачи автоматического определения функций.
- Нейронные сети - множество связанных однотипных элементов. Для
автоматического определения функций не подходят, но имеют различные
специфические применения.
- УНС - унифицированные нейронные сети (модель и принципы применения
предложены мной в дипломной работе). Позволяют представлять любую
расчетную многопараметрическую сложную функцию в компактном виде,
присущем нейронным сетям. Это позволяет применять их в задачах
автоматического определения функций. Также, обладают всеми качествами
нейронных сетей, однако имеют слишком сложную топологию. Обучаются по
ГА/ГП или К-Срезу.
- Автоматы - задают последовательность переходов состояний.
Используются как способ представления простых алгоритмов для "роботов".
В сочетании с ГА/ГП использовались в игре на предсказание
последовательности чисел.
Деревья поколений.
В генетическом программировании особи из популяции представляют собой
программы. Удобно представлять эти программы в виде деревьев, где функции
представлены внутренними узлами, к которым в качестве входных параметров
присоединены поддеревья. Листьями такого дерева будут константы, входные
параметры задачи или директивные команды программы.
Пример простой программы-дерева: =
|
+
/ \
* 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 достаточно, возможно лишь в редких
случаях. Поэтому, при выборе этого множества, как и при выборе основных
операций генетического алгоритма, приходится полагаться лишь на интуицию и
экспериментальный опыт.
|
