Source Code for Module evolver

  1  """ 
  2  evolver 
  3  ======= 
  4  This module contains the methods to start and finish a complete evolutionary run.  
  5  The present version can run strongly-typed  Koza-based GP using tournament 
  6  selection. 
  7   
  8  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
  9  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 10  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
 11  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 12  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
 13  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 
 14  THE SOFTWARE. 
 15   
 16  @author: by Mehdi Khoury 
 17  @version: 1.20 
 18  @copyright: (c) 2009 Mehdi Khoury under the mit license 
 19  http://www.opensource.org/licenses/mit-license.html 
 20  @contact: mehdi.khoury at gmail.com 
 21   
 22  """ 
 23   
 24  import settings 
 25  import timeit 
 26  import selection 
 27  import buildtree 
 28  import cPickle 
 29  import marshal 
 30  import pprint 
 31  #import shelve 
 32  import evalfitness 
 33  from pysqlite2 import dbapi2 as sqlite 
 34  import crossutil 
 35  import math 
 36  import writepop 
 37  import copy 
 38  import mutation 
 39  import psyco 
 40  import crossover 
 41  import os 
 42   
 43  psyco.profile() 
 44  # Exceptions related to operator probability 
 45 -class CrossoverProbError(Exception): pass 
 46 -class MutationProbError(Exception): pass 
 47 -class OperatorProbError(Exception): pass 
 48  # Exceptions related to population size 
 49 -class PopSizeError(Exception): pass 
 50   
 51   
 52 -def EvolutionRun(popsize,root_node,mindepth,maxdepth,buildmethod,max_nb_runs, fitness_criterion ,crossover_prob,mutation_prob,size, prob_selection,dbname,verbose): 
 53      """ 
 54       
 55      Function:  EvolutionRun 
 56      ======================= 
 57      The highest level function of the package.  
 58      It starts an evolutionary run with given parameters,and gives indications of 
 59      what is found after each generation. 
 60      @param popsize: size of the population 
 61      root_node: specify the root node and its arity (nb of children). e.g. (0,2,'root')  
 62      @param mindepth: min tree depth (at the moment only 2 working)  
 63      @param maxdepth: max depth of trees in new generation (should be >=3)  
 64      @param buildmethod: which Koza method is used to build the trees (either  
 65      'AddHalfNode' or 'AddFullNode' or 'AddGrowNodeMin' respectively for  
 66      Ramped Half-n-Half, Full, or Half) 
 67      @param max_nb_runs: the search will gon on until a maximum number of generations 
 68      is reached 
 69      @param fitness_criterion: the search will stop if the fitness found is <= to 
 70      the ideal fitness 
 71      @param crossover_prob: probability of crossover (will determine what proportion of  
 72      the population will be replaced by crossover-generated offsprings)   
 73      @param mutation_prob: probability of crossover (will determine what proportion of  
 74      the population will be replaced by mutation-generated offsprings)   
 75      @param dbname: path to database e.g. r'D:\3d_work\pythongp\pySTGP_0.51\src\pop_db'     
 76      @param verbose: print the best tree of each generation 
 77    
 78      """  
 79      try: 
 80          os.remove(dbname) 
 81      except: 
 82          pass 
 83       
 84      current_best_fitness=float('inf') 
 85      tablenames=[] 
 86      #build the intial population of random trees at generation 0  
 87      tablenames.append('tab0') 
 88      writepop.WriteInitialPopulation2DB(popsize,root_node,mindepth,maxdepth,buildmethod,dbname,tablenames[0]) 
 89      # get best fitness 
 90      db_list=selection.GetDBKeysAndFitness(dbname,tablenames[0]) 
 91      chosen_one=selection.SelectDBOneFittest(db_list) 
 92      current_best_fitness=chosen_one[1] 
 93      print ''.join(['generation 0 (db table name = tab0): -> best fit individual has id:',`chosen_one[0]`,' and fitness:',`current_best_fitness`]) 
 94       
 95      if verbose==True: 
 96          #writepop.GetPopStatFromDB(dbname,tablenames[0]) 
 97          con = sqlite.connect(dbname) 
 98          SELECT = "select tree from %s where o_id=%d" % (tablenames[0],chosen_one[0]) 
 99          cur = con.cursor() 
100          cur.execute(SELECT) 
101          con.commit() 
102          myresult= cur.fetchone() 
103          con.close() 
104          best_tree=copy.deepcopy(marshal.loads(myresult[0])) 
105          print best_tree 
106      if current_best_fitness<=fitness_criterion: 
107          print ''.join(['found solution: generation 0, db_id:',`chosen_one[0]`,' and fitness:',`current_best_fitness`]) 
108      else:     
109          # evolve the population for max_nb_runs 
110          i=1 
111          while i<max_nb_runs and current_best_fitness>fitness_criterion: 
112              tablenames.append(''.join(['tab',`i`])) 
113              TournamentSelectionEvolveDBPopulation2(popsize,maxdepth,crossover_prob,mutation_prob,size, prob_selection,dbname,tablenames[i-1],tablenames[i]) 
114              db_list=selection.GetDBKeysAndFitness(dbname,tablenames[i]) 
115              chosen_one=selection.SelectDBOneFittest(db_list) 
116              current_best_fitness=chosen_one[1] 
117              print ''.join(['generation ',`i`,' (db table name = tab',`i`,'): -> best fit individual has id:',`chosen_one[0]`,' and fitness:',`current_best_fitness`]) 
118               
119              if verbose==True: 
120                  #writepop.GetPopStatFromDB(dbname,tablenames[i]) 
121                  con = sqlite.connect(dbname) 
122                  SELECT = "select tree from %s where o_id=%d" % (tablenames[i],chosen_one[0]) 
123                  cur = con.cursor() 
124                  cur.execute(SELECT) 
125                  con.commit() 
126                  myresult= cur.fetchone() 
127                  con.close() 
128                  best_tree=copy.deepcopy(marshal.loads(myresult[0])) 
129                  print best_tree 
130               
131              i=i+1 
132          else: 
133              if current_best_fitness<=fitness_criterion: 
134                  print ''.join(['found solution at generation ',`i-1`,', with fitness:',`current_best_fitness`]) 
135                  writepop.PrintPopFromDB(dbname,tablenames[i-1],'lastpop') 
136              else: 
137                  print ''.join(['Fitness stopping criterion not found. Run ended at generation ',`i`]) 
138                
139       
140   
141       
142       
143       
144 -def TournamentSelectionEvolveDBPopulation2(popsize,maxdepth,crossover_prob,mutation_prob,size, prob_selection,dbname,tablename,tablename2): 
145      """ 
146      Function:  TournamentSelectionEvolveDBPopulation2 
147      ================================================= 
148      create a new population of randomly generated trees and write this new generation 
149      to a new table of name 'tab'+generation number in the database. 
150    
151      @param popsize: size of the population 
152      @param maxdepth: max depth of trees in new generation  
153      @param crossover_prob: probability of crossover (will determine what proportion of  
154      the population will be replaced by crossover-generated offsprings) 
155      @param mutation_prob: probability of crossover (will determine what proportion of  
156      the population will be replaced by mutation-generated offsprings) 
157      @param dbname: path to database e.g. r'D:\3d_work\pythongp\pySTGP_0.51\src\pop_db' 
158      @param tablename: name of the database table of the initial population 
159      @param tablename2: name of the database table of the next generation 
160    
161      """  
162       
163      if crossover_prob>1 or crossover_prob<0: 
164          raise CrossoverProbError, "Crossover Probability should be in interval [0,1]" 
165          exit 
166      if mutation_prob>1 or mutation_prob<0: 
167          raise MutationProbError, "Crossover Probability should be in interval [0,1]" 
168          exit 
169      reproduction_prob= 1-(crossover_prob+mutation_prob) 
170      if reproduction_prob>1 or reproduction_prob<0: 
171          raise OperatorProbError, "Sum of Mutation and Crossover Probability should be in interval [0,1]" 
172          exit 
173      if popsize<3: 
174          raise PopSizeError, "The size of the population must be at least 3" 
175          exit 
176       
177      new_pop=[] 
178      trees=[] 
179       
180      # build the appropriate size for the crossover offsprings,  
181      # mutation offsprings and reproduction offsprings 
182      crossover_size= math.ceil(popsize*crossover_prob) 
183      mutation_size= math.ceil(popsize*mutation_prob) 
184      reproduction_size= math.ceil(popsize*reproduction_prob) 
185      sizes=[crossover_size,mutation_size,reproduction_size] 
186      theoretical_size=sum(sizes) 
187      if theoretical_size >popsize: 
188          nb=theoretical_size-popsize 
189          if crossover_size>mutation_size and mutation_size>=reproduction_size: 
190              crossover_size=crossover_size-nb 
191          elif mutation_size>crossover_size and crossover_size>=reproduction_size: 
192              mutation_size=crossover_size-nb 
193          elif reproduction_size>crossover_size and crossover_size>=mutation_size: 
194              mutation_size=crossover_size-nb 
195          else: 
196              crossover_size=crossover_size-nb    
197      #print crossover_size 
198      #print mutation_size 
199      #print reproduction_size 
200      # get the ordered list of fitnesses with identifier keys 
201      db_list=selection.GetDBKeysAndFitness(dbname,tablename) 
202      # start by selecting fittest parents for reproduction 
203      reprod=selection.SelectDBSeveralFittest(int(reproduction_size), db_list) 
204      #print reprod 
205      # then select parents for crossover 
206      cross=selection.TournamentSelectDBSeveral(int(crossover_size),size, prob_selection,db_list) 
207      #print cross 
208      # then select parents for mutation 
209      mut=selection.TournamentSelectDBSeveral(int(mutation_size),size, prob_selection,db_list) 
210      #print mut 
211       
212   
213      #open database 
214      con = sqlite.connect(dbname) 
215      #add to new population these reproduced offsprings 
216      #writepop.ClearDBTable(dbname,tablename2) 
217      #con.execute("create table %s(o_id INTEGER PRIMARY KEY,tree TEXT,\ 
218      # tree_mapping TEXT, treedepth INTEGER, evaluated INTEGER, fitness FLOAT)"%tablename2) 
219       
220      # apply reproduction operator and copy to new population database 
221      for elem in reprod: 
222          o_id=elem[0] 
223          #print o_id 
224          SELECT = "select tree, tree_mapping, treedepth, evaluated, fitness from %s where o_id=%d" % (tablename,o_id) 
225          cur = con.cursor() 
226          cur.execute(SELECT) 
227          con.commit() 
228          myresult= cur.fetchone() 
229          my_tree=copy.deepcopy(marshal.loads(myresult[0])) 
230          my_tree_mapping=copy.deepcopy(marshal.loads(myresult[1])) 
231          my_treedepth=myresult[2] 
232          my_evaluated=myresult[3] 
233          my_fitness=myresult[4] 
234          # write a copy of the selected parent in the new database 
235          new_pop.append((o_id,my_tree, my_tree_mapping,my_treedepth,my_evaluated,my_fitness)) 
236          trees.append(my_tree) 
237          #con.execute("insert into %s(o_id,tree,tree_mapping,treedepth,evaluated,fitness) values (NULL,?,?,?,?,?)"%tablename2,(buffer(marshal.dumps(myresult[0],-1)),buffer(marshal.dumps(myresult[1],-1)),my_treedepth,my_evaluated,my_fitness)) 
238          con.commit() 
239      # apply mutation operator and copy to new population database   
240      for elem in mut: 
241          o_id=elem[0] 
242          #print o_id 
243          SELECT = "select tree, tree_mapping, treedepth, evaluated, fitness from %s where o_id=%d" % (tablename,o_id) 
244          cur = con.cursor() 
245          cur.execute(SELECT) 
246          con.commit() 
247          myresult= cur.fetchone() 
248          my_tree=copy.deepcopy(marshal.loads(myresult[0])) 
249          my_tree_mapping=copy.deepcopy(marshal.loads(myresult[1])) 
250          my_treedepth=myresult[2] 
251          my_evaluated=myresult[3] 
252          my_fitness=myresult[4] 
253          same_tree=True 
254          mt=mutation.Mutate(maxdepth,my_tree,my_tree_mapping,my_treedepth) 
255          same_tree=mt[0] 
256          if mt in trees: 
257              same_tree=True 
258          # make sure to try another mutation if the offspring is identical to the parent 
259          if same_tree==True: 
260              while same_tree==True: 
261                  mt=mutation.Mutate(maxdepth,my_tree,my_tree_mapping,my_treedepth) 
262                  same_tree=mt[0] 
263          mt_map=crossutil.GetIndicesMappingFromTree(mt[1]) 
264          mt_depth=crossutil.GetDepthFromIndicesMapping(mt_map) 
265          mt_evaluated=1 
266          # get fitness of the tree 
267          result_fitness=settings.FitnessFunction(mt[1]) 
268          #mt_fitness=evalfitness.EvalTreeForAllInputSets(mt[1],xrange(settings.nb_eval)) 
269          #mt_fitness=evalfitness.EvalTreeForOneListInputSet(mt[1]) 
270          #result_fitness=evalfitness.FinalFitness(mt_fitness) 
271          #result_fitness=evalfitness.FinalFitness2(mt_fitness) 
272          #result_fitness=evalfitness.FinalFitness3(mt_fitness) 
273          #result_fitness=evalfitness.FinalFitness4(mt_fitness) 
274          #print result_fitness 
275          # write a copy of the selected parent in the new database 
276          new_pop.append((o_id,mt[1], mt_map,mt_depth,mt_evaluated,result_fitness)) 
277          #con.execute("insert into %s(o_id,tree,tree_mapping,treedepth,evaluated,fitness) values (NULL,?,?,?,?,?)"%tablename2,(buffer(marshal.dumps(mt[1],-1)),buffer(marshal.dumps(mt_map,-1)),mt_depth,mt_evaluated,result_fitness)) 
278          con.commit() 
279         
280      # apply crossover operator and copy to new population database   
281      for elem in cross: 
282          # select the second parent using tournament selection 
283          parent2=selection.TournamentSelectDBSeveral(2,7, 0.8,db_list) 
284          # make sure parent2 is different from parent1 
285          if elem==parent2[0]: 
286              elem2=parent2[1] 
287          else: 
288              elem2=parent2[0] 
289           
290              
291          o_id=elem[0] 
292          o_id2=elem2[0] 
293          #print o_id 
294          #print o_id2 
295          cur = con.cursor() 
296          SELECT1 = "select tree, tree_mapping, treedepth, evaluated, fitness from %s where o_id=%d" % (tablename,o_id)  
297          cur.execute(SELECT1) 
298          con.commit() 
299          myresult1= cur.fetchone() 
300          SELECT2 = "select tree, tree_mapping, treedepth, evaluated, fitness from %s where o_id=%d" % (tablename,o_id2) 
301          cur.execute(SELECT2) 
302          con.commit() 
303          myresult2= cur.fetchone() 
304           
305          my_tree1=copy.deepcopy(marshal.loads(myresult1[0])) 
306          my_tree1_mapping=copy.deepcopy(marshal.loads(myresult1[1])) 
307          my_tree1depth=myresult1[2] 
308          my_evaluated1=myresult1[3] 
309          my_fitness1=myresult1[4] 
310           
311          my_tree2=copy.deepcopy(marshal.loads(myresult2[0])) 
312          my_tree2_mapping=copy.deepcopy(marshal.loads(myresult2[1])) 
313          my_tree2depth=myresult2[2] 
314          my_evaluated2=myresult2[3] 
315          my_fitness2=myresult2[4] 
316          #cs=crossover.Koza1PointCrossover(maxdepth,my_tree1,my_tree2,my_tree1_mapping,my_tree2_mapping,my_tree1depth,my_tree2depth) 
317          #print cs 
318          #cs=mutation.Mutate(maxdepth,my_tree,my_tree_mapping,my_treedepth) 
319           
320           
321           
322          cs_evaluated=1 
323          # get fitness of the tree 
324          input_sets=xrange(settings.nb_eval) 
325          cs=[[0,0,0,0]] 
326          i=0 
327          while cs[0]!=[1,1,1,1] and i<100 : 
328              #cp_my_tree1=copy.deepcopy(marshal.loads(myresult1[0])) 
329              #cp_my_tree1_mapping=copy.deepcopy(marshal.loads(myresult1[1])) 
330              #cp_my_tree2=copy.deepcopy(marshal.loads(myresult2[0])) 
331              #cp_my_tree2_mapping=copy.deepcopy(marshal.loads(myresult2[1])) 
332              cp_my_tree1=marshal.loads(myresult1[0]) 
333              cp_my_tree1_mapping=marshal.loads(myresult1[1]) 
334              cp_my_tree2=marshal.loads(myresult2[0]) 
335              cp_my_tree2_mapping=marshal.loads(myresult2[1]) 
336              cs=crossover.Koza1PointCrossover(maxdepth,cp_my_tree1,cp_my_tree2,cp_my_tree1_mapping,cp_my_tree2_mapping,my_tree1depth,my_tree2depth) 
337              #trees.append(cs[1]) 
338              #trees.append(cs[2]) 
339              i=i+1 
340          #print cs[1] 
341          #print cs[2] 
342           
343          # if after trying 50 times , the crossover cannot give a correct offspring, then  
344          # create a new offspring using mutation... 
345          if cs[0]!=[1,1,1,1] and settings.Substitute_Mutation==1: 
346              mt=mutation.Mutate(maxdepth,cp_my_tree1,cp_my_tree1_mapping,my_tree1depth) 
347              mt_map=crossutil.GetIndicesMappingFromTree(mt[1]) 
348              mt_depth=crossutil.GetDepthFromIndicesMapping(mt_map) 
349              mt_evaluated=1 
350              # get fitness of the tree 
351              result_fitness=settings.FitnessFunction(mt[1]) 
352              new_pop.append((o_id,mt[1], mt_map,mt_depth,mt_evaluated,result_fitness)) 
353          else: 
354               
355              try: 
356                  offspring1_result_fitness=settings.FitnessFunction(cs[1]) 
357                   
358                  #cs_offspring1_fitness=evalfitness.EvalTreeForAllInputSets(cs[1],input_sets) 
359                  #cs_offspring1_fitness=evalfitness.EvalTreeForOneListInputSet(cs[1]) 
360              except: 
361                  print 'pb when applying fitness function to results of crossover' 
362                  print cs[1] 
363                   
364                  print cs[0] 
365              try: 
366                   
367                  offspring2_result_fitness=settings.FitnessFunction(cs[2]) 
368                  #cs_offspring1_fitness=evalfitness.EvalTreeForAllInputSets(cs[1],input_sets) 
369                  #cs_offspring1_fitness=evalfitness.EvalTreeForOneListInputSet(cs[1]) 
370              except: 
371                  print 'pb when applying fitness function to results of crossover' 
372                   
373                  print cs[2] 
374                  print cs[0] 
375              #try: 
376              #    cs_offspring2_fitness=evalfitness.EvalTreeForAllInputSets(cs[2],input_sets) 
377                  #cs_offspring2_fitness=evalfitness.EvalTreeForOneListInputSet(cs[2]) 
378              #except: 
379              #    print cs[2] 
380              #    print cs[0] 
381              #offspring1_result_fitness=evalfitness.FinalFitness(cs_offspring1_fitness) 
382              #offspring2_result_fitness=evalfitness.FinalFitness(cs_offspring2_fitness) 
383              #offspring1_result_fitness=evalfitness.FinalFitness2(cs_offspring1_fitness) 
384              #offspring2_result_fitness=evalfitness.FinalFitness2(cs_offspring2_fitness) 
385              #offspring1_result_fitness=evalfitness.FinalFitness3(cs_offspring1_fitness) 
386              #offspring2_result_fitness=evalfitness.FinalFitness3(cs_offspring2_fitness) 
387              #offspring1_result_fitness=evalfitness.FinalFitness4(cs_offspring1_fitness) 
388              #offspring2_result_fitness=evalfitness.FinalFitness4(cs_offspring2_fitness) 
389              #print result_fitness 
390              # write a copy of the selected parent in the new database 
391              if offspring1_result_fitness>=offspring2_result_fitness: 
392                  cs_map=crossutil.GetIndicesMappingFromTree(cs[1]) 
393                  cs_depth=crossutil.GetDepthFromIndicesMapping(cs_map) 
394                  #con.execute("insert into %s(o_id,tree,tree_mapping,treedepth,evaluated,fitness) values (NULL,?,?,?,?,?)"%tablename2,(buffer(marshal.dumps(cs[1],-1)),buffer(marshal.dumps(cs_map,-1)),cs_depth,cs_evaluated,offspring1_result_fitness)) 
395                  new_pop.append((o_id,cs[1], cs_map,cs_depth,cs_evaluated,offspring1_result_fitness)) 
396                  #trees.append(cs[1]) 
397              if offspring1_result_fitness<offspring2_result_fitness: 
398                  cs_map=crossutil.GetIndicesMappingFromTree(cs[2]) 
399                  cs_depth=crossutil.GetDepthFromIndicesMapping(cs_map) 
400                  #con.execute("insert into %s(o_id,tree,tree_mapping,treedepth,evaluated,fitness) values (NULL,?,?,?,?,?)"%tablename2,(buffer(marshal.dumps(cs[2],-1)),buffer(marshal.dumps(cs_map,-1)),cs_depth,cs_evaluated,offspring2_result_fitness)) 
401                  new_pop.append((o_id,cs[2], cs_map,cs_depth,cs_evaluated,offspring2_result_fitness)) 
402              #trees.append(cs[2]) 
403          con.commit()      
404      con.close() 
405       
406      con = sqlite.connect(dbname) 
407      #writepop.ClearDBTable(dbname,tablename2) 
408      con.execute("create table %s(o_id INTEGER PRIMARY KEY,tree TEXT,\ 
409       tree_mapping TEXT, treedepth INTEGER, evaluated INTEGER, fitness FLOAT)"%tablename2) 
410      #print len(new_pop) 
411      for i in xrange(0,popsize): 
412          con.execute("insert into %s(o_id,tree,tree_mapping,treedepth,evaluated,fitness) values (NULL,?,?,?,?,?)"%tablename2,(buffer(marshal.dumps(new_pop[i][1],-1)),buffer(marshal.dumps(new_pop[i][2],-1)),new_pop[i][3],new_pop[i][4],new_pop[i][5])) 
413      con.commit() 
414      con.close() 
415       
416       
417       
418       
419   
420       
421  if __name__ == '__main__': 
422      #dbname=r'D:\3d_work\pythongp\pySTEP_0.95\src\pop_db' 
423      dbname=r'D:\mehdi\python projects\pySTEP_0.95\src\pop_db' 
424      #tablename='tab8'     
425      #tablename2='tab9' 
426      #db_list=selection.GetDBKeysAndFitness(dbname,tablename) 
427      #TournamentSelectionEvolveDBPopulation(100,8,0.9,0.05,dbname,tablename,tablename2) 
428      #(popsize,maxdepth,crossover_prob,mutation_prob,dbname,tablename,tablename2) 
429      #t2 = timeit.Timer('new_generation=evolver.TournamentSelectionEvolveDBPopulation2(6000,10,0.9,0.05,dbname,tablename,tablename2)',  'from __main__ import dbname, tablename, db_list,tablename2 ;import evolver') 
430      #print t2.repeat(1,1) 
431       
432       
433      #EvolutionRun(2000,(0,2,'root'),2,6,'AddHalfNode',100, 0.1 ,0.5,0.49,dbname,True) 
434      EvolutionRun(2000,(0,3,'root'),2,6,'AddHalfNode',100, 0.1 ,0.5,0.49,7,0.8,dbname,True) 
435