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

Source Code for Module Bio.GA.Crossover.GeneralPoint

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