Golang Genetic Algorithm

Overview

goga Build Status Coverage Status Go Report Card

Golang implementation of a genetic algorithm. See ./examples for info on how to use the library.

Overview

Goga is a genetic algorithm solution written in Golang. It is used and configured by injecting different behaviours into the main genetic algorithm object. The main injectable components are the simulator, selector and mater.

The simulator provides a function that accepts a single genome and assigns a fitness score to it. The higher the fitness, the better the genome has done in the simulation. A genome can be simulated by however the application sees fit as long as it can be encoded into a bitset of 0s and 1s. A simulator also provides a function to tell the algorithm when to stop.

The selector object takes a popualtion of genomes and the total fitness and returns a genome from the population that it has chosen. A common implementation is roulette in which a random value between 0..totalFitness is generated and the genomes are cycled through subtracting their fitness away from this random number. Then this number goes below 0 then a genome has been 'selected'. The idea is that a genome with a higher fitness will be more likely to be chosen.

A mater accepts two genomes from the selector and combines them to produce two others. There are some common predefined mating algorithms but the user is also free to define their own.

As genomes that have a fitness are more likely to mate, the program will slowly work its way towards what it thinks is an optimal solution.

Examples

This section will talk through any example programs using this library.

examples/string_matcher.go

To run:

cd examples
go run string_matcher.go

The string matcher is a program that can be configured with any string and the goga library will attempt to generate a bitset that decodes to this string. Each character is representated by 8 bits in each genome.

There are some configuration constants just above the main function, use this to configure the string you'd like the algorithm to match to.

const (
	kTargetString = "abcdefghijklmnopqrstuvwxyz"
	// ...
)

The elite consumer is called after each simulation with the best genome of that iteration. It prints it out along with the iteration number and the fitness for that particular genome. A typical output might look something like this:

1 	 Øoâ|-7rPKw
                   D( 	 71
2 	 Xnæ=írVÏw
T3 	 74
3 	 �oî,ë.2wës
�# 	 81
4 	 XOà|m,�WOz
D" 	 84
5 	 XOålo,rWorD# 	 89
6 	 XOìlo.0WozD# 	 91
7 	 Xgflm,pWorND# 	 93
8 	 Xgllo,0WorD# 	 96
9 	 Xgllo.0WorNd# 	 97
10 	 Xello.0WorNd# 	 98
11 	 Hello,0WorNd# 	 100
12 	 Hello,0WorNd# 	 100
13 	 Hello, WorNd# 	 101
14 	 Hello, Wornd! 	 103
15 	 Hello, Wornd! 	 103
16 	 Hello, World! 	 104
151.88245ms

You can see the string slowly becoming more like the input string as there are more iterations.

examples/image_matcher.go

To run:

cd examples
go run image_matcher.go <path_to_image>

Image matcher takes an input image and attempts to produce an output image that is as close to it as possible only using RGBA coloured rectangles and circles. There are a few parameters at the top of the file that are interesting to fiddle with:

numShapes = 100
populationSize = 1000
maxIterations = 9999999
bitsPerCoordinateNumber = 9
parallelSimulations = 24
maxCircleRadiusFactor = 3
  • numShapes - the number of shapes that are used when the algorithm re-creates the input image
  • populationSize - the number of genomes in each population. Each genome can be decoded into a picture. A high value will mean each iteration takes longer, and usually results in the algorithm finding its optimal solution in less iterations.
  • maxIterations - the maximum number of simulations/iterations to run. Providing a huge number will essentially run until the algorithm has figured out what it thinks is an optimal solution.
  • bitsPerCoordinateNumber - Each shape is positioned using coordinates. A rect is represented by the top left and bottom right coordinates, and a circle by its centre. A coordinate is made up of two numbers, each number is represented by this many bits. The number generated is used to calculate a percentage of the overall width/height of the image for the coordinate to be positioned at. For example, if bitsPerCoordinateNumber is 8, that means the maximum value a coordinte can be is 0b11111111, or 255. To calculate the coordinates number relative to the image's width and height we normalise this and apply the decimal to the pictures dimensions. For example, if our X coordinate produced by the algorithm is 233, and our images width is 120. ( 233 / 255 ) * 120 == 109 == our X coordinate. Setting this to a high value means the algorithm has more accuracy when placing shapes. A low value of 2 or 3 also creates some interesting effects.
  • parallelSimulations - The number of simulations to run in parallel. A higher value usually means each iteration takes less time, up to a certain point.
  • maxCircleRadiusFactor - A number to divide a circles radius by. 1 will mean a circles radius can be anywhere between 1 and max( inputImageWidth, inputImageHeight ). From experimenting, restricting the radius a little creates 'better' images quicker

The script outputs the 'best' genome from each iteration to "elite.png" as well as the original overlayed in "elite_with_original.png".

Here's an example of what can be generated. Input, output and both overlayed over the top of each other:

input output overlayed

You might also like...
Golang Neural Network
Golang Neural Network

Varis Neural Networks with GO About Package Some time ago I decided to learn Go language and neural networks. So it's my variation of Neural Networks

Golang HTML to PDF Converter
Golang HTML to PDF Converter

Golang HTML to PDF Converter For reading any document, one prefers PDF format over any other formats as it is considered as a standard format for any

A high-performance timeline tracing library for Golang, used by TiDB

Minitrace-Go A high-performance, ergonomic timeline tracing library for Golang. Basic Usage package main import ( "context" "fmt" "strcon

Gota: DataFrames and data wrangling in Go (Golang)

Gota: DataFrames, Series and Data Wrangling for Go This is an implementation of DataFrames, Series and data wrangling methods for the Go programming l

Golang k-d tree implementation with duplicate coordinate support

Golang k-d tree implementation with duplicate coordinate support

Another AOC repo (this time in golang!)

advent-of-code Now with 100% more golang! (It's going to be a long advent of code...) To run: Get your data for a given year/day and copy paste it to

Go (Golang) encrypted deep learning library; Fully homomorphic encryption over neural network graphs

DC DarkLantern A lantern is a portable case that protects light, A dark lantern is one who's light can be hidden at will. DC DarkLantern is a golang i

Clean Architecture With Golang

Clean Architecture With Golang When init a new project go mod init github.com/samuelterra22/clean-architecture-go Run testes go test ./... Generate a

TFKG - A Tensorflow and Keras Golang port

TFKG - A Tensorflow and Keras Golang port This is experimental and quite nasty under the hood* Support macOS: running docker container, no GPU acceler

Comments
  • Refactor all the things

    Refactor all the things

    Just took a brief look at the library. I've forked it and plan on refactoring lots of things in it. If you don't mind I'd like to make PRs against your repo. These are the things which are "not good"

    • Package name should be goga, not ga
    • Adding support for Go modules
    • Remove pointer-interface arguments from functions (needless and verbose, interfaces are already pointers)
    • fix it not compiling in Go 1.17

    Surely I might find other things wrong with the library, but these were the first things apparent.

    opened by soypat 0
Owner
null
Genetic Algorithms library written in Go / golang

Description Genetic Algorithms for Go/Golang Install $ go install git://github.com/thoj/go-galib.git Compiling examples: $ git clone git://github.com

Thomas Jager 193 Sep 27, 2022
Genetic algorithms using Golang Generics

Package genetic Package genetic implements genetic algorithms using Golang's Gen

Konnor Klashinsky 8 Sep 23, 2022
Golang implementation of the Paice/Husk Stemming Algorithm

##Golang Implementation of the Paice/Husk stemming algorithm This project was created for the QUT course INB344. Details on the algorithm can be found

Aaron Groves 29 Sep 27, 2022
A native Go clean room implementation of the Porter Stemming algorithm.

Go Porter Stemmer A native Go clean room implementation of the Porter Stemming Algorithm. This algorithm is of interest to people doing Machine Learni

Charles Iliya Krempeaux 183 Jan 3, 2023
Fast (linear time) implementation of the Gaussian Blur algorithm in Go.

Song2 Fast (linear time) implementation of the Gaussian Blur algorithm in Go.

Masaya Watanabe 52 Oct 25, 2022
An iterative algorithm to generate high-quality triangulated images.

An iterative algorithm to generate high quality triangulated images. Introduction Triangula uses a modified genetic algorithm to triangulate images. I

null 3.8k Dec 29, 2022
k-means clustering algorithm implementation written in Go

kmeans k-means clustering algorithm implementation written in Go What It Does k-means clustering partitions a multi-dimensional data set into k cluste

Christian Muehlhaeuser 414 Dec 6, 2022
a* pathfinding algorithm written in go

astar a* (a-star) pathfinding algorithm written in go Wikipedia: EN: A* search algorithm DE: A*-Algorithmus Install go get github.com/jpierer/[email protected]

Julian Pierer 26 Mar 21, 2022
Naive Bayesian Classification for Golang.

Naive Bayesian Classification Perform naive Bayesian classification into an arbitrary number of classes on sets of strings. bayesian also supports ter

Jake Brukhman 745 Dec 30, 2022
Ensembles of decision trees in go/golang.

CloudForest Google Group Fast, flexible, multi-threaded ensembles of decision trees for machine learning in pure Go (golang). CloudForest allows for a

Ryan Bressler 722 Dec 1, 2022