Page 1 of 1

Intro to Genetic Algorithms Rate Topic: ***** 1 Votes

#1 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9205
  • View blog
  • Posts: 34,583
  • 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)
        _alFitness = GradeFitness(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes)
        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 --")
            _alFitness = GradeFitness(_alPopulation, _lMaxPopulation, _lMaxNumberOfGenes)
            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.

Advanced topics:
- 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? 7
  • +

Replies To: Intro to Genetic Algorithms

#2 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,170
  • 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

Was This Post Helpful? 0
  • +
  • -

#3 Smurphy  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 35
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#4 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9205
  • View blog
  • Posts: 34,583
  • 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?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1