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   
44 -class GeneralPointCrossover(object):
45 """Perform n-point crossover between genomes at some defined rates. 46 47 Ideas on how to use this class: 48 49 - Call it directly ( construct, do_crossover ) 50 - Use one of the provided subclasses 51 - Inherit from it: 52 * replace _generate_locs with a more domain 53 specific technique 54 * replace _crossover with a more efficient 55 technique for your point-count 56 """
57 - def __init__(self, points, crossover_prob=.1):
58 """Initialize to do crossovers at the specified probability. 59 """ 60 self._crossover_prob = crossover_prob 61 62 self._sym = points % 2 # odd n, gets a symmetry flag 63 self._npoints = (points + self._sym) // 2 # (N or N+1)//2
64
65 - def do_crossover(self, org_1, org_2):
66 """Potentially do a crossover between the two organisms. 67 """ 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 109 - bound (int) - upper bound 110 111 returns: [0]+x_0...x_n+[bound] 112 where n=self._npoints-1 113 and 0 < x_0 < x_1 ... < bound 114 """ 115 results = [] 116 for increment in range(self._npoints): 117 x = random.randint(1, bound - 1) 118 while (x in results): # uniqueness 119 x = random.randint(1, bound - 1) 120 results.append(x) 121 results.sort() # sorted 122 return [0] + results + [bound] # [0, +n points+, bound]
123
124 - def _crossover(self, x, no, locs):
125 """Generalized Crossover Function: 126 127 arguments: 128 - x (int) - genome number [0|1] 129 - no (organism,organism) 130 131 - new organisms 132 133 - locs (int list, int list) 134 135 - lists of locations, 136 [0, +n points+, bound] 137 for each genome (sync'd with x) 138 139 return type: sequence (to replace no[x]) 140 """ 141 s = no[x].genome[:locs[x][1]] 142 for n in range(1, self._npoints): 143 # flipflop between genome_0 and genome_1 144 mode = (x + n) % 2 145 # _generate_locs gives us [0, +n points+, bound] 146 # so we can iterate: { 0:loc(1) ... loc(n):bound } 147 t = no[mode].genome[locs[mode][n]:locs[mode][n + 1]] 148 if (s): 149 s = s + t 150 else: 151 s = t 152 return s
153 154
155 -class TwoCrossover(GeneralPointCrossover):
156 """Helper class for Two Point crossovers. 157 158 Offers more efficient replacements to the GeneralPoint framework 159 for single pivot crossovers 160 """
161 - def _generate_locs(self, bound):
162 """Replacement generation. 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 """Replacement crossover 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 - def __init__(self, crossover_prob=0.1):
183 GeneralPointCrossover.__init__(self, 0, crossover_prob)
184
185 - def _generate_locs(self, bound):
186 return list(range(-1, bound + 1))
187
188 - def _crossover(self, x, no, locs):
189 s = no[x].genome[0:1] 190 for n in range(1, self._npoints + 2): 191 mode = (x + n) % 2 192 s += no[mode].genome[n:n + 1] 193 return s + no[mode].genome[self._npoints + 3:]
194