crossover.go
package eaopt
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()
var o1 = p*p1[i] + (1-p)*p2[i]
var o2 = (1-p)*p1[i] + p*p2[i]
p1[i] = o1
p2[i] = o2
}
}
// 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 uint, 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 uint, rng *rand.Rand) {
CrossGNX(IntSlice(s1), IntSlice(s2), n, rng)
}
// CrossGNXFloat64 calls CrossGNX on two float64 slices.
func CrossGNXFloat64(s1 []float64, s2 []float64, n uint, rng *rand.Rand) {
CrossGNX(Float64Slice(s1), Float64Slice(s2), n, rng)
}
// CrossGNXString calls CrossGNX on two string slices.
func CrossGNXString(s1 []string, s2 []string, n uint, 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 p1Occurences, p2Occurences = make(setInt), make(setInt)
for i := b; i < a+n; i++ {
var k = i % n
p1Occurences[p1.At(k)]++
p2Occurences[p2.At(k)]++
}
// 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 p1Occurences[p2.At(k)] > 0 {
p1Occurences[p2.At(k)]--
o1.Set(j1%n, p2.At(k))
j1++
}
if p2Occurences[p1.At(k)] > 0 {
p2Occurences[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))
}