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