When learning a new programming language, I start with a familiar problem and try to learn enough of the new language to solve it.
Here I’ve chosen to implement a simple genetic solver using Google’s Go programming language. I’ve previously solved this problem in C#. If you are new to genetic algorithms start with that post as I cover more of the genetic concepts.
This is my first program in Go and from scratch it took about two hours to learn enough to get it working.
Enough talk, here’s the problem statement: duplicate a string without hard coding the result.
We’ll start off with a standard set of genes and a target string:
const geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!." target := "Not all those who wander are lost."
Note: In this project the genes are the desired value so we don’t have to transform it in any way before using it further.
We’ll need a function that determines a fitness based on the number of differences between the candidate and the target.
func getFitness(target, candidate string) int {
differenceCount := 0
for i := 0; i < len(target); i++ {
if target[i] != candidate[i] {
differenceCount++
}
}
return len(target) - differenceCount
}
Next we need a function to generate a random gene sequence from the gene set
func generateParent(geneSet string, length int) string {
s := ""
for i := 0; i < length; i++ {
index := rand.Intn(len(geneSet))
s += geneSet[index:1+index]
}
return s
}
and another one to create a candidate by mutating an existing gene sequence.
func mutateParent(parent, geneSet string) string {
geneIndex := rand.Intn(len(geneSet))
parentIndex := rand.Intn(len(parent))
candidate := ""
if parentIndex > 0 {
candidate += parent[:parentIndex]
}
candidate += geneSet[geneIndex:1+geneIndex]
if parentIndex+1 < len(parent) {
candidate += parent[parentIndex+1:]
}
return candidate
}
The heart of the genetic solver uses those functions to generate, evaluate and iteratively improve a single parent.
func getBest(getFitness func(string) int, display func(string), geneSet string, length int) string {
var bestParent = generateParent(geneSet, length)
value := getFitness(bestParent)
var bestFitness = value
for bestFitness < length {
child := mutateParent(bestParent, geneSet)
fitness := getFitness(child)
if fitness > bestFitness {
display(child)
bestFitness = fitness
bestParent = child
}
}
return bestParent
}
We also need a function to display the improvements to the user.
disp := func (candidate string) {
fmt.Print(candidate)
fmt.Print("\t")
fmt.Print(calc(candidate))
fmt.Print("\t")
fmt.Println(time.Since(start))
}
The main program glues all the parts together to generate a random string and refine it over and over until it matches the target. Here’s the full program:
package main
import (
"fmt";
"math/rand";
"time"
)
func main() {
rand.Seed(time.Now().UnixNano())
const geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
target := "Not all those who wander are lost."
calc := func (candidate string) int {
return getFitness(target, candidate)
}
start := time.Now()
disp := func (candidate string) {
fmt.Print(candidate)
fmt.Print("\t")
fmt.Print(calc(candidate))
fmt.Print("\t")
fmt.Println(time.Since(start))
}
var best = getBest(calc, disp, geneSet, len(target))
println(best)
fmt.Print("Total time: ")
fmt.Println(time.Since(start))
}
func getBest(getFitness func(string) int, display func(string), geneSet string, length int) string {
var bestParent = generateParent(geneSet, length)
value := getFitness(bestParent)
var bestFitness = value
for bestFitness < length {
child := mutateParent(bestParent, geneSet)
fitness := getFitness(child)
if fitness > bestFitness {
display(child)
bestFitness = fitness
bestParent = child
}
}
return bestParent
}
func mutateParent(parent, geneSet string) string {
geneIndex := rand.Intn(len(geneSet))
parentIndex := rand.Intn(len(parent))
candidate := ""
if parentIndex > 0 {
candidate += parent[:parentIndex]
}
candidate += geneSet[geneIndex:1+geneIndex]
if parentIndex+1 < len(parent) {
candidate += parent[parentIndex+1:]
}
return candidate
}
func generateParent(geneSet string, length int) string {
s := ""
for i := 0; i < length; i++ {
index := rand.Intn(len(geneSet))
s += geneSet[index:1+index]
}
return s
}
func getFitness(target, candidate string) int {
differenceCount := 0
for i := 0; i < len(target); i++ {
if target[i] != candidate[i] {
differenceCount++
}
}
return len(target) - differenceCount
}
Save the code above in a file called
genetic.go
and run it from the commandline with:
go run genetic.go
Sample output:
yEMzTlTDjtwx SKZlPnwNcbkUC ofQShNh 1 1.0001ms yEMzTlTDjtwx SwZlPnwNcbkUC ofQShNh 2 2.0002ms yEMzTlTDjtwx SwZlPnaNcbkUC ofQShNh 3 3.0002ms yEMzTlTDjtwx SwZlPnaNcbrUC ofQShNh 4 4.0003ms yEM TlTDjtwx SwZlPnaNcbrUC ofQShNh 5 4.0003ms yEM TlTDjtwx SwZl naNcbrUC ofQShNh 6 5.0003ms yEt TlTDjtwx SwZl naNcbrUC ofQShNh 7 5.0003ms yEt TlTDjhwx SwZl naNcbrUC ofQShNh 8 6.0004ms yEt TlTDjhwx SwZl naNcbrUC ofQohNh 9 7.0004ms yEt TlTDjhwx wZl naNcbrUC ofQohNh 10 7.0004ms yEt TllDjhwx wZl naNcbrUC ofQohNh 11 8.0005ms yot TllDjhwx wZl naNcbrUC ofQohNh 12 9.0006ms yot TllDjhwxe wZl naNcbrUC ofQohNh 13 9.0006ms yot TllDjhwxe wZl naNdbrUC ofQohNh 14 10.0006ms yot TllDjhwxe wZl naNdbrUC ofQohN. 15 11.0007ms yot TllDjhwxe wZl naNdbrUCrofQohN. 16 11.0007ms yot TllDjhwxe wZl naNderUCrofQohN. 17 12.0007ms yot TllDjhwxe wZl naNderUarofQohN. 18 13.0008ms yot TllDjhwxe wZl naNderUarofQosN. 19 13.0008ms yot allDjhwxe wZl naNderUarofQosN. 20 14.0008ms yot allDjhwxe wZo naNderUarofQosN. 21 15.0009ms yot allDjhwxe wZo waNderUarofQosN. 22 15.0009ms yot all jhwxe wZo waNderUarofQosN. 23 16.001ms yot all jhwse wZo waNderUarofQosN. 24 17.001ms yot all jhwse wZo waNderUarofQost. 25 17.001ms yot all jhwse wZo waNderUarefQost. 26 19.0011ms yot all jhwse wZo waNder arefQost. 27 20.0012ms Not all jhwse wZo waNder arefQost. 28 21.0012ms Not all thwse wZo waNder arefQost. 29 21.0012ms Not all thwse who waNder arefQost. 30 22.0013ms Not all thwse who waNder are Qost. 31 23.0014ms Not all those who waNder are Qost. 32 23.0014ms Not all those who wander are Qost. 33 25.0015ms Not all those who wander are lost. 34 26.0015ms Not all those who wander are lost. Total time: 27.0016ms
Snappy!
This source code is also available from my github repository.
Go on to part 2.
On Line 39 you got a typo
, “bestValue” doesnt exist – it should be “bestFitness”
fixed, thanks!