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  """ 
  7  Generalized N-Point Crossover. 
  8   
  9  For even values of N, perform N point crossover 
 10    (select N/2 points each in the two genomes, and alternate) 
 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  # standard modules 
 39  import random 
 40   
 41  from Bio._py3k import range 
 42   
 43  __docformat__ = "restructuredtext en" 
 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 50 - Call it directly ( construct, do_crossover ) 51 - Use one of the provided subclasses 52 - Inherit from it: 53 * replace _generate_locs with a more domain 54 specific technique 55 * replace _crossover with a more efficient 56 technique for your point-count 57 """
58 - def __init__(self, points, crossover_prob=.1):
59 """Initialize to do crossovers at the specified probability. 60 """ 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 """ 69 new_org = (org_1.copy(), org_2.copy()) 70 71 # determine if we have a crossover 72 crossover_chance = random.random() 73 if crossover_chance <= self._crossover_prob: 74 75 # pre-compute bounds (len(genome)) 76 bound = (len(new_org[0].genome), len(new_org[1].genome)) 77 78 mbound = min(bound) 79 # can't have more than 0,x_0...x_n,bound locations 80 if (self._npoints == 0 or self._npoints > mbound-2): 81 self._npoints = mbound-2 82 83 y_locs = [] 84 # generate list for the shortest of the genomes 85 x_locs = self._generate_locs(mbound) 86 87 if (self._sym != 0): 88 y_locs = x_locs 89 else: 90 # figure out which list we've generated 91 # for, and generate the other 92 if (mbound == bound[0]): 93 y_locs = self._generate_locs(bound[1]) 94 else: 95 y_locs = x_locs 96 xlocs = self._generate_locs(bound[0]) 97 98 # copy new genome strings over 99 tmp = self._crossover(0, new_org, (x_locs, y_locs)) 100 new_org[1].genome = self._crossover(1, new_org, (x_locs, y_locs)) 101 new_org[0].genome = tmp 102 103 return new_org
104
105 - def _generate_locs(self, bound):
106 """Generalized Location Generator: 107 108 arguments: 109 110 - bound (int) - upper bound 111 112 returns: [0]+x_0...x_n+[bound] 113 where n=self._npoints-1 114 and 0 < x_0 < x_1 ... < bound 115 """ 116 results = [] 117 for increment in range(self._npoints): 118 x = random.randint(1, bound-1) 119 while (x in results): # uniqueness 120 x = random.randint(1, bound-1) 121 results.append(x) 122 results.sort() # sorted 123 return [0]+results+[bound] # [0, +n points+, bound]
124
125 - def _crossover(self, x, no, locs):
126 """Generalized Crossover Function: 127 128 arguments: 129 - x (int) - genome number [0|1] 130 - no (organism,organism) 131 132 - new organisms 133 134 - locs (int list, int list) 135 136 - lists of locations, 137 [0, +n points+, bound] 138 for each genome (sync'd with x) 139 140 return type: sequence (to replace no[x]) 141 """ 142 s = no[x].genome[:locs[x][1]] 143 for n in range(1, self._npoints): 144 # flipflop between genome_0 and genome_1 145 mode = (x+n)%2 146 # _generate_locs gives us [0, +n points+, bound] 147 # so we can iterate: { 0:loc(1) ... loc(n):bound } 148 t = no[mode].genome[locs[mode][n]:locs[mode][n+1]] 149 if (s): 150 s = s + t 151 else: 152 s = t 153 return s
154 155
156 -class TwoCrossover(GeneralPointCrossover):
157 """Helper class for Two Point crossovers. 158 159 Offers more efficient replacements to the GeneralPoint framework 160 for single pivot crossovers 161 """
162 - def _generate_locs(self, bound):
163 """Replacement generation. 164 165 See GeneralPoint._generate_locs documentation for details 166 """ 167 return [0, random.randint(1, bound-1), bound]
168
169 - def _crossover(self, x, no, locs):
170 """Replacement crossover 171 172 see GeneralPoint._crossover documentation for details 173 """ 174 y = (x+1)%2 175 return no[x].genome[:locs[x][1]] + no[y].genome[locs[y][1]:]
176 177
178 -class InterleaveCrossover(GeneralPointCrossover):
179 """Demonstration class for Interleaving crossover. 180 181 Interleaving: AbCdEfG, aBcDeFg 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