123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339 |
- 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)
- }
|