Sonntag, 23. November 2014

Python Programming Genetic Programm programming


Python Programming Genetic Programm programming

Author D.Selzer-McKenzie

Video: http://youtu.be/FAeYfei2cs4


 

 

## Note: You may use this Genetic Programming module in any way you wish

## But please do not forget to give me the credit which I deserve

 

 

from random import *

from math import *

from pickle import *

#Global

 

 

class Variables:

    def __init__(self,VarList=[]):

        self.VarDict={}

        for variable in VarList:

            self.VarDict[variable]=0 #initially alot each variable a zero value

       

    def GetVal(self,var):

       

        if type(var)==type("String"):

           

            if self.VarDict.has_key(var):   

                return self.VarDict[var]

            else:

                return 0

        else:

            return var

    def SetVal(self,var,val):

        if self.VarDict.has_key(var):

            self.VarDict[var]=val

           

 

    def __len__(self):

        return len(self.VarDict)

 

    def keys(self):

        return self.VarDict.keys()

 

# NodeTypes

# LF:Leaf e.g constant or a varibele i.e it comprises of CS and VR

# CS:Constant e.g 1,2,3 etc. ,

# VR: variables A,B,C ,etc. and

# FN: Function eg. ADD, SUB, etc.

 

class Node:

    NodeTypes = {"FN":0,"LF":1,"CS":2, "VR":3}

 

    def __init__(self,Value=None,Nodes=[],Type="FN",FuncName=None,Variables=None):

        if Value=="random":

            self.Value=random()

        else:

            self.Value=Value

        self.Nodes=Nodes

        self.NodeValues=[]

        self.Type=self.NodeTypes[Type]

        self.FuncName=FuncName

        self.Variables=Variables

        self.Size=1

        self.Depth=1

        self.NodeId=1

       

    def GetNode(self,nodeno):

        self.SetNodeId()

        RetVal=self.GetNodeTemp(nodeno)

        return RetVal

 

    def SetNodeId(self,curnumber=1):

        self.NodeId=curnumber

        if self.Nodes:

            for i in range(0,len(self.Nodes)):

                curnumber=self.Nodes[i].SetNodeId(curnumber+1)

        return curnumber

 

    def GetNodeTemp(self,nodeno):

        if nodeno==self.NodeId:

            return self

        if self.Nodes:

            for i in range(0,len(self.Nodes)):

                if self.Nodes[i].GetNodeTemp(nodeno)!=None:

                    return self.Nodes[i].GetNodeTemp(nodeno)

           

        return None

 

    def SetNode(self,nodeno,CopyNode):

        if nodeno==self.NodeId:

            self=CopyNode

            return 1

        if self.Nodes:

            for i in range(0,len(self.Nodes)):

                reval=self.Nodes[i].SetNode(nodeno,CopyNode)

                if reval==1:

                    self.Nodes[i]=CopyNode

 

        return None

 

    def RecalSize(self):

        self.Size=1

        if self.Nodes:

            for Unit in self.Nodes:

                self.Size+=Unit.RecalSize()

        return self.Size

 

    def ReInit(self):

        self.SetNodeId()

        self.ReCalculate()

       

    def ReCalculate(self):

        self.Size=1

        self.Depth=1

        largest_depth=1

        if self.Nodes:

            for Unit in self.Nodes:

                Unit.ReCalculate()

                if Unit.Depth > largest_depth:

                    largest_depth=Unit.Depth

                self.Size+=Unit.Size

            self.Depth+=largest_depth

   

    def Eval(self):

        self.NodeValues[:]=[]

        if self.Type==self.NodeTypes["VR"]:

            return self.Variables.GetVal(self.Value)

        elif self.Type== self.NodeTypes["CS"]:

            return self.Value

        else:

            for Unit in self.Nodes:

                    self.NodeValues.append(Unit.Eval())

            return self.FuncName(self.NodeValues)

 

    def PrintTree(self):

        self.DrawTree(1)

 

    def DrawTree(self,level):

        kIndentText = "|  "

        IndentText=""

        for n in range(1,level):

            IndentText = IndentText+kIndentText

        self.NodeValues[:]=[]

        if self.Type==self.NodeTypes["VR"]:

            print IndentText+"+--["+self.Value+"]"

        elif self.Type==self.NodeTypes["CS"]:

            print IndentText+"+--["+str(self.Value)+"]"

        else:

            print IndentText+"+--"+self.FuncName.__name__

            for i in range(0,len(self.Nodes)):

                self.Nodes[i].DrawTree(level+1)

           

       

class Program:

    NodeTypes = {"FN":0,"LF":1,"CS":2, "VR":3}

 

    def RandomTree(self,depth):

        if depth==1:

            NodeUse=self.NodeTypes["FN"]

        elif depth==self.MaxDepth:

            NodeUse=self.NodeTypes["LF"]

        else:

            NodeUse=randint(0,1)

        if NodeUse==self.NodeTypes["FN"]:

            childFuncList=[]

            FuncToUse=randint(0,len(self.FuncDict)-1)

 

            for i in range(0,self.FuncDict.values()[FuncToUse]):

                child=self.RandomTree(depth+1)

                if not child:

                    print "Error: Child is nonetype"

                    break

                childFuncList.append(child)

            return Node(None,childFuncList,"FN",self.FuncDict.keys()[FuncToUse],self.Variables)

        else:

            #there is 50/50 chance that leaf would be variable or constant

            if randint(0,1)==0:

                #leaf would be constant

                TermToUse=randint(0,len(self.TerminalList)-1)

                return Node(self.TerminalList[TermToUse],None,"CS",None,self.Variables)

            else:

                #leaf would be a variable

                VarToUse=randint(0,len(self.Variables)-1)

                return Node(self.Variables.VarDict.keys()[VarToUse],None,"VR",None,self.Variables)

           

 

    def __init__(self,FuncDict,TerminalList,Variable=[],MaxDepth=10):

        self.MaxDepth=MaxDepth

        self.FuncDict=FuncDict

        self.TerminalList=TerminalList

        self.Fitness=0

        self.Variables=Variables(Variable)

        self.Tree=self.RandomTree(1)

        self.Tree.ReInit()

       

    def EvalTree(self):

        return self.Tree.Eval()

 

    def PrintTree(self):

        self.Tree.PrintTree()

 

    def Depth(self):

        return self.Tree.Depth

 

    def Size(self):

        return self.Tree.Size

 

    def AssignFitness(self,Fitness):

        self.Fitness=Fitness

 

    def GetNode(self,nodeno):

        return self.Tree.GetNode(nodeno)

 

    def SetNode(self,CopyNode,NodeNo):

        self.Tree.SetNode(NodeNo,CopyNode)

 

    def RetCopy(self):

        return self

 

class Programs:

 

    def __init__(self,FuncDict,TerminalList,Variable,MaxDepth=10,Population=100,MaxGen=100,ReqFitness=99,CrossRate=0.9,MutRate=0.1,BirthRate=0.2,HighFitness=100):

        self.Progs=[]

        self.MaxGen=MaxGen

        self.Population=Population

        self.ReqFitness=ReqFitness

        self.CrossRate=CrossRate

        self.MutRate=MutRate

        self.MaxFitness=0

        self.MaxFitnessProg=None

        self.BirthRate=BirthRate

        self.HighFitness=HighFitness

        self.MaxDepth=MaxDepth

        for i in range(0,Population):

            self.Progs.append(Program(FuncDict,TerminalList,Variable,MaxDepth))

 

    def MainLoop(self):

        for i in range(0,1+self.MaxGen):

            print "Generation no:",i

            for j in range(0,self.Population):

                CurFitness=FitnessFunction(self.Progs[j])

                self.Progs[j].AssignFitness(CurFitness)

                if CurFitness>self.MaxFitness:

                    self.MaxFitness=CurFitness

                    self.MaxFitnessProg=self.Progs[j]

                if self.MaxFitness>=self.ReqFitness:

                    print "Solution found."

                    self.Progs[j].PrintTree()

                    print "The fitness value is:",FitnessFunction(self.Progs[j])

                    return self.Progs[j]

            if random()>=(1-self.CrossRate):

                self.CrossOver()

                pass

            if random()>=(1-self.MutRate):

                self.Mutation()

                pass

            ### If you want confirmation to continue after each generation uncomment the following

 

            #ans=raw_input("Do you wanna quit? (1==Yes,0==No)")

            #print ans,":",type(ans)

            #if ans=="1":

                #break

           

        self.MaxFitness=0

        i=0

        for Unit in self.Progs:

            if Unit.Fitness>self.MaxFitness:

                best=Unit

                self.MaxFitness=best.Fitness

                best_number=i

            i+=1

        print "The end of all the generations."

        print "The best solution found is Program number: "+str(best_number)

        best.PrintTree()

        print "The fitness value is:",FitnessFunction(best)

        return best

 

 

 

    def CrossOver(self):

        Children=[] #list of children

        totalfitness=0

        for j in range(0,self.Population):

            totalfitness+=self.Progs[j].Fitness

        total_children=int(self.BirthRate*(self.Population/2)) #always an even number

 

        # One loop produces 2 children, therefore half the loops

        for i in range(0,total_children): # Selecting two parents for each child

            normal_children=0

            while not normal_children: #While offsprings are not normal

                accufitness=0

                RandFit=randint(0,totalfitness)

                for j in range(0,self.Population):

                    accufitness+=self.Progs[j].Fitness # Selecting most fit tree as parent, this random method favours more fit trees than lesser ones

 

                    if accufitness>=RandFit:

                        Parent1=loads(dumps(self.Progs[j]))

                        Parent1No=j

                        Parent1Point=randint(1,Parent1.Size())

                        break

 

                RandFit=randint(0,totalfitness)

                accufitness=0

                for j in range(0,self.Population):

                    accufitness+=self.Progs[j].Fitness # Selecting most fit tree as parent, this random method favours more fit trees than lesser ones

 

                    if accufitness>=RandFit:

                        Parent2=loads(dumps(self.Progs[j]))

                        Parent2No=j

                        Parent2Point=randint(1,Parent2.Size())

                        break

 

 

                Child1=Parent1.Tree.GetNode(Parent1Point)

                Child2=Parent2.Tree.GetNode(Parent2Point)

                Parent1.SetNode(Child2,Parent1Point)

                Parent2.SetNode(Child1,Parent2Point)

                Parent1.Tree.ReInit()

                Parent2.Tree.ReInit()

 

                #We check here if the depth of child tree is greater than maxdepth

                # then the child (Parent1) is not fit to live

 

                if (Parent2.Depth()<= self.MaxDepth) and (Parent1.Depth()<= self.MaxDepth):

                    normal_children=1 #Both are normal_children

 

            Children.append(Parent1)

            Children.append(Parent2)

           

        for i in range(0,len(Children)):

            RandFit=randint(0,totalfitness)

            accufitness=0

            for j in range(0,self.Population):

                accufitness+=(self.HighFitness-self.Progs[j].Fitness) #Replacing parent trees with child trees and least fit old trees with parent trees

                if accufitness>=RandFit:

                    self.Progs[j]=loads(dumps(Children[i]))

                    self.Progs[j].Tree.ReInit()

                    break

 

    def Mutation(self):

        individno=randint(0,self.Population-1)

        randpoint=randint(1,self.Progs[individno].Size())

        randProg=self.Progs[individno].RandomTree(self.Progs[individno].Depth()-int(self.Progs[individno].Size()/self.Progs[individno].Depth()))

        self.Progs[individno].SetNode (randpoint,randProg)

        self.Progs[individno].Tree.ReInit()

 

    def RetCopy(self):

        return self

 

   

def ADD(ValuesList):

    sumtotal=0

    for val in ValuesList:

        sumtotal=sumtotal+val

    return sumtotal

 

def SUB(ValuesList):

    return ValuesList[0]-ValuesList[1]

 

def MUL(ValuesList):

    return ValuesList[0]*ValuesList[1]

 

def DIV(ValuesList):

    if ValuesList[1]==0: #This is protected division i.e. if a number is divided by 0 the result is 1

        return 1

    return ValuesList[0]/ValuesList[1]

 

def COS(Value):

    return cos(Value[0])

 

def RANDINT(ValuesList): #return a random integer between ranges a,b

    if ValuesList[1]

        return randint(ValuesList[1],ValuesList[0])

    return randint(ValuesList[0],ValuesList[1])

 

def RANDOM(ValuesList):

    return random()

 

def X(ValuesList):

    return 100

 

def DummyFunc():

    pass

 

# You just need to modify this function to generate trees of your own choice

def FitnessFunction(Prog):

 

    #testing fitness on 10 different X and then averaging the result

   

    fitness=0

    for i in range(1,11):

        x=uniform(-1,1) # returns a random float between -1 to 1

        Prog.Variables.SetVal("X",x) # Set the values of the variables

        retvalue=Prog.EvalTree()

        fitness+=100/(abs(symbolic_regression(x)-retvalue)+1)

    return int(fitness/10)

   

def symbolic_regression(x):

    return(x*x+x+1)

 

 

### Problem Description

# We will try to evolve a tree for Symbolic Regression of a Quadratic Polynomial

# That is the fitness function x^2+x+1 in the range of -1 to 1

 

 

if __name__=="__main__":

    pr=Programs({ADD:2,SUB:2,MUL:2,DIV:2},range(-1,2),["X"],10,50,100)

    # pr=Programs({ADD:2,SUB:2,MUL:2,DIV:2},["random"],["X"],5,100,100)

    pr.MainLoop()

    wait=raw_input("Press any key to terminate....")

 

#### Sample Usage example

# prg = Programs({COS:1,RANDOM:0}, [1,2],["A","B"])

 

#### Syntax of the program

# pr=Programs(FuncDict,TerminalList,Variable,MaxDepth=10,Population=100,MaxGen=100,ReqFitness=99,CrossRate=0.9,MutRate=0.1,BirthRate=0.2,HighFitness=100)

# pr.MainLoop()

 

# pr=Prograns( {function1: no_of_arguments_of_function,...} , [list of leafs or constants], [list of variable names] )

 

### Description of arguments

 

# FuncDictis the dictionary of actual function names and the number of arguments it takes

# TerminalList is the list of terminal constants possible in the tree e.g. [1,2,5,6] or range(5,11) or [1,2,"random"[]

# "random" in the Terminal List produces a number between 0 and 1 and e.g. 0.257522 or 0.444621

# Variable is a list of possible variables in the tree e.g. ["X","Y"] or ["A","B"]

# It is the responsibility of fitness function to supply values to the variables by using syntax:

# Prog.Variables.SetVal(Variable_Name,Variable_Value) e.g Prog.Variables.SetVal("X",10)

# MaxDepth is the maximum depth allowed for the initial trees

# Population is population in each generation. It starts from 0 to 99 i.e If u want 100 individuals then pass 99 as parameter

# MaxGen is the maximum number of generations until the evolution is aborted

# ReqFitness is the fitness level above which if any program is possesing fitness the program is terminated

# In the default case it is 99, i.e if any program has fitness greater than 99, the evolution is aborted and the candidate is termed as best

# CrossRate is the crossover rate, its default value is 0.9 i.e. the crossover is bound to happen 90% of time

# MutRate is the rate of mutation

# BirthRate is the number of new individuals produced per unit of population

# Its default value is 0.2 i.e if the population is 100 then 20 children will be produced per crossover operation

# HighFitness is the highest fitness attainable by the candidate, in default case it is 100

# MaxGen is maximum number of generations

# BirthRate is no of offsprings per 100 population e.g. if BirthRate is 2 and population of current population is 100 then in the next generation only 2 offsprings will be produced

 

#### Sample Usage example

# prg = Programs({COS:1,RANDOM:0}, [1,2],["A","B"])

 

#### To define functions of your own

# The functions used in the trees are real world python functions

# So of you want to add a new function such as power(a,b) i.e to calculate a^b

# use the following synatx

 

def POWER(ValuesList):

    ans=ValuesList[0]

    if ValuesList[1]<0: o:p="">

        return 0

    for i in range(0,ValuesList[1]):

        ans=ans*ValuesList[0]

    return ans

 

# The fuctions which you will define will always contain only one argument which is ValuesList

# ValuesList is the list of values passed to the function

# In the present case of a^b ValuesList will contain values of a and b

# So ValuesList[0] will represent the first value i.e a

# and ValuesList[1] will represent the second value i.e b

 

# If your function takes three values then you will also use ValuesList[2]

# If your function does not takes any values such as RANDOM() then the list will be empty

 

# But observe that only one value can be returned from the function

 

 

### Note

# You may also use this module to create instancesof many GPs running simultaneously

# Or use it to run GP elsewhere in your program

 

Keine Kommentare:

Kommentar veröffentlichen

Hinweis: Nur ein Mitglied dieses Blogs kann Kommentare posten.