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