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  # standard modules 
 32  import random 
 33   
 34   
 35 -class GeneralPointCrossover(object): 
 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): 
135                  s = s + t 
136              else: 
137                  s = t 
138          return s 
139   
140   
141 -class TwoCrossover(GeneralPointCrossover): 
142      """Helper class for Two Point crossovers. 
143   
144      Offers more efficient replacements to the GeneralPoint framework 
145      for single pivot crossovers 
146      """ 
147 -    def _generate_locs(self, bound): 
148          """Replacement generation. 
149   
150          See GeneralPoint._generate_locs documentation for details 
151          """ 
152          return [0, random.randint(1,bound-1), bound] 
153   
154 -    def _crossover( self, x, no, locs ): 
155          """Replacement crossover 
156   
157             see GeneralPoint._crossover documentation for details 
158          """ 
159          y = (x+1)%2 
160          return no[x].genome[ : locs[x][1] ] + no[y].genome[ locs[y][1] : ] 
161   
162   
163 -class InterleaveCrossover(GeneralPointCrossover): 
164      """Demonstration class for Interleaving crossover. 
165   
166      Interleaving:  AbCdEfG, aBcDeFg 
167      """ 
168 -    def __init__(self,crossover_prob=0.1): 
169          GeneralPointCrossover.__init__(self,0,crossover_prob) 
170   
171 -    def _generate_locs(self,bound): 
172          return range(-1,bound+1) 
173   
174 -    def _crossover( self, x, no, locs ): 
175          s = no[ x ].genome[ 0:1 ] 
176          for n in range(1,self._npoints+2): 
177              mode = ( x+n )%2 
178              s += no[ mode ].genome[ n:n+1 ] 
179          return s+no[mode].genome[self._npoints+3:] 
180