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 return [0, random.randint(1,bound-1), bound]
151
153 """Replacement crossover
154
155 see GeneralPoint._crossover documentation for details
156 """
157 y = (x+1)%2
158 return no[x].genome[ : locs[x][1] ] + no[y].genome[ locs[y][1] : ]
159
161 """Demonstration class for Interleaving crossover.
162
163 Interleaving: AbCdEfG, aBcDeFg
164 """
167
169 return range(-1,bound+1)
170
172 s = no[ x ].genome[ 0:1 ]
173 for n in range(1,self._npoints+2):
174 mode = ( x+n )%2
175 s += no[ mode ].genome[ n:n+1 ]
176 return s+no[mode].genome[self._npoints+3:]
177