Package Bio :: Package GA :: Package Crossover :: Module GeneralPoint
[hide private]
[frames] | no frames]

Source Code for Module Bio.GA.Crossover.GeneralPoint

  1  """ 
  2  Generalized N-Point Crossover. 
  3   
  4  For even values of N, perform N point crossover  
  5    (select N/2 points each in the two genomes, and alternate) 
  6  For odd values of N, perform symmetric N+1 point crossover 
  7    (select N/2 points for both genomes) 
  8     
  9  N-Point introduction (my notation): 
 10      genome 1:    A-----B-----C-----D-----E-----F-----G 
 11      genome 2:    a=====b=====c=====d=====e=====f=====g 
 12       
 13      2-point, symmetric (points=1): 
 14                   A-----B-----C- 1 -D-----E-----F-----G 
 15                   a=====b=====c= 2 =d=====e=====f=====g 
 16      returns: (ABCdefg, abcDEFG) 
 17   
 18      2-point, asymmetric (points=2): 
 19                   A-----B- 1 -C-----D-----E-----F-----G 
 20                   a=====b=====c=====d=====e= 2 =f=====g 
 21      returns: (ABfg, abcdeCDEFG) 
 22   
 23  and for the drastic (n can be arbitrary to the length of the genome!): 
 24      12-point, symmetric (points=11): 
 25                   A- 1 -B- 2 -C- 3 -D- 4 -E- 5 -F- 6 -G 
 26                   a= 7 =b= 8 =c= 9 =d= 10 e= 11 f= 12 g 
 27      returns: (AbCdEfG, aBcDeFg) 
 28      (note that points=12 will yield the same result, but 11 
 29       may be somewhat faster) 
 30           
 31  """ 
 32  # standard modules 
 33  import random 
 34   
35 -class GeneralPointCrossover:
36 """Perform n-point crossover between genomes at some defined rates. 37 38 Ideas on how to use this class: 39 - Call it directly ( construct, do_crossover ) 40 - Use one of the provided subclasses 41 - Inherit from it: 42 * replace _generate_locs with a more domain 43 specific technique 44 * replace _crossover with a more efficient 45 technique for your point-count 46 """
47 - def __init__(self, points, crossover_prob = .1):
48 """Initialize to do crossovers at the specified probability. 49 """ 50 self._crossover_prob = crossover_prob 51 52 self._sym = points % 2 # odd n, gets a symmetry flag 53 self._npoints = (points + self._sym)//2 # (N or N+1)//2
54
55 - def do_crossover(self, org_1, org_2):
56 """Potentially do a crossover between the two organisms. 57 """ 58 new_org = ( org_1.copy(), org_2.copy() ) 59 60 # determine if we have a crossover 61 crossover_chance = random.random() 62 if crossover_chance <= self._crossover_prob: 63 64 # pre-compute bounds (len(genome)) 65 bound = (len(new_org[0].genome), len(new_org[1].genome)) 66 67 mbound = min(bound) 68 # can't have more than 0,x_0...x_n,bound locations 69 if (self._npoints == 0 or self._npoints > mbound-2): 70 self._npoints = mbound-2 71 72 y_locs = [] 73 # generate list for the shortest of the genomes 74 x_locs = self._generate_locs( mbound ) 75 76 if (self._sym != 0): 77 y_locs = x_locs 78 else: 79 # figure out which list we've generated 80 # for, and generate the other 81 if (mbound == bound[0]): 82 y_locs = self._generate_locs( bound[1] ) 83 else: 84 y_locs = x_locs 85 xlocs = self._generate_locs( bound[0] ) 86 87 # copy new genome strings over 88 tmp = self._crossover(0, new_org, (x_locs,y_locs)) 89 new_org[1].genome = self._crossover(1, new_org, (x_locs,y_locs)) 90 new_org[0].genome = tmp 91 92 return new_org
93
94 - def _generate_locs(self, bound):
95 """Generalized Location Generator: 96 97 arguments: 98 bound (int) - upper bound 99 100 returns: [0]+x_0...x_n+[bound] 101 where n=self._npoints-1 102 and 0 < x_0 < x_1 ... < bound 103 """ 104 results = [] 105 for increment in range(self._npoints): 106 x = random.randint(1,bound-1) 107 while (x in results): # uniqueness 108 x = random.randint(1,bound-1) 109 results.append( x ) 110 results.sort() # sorted 111 return [0]+results+[bound] # [0, +n points+, bound]
112
113 - def _crossover( self, x, no, locs ):
114 """Generalized Crossover Function: 115 116 arguments: 117 x (int) - genome number [0|1] 118 no (organism,organism) 119 - new organisms 120 locs (int list, int list) 121 - lists of locations, 122 [0, +n points+, bound] 123 for each genome (sync'd with x) 124 125 return type: sequence (to replace no[x]) 126 """ 127 s = no[ x ].genome[ :locs[ x ][1] ] 128 for n in range(1,self._npoints): 129 # flipflop between genome_0 and genome_1 130 mode = (x+n)%2 131 # _generate_locs gives us [0, +n points+, bound] 132 # so we can iterate: { 0:loc(1) ... loc(n):bound } 133 t = no[ mode ].genome[ locs[mode][n]:locs[mode][n+1] ] 134 if (s): s = s + t 135 else: s = t 136 return s
137 138
139 -class TwoCrossover(GeneralPointCrossover):
140 """Helper class for Two Point crossovers. 141 142 Offers more efficient replacements to the GeneralPoint framework 143 for single pivot crossovers 144 """
145 - def _generate_locs(self, bound):
146 """Replacement generation. 147 148 See GeneralPoint._generate_locs documentation for details 149 """ 150 return [0, random.randint(1,bound-1), bound]
151
152 - def _crossover( self, x, no, locs ):
153 """Replacement crossover 154 155 see GeneralPoint._crossover documentation for details 156 """ 157 y = (x+1)%2 158 return no[x].genome[ : locs[x][1] ] + no[y].genome[ locs[y][1] : ]
159
160 -class InterleaveCrossover(GeneralPointCrossover):
161 """Demonstration class for Interleaving crossover. 162 163 Interleaving: AbCdEfG, aBcDeFg 164 """
165 - def __init__(self,crossover_prob=0.1):
166 GeneralPointCrossover.__init__(self,0,crossover_prob)
167
168 - def _generate_locs(self,bound):
169 return range(-1,bound+1)
170
171 - def _crossover( self, x, no, locs ):
172 s = no[ x ].genome[ 0:1 ] 173 for n in range(1,self._npoints+2): 174 mode = ( x+n )%2 175 s += no[ mode ].genome[ n:n+1 ] 176 return s+no[mode].genome[self._npoints+3:]
177