Программы как деревья

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

Программы на большинстве языков – неважно, компилируемых или интерпретируемых – сначала преобразуются в дерево разбора, очень напоминающее то, с чем мы будем работать далее. (Язык программирования Lisp и его диалекты – это, по существу, способ непосредственного представления программы в виде дерева разбора.) На рис. 11.2 представлен пример дерева разбора.

Каждый узел представляет либо операцию над дочерними узлами либо является листовым, например параметром или константой. Так, кружочком представлена операция суммирования двух ветвей, в данном случае значений переменной Y и константы 5. Вычисленная сумма передается вышестоящему узлу, который применяет собственную операцию

Рис. 11.2. Программа, представленная в виде дерева

к своим потомкам. Обратите внимание, что один из узлов соответствует операции if; это означает, что если значение левой ветви равно true, то он возвращает свою центральную ветвь, а если false – то правую ветвь.

Обход всего дерева эквивалентен следующей функции на языке Python:

def func(x,y) if x>3:

return y + 5 else:

return y – 2

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100