340 lines
11 KiB
Go
340 lines
11 KiB
Go
|
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) (o1 []float64, o2 []float64) {
|
||
|
|
var gSize = len(p1)
|
||
|
|
o1 = make([]float64, gSize)
|
||
|
|
o2 = make([]float64, gSize)
|
||
|
|
// For every gene pick a random number between 0 and 1
|
||
|
|
for i := 0; i < gSize; i++ {
|
||
|
|
var p = rng.Float64()
|
||
|
|
o1[i] = p*p1[i] + (1-p)*p2[i]
|
||
|
|
o2[i] = (1-p)*p1[i] + p*p2[i]
|
||
|
|
}
|
||
|
|
return o1, o2
|
||
|
|
}
|
||
|
|
|
||
|
|
// Generic mutations for slices
|
||
|
|
|
||
|
|
// Contains the deterministic part of the GNX method for testing purposes.
|
||
|
|
func gnx(p1, p2 Slice, indexes []int) (Slice, Slice) {
|
||
|
|
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
|
||
|
|
}
|
||
|
|
return o1, 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) (o1 Slice, o2 Slice) {
|
||
|
|
var indexes = randomInts(n, 1, p1.Len(), rng)
|
||
|
|
sort.Ints(indexes)
|
||
|
|
return gnx(p1, p2, indexes)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossGNXInt calls CrossGNX on two int slices.
|
||
|
|
func CrossGNXInt(s1 []int, s2 []int, n int, rng *rand.Rand) ([]int, []int) {
|
||
|
|
var o1, o2 = CrossGNX(IntSlice(s1), IntSlice(s2), n, rng)
|
||
|
|
return o1.(IntSlice), o2.(IntSlice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossGNXFloat64 calls CrossGNX on two float64 slices.
|
||
|
|
func CrossGNXFloat64(s1 []float64, s2 []float64, n int, rng *rand.Rand) ([]float64, []float64) {
|
||
|
|
var o1, o2 = CrossGNX(Float64Slice(s1), Float64Slice(s2), n, rng)
|
||
|
|
return o1.(Float64Slice), o2.(Float64Slice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossGNXString calls CrossGNX on two string slices.
|
||
|
|
func CrossGNXString(s1 []string, s2 []string, n int, rng *rand.Rand) ([]string, []string) {
|
||
|
|
var o1, o2 = CrossGNX(StringSlice(s1), StringSlice(s2), n, rng)
|
||
|
|
return o1.(StringSlice), o2.(StringSlice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Contains the deterministic part of the PMX method for testing purposes.
|
||
|
|
func pmx(p1, p2 Slice, a, b int) (Slice, Slice) {
|
||
|
|
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))
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return o1, 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) (o1 Slice, o2 Slice) {
|
||
|
|
var indexes = randomInts(2, 0, p1.Len(), rng)
|
||
|
|
sort.Ints(indexes)
|
||
|
|
return pmx(p1, p2, indexes[0], indexes[1])
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossPMXInt calls CrossPMX on an int slice.
|
||
|
|
func CrossPMXInt(s1 []int, s2 []int, rng *rand.Rand) ([]int, []int) {
|
||
|
|
var o1, o2 = CrossPMX(IntSlice(s1), IntSlice(s2), rng)
|
||
|
|
return o1.(IntSlice), o2.(IntSlice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossPMXFloat64 calls CrossPMX on a float64 slice.
|
||
|
|
func CrossPMXFloat64(s1 []float64, s2 []float64, rng *rand.Rand) ([]float64, []float64) {
|
||
|
|
var o1, o2 = CrossPMX(Float64Slice(s1), Float64Slice(s2), rng)
|
||
|
|
return o1.(Float64Slice), o2.(Float64Slice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossPMXString calls CrossPMX on a string slice.
|
||
|
|
func CrossPMXString(s1 []string, s2 []string, rng *rand.Rand) ([]string, []string) {
|
||
|
|
var o1, o2 = CrossPMX(StringSlice(s1), StringSlice(s2), rng)
|
||
|
|
return o1.(StringSlice), o2.(StringSlice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Contains the deterministic part of the OX method for testing purposes.
|
||
|
|
func ox(p1, p2 Slice, a, b int) (Slice, Slice) {
|
||
|
|
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++
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return o1, 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) (o1 Slice, o2 Slice) {
|
||
|
|
var indexes = randomInts(2, 0, p1.Len(), rng)
|
||
|
|
sort.Ints(indexes)
|
||
|
|
return ox(p1, p2, indexes[0], indexes[1])
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossOXInt calls CrossOX on a int slice.
|
||
|
|
func CrossOXInt(s1 []int, s2 []int, rng *rand.Rand) ([]int, []int) {
|
||
|
|
var o1, o2 = CrossOX(IntSlice(s1), IntSlice(s2), rng)
|
||
|
|
return o1.(IntSlice), o2.(IntSlice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossOXFloat64 calls CrossOX on a float64 slice.
|
||
|
|
func CrossOXFloat64(s1 []float64, s2 []float64, rng *rand.Rand) ([]float64, []float64) {
|
||
|
|
var o1, o2 = CrossOX(Float64Slice(s1), Float64Slice(s2), rng)
|
||
|
|
return o1.(Float64Slice), o2.(Float64Slice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossOXString calls CrossOX on a string slice.
|
||
|
|
func CrossOXString(s1 []string, s2 []string, rng *rand.Rand) ([]string, []string) {
|
||
|
|
var o1, o2 = CrossOX(StringSlice(s1), StringSlice(s2), rng)
|
||
|
|
return o1.(StringSlice), o2.(StringSlice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// 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) (Slice, 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
|
||
|
|
}
|
||
|
|
return o1, o2
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossCXInt calls CrossCX on an int slice.
|
||
|
|
func CrossCXInt(s1 []int, s2 []int) ([]int, []int) {
|
||
|
|
var o1, o2 = CrossCX(IntSlice(s1), IntSlice(s2))
|
||
|
|
return o1.(IntSlice), o2.(IntSlice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossCXFloat64 calls CrossCX on a float64 slice.
|
||
|
|
func CrossCXFloat64(s1 []float64, s2 []float64) ([]float64, []float64) {
|
||
|
|
var o1, o2 = CrossCX(Float64Slice(s1), Float64Slice(s2))
|
||
|
|
return o1.(Float64Slice), o2.(Float64Slice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossCXString calls CrossCX on a string slice.
|
||
|
|
func CrossCXString(s1 []string, s2 []string) ([]string, []string) {
|
||
|
|
var o1, o2 = CrossCX(StringSlice(s1), StringSlice(s2))
|
||
|
|
return o1.(StringSlice), o2.(StringSlice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossERX (Edge Recombination Crossover).
|
||
|
|
func CrossERX(p1, p2 Slice) (Slice, 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
|
||
|
|
}
|
||
|
|
// 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)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return o1, o2
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossERXInt calls CrossERX on an int slice.
|
||
|
|
func CrossERXInt(s1 []int, s2 []int) ([]int, []int) {
|
||
|
|
var o1, o2 = CrossERX(IntSlice(s1), IntSlice(s2))
|
||
|
|
return o1.(IntSlice), o2.(IntSlice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossERXFloat64 callsCrossERX on a float64 slice.
|
||
|
|
func CrossERXFloat64(s1 []float64, s2 []float64) ([]float64, []float64) {
|
||
|
|
var o1, o2 = CrossERX(Float64Slice(s1), Float64Slice(s2))
|
||
|
|
return o1.(Float64Slice), o2.(Float64Slice)
|
||
|
|
}
|
||
|
|
|
||
|
|
// CrossERXString calls CrossERX on a string slice.
|
||
|
|
func CrossERXString(s1 []string, s2 []string) ([]string, []string) {
|
||
|
|
var o1, o2 = CrossERX(StringSlice(s1), StringSlice(s2))
|
||
|
|
return o1.(StringSlice), o2.(StringSlice)
|
||
|
|
}
|