Evolutionary Computing Framework

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.

Evolutionary Computing Framework

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
```

Evolutionary Computing Framework

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()
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
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

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
```

Evolutionary Computing Framework

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
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)
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

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
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()
Next
End If

End Sub

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

End Class
```