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