Введение в Генетическое Программирование

Идею генетического программирования (ГП) - впервые предложил Коза в 1992 году, опираясь на концепцию генетических алгоритмов (ГА). Эта идея заключается в том, что в отличие от ГА в ГП все операции производятся не над строками, а над деревьями. При этом используются такие же операторы, как и в ГА: селекция, скрещивание и мутация.

1. Введение в генетическое программирование

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

Для примера можно рассмотреть функцию 2+x*4/7, представленную на рисунке 1. Терминальные элементы T = {2,x,4,7}, функциональные F = {+,*,/}.

Рис. 1. Древовидное представление функции 2+x*4/7

Для того чтобы применить ГП к какой-либо проблеме, необходимо определить:

• Множество терминальных элементов.
• Множество функциональных элементов.
• Меру приспособленности (fitness).
• Параметры, контролирующие эволюцию.
• Критерий останова эволюции.

2. Особенности операторов ГП

Алгоритм работы ГП такой же как и ГА: селекция, скрещивание и мутация. Однако поскольку ГП оперирует над деревьями, а не над строками, то операторы скрещивания и мутации имеют отличия.

2.1 Скрещивание

Оператор скрещивания работает следующем образом: выбираются случайные части родительских деревьев и эти части меняются местами.

Рис. 2. Скрещивание двух деревьев

В качестве особенности необходимо отметить, что в ГП размер хромосомы меняется. Чтобы предотвратить чрезмерное разрастание дерева, вводят максимальное количество функциональных элементов в дереве или максимальную глубину дерева. Однако при операции скрещивания возможна ситуация, когда при скрещивании двух деревьев получится одно из деревьев, превосходящее заданный лимит. В этом случае вместо конфликтного дерева копируется родительское дерево.

Рис. 3. Разрешение конфликтной ситуации предыдущего оператора
скрещивания при максимальной глубине дерева равной трем

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

 (NOT (NOT X))
 (IF (2=1)...X)
 (MOVE-LEFT MOVE-RIGHT)
 (DIV X X)
 (-X 0)
 (*X 1)

2.2 Мутация

Оператор мутации случайно удаляет часть дерева и заменяет ее новым деревом.

Рис. 4. Оператор мутации