Public Pastes
Guest

Untitled

By: a guest on Feb 11th, 2012  |  syntax: None  |  size: 16.96 KB  |  hits: 48  |  expires: Never
download  |  raw  |  embed  |  report abuse
Copied
  1. ### Genetic Programming System
  2. ### By Paras Chopra
  3. ### http://www.paraschopra.com
  4. ### email: paras1987 [at] gmail [dot] com
  5. ### email: paraschopra [at] paraschopra [dot] com
  6.  
  7. ## Note: You may use this Genetic Programming module in any way you wish
  8. ## But please do not forget to give me the credit which I deserve
  9.  
  10.  
  11. from random import *
  12. from math import *
  13. from pickle import *
  14. #Global
  15.  
  16.  
  17. class Variables:
  18.     def __init__(self,VarList=[]):
  19.         self.VarDict={}
  20.         for variable in VarList:
  21.             self.VarDict[variable]=0 #initially alot each variable a zero value
  22.        
  23.     def GetVal(self,var):
  24.        
  25.         if type(var)==type("String"):
  26.            
  27.             if self.VarDict.has_key(var):    
  28.                 return self.VarDict[var]
  29.             else:
  30.                 return 0
  31.         else:
  32.             return var
  33.     def SetVal(self,var,val):
  34.         if self.VarDict.has_key(var):
  35.             self.VarDict[var]=val
  36.            
  37.  
  38.     def __len__(self):
  39.         return len(self.VarDict)
  40.  
  41.     def keys(self):
  42.         return self.VarDict.keys()
  43.  
  44. # NodeTypes
  45. # LF:Leaf e.g constant or a varibele i.e it comprises of CS and VR
  46. # CS:Constant e.g 1,2,3 etc. ,
  47. # VR: variables A,B,C ,etc. and
  48. # FN: Function eg. ADD, SUB, etc.
  49.  
  50. class Node:
  51.     NodeTypes = {"FN":0,"LF":1,"CS":2, "VR":3}
  52.  
  53.     def __init__(self,Value=None,Nodes=[],Type="FN",FuncName=None,Variables=None):
  54.         if Value=="random":
  55.             self.Value=random()
  56.         else:
  57.             self.Value=Value
  58.         self.Nodes=Nodes
  59.         self.NodeValues=[]
  60.         self.Type=self.NodeTypes[Type]
  61.         self.FuncName=FuncName
  62.         self.Variables=Variables
  63.         self.Size=1
  64.         self.Depth=1
  65.         self.NodeId=1
  66.        
  67.     def GetNode(self,nodeno):
  68.         self.SetNodeId()
  69.         RetVal=self.GetNodeTemp(nodeno)
  70.         return RetVal
  71.  
  72.     def SetNodeId(self,curnumber=1):
  73.         self.NodeId=curnumber
  74.         if self.Nodes:
  75.             for i in range(0,len(self.Nodes)):
  76.                 curnumber=self.Nodes[i].SetNodeId(curnumber+1)
  77.         return curnumber
  78.  
  79.     def GetNodeTemp(self,nodeno):
  80.         if nodeno==self.NodeId:
  81.             return self
  82.         if self.Nodes:
  83.             for i in range(0,len(self.Nodes)):
  84.                 if self.Nodes[i].GetNodeTemp(nodeno)!=None:
  85.                     return self.Nodes[i].GetNodeTemp(nodeno)
  86.            
  87.         return None
  88.  
  89.     def SetNode(self,nodeno,CopyNode):
  90.         if nodeno==self.NodeId:
  91.             self=CopyNode
  92.             return 1
  93.         if self.Nodes:
  94.             for i in range(0,len(self.Nodes)):
  95.                 reval=self.Nodes[i].SetNode(nodeno,CopyNode)
  96.                 if reval==1:
  97.                     self.Nodes[i]=CopyNode
  98.  
  99.         return None
  100.  
  101.     def RecalSize(self):
  102.         self.Size=1
  103.         if self.Nodes:
  104.             for Unit in self.Nodes:
  105.                 self.Size+=Unit.RecalSize()
  106.         return self.Size
  107.  
  108.     def ReInit(self):
  109.         self.SetNodeId()
  110.         self.ReCalculate()
  111.        
  112.     def ReCalculate(self):
  113.         self.Size=1
  114.         self.Depth=1
  115.         largest_depth=1
  116.         if self.Nodes:
  117.             for Unit in self.Nodes:
  118.                 Unit.ReCalculate()
  119.                 if Unit.Depth > largest_depth:
  120.                     largest_depth=Unit.Depth
  121.                 self.Size+=Unit.Size
  122.             self.Depth+=largest_depth
  123.    
  124.     def Eval(self):
  125.         self.NodeValues[:]=[]
  126.         if self.Type==self.NodeTypes["VR"]:
  127.             return self.Variables.GetVal(self.Value)
  128.         elif self.Type== self.NodeTypes["CS"]:
  129.             return self.Value
  130.         else:
  131.             for Unit in self.Nodes:
  132.                     self.NodeValues.append(Unit.Eval())
  133.             return self.FuncName(self.NodeValues)
  134.  
  135.     def PrintTree(self):
  136.         self.DrawTree(1)
  137.  
  138.     def DrawTree(self,level):
  139.         kIndentText = "|  "
  140.         IndentText=""
  141.         for n in range(1,level):
  142.             IndentText = IndentText+kIndentText
  143.         self.NodeValues[:]=[]
  144.         if self.Type==self.NodeTypes["VR"]:
  145.             print IndentText+"+--["+self.Value+"]"
  146.         elif self.Type==self.NodeTypes["CS"]:
  147.             print IndentText+"+--["+str(self.Value)+"]"
  148.         else:
  149.             print IndentText+"+--"+self.FuncName.__name__
  150.             for i in range(0,len(self.Nodes)):
  151.                 self.Nodes[i].DrawTree(level+1)
  152.            
  153.        
  154. class Program:
  155.     NodeTypes = {"FN":0,"LF":1,"CS":2, "VR":3}
  156.  
  157.     def RandomTree(self,depth):
  158.         if depth==1:
  159.             NodeUse=self.NodeTypes["FN"]
  160.         elif depth==self.MaxDepth:
  161.             NodeUse=self.NodeTypes["LF"]
  162.         else:
  163.             NodeUse=randint(0,1)
  164.         if NodeUse==self.NodeTypes["FN"]:
  165.             childFuncList=[]
  166.             FuncToUse=randint(0,len(self.FuncDict)-1)
  167.  
  168.             for i in range(0,self.FuncDict.values()[FuncToUse]):
  169.                 child=self.RandomTree(depth+1)
  170.                 if not child:
  171.                     print "Error: Child is nonetype"
  172.                     break
  173.                 childFuncList.append(child)
  174.             return Node(None,childFuncList,"FN",self.FuncDict.keys()[FuncToUse],self.Variables)
  175.         else:
  176.             #there is 50/50 chance that leaf would be variable or constant
  177.             if randint(0,1)==0:
  178.                 #leaf would be constant
  179.                 TermToUse=randint(0,len(self.TerminalList)-1)
  180.                 return Node(self.TerminalList[TermToUse],None,"CS",None,self.Variables)
  181.             else:
  182.                 #leaf would be a variable
  183.                 VarToUse=randint(0,len(self.Variables)-1)
  184.                 return Node(self.Variables.VarDict.keys()[VarToUse],None,"VR",None,self.Variables)
  185.            
  186.  
  187.     def __init__(self,FuncDict,TerminalList,Variable=[],MaxDepth=10):
  188.         self.MaxDepth=MaxDepth
  189.         self.FuncDict=FuncDict
  190.         self.TerminalList=TerminalList
  191.         self.Fitness=0
  192.         self.Variables=Variables(Variable)
  193.         self.Tree=self.RandomTree(1)
  194.         self.Tree.ReInit()
  195.        
  196.     def EvalTree(self):
  197.         return self.Tree.Eval()
  198.  
  199.     def PrintTree(self):
  200.         self.Tree.PrintTree()
  201.  
  202.     def Depth(self):
  203.         return self.Tree.Depth
  204.  
  205.     def Size(self):
  206.         return self.Tree.Size
  207.  
  208.     def AssignFitness(self,Fitness):
  209.         self.Fitness=Fitness
  210.  
  211.     def GetNode(self,nodeno):
  212.         return self.Tree.GetNode(nodeno)
  213.  
  214.     def SetNode(self,CopyNode,NodeNo):
  215.         self.Tree.SetNode(NodeNo,CopyNode)
  216.  
  217.     def RetCopy(self):
  218.         return self
  219.  
  220. class Programs:
  221.  
  222.     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):
  223.         self.Progs=[]
  224.         self.MaxGen=MaxGen
  225.         self.Population=Population
  226.         self.ReqFitness=ReqFitness
  227.         self.CrossRate=CrossRate
  228.         self.MutRate=MutRate
  229.         self.MaxFitness=0
  230.         self.MaxFitnessProg=None
  231.         self.BirthRate=BirthRate
  232.         self.HighFitness=HighFitness
  233.         self.MaxDepth=MaxDepth
  234.         for i in range(0,Population):
  235.             self.Progs.append(Program(FuncDict,TerminalList,Variable,MaxDepth))
  236.  
  237.     def MainLoop(self):
  238.         for i in range(0,1+self.MaxGen):
  239.             print "Generation no:",i
  240.             for j in range(0,self.Population):
  241.                 CurFitness=FitnessFunction(self.Progs[j])
  242.                 self.Progs[j].AssignFitness(CurFitness)
  243.                 if CurFitness>self.MaxFitness:
  244.                     self.MaxFitness=CurFitness
  245.                     self.MaxFitnessProg=self.Progs[j]
  246.                 if self.MaxFitness>=self.ReqFitness:
  247.                     print "Solution found."
  248.                     self.Progs[j].PrintTree()
  249.                     print "The fitness value is:",FitnessFunction(self.Progs[j])
  250.                     return self.Progs[j]
  251.             if random()>=(1-self.CrossRate):
  252.                 self.CrossOver()
  253.                 pass
  254.             if random()>=(1-self.MutRate):
  255.                 self.Mutation()
  256.                 pass
  257.             ### If you want confirmation to continue after each generation uncomment the following
  258.  
  259.             #ans=raw_input("Do you wanna quit? (1==Yes,0==No)")
  260.             #print ans,":",type(ans)
  261.             #if ans=="1":
  262.                 #break
  263.            
  264.         self.MaxFitness=0
  265.         i=0
  266.         for Unit in self.Progs:
  267.             if Unit.Fitness>self.MaxFitness:
  268.                 best=Unit
  269.                 self.MaxFitness=best.Fitness
  270.                 best_number=i
  271.             i+=1
  272.         print "The end of all the generations."
  273.         print "The best solution found is Program number: "+str(best_number)
  274.         best.PrintTree()
  275.         print "The fitness value is:",FitnessFunction(best)
  276.         return best
  277.  
  278.  
  279.  
  280.     def CrossOver(self):
  281.         Children=[] #list of children
  282.         totalfitness=0
  283.         for j in range(0,self.Population):
  284.             totalfitness+=self.Progs[j].Fitness
  285.         total_children=int(self.BirthRate*(self.Population/2)) #always an even number
  286.  
  287.         # One loop produces 2 children, therefore half the loops
  288.         for i in range(0,total_children): # Selecting two parents for each child
  289.             normal_children=0
  290.             while not normal_children: #While offsprings are not normal
  291.                 accufitness=0
  292.                 RandFit=randint(0,totalfitness)
  293.                 for j in range(0,self.Population):
  294.                     accufitness+=self.Progs[j].Fitness # Selecting most fit tree as parent, this random method favours more fit trees than lesser ones
  295.  
  296.                     if accufitness>=RandFit:
  297.                         Parent1=loads(dumps(self.Progs[j]))
  298.                         Parent1No=j
  299.                         Parent1Point=randint(1,Parent1.Size())
  300.                         break
  301.  
  302.                 RandFit=randint(0,totalfitness)
  303.                 accufitness=0
  304.                 for j in range(0,self.Population):
  305.                     accufitness+=self.Progs[j].Fitness # Selecting most fit tree as parent, this random method favours more fit trees than lesser ones
  306.  
  307.                     if accufitness>=RandFit:
  308.                         Parent2=loads(dumps(self.Progs[j]))
  309.                         Parent2No=j
  310.                         Parent2Point=randint(1,Parent2.Size())
  311.                         break
  312.  
  313.  
  314.                 Child1=Parent1.Tree.GetNode(Parent1Point)
  315.                 Child2=Parent2.Tree.GetNode(Parent2Point)
  316.                 Parent1.SetNode(Child2,Parent1Point)
  317.                 Parent2.SetNode(Child1,Parent2Point)
  318.                 Parent1.Tree.ReInit()
  319.                 Parent2.Tree.ReInit()
  320.  
  321.                 #We check here if the depth of child tree is greater than maxdepth
  322.                 # then the child (Parent1) is not fit to live
  323.  
  324.                 if (Parent2.Depth()<= self.MaxDepth) and (Parent1.Depth()<= self.MaxDepth):
  325.                     normal_children=1 #Both are normal_children
  326.  
  327.             Children.append(Parent1)
  328.             Children.append(Parent2)
  329.            
  330.         for i in range(0,len(Children)):
  331.             RandFit=randint(0,totalfitness)
  332.             accufitness=0
  333.             for j in range(0,self.Population):
  334.                 accufitness+=(self.HighFitness-self.Progs[j].Fitness) #Replacing parent trees with child trees and least fit old trees with parent trees
  335.                 if accufitness>=RandFit:
  336.                     self.Progs[j]=loads(dumps(Children[i]))
  337.                     self.Progs[j].Tree.ReInit()
  338.                     break
  339.  
  340.     def Mutation(self):
  341.         individno=randint(0,self.Population-1)
  342.         randpoint=randint(1,self.Progs[individno].Size())
  343.         randProg=self.Progs[individno].RandomTree(self.Progs[individno].Depth()-int(self.Progs[individno].Size()/self.Progs[individno].Depth()))
  344.         self.Progs[individno].SetNode (randpoint,randProg)
  345.         self.Progs[individno].Tree.ReInit()
  346.  
  347.     def RetCopy(self):
  348.         return self
  349.  
  350.    
  351. def ADD(ValuesList):
  352.     sumtotal=0
  353.     for val in ValuesList:
  354.         sumtotal=sumtotal+val
  355.     return sumtotal
  356.  
  357. def SUB(ValuesList):
  358.     return ValuesList[0]-ValuesList[1]
  359.  
  360. def MUL(ValuesList):
  361.     return ValuesList[0]*ValuesList[1]
  362.  
  363. def DIV(ValuesList):
  364.     if ValuesList[1]==0: #This is protected division i.e. if a number is divided by 0 the result is 1
  365.         return 1
  366.     return ValuesList[0]/ValuesList[1]
  367.  
  368. def COS(Value):
  369.     return cos(Value[0])
  370.  
  371. def RANDINT(ValuesList): #return a random integer between ranges a,b
  372.     if ValuesList[1]<ValuesList[0]:
  373.         return randint(ValuesList[1],ValuesList[0])
  374.     return randint(ValuesList[0],ValuesList[1])
  375.  
  376. def RANDOM(ValuesList):
  377.     return random()
  378.  
  379. def X(ValuesList):
  380.     return 100
  381.  
  382. def DummyFunc():
  383.     pass
  384.  
  385. # You just need to modify this function to generate trees of your own choice
  386. def FitnessFunction(Prog):
  387.  
  388.     #testing fitness on 10 different X and then averaging the result
  389.    
  390.     fitness=0
  391.     for i in range(1,11):
  392.         x=uniform(-1,1) # returns a random float between -1 to 1
  393.         Prog.Variables.SetVal("X",x) # Set the values of the variables
  394.         retvalue=Prog.EvalTree()
  395.         fitness+=100/(abs(symbolic_regression(x)-retvalue)+1)
  396.     return int(fitness/10)
  397.    
  398. def symbolic_regression(x):
  399.     return(x*x+x+1)
  400.  
  401.  
  402. ### Problem Description
  403. # We will try to evolve a tree for Symbolic Regression of a Quadratic Polynomial
  404. # That is the fitness function x^2+x+1 in the range of -1 to 1
  405.  
  406.  
  407. if __name__=="__main__":
  408.     pr=Programs({ADD:2,SUB:2,MUL:2,DIV:2},range(-1,2),["X"],10,50,100)
  409.     # pr=Programs({ADD:2,SUB:2,MUL:2,DIV:2},["random"],["X"],5,100,100)
  410.     pr.MainLoop()
  411.     wait=raw_input("Press any key to terminate....")
  412.  
  413. #### Sample Usage example
  414. # prg = Programs({COS:1,RANDOM:0}, [1,2],["A","B"])
  415.  
  416. #### Syntax of the program
  417. # pr=Programs(FuncDict,TerminalList,Variable,MaxDepth=10,Population=100,MaxGen=100,ReqFitness=99,CrossRate=0.9,MutRate=0.1,BirthRate=0.2,HighFitness=100)
  418. # pr.MainLoop()
  419.  
  420. # pr=Prograns( {function1: no_of_arguments_of_function,...} , [list of leafs or constants], [list of variable names] )
  421.  
  422. ### Description of arguments
  423.  
  424. # FuncDictis the dictionary of actual function names and the number of arguments it takes
  425. # 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"[]
  426. # "random" in the Terminal List produces a number between 0 and 1 and e.g. 0.257522 or 0.444621
  427. # Variable is a list of possible variables in the tree e.g. ["X","Y"] or ["A","B"]
  428. # It is the responsibility of fitness function to supply values to the variables by using syntax:
  429. # Prog.Variables.SetVal(Variable_Name,Variable_Value) e.g Prog.Variables.SetVal("X",10)
  430. # MaxDepth is the maximum depth allowed for the initial trees
  431. # Population is population in each generation. It starts from 0 to 99 i.e If u want 100 individuals then pass 99 as parameter
  432. # MaxGen is the maximum number of generations until the evolution is aborted
  433. # ReqFitness is the fitness level above which if any program is possesing fitness the program is terminated
  434. # 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
  435. # CrossRate is the crossover rate, its default value is 0.9 i.e. the crossover is bound to happen 90% of time
  436. # MutRate is the rate of mutation
  437. # BirthRate is the number of new individuals produced per unit of population
  438. # Its default value is 0.2 i.e if the population is 100 then 20 children will be produced per crossover operation
  439. # HighFitness is the highest fitness attainable by the candidate, in default case it is 100
  440. # MaxGen is maximum number of generations
  441. # 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
  442.  
  443. #### Sample Usage example
  444. # prg = Programs({COS:1,RANDOM:0}, [1,2],["A","B"])
  445.  
  446. #### To define functions of your own
  447. # The functions used in the trees are real world python functions
  448. # So of you want to add a new function such as power(a,b) i.e to calculate a^b
  449. # use the following synatx
  450.  
  451. def POWER(ValuesList):
  452.     ans=ValuesList[0]
  453.     if ValuesList[1]<0:
  454.         return 0
  455.     for i in range(0,ValuesList[1]):
  456.         ans=ans*ValuesList[0]
  457.     return ans
  458.  
  459. # The fuctions which you will define will always contain only one argument which is ValuesList
  460. # ValuesList is the list of values passed to the function
  461. # In the present case of a^b ValuesList will contain values of a and b
  462. # So ValuesList[0] will represent the first value i.e a
  463. # and ValuesList[1] will represent the second value i.e b
  464.  
  465. # If your function takes three values then you will also use ValuesList[2]
  466. # If your function does not takes any values such as RANDOM() then the list will be empty
  467.  
  468. # But observe that only one value can be returned from the function
  469.  
  470.  
  471. ### Note
  472. # You may also use this module to create instancesof many GPs running simultaneously
  473. # Or use it to run GP elsewhere in your program
create a new version of this paste RAW Paste Data