This repository has been archived by the owner on Aug 3, 2018. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 1
/
crossover.go
325 lines (298 loc) · 9.3 KB
/
crossover.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
package gago
import (
"math/rand"
"sort"
)
// Type specific mutations for slices
// CrossUniformFloat64 crossover combines two individuals (the parents) into one
// (the offspring). Each parent's contribution to the Genome is determined by
// the value of a probability p. Each offspring receives a proportion of both of
// it's parents genomes. The new values are located in the hyper-rectangle
// defined between both parent's position in Cartesian space.
func CrossUniformFloat64(p1 []float64, p2 []float64, rng *rand.Rand) {
for i := range p1 {
var p = rng.Float64()
p1[i] = p*p1[i] + (1-p)*p2[i]
p2[i] = (1-p)*p1[i] + p*p2[i]
}
}
// Generic mutations for slices
// Contains the deterministic part of the GNX method for testing purposes.
func gnx(p1, p2 Slice, indexes []int) {
var (
n = p1.Len()
o1 = p1.Copy()
o2 = p2.Copy()
toggle = true
)
// Add the first and last indexes
indexes = append([]int{0}, indexes...)
indexes = append(indexes, n)
for i := 0; i < len(indexes)-1; i++ {
if toggle {
o1.Slice(indexes[i], indexes[i+1]).Replace(p1.Slice(indexes[i], indexes[i+1]))
o2.Slice(indexes[i], indexes[i+1]).Replace(p2.Slice(indexes[i], indexes[i+1]))
} else {
o1.Slice(indexes[i], indexes[i+1]).Replace(p2.Slice(indexes[i], indexes[i+1]))
o2.Slice(indexes[i], indexes[i+1]).Replace(p1.Slice(indexes[i], indexes[i+1]))
}
toggle = !toggle // Alternate for the new copying
}
p1.Replace(o1)
p2.Replace(o2)
}
// CrossGNX (Generalized N-point Crossover). An identical point is chosen on
// each parent's genome and the mirroring segments are switched. n determines
// the number of crossovers (aka mirroring segments) to perform. n has to be
// equal or lower than the number of genes in each parent.
func CrossGNX(p1 Slice, p2 Slice, n int, rng *rand.Rand) {
var indexes = randomInts(n, 1, p1.Len(), rng)
sort.Ints(indexes)
gnx(p1, p2, indexes)
}
// CrossGNXInt calls CrossGNX on two int slices.
func CrossGNXInt(s1 []int, s2 []int, n int, rng *rand.Rand) {
CrossGNX(IntSlice(s1), IntSlice(s2), n, rng)
}
// CrossGNXFloat64 calls CrossGNX on two float64 slices.
func CrossGNXFloat64(s1 []float64, s2 []float64, n int, rng *rand.Rand) {
CrossGNX(Float64Slice(s1), Float64Slice(s2), n, rng)
}
// CrossGNXString calls CrossGNX on two string slices.
func CrossGNXString(s1 []string, s2 []string, n int, rng *rand.Rand) {
CrossGNX(StringSlice(s1), StringSlice(s2), n, rng)
}
// Contains the deterministic part of the PMX method for testing purposes.
func pmx(p1, p2 Slice, a, b int) {
var (
n = p1.Len()
o1 = p1.Copy()
o2 = p2.Copy()
)
// Create lookup maps to quickly see if a gene has been visited
var (
p1Visited, p2Visited = make(set), make(set)
o1Visited, o2Visited = make(set), make(set)
)
for i := a; i < b; i++ {
p1Visited[p1.At(i)] = true
p2Visited[p2.At(i)] = true
o1Visited[i] = true
o2Visited[i] = true
}
for i := a; i < b; i++ {
// Find the element in the second parent that has not been copied in the first offspring
if !p1Visited[p2.At(i)] {
var j = i
for o1Visited[j] {
j, _ = search(o1.At(j), p2)
}
o1.Set(j, p2.At(i))
o1Visited[j] = true
}
// Find the element in the first parent that has not been copied in the second offspring
if !p2Visited[p1.At(i)] {
var j = i
for o2Visited[j] {
j, _ = search(o2.At(j), p1)
}
o2.Set(j, p1.At(i))
o2Visited[j] = true
}
}
// Fill in the offspring's missing values with the opposite parent's values
for i := 0; i < n; i++ {
if !o1Visited[i] {
o1.Set(i, p2.At(i))
}
if !o2Visited[i] {
o2.Set(i, p1.At(i))
}
}
p1.Replace(o1)
p2.Replace(o2)
}
// CrossPMX (Partially Mapped Crossover). The offsprings are generated by
// copying one of the parents and then copying the other parent's values up to a
// randomly chosen crossover point. Each gene that is replaced is permuted with
// the gene that is copied in the first parent's genome. Two offsprings are
// generated in such a way (because there are two parents). The PMX method
// preserves gene uniqueness.
func CrossPMX(p1 Slice, p2 Slice, rng *rand.Rand) {
var indexes = randomInts(2, 1, p1.Len(), rng)
sort.Ints(indexes)
pmx(p1, p2, indexes[0], indexes[1])
}
// CrossPMXInt calls CrossPMX on an int slice.
func CrossPMXInt(s1 []int, s2 []int, rng *rand.Rand) {
CrossPMX(IntSlice(s1), IntSlice(s2), rng)
}
// CrossPMXFloat64 calls CrossPMX on a float64 slice.
func CrossPMXFloat64(s1 []float64, s2 []float64, rng *rand.Rand) {
CrossPMX(Float64Slice(s1), Float64Slice(s2), rng)
}
// CrossPMXString calls CrossPMX on a string slice.
func CrossPMXString(s1 []string, s2 []string, rng *rand.Rand) {
CrossPMX(StringSlice(s1), StringSlice(s2), rng)
}
// Contains the deterministic part of the OX method for testing purposes.
func ox(p1, p2 Slice, a, b int) {
var (
n = p1.Len()
o1 = p1.Copy()
o2 = p2.Copy()
)
// Create lookup maps to quickly see if a gene has been copied from a parent or not
var p1Visited, p2Visited = make(set), make(set)
for i := a; i < b; i++ {
p1Visited[p1.At(i)] = true
p2Visited[p2.At(i)] = true
}
// Keep two indicators to know where to fill the offsprings
var j1, j2 = b, b
for i := b; i < b+n; i++ {
var k = i % n
if !p1Visited[p2.At(k)] {
o1.Set(j1%n, p2.At(k))
j1++
}
if !p2Visited[p1.At(k)] {
o2.Set(j2%n, p1.At(k))
j2++
}
}
p1.Replace(o1)
p2.Replace(o2)
}
// CrossOX (Ordered Crossover). Part of the first parent's genome is copied onto
// the first offspring's genome. Then the second parent's genome is iterated
// over, starting on the right of the part that was copied. Each gene of the
// second parent's genome is copied onto the next blank gene of the first
// offspring's genome if it wasn't already copied from the first parent. The OX
// method preserves gene uniqueness.
func CrossOX(p1 Slice, p2 Slice, rng *rand.Rand) {
var indexes = randomInts(2, 1, p1.Len(), rng)
sort.Ints(indexes)
ox(p1, p2, indexes[0], indexes[1])
}
// CrossOXInt calls CrossOX on a int slice.
func CrossOXInt(s1 []int, s2 []int, rng *rand.Rand) {
CrossOX(IntSlice(s1), IntSlice(s2), rng)
}
// CrossOXFloat64 calls CrossOX on a float64 slice.
func CrossOXFloat64(s1 []float64, s2 []float64, rng *rand.Rand) {
CrossOX(Float64Slice(s1), Float64Slice(s2), rng)
}
// CrossOXString calls CrossOX on a string slice.
func CrossOXString(s1 []string, s2 []string, rng *rand.Rand) {
CrossOX(StringSlice(s1), StringSlice(s2), rng)
}
// CrossCX (Cycle Crossover). Cycles between the parents are indentified, they
// are then copied alternatively onto the offsprings. The CX method is
// deterministic and preserves gene uniqueness.
func CrossCX(p1, p2 Slice) {
var (
o1 = p1.Copy()
o2 = p2.Copy()
cycles = getCycles(p1, p2)
toggle = true
)
for i := 0; i < len(cycles); i++ {
for _, j := range cycles[i] {
if toggle {
o1.Set(j, p1.At(j))
o2.Set(j, p2.At(j))
} else {
o2.Set(j, p1.At(j))
o1.Set(j, p2.At(j))
}
}
toggle = !toggle
}
p1.Replace(o1)
p2.Replace(o2)
}
// CrossCXInt calls CrossCX on an int slice.
func CrossCXInt(s1 []int, s2 []int) {
CrossCX(IntSlice(s1), IntSlice(s2))
}
// CrossCXFloat64 calls CrossCX on a float64 slice.
func CrossCXFloat64(s1 []float64, s2 []float64) {
CrossCX(Float64Slice(s1), Float64Slice(s2))
}
// CrossCXString calls CrossCX on a string slice.
func CrossCXString(s1 []string, s2 []string) {
CrossCX(StringSlice(s1), StringSlice(s2))
}
// CrossERX (Edge Recombination Crossover).
func CrossERX(p1, p2 Slice) {
var (
n = p1.Len()
o1 = p1.Copy()
o2 = p2.Copy()
parents = []Slice{p1, p2}
offsprings = []Slice{o1, o2}
p1Neighbours = getNeighbours(p1)
p2Neighbours = getNeighbours(p2)
pNeighbours = make(map[interface{}]set)
)
// Merge the neighbours of each parent whilst ignoring duplicates
for i := range p1Neighbours {
pNeighbours[i] = union(p1Neighbours[i], p2Neighbours[i])
}
// Hold two copies of the parent neighbours (one for each offspring)
var neighbours = []map[interface{}]set{pNeighbours, nil}
neighbours[1] = make(map[interface{}]set)
for k, v := range pNeighbours {
neighbours[1][k] = v
}
// Set the first element of each offspring to be the one of the
// corresponding parent
o1.Set(0, p1.At(0))
o2.Set(0, p2.At(0))
// Delete the neighbour from the adjacency set
for i := range neighbours {
delete(neighbours[i], parents[i].At(0))
for j := range neighbours[i] {
if neighbours[i][j][parents[i].At(0)] {
delete(neighbours[i][j], parents[i].At(0))
}
}
}
for o := range offsprings {
for i := 1; i < n; i++ {
// Find the gene with the least neighbours
var (
j interface{}
min = 5 // There can't be more than 5 neighbours between 2 parents
)
for k, v := range neighbours[o] {
if len(v) < min {
j = k
min = len(v)
}
}
offsprings[o].Set(i, j)
delete(neighbours[o], j)
for k := range neighbours[o] {
if neighbours[o][k][j] {
delete(neighbours[o][k], j)
}
}
}
}
p1.Replace(o1)
p2.Replace(o2)
}
// CrossERXInt calls CrossERX on an int slice.
func CrossERXInt(s1 []int, s2 []int) {
CrossERX(IntSlice(s1), IntSlice(s2))
}
// CrossERXFloat64 callsCrossERX on a float64 slice.
func CrossERXFloat64(s1 []float64, s2 []float64) {
CrossERX(Float64Slice(s1), Float64Slice(s2))
}
// CrossERXString calls CrossERX on a string slice.
func CrossERXString(s1 []string, s2 []string) {
CrossERX(StringSlice(s1), StringSlice(s2))
}