What on Earth Is That?

Evolutionary computing is the application of evolutionary theory within the computing environment. It uses the principles of Darwinian Evolutionary Theory such as natural selection, reproduction, and mutation to breed progressively better solutions to a given problem.

A Sample Evolutionary Computing Framework

To understand how evolutionary principles may be applied to a computing problem, a framework is needed to define a set of roles:

1. The environment: The environment defines the problem that the evolutionary computing application is trying to solve. It is responsible for calculating the fitness of an individual and assigning the problem space meaning to the members of the gene set and for setting the constraints such as the baseline rate of gene mutation. Additional real-world constraints such as the control of the population size to optimise the use of the computer hardware are also supplied by the environment.
2. The population: The population represents a set of potential solutions to the problem. It can be created from a randomly generated, or seeded by a predefined set, of individuals
3. The individual (aka The genome): The genome defines the number of genes a member of a population has and their explicit locations. These locations have an explicit meaning in relation to the problem being tested by the environment and are not interchangeable

   When two (or more) individuals reproduce, the new gene set is populated by genes selected from one of the parent individuals at random. There is also the chance (controlled by the environment) that the genes themselves may be subject to mutation at this stage.

4. The gene: The gene holds the current value for an individual variable that is used to compute the gene set's fitness to solve the environment's problem

What Is It Used For?

Evolutionary computing is most useful when it is not immediately obvious how to solve a problem, but when it is possible to test the relative correctness of a solution.

The Framework Itself

The following bare bones framework defines the elements involved in an evolutionary programming solution:

IEnvironment: Defines the environment

'\\ --[IEnvironment]------------------------------
'\\  The environment defines the problem that the
'\\ evolutionary computing application
'\\ is trying to solve. It is responsible for
'\\ calculating the fitness of an individual
'\\ and assigning the problem space meaning to
'\\ the members of the gene set and for
'\\ setting the constrains such as the baseline
'\\ rate of gene mutation
'\\ ----------------------------------------------

Public MustInherit Class IEnvironment

   Public MustOverride Function GetPopulation() As IPopulation

   Public MustOverride Function GetHealth(ByVal TestIndividual _
                                          As IGenome) As Integer

   Public MustOverride Function Breed(ByVal Parents As IPopulation) _
                                      As IGenome

   Public MustOverride ReadOnly Property MutationRate() As Single

End Class

IPopulation: Defines a population of potential solutions

'\\ --[IPopulation]-------------------------------
'\\ The population represents a set of potential
'\\ solutions to the problem. It can be
'\\ created from a randomly generated, or seeded
'\\ by a predefined set, of individuals.
'\\ ----------------------------------------------

Public MustInherit Class IPopulation
   Inherits System.Collections.CollectionBase

#Region "Public constructors"
   Public Sub New()

   End Sub

   Public Sub New(ByVal Seedgroup() As IGenome)

   End Sub
#End Region
End Class

IGenome: Defines a single solution to a problem

'\\ --[IGenome]-----------------------------------
'\\  The genome defines the number of genes a 
'\\ member of a population has and their explicit 
'\\ locations. These locations have an explicit 
'\\ meaning in relation to the problem being 
'\\ tested by the environment and are not 
'\\ interchangeable
'\\ ----------------------------------------------
Public MustInherit Class IGenome

   Public MustOverride Function GetGene(ByVal GeneLocation _
                                        As Object) As IGene

End Class

IGene: Defines a single property of the proposed solution

'\\ --[IGene]-------------------------------------
'\\ The gene holds the current value for an
'\\ individual variable that is used to compute
'\\ the gene set's fitness to solve the
'\\ environment's problem
'\\ ----------------------------------------------
Public MustInherit Class IGene

   Public MustOverride Property Value() As Object

   Protected Overridable Function IsValueValid() As Boolean
      Return True
   End Function

End Class

Example: A Mastermind Solver

Mastermind is a game whereby you have to guess the colour and order of a set of pegs relying only on the correctness of past guesses. This example is a quick and dirty application to show how you might solve such a problem using the evolutionary computing framework

MastermindGene: The IGene implementation

Our simple game has eight possible peg colours that are described as an enumerated type.

'\\ --[MastermindGuessGene]-----------------------
'\\ Represents the IGene implementation that is a
'\\ single guess in the game of mastermind
'\\ ----------------------------------------------
Public Class MastermindGuessGene
   Inherits IGene

   Public Enum Peg_Colours
      White_Peg
      Black_Peg
      Green_Peg
      Blue_Peg
      Yellow_Peg
      Red_Peg
      Orange_Peg
      Brown_Peg
   End Enum

#Region "Private members"
   Private _PegColour As Peg_Colours
#End Region

   Public Overrides Property Value() As Object
      Get
         Return _PegColour
      End Get
      Set(ByVal Value As Object)
         If TypeOf (Value) Is Peg_Colours Then
            _PegColour = Value
         Else
            Throw New ArgumentException("Only acceptable value
                                         is one of the defined
                                         peg colours")
         End If
      End Set
   End Property

#Region "Public constructors"
   Public Sub New()
      '\\ Start with a peg colour chosen at random
      Randomize()
      _PegColour = CType(CInt(Int((7 * Rnd()))), Peg_Colours)
   End Sub

   Public Sub New(ByVal PegColour As Peg_Colours)
      _PegColour = PegColour
   End Sub
#End Region
End Class

MastermindGenome: IGenome implementation

This represents a single "guess" at the mastermind solution.

Public Class MastermindGenome
   Inherits IGenome

#Region "Private members"
   Private _MastermindGenes As New MastermindGeneCollection()
   Private _NumberOfPegHoles As Integer
#End Region

   Public Overrides Function GetGene(ByVal Location As Object) _
         As IGene
         Return _MastermindGenes.Item(CType(Location, Integer))
   End Function

#Region "Public constructors"
   Public Sub New(ByVal NumberOfPegHoles As Integer)

      If NumberOfPegHoles <= 1 Then
         Throw New ArgumentException("There must be at least 2 _
                                      peg holes", _
                                    "NumberOfPegHoles")
      ElseIf NumberOfPegHoles > 10 Then
         Throw New ArgumentException("There must be at most 10 _
                                       peg holes", _
                                     "NumberOfPegHoles")
      Else
         Dim nItem As Integer
         For nItem = 1 To NumberOfPegHoles
             _MastermindGenes.Add(New MastermindGuessGene())
         Next
         _NumberOfPegHoles = NumberOfPegHoles
      End If
   End Sub
#End Region

   Public ReadOnly Property Count() As Integer
      Get
         Return _MastermindGenes.Count
      End Get
   End Property

   Public ReadOnly Property NumberOfPegHoles() As Integer
      Get
         Return _NumberOfPegHoles
      End Get
   End Property

   Public Function Contains(ByVal TestColour _
                            As MastermindGuessGene.Peg_Colours) _
                            As Boolean
      Dim TestGene As MastermindGuessGene
      For Each TestGene In _MastermindGenes
         If TestGene.Value = TestColour Then
            Return True
         End If
      Next
   End Function

#Region "MastermindGeneCollection"
   '\\ --[MastermindGeneCollection]--------------
   '\\ A strongly typed collection of mastermind 
   '\\ guess genes
   '\\ ------------------------------------------
   Private Class MastermindGeneCollection
           Inherits CollectionBase

      Default Public Property Item(ByVal index As Integer) _
                                   As MastermindGuessGene
         Get
            Return CType(List(index), MastermindGuessGene)
         End Get
         Set(ByVal Value As MastermindGuessGene)
            List(index) = Value
         End Set
      End Property

      Public Function Add(ByVal value As MastermindGuessGene) _
             As Integer
         Return List.Add(value)
      End Function 'Add

      Public Function IndexOf(ByVal value As MastermindGuessGene) _
             As Integer
         Return List.IndexOf(value)
      End Function 'IndexOf

      Public Sub Insert(ByVal index As Integer, ByVal value _
                        As MastermindGuessGene)
         List.Insert(index, value)
      End Sub 'Insert

      Public Sub Remove(ByVal value As MastermindGuessGene)
         List.Remove(value)
      End Sub 'Remove

      Public Function Contains(ByVal value As MastermindGuessGene) _
             As Boolean
         ' If value is not of type MastermindGuessGene,
         ' this will return false.
         Return List.Contains(value)
      End Function 'Contains

      Protected Overrides Sub OnInsert(ByVal index As Integer, _
                ByVal value As [Object])
         ' Insert additional code to be run only when inserting
         ' values.
      End Sub 'OnInsert

      Protected Overrides Sub OnRemove(ByVal index As Integer, _
                ByVal value As [Object])
         ' Insert additional code to be run only when removing
         ' values.
      End Sub 'OnRemove

      Protected Overrides Sub OnSet(ByVal index As Integer, _
                ByVal oldValue As [Object], ByVal newValue As [Object])
         ' Insert additional code to be run only when setting
         ' values.
      End Sub 'OnSet

      Protected Overrides Sub OnValidate(ByVal value As [Object])
         If Not value.GetType() Is Type.GetType( _
            "Mastermind.MastermindGuessGene") Then
             Throw New ArgumentException("value must be of type _
                                          MastermindGuessGene.", _
                                         "value")
         End If
      End Sub 'OnValidate 

   End Class
#End Region

End Class

MastermindPopulation: IPopulation implementation

This is a breeding population of answers from which we are trying to find the mastermind solution.

'\\ --[MastermindGuessPopulation]-----------------
'\\ Represents the IPopulation implementation
'\\ that represents a the current guess
'\\ population of a game of mastermind in
'\\ progress...
'\\ ----------------------------------------------
Public Class MastermindGuessPopulation
   Inherits IPopulation

#Region "Private properties"
   Private _Genomes As New MastermindGenomeCollection()
#End Region

#Region "Public constructors"
   Public Sub New(ByVal PopulationSize As Integer, _
                  ByVal NumberOfPegholes As Integer)
      Dim nItem As Integer

      If PopulationSize <= 5 Then
         Throw New ArgumentException("There must be at least 5 _
                                      mastermind genomes in the _
                                      population", "PopulationSize")
      ElseIf PopulationSize > 1000 Then
         Throw New ArgumentException("There must be at most 1000 _
                                      mastermind genomes in the _
                                      population", "PopulationSize")
      Else
         For nItem = 1 To PopulationSize
            _Genomes.Add(New MastermindGenome(NumberOfPegholes))
         Next
      End If
   End Sub

   Public Sub New()

   End Sub
#End Region

#Region "Public properties"
   Default Public ReadOnly Property Item(ByVal index As Integer) _
         As MastermindGenome
      Get
         Return _Genomes.Item(index)
      End Get
   End Property

   Public ReadOnly Property PopulationSize() As Integer
      Get
         Return _Genomes.Count
      End Get
   End Property

   Public Function AddGenome(ByVal Genome As MastermindGenome)
      _Genomes.Add(Genome)
   End Function

   Public Sub Kill(ByVal index As Integer)
      _Genomes.RemoveAt(index)
   End Sub
#End Region

#Region "MastermindGenomeCollection"
   '\\ --[MastermindGeneCollection]--------------
   '\\ A strongly typed collection of mastermind 
   '\\ genomes
   '\\ ------------------------------------------
   Private Class MastermindGenomeCollection
           Inherits CollectionBase

      Default Public Property Item(ByVal index As Integer) _
              As MastermindGenome
         Get
            Return CType(List(index), MastermindGenome)
         End Get
         Set(ByVal Value As MastermindGenome)
             List(index) = Value
         End Set
      End Property

      Public Function Add(ByVal value As MastermindGenome) As Integer
         Return List.Add(value)
      End Function 'Add

      Public Function IndexOf(ByVal value As MastermindGenome) _
            As Integer
         Return List.IndexOf(value)
      End Function 'IndexOf

      Public Sub Insert(ByVal index As Integer, ByVal value _
                        As MastermindGenome)
         List.Insert(index, value)
      End Sub 'Insert

      Public Sub Remove(ByVal value As MastermindGenome)
         List.Remove(value)
      End Sub 'Remove

      Public Function Contains(ByVal value As MastermindGenome) _
             As Boolean
         ' If value is not of type MastermindGuessGene, this will
         ' return false.
         Return List.Contains(value)
      End Function 'Contains

      Protected Overrides Sub OnInsert(ByVal index As Integer, _
                ByVal value As [Object])
         ' Insert additional code to be run only when inserting
         ' values.
      End Sub 'OnInsert

      Protected Overrides Sub OnRemove(ByVal index As Integer, _
                ByVal value As [Object])
         ' Insert additional code to be run only when removing
         ' values.
      End Sub 'OnRemove

      Protected Overrides Sub OnSet(ByVal index As Integer, _
                                    ByVal oldValue As [Object], _
                                    ByVal newValue As [Object])
         ' Insert additional code to be run only when setting values.
      End Sub 'OnSet

      Protected Overrides Sub OnValidate(ByVal value As [Object])
         If Not value.GetType() Is _
            Type.GetType("Mastermind.MastermindGenome") Then
            Throw New ArgumentException("value must be of type _
                                         MastermindGenome.", _
                                        "value")
         End If
      End Sub 'OnValidate 

   End Class
#End Region

End Class

MastermindEnvironment: IEnvironment implementation

This defines the rules by which a game of mastermind can be solved.

'\\ --[ManstermindEnvironment]--------------------
'\\ Represents the IEnvironment implementation 
'\\ that represents a game
'\\ of mastermind in progress...
'\\ ----------------------------------------------
Public Class MastermindEnvironment
   Inherits EvolutionaryComputingFramework.IEnvironment

#Region "Private properties"
   Private _CorrectGuess As MastermindGenome
   Private _Population As MastermindGuessPopulation
   Private _MaxScore As Integer
   Private _HealthiestIndividual As MastermindGenome
#End Region

#Region "Private constants"
   Private _PointsForRightColourWrongPosition As Int32 = 5
   Private _PointsForRightColourRightPosition As Int32 = 50
#End Region

#Region "IEnvironment implementation"
   Public Overrides Function GetPopulation() As IPopulation
      If Not _Population Is Nothing Then
         Return _Population
      Else
         Throw New InvalidOperationException("The population has _
                                              not been created yet")
      End If
   End Function

   Public Overrides Function GetHealth(ByVal TestIndividual _
                                       As IGenome) As Integer
      If Not TestIndividual.GetType() Is Type.GetType( _
            "Mastermind.MastermindGenome") Then
          Throw New ArgumentException("TestIndividual must be of _
                type MastermindGenome.", "value")
      Else
         Dim CumulativeScore As Integer
         '\\ Go through each GuessGene in the test individual
         Dim NextGuessPosition As Integer
         Dim GuessIndividual As MastermindGenome
         GuessIndividual = CType(TestIndividual, MastermindGenome)
         For NextGuessPosition = 0 To GuessIndividual.Count - 1
            '\\ If it is the right colour in the right place
            '\\ add points for that
            If GuessIndividual.GetGene(NextGuessPosition).Value +
               = _CorrectGuess.GetGene(NextGuessPosition).Value Then
               CumulativeScore += _PointsForRightColourRightPosition
            Else
               '\\ Otherwise if it is the right colour in the
               '\\ wrong place add points for that
               If _CorrectGuess.Contains(GuessIndividual.GetGene _
                                        (NextGuessPosition).Value) Then
                   CumulativeScore += _PointsForRightColourWrongPosition
               End If
            End If
         Next NextGuessPosition
         Return CumulativeScore
      End If
   End Function

   Public Overrides Function Breed(ByVal Parents As IPopulation) _
         As IGenome
      '\\ Currently our "mastermind species" only breeds from two
      '\\ parents.
      '\\ Future versions can have this configurable to measure
      '\\ the effect of increasing the parental pool.
      Dim GenomeOut As New MastermindGenome(_CorrectGuess.NumberOfPegHoles)
      '\\ Make Genome out by selecting (at random) a dominant
      '\\ gene from each of the two parents
      Dim ParentOne As MastermindGenome = CType(Parents, _
          MastermindGuessPopulation).Item(0)
      Dim ParentTwo As MastermindGenome = CType(Parents, _
          MastermindGuessPopulation).Item(1)
      Dim GeneIndex As Integer
      For GeneIndex = 0 To GenomeOut.NumberOfPegHoles - 1
          If Rnd() <= MutationRate Then
             GenomeOut.GetGene(GeneIndex).Value = New _
                   MastermindGuessGene().Value
          Else
             If Rnd() < 0.5 Then
                GenomeOut.GetGene(GeneIndex).Value = _
                ParentOne.GetGene(GeneIndex).Value
             Else
                GenomeOut.GetGene(GeneIndex).Value = _
                ParentTwo.GetGene(GeneIndex).Value
             End If
         End If
      Next
      Return GenomeOut

   End Function

   Public Overrides ReadOnly Property MutationRate() As Single
      Get
         Return 0.1
      End Get
   End Property

#End Region

#Region "Public constructors"
   Public Sub New(ByVal PopulationSize As Integer, _
                  ByVal CorrectGuess As MastermindGenome)
      _CorrectGuess = CorrectGuess
      _Population = New MastermindGuessPopulation(PopulationSize, _
                        CorrectGuess.NumberOfPegHoles)
      _MaxScore = CorrectGuess.NumberOfPegHoles * _
                  _PointsForRightColourRightPosition
   End Sub
#End Region

#Region "Public properties"
   Public ReadOnly Property MaximumScore() As Integer
      Get
         Return _MaxScore
      End Get
   End Property

   '\\ --[NextGeneration]------------------------
   '\\ Evaluates the health of each individual 
   '\\ in the current population, 
   '\\ killing off the least healthy and 
   '\\ breeding from the rest
   '\\ ------------------------------------------
   Public Sub NextGeneration()

      If _Population.PopulationSize = 0 Then
         Throw New Exception("The population is extinct")
      Else
         Dim GenomeHealth As Integer
         Dim TotalHealth As Integer
         _HealthiestIndividual = Nothing
         Dim TestGenome As Integer
         For TestGenome = 0 To _Population.PopulationSize - 1
            If _HealthiestIndividual Is Nothing Then
               _HealthiestIndividual = _Population.Item(TestGenome)
               TotalHealth = GetHealth(_Population.Item(TestGenome))
            Else
               GenomeHealth = GetHealth(_Population.Item(TestGenome))
               If GenomeHealth > GetHealth(_HealthiestIndividual) Then
                   _HealthiestIndividual = _Population.Item(TestGenome)
               End If
                  TotalHealth = TotalHealth + GenomeHealth
            End If
         Next
         Dim Averagehealth As Integer = TotalHealth / _
            _Population.PopulationSize
         Dim MaxIndex As Integer = _Population.PopulationSize - 1
         For TestGenome = 0 To MaxIndex
            If TestGenome > MaxIndex Then
               Exit For
            End If
            GenomeHealth = GetHealth(_Population.Item(TestGenome))
            If GenomeHealth < Averagehealth OrElse GenomeHealth = 0 Then
               _Population.Kill(TestGenome)
               MaxIndex = MaxIndex - 1
            End If
         Next
         For TestGenome = 0 To _Population.PopulationSize - 2 Step 2
            Dim Parents As New MastermindGuessPopulation()
            Parents.AddGenome(_Population.Item(TestGenome))
            Parents.AddGenome(_Population.Item(TestGenome + 1))
            _Population.AddGenome(Breed(Parents))
         Next
      End If

   End Sub

   Public ReadOnly Property BestGuess() As MastermindGenome
      Get
         Return _HealthiestIndividual
      End Get
   End Property
#End Region

End Class