Представление деревьев на языке Python

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

Создайте новый файл gp.py и в нем четыре класса – fwrapper, node,

paramnode и constnode:

from random import random,randint,choice from copy import deepcopy from math import log

class fwrapper: def      init     (self,function,childcount,name):

self.function=function

self.childcount=childcount

self.name=name

class node:

def ____ init   (self,fw,children):

self.function=fw.function

self.name=fw.name

self.children=children

def evaluate(self,inp):

results=[n.evaluate(inp) for n in self.children] return self.function(results)

class paramnode: def __init__(self,idx): self.idx=idx

def evaluate(self,inp): return inp[self.idx]

class constnode: def __init__(self,v): self.v=v

def evaluate(self,inp): return self.v

Эти классы предназначены для следующих целей:

fwrapper

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

node

Класс функциональных узлов (имеющих потомков). Инициализируется экземпляром класса fwrapper. Метод evaluate вычисляет значения дочерних узлов и передает их представленной данным узлом функции в качестве параметров.

paramnode

Класс узлов, которые просто возвращают один из переданных программе параметров. Его метод evaluate возвращает параметр, соответствующий значению idx.

constnode

Узлы, возвращающие константы. Метод evaluate просто возвращает то значение, которым экземпляр был инициализирован.

Потребуются также функции, которые будут вызываться при посещении узлов. Такие функции вы должны будете написать и передать

вместе с именем и счетчиком параметров конструктору класса fwrapper.

Добавьте в файл gp.py следующий список функций:

addw=fwrapper(lambda l:l[0]+l[1],2,’add’) subw=fwrapper(lambda l:l[0]-l[1],2,’subtract’) mulw=fwrapper(lambda l:l[0]*l[1],2,’multiply’)

def iffunc(l):

if l[0]>0: return l[1] else: return l[2] ifw=fwrapper(iffunc,3,’if’)

def isgreater(l):

if l[0]>l[1]: return 1 else: return 0 gtw=fwrapper(isgreater,2,’isgreater’)

flist=[addw,mulw,ifw,gtw,subw]

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

Построение и вычисление деревьев

Теперь с помощью класса node можно построить дерево программы, изображенное на рис. 11.2. Добавьте в файл gp.py функцию exampletree:

def exampletree( ): return node(ifw,[

node(gtw,[paramnode(0),constnode(3)]),

node(addw,[paramnode(1),constnode(5)]),

node(subw,[paramnode(1),constnode(2)]),

]

)

Запустите интерпретатор Python и протестируйте программу: >>> import gp

>>> exampletree=gp.exampletree( ) >>> exampletree.evaluate([2,3])

1

>>> exampletree.evaluate([5,3])

8

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

Визуализация программы

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

Создайте в классе node метод display, который выводит представление дерева в виде строки:

def display(self,indent=0): print (‘ ‘*indent)+self.name for c in self.children: c.display(indent+1)

Необходимо также добавить метод display в класс paramnode, где он будет просто печатать индекс возвращаемого параметра:

def display(self,indent=0):

print ‘%sp%d’ % (‘ ‘*indent,self.idx)

и в класс constnode:

def display(self,indent=0):

print ‘%s%d’ % (‘ ‘*indent,self.v)

Воспользуйтесь этими методами для распечатки дерева: >>> reload(gp)

<module ‘gp’ from ‘gp.py’>

>>> exampletree=gp.exampletree( )

>>> exampletree.display( )

if

isgreater p0

add p1 5

subtract p1

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

Вы можете следить за любыми ответами на эту запись через 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