Page 1 of 1

## Intro to Genetic Algorithms Rate Topic: 1 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=319577&amp;s=fa39d2bd54ee703b2a52d18823374611&md5check=' + ipb.vars['secure_hash'], cur_rating: 5, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 modi123_1

• Suitor #2

Reputation: 14094
• Posts: 56,469
• Joined: 12-June 08

Posted 25 April 2013 - 08:07 PM

POPULAR

Tools: Visual Studios, VB.NET, 4.0 framework, console project.

Genetic Algorithms (GA) are a fun and interesting way to, in my opinion, have a directed (heuristic) brute force method rooted in biological functions. While they are not an end all-be all solution I think their solution space can provide interesting answers for interesting applications.

The gist of GAs is to throw possible solutions at the wall, determine which are closer to your goal, drop those that are not, and create new solutions from those closest to the goal. Simple enough, right?

The way this happens is through three neat functions:
1. Cross Over
- Cross over is where you cut apart two solutions and mash up their parts to make a new offspring. There are many ways to go about this - one is the single cross over. You pick a point inside your array of values, and take from 0 to that point from one parent and mash it with that point to the length of the array of another to produce a new solution. You can also try interweaving values (alternating one value from each parent), pick two cross over points, and so on. It sort of depends on how you want to have the solution created.

Example:
If I had two parent strings,
1 2 3 4 5
51 67 71 73 92

and their cross over point is 3, that means the child would look like:
1 2 3 73 92

2. Mutations
- Mutations are a way to try and keep the GA from falling into a pit of bad optimization. Mutations take a cell and either flip it, add to it, or in some way change the value. Preferably you want to keep this rate pretty low else you trample on possible solutions. Remember - GAs are more of an art like cooking!

3. Feed back on fitness.
- Fitness is a way to tell how close each entity is to your goal or solution. When you examine each entity you would compare it's value against the fitness and if it meets or exceeds you keep it. Otherwise you drop it to the curb. Preferably you want to keep the fitness threshold moving forward - so as the better the solutions that are being generated the more stringent the threshold. This helps push the over all search space into a more directed path.

I want to stress again - Genetic Algorithms are not a solution to everything, but when framed right they can lead to surprisingly interesting solutions and optimization.

Here's an example of how this would be setup.

The problem is I want an array of bits to be all one's. A pretty trivial problem, but it illustrates the principles well.
- The fitness will start out at 6.. I want to have each string have at least six ones to be fit to be a parent.
- I'll keep the threshold moving if the average fitness (of all the arrays that generation) is greater than the current fitness.
- Mutations I'll keep at a low 10%
- I'll start out with a string of ten spots I want filled up.
- Cross overs will be determined by randomly picking a point and mashing 0->crossover point of one parent with crossover point-> length of array of the second parent.
- Parents are selected from the most fit, will allow be randomly assigned another parent, and will allow the same parent to be both parents.
- If there is only one fit row throw an error and quit.

You will notice the code is not overly complex.. just a whole mess of cell and row traversal. They key is the depth of the search space and the ever more directed push towards the goal.

The pattern is pretty straight forward:
- Create the population
- Determine fitness
- Remove unfit
- From the fit make the next generation
- Apply mutations
- Repeat.

Private _alPopulation(,) As Int32 '-- main population array.
Private _lMaxPopulation As Int32 = 0 '-- how many rows we want
Private _lMaxNumberOfGenes As Int32 = 0 '-- number of columns.
Private _r As Random

Private _alFitness() As Int32 '-- judges each line based on 'fitness'.
Private _lFitnessThreshold As Int32 '-- a shifting bar that should always increase as more fit generations occur..
Private _dMutationRate As Decimal '-- how much we want to factor in mutations.

Private _bDebug As Boolean = False '-- print out all the screens as they happen.

Private _lSolution As Int32 = 145

'-- goal is to take random strings and try to coax a string of all 1's out through cross overs, mutations, and an increasing threshold of fitness.
'-- the three important parts are:
'-- -- 1.0 Fitness
'-- -- -- -- This is the measurement we judge each offspring and remove ones that are not up to par.
'-- -- -- -- This also slides to larger and larger numbers.. a static fitness only goes so far, but a sliding fitness prevents stagnation.
'-- -- 2.0 Cross over.
'-- -- -- -- This simulates the gene exchange from parents to off spring.
'-- -- -- -- Two randomly selected parents (of those who are deemed fit), have a random spot in their sequence selected.
'-- -- -- -- Parent1 donates the first half to this cross over point to the offspring.
'-- -- -- -- Parent2 donates the second half from the cross over point to the end of the sequence.
'-- -- 3.0 Mutation
'-- -- -- -- To keep things from stagnating further random mutations are introduced... this may take a super fit offspring down a peg, or might propel a mediocre one higher.
'-- -- -- -- A bit of randomness keeps things active, but too much destroys cohesion.
Public Sub Main()
_lMaxPopulation = 10 '-- how many rows
_lMaxNumberOfGenes = 10 '-- how many columns

_lFitnessThreshold = 6 '-- flexible, but six is good here.
_dMutationRate = 0.1

_alPopulation = New Int32(_lMaxPopulation, _lMaxNumberOfGenes) {}
_alFitness = New Int32(_lMaxPopulation) {}

'-- I like my random numbers juicy.
_r = New Random(DateTime.Now.Millisecond + DateTime.Now.Second + DateTime.Now.Minute + DateTime.Now.Hour + DateTime.Now.Day)

Dim temp As Int32 = 0
Dim numberOfGenerations As Int32 = 15 '-- how may rounds of off spring we want to create.

Console.WriteLine("----- Initial setup -----")
Console.WriteLine(String.Format("Max Population: {0}", _lMaxPopulation))
Console.WriteLine(String.Format("Max Number of Genes: {0}", _lMaxNumberOfGenes))
Console.WriteLine(String.Format("Fitness threshold: {0}", _lFitnessThreshold))
Console.WriteLine(String.Format("Mutation rate: {0}", _dMutationRate))

GeneratePopulation(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _r)
Print(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness)
GetFitnessStats(_lMaxPopulation, _alFitness)
Console.WriteLine(String.Format("Fitness threshold: {0}", _lFitnessThreshold))

While (temp < numberOfGenerations)
Console.WriteLine("=======================================")
Console.WriteLine("              Generation: " + temp.ToString)
Console.WriteLine("=======================================")

If _bDebug Then Console.WriteLine(Environment.NewLine + "----- Post Fitness Ordering -----")
OrderByFitness(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness)
If _bDebug Then Print(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness)

If _bDebug Then Console.WriteLine(Environment.NewLine + "----- Remove low fitness -----")
RemoveByFitness(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness, _lFitnessThreshold)
If _bDebug Then Print(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness)

If _bDebug Then Console.WriteLine(Environment.NewLine + "----- New Generation-----")
If DoCrossover(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness, _r) Then
Exit While
End If
If _bDebug Then Print(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness)

If _bDebug Then Console.WriteLine(Environment.NewLine + "----- Post Mutation -----")
DoMutation(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _r)
If _bDebug Then Print(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness)

Console.WriteLine("")
Console.WriteLine("-- New Population --")
Print(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness)
GetFitnessStats(_lMaxPopulation, _alFitness)
_lFitnessThreshold = UpdateFitnessThreshold(_lMaxPopulation, _lMaxNumberOfGenes, _alFitness, _lFitnessThreshold)
Console.WriteLine(String.Format("Fitness threshold: {0}", _lFitnessThreshold))

If CheckForWinner(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes, _alFitness) Then
Console.WriteLine("!!!MAX FOUND! !!")
Exit While
End If

temp += 1
End While

Stop
End Sub

''' <summary>
''' Randomly create a population of 1 and 0
''' </summary>
Private Sub GeneratePopulation(ByRef pop(,) As Int32, ByVal popMax As Int32, ByVal geneMax As Int32, ByVal r As Random)

For i As Int32 = 0 To popMax - 1
For z As Int32 = 0 To geneMax - 1
pop(i, z) = r.Next(2)
Next
Next

End Sub

''' <summary>
''' Prints out the population and the fitness of each row.
''' </summary>
Private Sub Print(ByRef pop(,) As Int32, ByVal popMax As Int32, ByVal geneMax As Int32, ByVal fitness() As Int32)
For i As Int32 = 0 To popMax - 1
For z As Int32 = 0 To geneMax - 1
Console.Write(String.Format("{0} ", pop(i, z)))
Next
Console.Write(String.Format(" : ({0}) {1}", fitness(i), Environment.NewLine))
Next
End Sub

''' <summary>
''' A simple scheme of adding up how many ones are in the row.
''' </summary>
Private Function GradeFitness(ByVal pop(,) As Int32, ByVal popMax As Int32, ByVal geneMax As Int32) As Int32()
Dim lFitness() As Int32 = New Int32(popMax) {}
Dim lTemp As Int32 = 0

For i As Int32 = 0 To popMax - 1
lTemp = 0
For z As Int32 = 0 To geneMax - 1
If pop(i, z) = 1 Then lTemp += 1
Next
lFitness(i) = lTemp
Next

Return lFitness
End Function

''' <summary>
''' Bubble sort the parents from best to worst.
''' </summary>
Private Sub OrderByFitness(ByRef pop(,) As Int32, ByVal popMax As Int32, ByVal geneMax As Int32, ByVal fitness() As Int32)
Dim lMax As Int32 = 0
Dim ltemp As Int32 = 0
Dim temp() As Int32 = New Int32(geneMax) {}

For i As Int32 = 0 To popMax - 1
For z As Int32 = i To popMax - 1
If fitness(z) > fitness(i) Then
ltemp = fitness(i)
fitness(i) = fitness(z)
fitness(z) = ltemp

For a As Int32 = 0 To geneMax - 1
temp(a) = pop(i, a)
Next

For a As Int32 = 0 To geneMax - 1
pop(i, a) = pop(z, a)
Next
For a As Int32 = 0 To geneMax - 1
pop(z, a) = temp(a)
Next

End If
Next

Next
End Sub

''' <summary>
''' If the solution doesn't meet the threshold zero it out.
''' </summary>
Private Sub RemoveByFitness(ByRef pop(,) As Int32, ByVal popMax As Int32, ByVal geneMax As Int32, ByVal fitness() As Int32, ByVal fitnessLevel As Int32)
For i As Int32 = 0 To popMax - 1
If fitness(i) < fitnessLevel Then
fitness(i) = 0
For z As Int32 = 0 To geneMax - 1
pop(i, z) = 0
Next
End If
Next
End Sub

''' <summary>
''' Take in our sorted, and passed fit threshold, population.  Randomly select two parents,select a cross over point, and exchange genes until the new population is created.
''' Does allow for both parents to be the same line.
''' Does not allow continuing if only one line is deemed fit.
''' </summary>
Private Function DoCrossover(ByRef pop(,) As Int32, ByVal popMax As Int32, ByVal geneMax As Int32, ByRef fitness() As Int32, ByVal r As Random) As Boolean
Dim bRet As Boolean = False '-- if there are not enough parents exit and let hte main loop know.

Dim newPop(,) As Int32 = New Int32(popMax, geneMax) {}

Dim lCrossoverPoint As Int32 = 0
Dim p1 As Int32 = 0
Dim p2 As Int32 = 0

Dim lMaxLoc As Int32 = 0
For i As Int32 = 0 To popMax - 1
If fitness(i) = 0 Then
Exit For
End If
lMaxLoc = i
Next

If lMaxLoc = 0 Then
Console.WriteLine("Busted! - not enough parents to produce offspring!")
bRet = True
Return bRet
End If
'-- keep grabbing parents until you have enough offspring
For i As Int32 = 0 To popMax - 1
lCrossoverPoint = r.Next(geneMax - 1) + 1

p1 = r.Next(lMaxLoc + 1)
p2 = r.Next(lMaxLoc + 1)

If _bDebug Then Console.WriteLine(String.Format("p1: {0}, p2: {1}, crossover: {2} ", p1, p2, lCrossoverPoint))

For z As Int32 = 0 To lCrossoverPoint - 1
newPop(i, z) = pop(p1, z)
Next

For z As Int32 = lCrossoverPoint To geneMax - 1
newPop(i, z) = pop(p2, z)
Next
Next

pop = newPop
fitness = New Int32(popMax) {}

Return bRet
End Function

''' <summary>
''' Go through each cell and determine if you want to flip a bit.  In other applications this could be adding to the cell value, subtracting, etc.
''' </summary>
Private Sub DoMutation(ByRef pop(,) As Int32, ByVal popMax As Int32, ByVal geneMax As Int32, ByVal r As Random)

Dim temp As Int32 = 0
Dim lTotalMutations As Int32 = 0

For i As Int32 = 0 To popMax - 1
For z As Int32 = 0 To geneMax - 1
If r.Next(100) < _dMutationRate * 100 Then
If pop(i, z) = 0 Then
pop(i, z) = 1
Else
pop(i, z) = 0
End If
lTotalMutations += 1
End If
Next
Next

Console.WriteLine("TotalMutations: " + lTotalMutations.ToString)
End Sub

''' <summary>
''' A little math to see how the generations are doing as they happen.
''' </summary>
Private Sub GetFitnessStats(ByVal popMax As Int32, ByVal fitness() As Int32)
Dim dRet As Decimal = 0

Dim lMax As Int32 = fitness(0)
Dim lMin As Int32 = fitness(0)

For i As Int32 = 0 To popMax - 1
dRet += fitness(i)

If fitness(i) > lMax Then lMax = fitness(i)
If fitness(i) < lMin Then lMin = fitness(i)
Next
Console.WriteLine(Environment.NewLine)
Console.WriteLine(String.Format("Average fitness: {0}", dRet / popMax))
Console.WriteLine(String.Format("min fitness: {0}", lMin))
Console.WriteLine(String.Format("max fitness: {0}", lMax))
End Sub

''' <summary>
''' The 'win' condition can be meeting a specific threshold, finding a value, or in this case having a whole line as 1s.
''' </summary>
Private Function CheckForWinner(ByVal pop(,) As Int32, ByVal popMax As Int32, ByVal geneMax As Int32, ByVal fitness() As Int32) As Boolean
Dim bReturn As Boolean = False

For i As Int32 = 0 To popMax - 1

If fitness(i) = geneMax Then
bReturn = True
Exit For
End If
Next

Return bReturn
End Function

''' <summary>
''' Get an average fitness and only increase the over all threshold if it exceeds the current value.  Always push for better generations!
''' </summary>
Private Function UpdateFitnessThreshold(ByVal popMax As Int32, ByVal geneMax As Int32, ByVal fitness() As Int32, ByVal fitnessThreshold As Int32) As Int32
Dim dRet As Decimal = 0
For i As Int32 = 0 To popMax - 1
dRet += fitness(i)
Next
dRet /= popMax

If dRet > fitnessThreshold Then
fitnessThreshold = Math.Floor(dRet)
End If

Return fitnessThreshold
End Function

Example run (with debugging turned on)
Spoiler

In a slightly more complex example - let's say I want to find solutions to: 145 = a^2 + 4b + 2c - d

Maybe this is a traveling equation, composite variables for materials, or parts of a strength equation for a structure. What ever the reason - I have an equation and I want to find values to fit into that solution.

- The fitness here is going to be determined by how close the numbers are to the solution (145). This means my fitness will be shrinking (hopefully) with each generation.
- I will keep the single point cross over in effect.
- The population will be positive and negative values from -10 to 10.
- Mutations are kept at 10%, but instead of flipping a value they will add (or subtract) a random value (up to five) from the cell.
- To help test fitness I built a small function that takes in an array and generates the outcome when put into the equation.

Spoiler

Spoiler

Pretty cool, eh?

There's a pretty high level over view of what genetic algorithms are all about. Sure there's a ton of tweaking for values, cross over methods, mutation methods, popluation generation methods, and that is fine. There are no real hard or fast rules outside of some general guidelines.

- Create a method to track lineage from the solution to the start.
- Apply this GAs to find various solutions to a small hash.
- When applying crossovers use a probability function for dominant and recessive at each cell/trait.

Is This A Good Question/Topic? 8

## Replies To: Intro to Genetic Algorithms

### #2 xclite

• I wrote you an code

Reputation: 1281
• Posts: 4,089
• Joined: 12-May 09

Posted 26 April 2013 - 09:54 AM

My browser seems to block Javascript at work, but I'l upvote later.

Genetic algorithms are tons of fun. The frustrating part can be the occasional challenge in finding a good representation that allows for crossover and mutation of the string.

Other fun stuff that can be played with to alter the time it takes to find an acceptable solution:
elite children (high scoring solutions get passed directly into the next generation)
culling before mutation/crossover (removes low fitness solutions from pool before selecting "parents").

Depending on the solution space and mutation probabilities, these can have an interesting impact on the fitness of each successive generation.

This post has been edited by xclite: 26 April 2013 - 09:55 AM

### #3 Smurphy

• D.I.C Regular

Reputation: 35
• Posts: 367
• Joined: 07-July 08

Posted 26 April 2013 - 02:11 PM

Cool article modi. One of my favorite assignments was using genetic algorithms to solve the knapsack problem. It is really amazing how natural selection and other biological traits can be assimilated into algorithms.

### #4 modi123_1

• Suitor #2

Reputation: 14094
• Posts: 56,469
• Joined: 12-June 08

Posted 26 April 2013 - 02:13 PM

Yeah.. directed bruce force optimization! Do you remember how you broke that problem down for better GA consumption?