Back to index

python-biopython  1.60
GeneralPoint.py
Go to the documentation of this file.
00001 """
00002 Generalized N-Point Crossover.
00003 
00004 For even values of N, perform N point crossover 
00005   (select N/2 points each in the two genomes, and alternate)
00006 For odd values of N, perform symmetric N+1 point crossover
00007   (select N/2 points for both genomes)
00008   
00009 N-Point introduction (my notation):
00010     genome 1:    A-----B-----C-----D-----E-----F-----G
00011     genome 2:    a=====b=====c=====d=====e=====f=====g
00012     
00013     2-point, symmetric (points=1):
00014                  A-----B-----C- 1 -D-----E-----F-----G
00015                  a=====b=====c= 2 =d=====e=====f=====g
00016     returns: (ABCdefg, abcDEFG)
00017 
00018     2-point, asymmetric (points=2):
00019                  A-----B- 1 -C-----D-----E-----F-----G
00020                  a=====b=====c=====d=====e= 2 =f=====g
00021     returns: (ABfg, abcdeCDEFG)
00022 
00023 and for the drastic (n can be arbitrary to the length of the genome!):
00024     12-point, symmetric (points=11):
00025                  A- 1 -B- 2 -C- 3 -D- 4 -E- 5 -F- 6 -G
00026                  a= 7 =b= 8 =c= 9 =d= 10 e= 11 f= 12 g
00027     returns: (AbCdEfG, aBcDeFg)
00028     (note that points=12 will yield the same result, but 11
00029      may be somewhat faster)
00030         
00031 """
00032 # standard modules
00033 import random
00034 
00035 class GeneralPointCrossover(object):
00036     """Perform n-point crossover between genomes at some defined rates.
00037 
00038        Ideas on how to use this class:
00039            - Call it directly ( construct, do_crossover )
00040            - Use one of the provided subclasses
00041            - Inherit from it:
00042                * replace _generate_locs with a more domain 
00043                  specific technique
00044                * replace _crossover with a more efficient 
00045                  technique for your point-count
00046     """
00047     def __init__(self, points, crossover_prob = .1):
00048         """Initialize to do crossovers at the specified probability.
00049         """
00050         self._crossover_prob = crossover_prob
00051 
00052         self._sym     = points % 2 # odd n, gets a symmetry flag
00053         self._npoints = (points + self._sym)//2 # (N or N+1)//2
00054     
00055     def do_crossover(self, org_1, org_2):
00056         """Potentially do a crossover between the two organisms.
00057         """
00058         new_org = ( org_1.copy(), org_2.copy() )
00059         
00060         # determine if we have a crossover
00061         crossover_chance = random.random()
00062         if crossover_chance <= self._crossover_prob:
00063             
00064             # pre-compute bounds (len(genome))
00065             bound  = (len(new_org[0].genome), len(new_org[1].genome))
00066             
00067             mbound = min(bound)
00068             # can't have more than 0,x_0...x_n,bound locations
00069             if (self._npoints == 0 or self._npoints > mbound-2):
00070                 self._npoints = mbound-2
00071                 
00072             y_locs = []
00073             # generate list for the shortest of the genomes
00074             x_locs = self._generate_locs( mbound )
00075 
00076             if (self._sym != 0):  
00077                 y_locs = x_locs
00078             else:
00079                 # figure out which list we've generated 
00080                 # for, and generate the other
00081                 if (mbound == bound[0]):
00082                     y_locs = self._generate_locs( bound[1] )
00083                 else:
00084                     y_locs = x_locs
00085                     xlocs  = self._generate_locs( bound[0] )
00086               
00087             # copy new genome strings over
00088             tmp = self._crossover(0, new_org, (x_locs,y_locs))
00089             new_org[1].genome = self._crossover(1, new_org, (x_locs,y_locs))
00090             new_org[0].genome = tmp
00091 
00092         return new_org
00093 
00094     def _generate_locs(self, bound):
00095         """Generalized Location Generator:
00096             
00097            arguments:
00098                bound (int)   - upper bound 
00099             
00100            returns: [0]+x_0...x_n+[bound]
00101              where n=self._npoints-1
00102                and 0 < x_0 < x_1 ... < bound
00103         """
00104         results = []
00105         for increment in range(self._npoints):
00106             x = random.randint(1,bound-1)
00107             while (x in results):  # uniqueness
00108                 x = random.randint(1,bound-1)
00109             results.append( x )
00110         results.sort()             # sorted
00111         return [0]+results+[bound] # [0, +n points+, bound]
00112             
00113     def _crossover( self, x, no, locs ):
00114         """Generalized Crossover Function:
00115             
00116            arguments: 
00117                x (int)        - genome number [0|1]
00118                no (organism,organism)
00119                               - new organisms
00120                locs (int list, int list)
00121                               - lists of locations, 
00122                                 [0, +n points+, bound]
00123                                 for each genome (sync'd with x)
00124 
00125             return type: sequence (to replace no[x])
00126         """
00127         s = no[ x ].genome[ :locs[ x ][1] ]
00128         for n in range(1,self._npoints):
00129             # flipflop between genome_0 and genome_1
00130             mode = (x+n)%2
00131             # _generate_locs gives us [0, +n points+, bound]
00132             #  so we can iterate: { 0:loc(1) ... loc(n):bound }
00133             t = no[ mode ].genome[ locs[mode][n]:locs[mode][n+1] ]
00134             if (s): s = s + t
00135             else:   s = t
00136         return s
00137 
00138     
00139 class TwoCrossover(GeneralPointCrossover):
00140     """Helper class for Two Point crossovers.
00141     
00142     Offers more efficient replacements to the GeneralPoint framework
00143     for single pivot crossovers
00144     """
00145     def _generate_locs(self, bound):
00146         """Replacement generation.
00147          
00148         See GeneralPoint._generate_locs documentation for details
00149         """
00150         return [0, random.randint(1,bound-1), bound]
00151     
00152     def _crossover( self, x, no, locs ):
00153         """Replacement crossover
00154          
00155            see GeneralPoint._crossover documentation for details
00156         """
00157         y = (x+1)%2
00158         return no[x].genome[ : locs[x][1] ] + no[y].genome[ locs[y][1] : ]
00159 
00160 class InterleaveCrossover(GeneralPointCrossover):
00161     """Demonstration class for Interleaving crossover.
00162     
00163     Interleaving:  AbCdEfG, aBcDeFg
00164     """
00165     def __init__(self,crossover_prob=0.1):
00166         GeneralPointCrossover.__init__(self,0,crossover_prob)
00167     
00168     def _generate_locs(self,bound):
00169         return range(-1,bound+1)
00170     
00171     def _crossover( self, x, no, locs ):
00172         s = no[ x ].genome[ 0:1 ]
00173         for n in range(1,self._npoints+2):
00174             mode = ( x+n )%2
00175             s += no[ mode ].genome[ n:n+1 ]
00176         return s+no[mode].genome[self._npoints+3:]