Tutorial guide: Learn Python basics

Hi ok, here are my own notes on the basics of Python. I am working on a Udemy course on data science and got excited about Python(it has been while since I’ve done something cool with Python, so I am excited 🙂 ). This is based on the Udemy course https://www.udemy.com/data-science-and-machine-learning-with-python-hands-on

Where it goes, hope it helps.

You can run python code as scripts or as a python notebook.

 

Running a script from a command prompt:

python “your script file location and name”

 

Basic basics

 

List definition:

listOfNumbers = [1, 2, 3, 4, 5, 6]

 

Iteration through a list of items:

for number in listOfNumbers:

print number,

if (number % 2 == 0):

print “is even”

else:

print “is odd”

 

#Notice: In python you differentiate between blocks of code by whitespace, or a tab. Not the same as let say Java or C# where the char { and } are used to differentiate a block of code. Pay attention to you formatting, indentation.

 

#Notice: The char , (comma) is used to tell that something is going to continue on the same print line, within the same block of code. See example above.

 

#Notice: Colons : differentiate clauses.

 

Importing modules

 

import numpy as np

 

A = np.random.normal(25.0, 5.0, 10)

print A

 

Data structures

 

Lists

 

Defining a list(Notice: The brackets [] define an mutable list):

x = [1, 2, 3, 4, 5, 6]

 

Printing the length of a list:

print len(x)

 

Sub setting lists:

 

First 3 elements(counting starts from zero):

x[:3]

 

Last 3 elements:

x[3:]

 

Last two elements from starting from the end of the list:

x[-2:]

 

Extend the list with a new list :

x.extend([7,8])

 

Add a new item to the list:

x.append(9)

 

Python is a weekly typed language which allows you to put whatever you want in a list:

 

Creating a multidimensional list:

y = [10, 11, 12]

listOfLists = [x, y]

listOfLists

 

Sort a list(descending):

z = [3, 2, 1]

z.sort()

 

Sort a list(ascending):

z.sort(reverse=True)

 

Tuples

 

Are just like lists but immutable.

You can not extend them append them, sort them etc. You can not change them.

 

Example:

 

#Tuples are just immutable lists. Use () instead of []

x = (1, 2, 3)

len(x)

 

y = (4, 5, 6)

 

listOfTuples = [x, y]

 

Tuples common usage for data science or data processing:

Is to use it to assign variables to input data that as it is read in.

 

This example creates variable with values from a “source” where data is split by the comma.

#Notice: It is important that you have the same about of variables in your tuple as you are retrieving/assigning from the data “source”.

(age, income) = “32,120000”.split(‘,’)

print age

print income

 

Dictionaries

 

A way to define a “lookup” table:

 

# Like a map or hash table in other languages

captains = {}

captains[“Enterprise”] = “Kirk”

captains[“Enterprise D”] = “Picard”

captains[“Deep Space Nine”] = “Sisko”

captains[“Voyager”] = “Janeway”

 

print captains[“Voyager”]

 

print captains.get(“Enterprise”)

 

for ship in captains:

print ship + “: ” + captains[ship]

 

If something is not found the result will be none:

print captains.get(“NX-01”)

 

Functions

 

Let you repeat a set of operation over and over again with different parameters.

 

Notice: use def to define a function and  () chars to define the parameters and use the return keyword to return value from the function.

 

def SquareIt(x):

return x * x

 

print SquareIt(2)

 

Pass functions around as parameters

#Notice: You have to make sure that what you are typing is correct because there is no strong typing in Python. Typing the wrong function name will cause errors.

 

#You can pass functions around as parameters

def DoSomething(f, x):

return f(x)

 

print DoSomething(SquareIt, 3)

 

Lambda functions

Is Functional programming: You can inline a function into a function

 

#Notice: lambda keyword is telling that you are defining a inline function to be used where you put it. In the example below inside a function parameter named x followed by a colon : character followed by what the function actually does. To pass in multiple parameters to a lambda function use the comma , to separate the variables.

 

#Lambda functions let you inline simple functions

print DoSomething(lambda x: x * x * x, 3)

 

Boolean Expressions

 

Valye is false

print 1 == 3

 

Value is true(or keyword check which is true)

print (True or False)

 

Check if something is a certain value( Use the is keyword)

print 1 is 3

 

If else clauses

 

if 1 is 3:

print “How did that happen?”

elif 1 > 3:

print “Yikes”

else:

print “All is well with the world”

 

Looping

 

Normal looping

for x in range(10):

print x,

 

Continue and Break

 

#Process only the first 5 items but skip the number one

for x in range(10):

if (x is 1):

continue

if (x > 5):

break

print x,

 

While

 

x = 0

while (x < 10):

print x,

x += 1

 

 

Advertisements

Learning AI – Part 4: Neural Networks Introduction and more

Contents

Intro. 4

Demos. 4

Minesweepers – Unsupervised learning Neural Network example. 5

Sweepers – NEAT – Neuro Evolution of Augmenting Topologies Neural Network example. 5

Basics. 6

Architecture. 6

The Artificial Neuron. 7

Design decisions. 7

Types of neural networks. 8

Single Layer Feedforward Network. 9

Multilayer Feedforward Network. 9

Recurrent Networks. 9

CHARACTERISTICS OF NEURAL NETWORKS. 9

TAXONOMY OF NEURAL NETWORK ARCHITECTURES. 10

Classification of NN systems with respect to learning methods and architecture types. 10

Neural network anatomy. 11

The Perceptron. 12

Perceptron processing steps. 12

Neuron. 13

Pattern recognition example. 16

How many hidden neurons. 16

Bias. 16

Neural Network learning methods. 23

Supervised Learning. 23

Backpropagation. 23

How Does Backpropagation Work. 23

Learn quicker and generalize better. 25

Adding Momentum.. 25

Overfitting. 28

Softmax Activation Function. 28

Unsupervised Learning. 29

Reinforcement Learning. 30

Classification of learning algorithms. 31

Activation methods. 32

Thresholding function. 32

Signum function. 34

Sigmoidal function. 36

Hyperbolic tangent function. 38

Evolving networks. 38

Offline. 38

Online. 39

Evolving Neural Network Topology. 39

Requirements and problems of neural networks. 39

Desired requirements. 39

Problems. 39

Competing Conventions Problem.. 40

Possible solutions attempts. 40

Constructive or destructive networks. 40

EANN – Evolutionary Artificial Neural Network. 41

Direct Encoding. 41

GENITOR. 41

Binary Matrix Encoding. 41

Some Related Problems. 42

Node-Based Encoding. 42

Path-Based Encoding. 43

Indirect Encoding. 44

Grammar-Based Encoding. 44

Bi-Dimensional Growth Encoding. 44

Promising solution: NEAT – Neuro Evolution of Augmenting Topologies. 45

NEAT genome. 45

Genetic Encoding. 47

Node link types. 51

Tracking Genes through Historical Markings. 52

How Innovations Help in the Design of a Valid Crossover Operator. 55

Protecting Innovation through Speciation. 56

The Genome Loop. 59

Minimizing Dimensionality through Complexification. 60

Neural network uses. 60

Tips and thoughts. 61

My own observations on Neural Networks. 61

Tips. 62

Bibliography. 63

 

Intro

 

This is going to be another long blog post. Mostly this is just my notes on different sources of information regarding Neural Networks. These are my bits of information which helped me understand Neural Networks. I did not feel like trying to minimize the explanations in the sources I was reading and learning since they seemed already strict and straightforward.

The code examples here will be based on the sample projects found in the book AI Game Programming Techniques by (Buckland, 2002 ). They are written in C# and running on Unity.

I’ll start off with the sample projects to give you an idea what can be done. Then this post will move onto theory where hopefully you will find a better understanding of how Neural Networks work.

Also I will not be showing off most of the code in these example because there is literally thousands of lines of code. It would be too big of a job to go through each functionality bit by bit. The idea for this post is to give you an idea on what Neural Networks are and how they work. You can look at the sample code and figure out for yourself what is what. If you are new to the subject like me then probably this would be the best approach to learn, to go through the code and alter it, play with it. And again the code is just demo code. It is rough and ugly in some parts, so do not expect at this moment anything “proper” or good quality code. I am just learning and sharing what I have learned so far. I leave it to you the reader to clean and optimize if you chose so.

As before I am on a learning process so please forgive my mistakes and if you have the time you can comment and correct me. I’ll gladly learn from my mistakes :). Thank you in advance and hope you find some useful information here.

In the next upcoming posts on AI I will cover Fuzzy Logic, Autonomous Agents and maybe Cellular Automata. For now this is enough :).

Previous posts in this series:

https://lionadi.wordpress.com/projects/learning-ai-skynet/

Source code:

The source codes for the Neural Network examples and general code I was playing around can be found here: https://github.com/lionadi/NatureOfCodePlayground/tree/master/AIEngineNew

For the NEAT Sweepers the main code is located here: https://github.com/lionadi/NatureOfCodePlayground/tree/master/AIEngineNew/Assets/Scripts/AI/NeuralNetworks/NEAT

For the Minesweepers NN example here:

https://github.com/lionadi/NatureOfCodePlayground/tree/master/AIEngineNew/Assets/Scripts/AI/NeuralNetworks

https://github.com/lionadi/NatureOfCodePlayground/tree/master/AIEngineNew/Assets/Scripts/AI/GeneticAlgorithms

The rest of the code with central controller and sweepers main logic are here:

https://github.com/lionadi/NatureOfCodePlayground/tree/master/AIEngineNew/Assets/Scripts

Demos

Both demos represent a competitive unsupervised learning Neural Network example.

Notice that the fitness functions on these examples used to evolve the neural networks are incomplete. There are still some bugs and inefficiencies which I did not want to work at. They worked “ok” for this learning process. So do not wonder if there are weirdness with how the sweepers behave.

Minesweepers – Unsupervised learning Neural Network example

minesweepers screen

This first demo is about sweepers which main function is to seek and collect as many mines as possible. The fitness function in this example will consist of the following factor which will determine the quality of a neural network and hence the best minesweeper. In other words the fitness of a sweeper is determined by the following factor:

  1. How many mines the sweeper has collected
  2. In how many different portions of the game area has the sweeper been
  3. Has it hit obstacles and how many will determine for a better or worse fitness, the more obstacles hit the worse the fitness
  4. Also the code will prefer sweepers which do not rotate in their place(this is due to how the sweepers move)

The sweepers move using to tracks, left and right. The Neural Network will take inputs which will determine the two outputs for the left and right track which will give a speed and rotational force. The inputs are:

  1. Data where the sweeper has been
  2. Data where the sweeper is heading such as is it hitting something and how close to the obstacle it is
  3. Data where the closes mine to collect is
  4. Data has the sweeper hit an obstacle

Sweepers will be color coded:

  1. White: The ones with the color white or white trails are neutral, they are average performers
  2. Green: Are within the top 10 performers
  3. Yellow: Top 5 performers
  4. Red: The best sweeper presently

The neural network is by design a feedforward network using unsupervised learning.

This is the main function which runs X amount of times operating on each sweepers to update it. The final steps after each iteration is to evolve the sweepers genomes to make them more “intelligent”.


/// &amp;lt;summary&amp;gt;
 /// This is the main workhorse. The entire simulation is controlled from here.
 /// This method is called each frame. The first half of the function iterates through the
 /// minesweepers, calling their update functions and updating the minesweepers’ fitness
 /// scores if a mine has been found.In addition, because m_vecThePopulation contains
 /// copies of all the genomes, the relevant fitness scores are adjusted here too.If the
 /// required number of frames has passed for the completion of a generation, the
 /// method runs an epoch of the genetic algorithm producing a new generation of
 /// weights.These weights are used to replace the old weights in the minesweeper’s
 /// neural nets and each minesweeper’s parameters are reset ready for a new generation.
 /// &amp;lt;/summary&amp;gt;
 /// &amp;lt;returns&amp;gt;&amp;lt;/returns&amp;gt;
 public bool PerformCalculations()
 {
 //run the sweepers through NeuralNetworkParams.NumTicks amount of cycles. During
 //this loop each sweepers NN is constantly updated with the appropriate
 //information from its surroundings. The output from the NN is obtained
 //and the sweeper is moved. If it encounters a mine its fitness is
 //updated appropriately,
 if (this.Ticks++ &amp;lt; NeuralNetworkParams.NumTicks)
 {
 for (int i = 0; i &amp;lt; NeuralNetworkParams.NumSweepers; ++i)
 {
 // TODO_: Optimize this by passing the targets and not collecting the positions
 var minePositions = (from mine in Mines
 select new Vector2(mine.transform.position.x, mine.transform.position.y)).ToList();
 //-----------------------------------------------------


 //update the NN and position
 if (!this.Sweepers[i].UpdateANN(minePositions))
 {
 //error in processing the neural net
 Debug.Log("Wrong amount of NN inputs!");

 return false;
 }

 //see if it's found a mine
 int GrabHit = this.Sweepers[i].CheckForMine(minePositions,
 NeuralNetworkParams.MineScale);

 // Fitness calculation for a sweeper
 // ----------------------------------------
 if (GrabHit &amp;gt;= 0)
 {
 //we have discovered a mine so increase fitness
 this.Sweepers[i].IncrementFitness();

 //mine found so replace the mine with another at a random 
 //position
 this.Mines[GrabHit].transform.position = GetNewMineLocation();
 }

 // increase the fitness by a ratio of total cells visited compared to total cells in memory map. In other words the more adventurous the sweeper is the better fitness score, the more new locations it explores the better fitness.
 if(this.Sweepers[i].GetNumberOfVisitedCellsInMemoryMap() &amp;gt; 0)
 this.Sweepers[i].IncrementFitness(this.Sweepers[i].GetRatioOfNumberOfVisitedCellsInMemoryMap());

 // Prefer sweepers which do not hit obstacles
 if (!this.Sweepers[i].HasHitObstacle)
 this.Sweepers[i].IncrementFitnessMediumImpact();

 // Prefer sweepers which do not rotate like crazy
 if(this.Sweepers[i].Rotation &amp;gt; -this.Sweepers[i].RotationTolerance &amp;amp;&amp;amp; this.Sweepers[i].Rotation &amp;lt; this.Sweepers[i].RotationTolerance)
 this.Sweepers[i].IncrementFitnessMediumImpact();

 // ----------------------------------------

 //update the chromos fitness score
 this.ThePopulation[i].Genome.Fitness = this.Sweepers[i].Fitness;

 }
 }

 //Another generation has been completed.

 //Time to run the GA and update the sweepers with their new NNs
 else
 {
 this.ThePopulation = this.GA.ProcessToNextGeneration(this.ThePopulation);

 //update the stats to be used in our stat window
 this.AverageFitnessValuesInGeneration.Add(this.GA.AverageFitness());
 this.BestFitnessValuesInGeneration.Add(this.GA.BestFitness());
 Debug.Log("This Gen average=&amp;gt; " + this.AverageFitnessValuesInGeneration[this.AverageFitnessValuesInGeneration.Count - 1]);
 Debug.Log("This Gen best=&amp;gt; " + this.BestFitnessValuesInGeneration[this.BestFitnessValuesInGeneration.Count - 1]);
 StringBuilder sb = new StringBuilder();
 foreach (double d in this.AverageFitnessValuesInGeneration)
 sb.AppendFormat("{0};", d);
 sb.AppendLine();
 foreach (double d in this.BestFitnessValuesInGeneration)
 sb.AppendFormat("{0};", d);
 sb.AppendLine();
 Debug.Log(sb.ToString());

 //increment the generation counter
 ++this.Generations;

 //reset cycles
 this.Ticks = 0;

 //run the GA to create a new population
 

 //insert the new (hopefully)improved brains back into the sweepers
 //and reset their positions etc
 for (int i = 0; i &amp;lt; NeuralNetworkParams.NumSweepers; ++i)
 {
 this.Sweepers[i].PutWeights(ref this.ThePopulation[i].Genome.Chromosomes);

 this.Sweepers[i].Reset();
 }
 }

 foreach (Minesweeper mineS in this.Sweepers)
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.white;

 foreach (Minesweeper mineS in this.Sweepers.OrderByDescending(o =&amp;gt; o.Fitness).Take(10))
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.green;

 foreach (Minesweeper mineS in this.Sweepers.OrderByDescending(o =&amp;gt; o.Fitness).Take(5))
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.yellow;

 foreach (Minesweeper mineS in this.Sweepers.OrderByDescending(o =&amp;gt; o.Fitness).Take(1))
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.red;

 return true;
 }



This is the sweepers main update function. Here the function gathers and calculates world related data before and after the  data is inserted as inputs to neural network.


public bool UpdateANN(List&amp;lt;Vector2&amp;gt; mines)
 {
 this.acceleration = Vector2.zero;
 this.velocity = Vector2.zero;
 //this.Rotation = 0;
 //Debug.Log("Before: UpdateANN start");

 //this will store all the inputs for the NN
 List&amp;lt;double&amp;gt; inputs = new List&amp;lt;double&amp;gt;();
 //this.Rotation = UnityEngine.Random.Range(0, AIConstants.TWO_PI);
 /*
 First of all, the function calculates a vector to the closest mine and then normalizes
 it. (Remember, when a vector is normalized its length becomes 1.) The
 minesweeper’s look-at vector doesn’t need to be normalized in this way because its
 length is always 1. Because both vectors have been effectively scaled to within the
 same limits, the inputs can be considered to be standardized.
 */
 //get vector to closest mine
 Vector2 vectorClosestMine = GetClosestMine(mines);

 //normalise it
 vectorClosestMine.Normalize();

 float dot = Vector2.Dot(this.LookAt, vectorClosestMine);
 int sign = -1;

 if (this.LookAt.y * vectorClosestMine.x &amp;gt; this.LookAt.x * vectorClosestMine.y)
 {
 sign = 1;
 }
 else
 {
 sign = -1;
 }

 /*
 The look-at vector and the vector to the closest mine are then input into the neural
 network. The NeuralNet Update function updates the minesweeper’s network with
 this information and returns a List of doubles as the output.
 */

 //add in vector to closest mine
 //inputs.Add(vectorClosestMine.x);
 //inputs.Add(vectorClosestMine.y);

 //add in sweepers look at vector
 //inputs.Add(this.LookAt.x);
 //inputs.Add(this.LookAt.y);
 //if (HasHitObstacle)
 //{
 // int y = 0;
 // Debug.Log("#####################################################");
 // Debug.Log(dot);
 // Debug.Log("item count: " + this.sweeperCollisionSensorData.Count);
 // foreach (double d in this.sweeperCollisionSensorData)
 // Debug.Log("sw: " + d);
 //}

 // TODO: Add mines to the neural network
 //inputs.Add(dot*sign);
 inputs.Add(dot * sign);
 inputs.Add(this.HasHitObstacle ? 1 : 0);
 inputs.AddRange(this.sweeperCollisionSensorData);
 inputs.AddRange(this.sweeperMemoryMapSensorData);

 //Debug.Log("update the brain and get feedback");
 //update the brain and get feedback
 List&amp;lt;double&amp;gt; output = this.Brain.Update(inputs);


 //make sure there were no errors in calculating the 
 //output
 if (output.Count &amp;lt; NeuralNetworkParams.NumOutputs)
 {
 return false;
 }


 //assign the outputs to the sweepers left &amp;amp; right tracks
 this.LeftTrack = output[0];
 this.RightTrack = output[1];

 /*
 After checking to make sure there are no errors when updating the neural network,
 the program assigns the outputs to LeftTrack and RightTrack. These values represent the
 forces being exerted on the left track and right track of the minesweeper.
 */

 //calculate steering forces
 double RotForce = this.LeftTrack - this.RightTrack;

 //clamp rotation
 Mathf.Clamp((float)RotForce, -(float)NeuralNetworkParams.MaxTurnRate, (float)NeuralNetworkParams.MaxTurnRate);

 /*
 The vehicle’s rotational force is calculated by subtracting the force exerted by the
 right track from the force exerted by the left track. This is then clamped to make
 sure it doesn’t exceed the maximum turn rate specified in the ini file. The vehicle’s
 speed is simply the sum of the left track and right track. Now that we know the
 minesweeper’s rotational force and speed, its position and rotation can be updated
 accordingly.
 */

 //update the minesweepers rotation
 this.Rotation += RotForce;
 //if (Rotation &amp;lt; 0)
 // Rotation = AIConstants.TWO_PI;

 //if (Rotation &amp;gt; AIConstants.TWO_PI)
 // Rotation = 0;

 if (this.HasHitObstacle)
 {
 this.Rotation += RotForce * 100;
 }

 this.Speed = (this.LeftTrack + this.RightTrack);
 if (this.Speed &amp;gt; NeuralNetworkParams.MaxSpeed)
 this.Speed = NeuralNetworkParams.MaxSpeed;
 //this.Speed *= 0.5f;
 //update Look At 

 this.LookAt.x = Mathf.Cos((float)this.Rotation);
 this.LookAt.y = -Mathf.Sin((float)this.Rotation);

 this.acceleration += (this.LookAt * (float)this.Speed);
 this.velocity += this.acceleration;
 var previousPosition = this.transform.position;

 var newPosition = previousPosition + (Vector3)this.velocity;
 var movementThisStep = newPosition - previousPosition;
 var movementLastStep = previousPosition - this.sweeperLastPosition;
 var previousPositionContinuedDirection = (previousPosition + movementLastStep) - previousPosition;
 var forward = transform.forward;
 float angle = Vector3.Angle(movementThisStep, previousPositionContinuedDirection);
 // Rotate the object towards the movement direction. NOTICE: the -90 degree turn is to point the sprite to the right direction
 transform.rotation = Quaternion.Euler(new Vector3(0, 0, (Mathf.Atan2(movementThisStep.y, movementThisStep.x) * Mathf.Rad2Deg) + -90));
 var movementThisStepSensorLength = movementThisStep * 4;

 this.DetectObstacles(previousPosition, movementThisStepSensorLength);
 this.ProcessMemoryMapWithSensors(previousPosition, movementThisStepSensorLength);


 // Move the object only if it has not hitted any obstacles
 if (!this.HasHitObstacle)
 {
 this.transform.position += (Vector3)this.velocity;


 //wrap around window limits
 if (this.transform.position.x &amp;gt; maxScreenTopRight.x)
 this.transform.position = new Vector3(minScreenBottomLeft.x, this.transform.position.y, 0);
 if (this.transform.position.x &amp;lt; minScreenBottomLeft.x)
 this.transform.position = new Vector3(maxScreenTopRight.x, this.transform.position.y, 0);
 if (this.transform.position.y &amp;gt; maxScreenTopRight.y)
 this.transform.position = new Vector3(this.transform.position.x, minScreenBottomLeft.y, 0);
 if (this.transform.position.y &amp;lt; minScreenBottomLeft.y)
 this.transform.position = new Vector3(this.transform.position.x, maxScreenTopRight.y, 0);
 this.sweeperLastPosition = previousPosition;
 }

 //if (this.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color == Color.red || this.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color == Color.yellow || this.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color == Color.magenta)
 {
 Debug.DrawRay(previousPosition, movementThisStep, this.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color, 1.7f);


 // Draw rays from current new position forward, this can be used for collision detection
 //--------------------------------------------------------

 // Points forward
 Debug.DrawRay(this.transform.position, movementThisStepSensorLength, Color.green);

 var sensorIn45DegreeForwardAngle = Quaternion.Euler(0, 0, 45) * movementThisStepSensorLength;
 var sensorInMinus45DegreeForwardAngle = Quaternion.Euler(0, 0, -45) * movementThisStepSensorLength;
 // Point 45 degrees forward
 Debug.DrawRay(this.transform.position, sensorIn45DegreeForwardAngle, Color.cyan);
 Debug.DrawRay(this.transform.position, sensorInMinus45DegreeForwardAngle, Color.cyan);

 var sensorIn90DegreeForwardAngle = Quaternion.Euler(0, 0, 90) * movementThisStepSensorLength;
 var sensorInMinus90DegreeForwardAngle = Quaternion.Euler(0, 0, -90) * movementThisStepSensorLength;
 // Points to the side of the object
 Debug.DrawRay(this.transform.position, sensorIn90DegreeForwardAngle, Color.yellow);
 Debug.DrawRay(this.transform.position, sensorInMinus90DegreeForwardAngle, Color.yellow);

 // Points backwards
 Debug.DrawRay(this.transform.position, movementThisStepSensorLength * -1, Color.red);


 //--------------------------------------------------------
 }

 this.MemoryMap.Update(this.transform.position.x, this.transform.position.y);
 return true;
 }


This is the neural network update function which will generate the outputs for a sweepers based on the inputs.


/// &amp;lt;summary&amp;gt;
 /// Calculates the outputs from a set of inputs. Is the main workhorse of the neural network.
 /// The Update function then
 /// loops through each layer processing each neuron summing up the inputs×weights
 /// and calculating each neuron’s activation by putting the total through the sigmoid
 /// function.
 /// &amp;lt;/summary&amp;gt;
 /// &amp;lt;param name="inputs"&amp;gt;&amp;lt;/param&amp;gt;
 /// &amp;lt;returns&amp;gt; Returns a list of values that correspond to the outputs from the ANN.&amp;lt;/returns&amp;gt;
 public List&amp;lt;double&amp;gt; Update(List&amp;lt;double&amp;gt; inputs)
 {
 //stores the resultant outputs from each layer
 List&amp;lt;double&amp;gt; outputs = new List&amp;lt;double&amp;gt;();

 int cWeight = 0;

 //first check that we have the correct amount of inputs
 if (inputs.Count != this.NumberOfInputsPerNeuron)
 {
 //just return an empty vector if incorrect.
 return outputs;
 }

 //For each layer....
 for (int i = 0; i &amp;lt; this.NumberOfHiddenLayers + 1; ++i)
 {

 // NOTICE: This version of the code updates the inputs with the previous iteration outputs to be carried on to the next iteration before the ouputs of the previous iteration is emptied
 if (i &amp;gt; 0)
 {
 inputs = outputs.ToList(); ;
 }

 outputs.Clear();

 cWeight = 0;

 //for each neuron sum the (inputs * corresponding weights).Throw 
 //the total at our sigmoid function to get the output.
 for (int j = 0; j &amp;lt; this.NeuronLayers[i].NumberOfNeurons; ++j)
 {
 double netinput = 0;

 int NumInputs = this.NeuronLayers[i].Neurons[j].NumberOfInputs;

 //for each weight
 for (int k = 0; k &amp;lt; NumInputs - 1; ++k)
 {
 //sum the weights x inputs
 netinput += this.NeuronLayers[i].Neurons[j].Weight[k] *
 inputs[cWeight];
 cWeight++;
 }

 //add in the bias
 /*
 Don’t forget that the last weight in each neuron’s weight vector is the weight for the
 bias, which as we have already discussed, is always set to -1
 */
 netinput += this.NeuronLayers[i].Neurons[j].Weight[NumInputs - 1] *
 NeuralNetworkParams.Bias;

 //we can store the outputs from each layer as we generate them. 
 //The combined activation is first filtered through the sigmoid 
 //function
 outputs.Add(Sigmoid(netinput,
 NeuralNetworkParams.ActivationResponse));

 cWeight = 0;
 }
 }

 return outputs;

 }


This is the Genetic Algorithm which will evolve the genomes(weights) of the neural network to produce better outcomes, better solutions.



/// &amp;lt;summary&amp;gt;
 /// takes a population of chromosones and runs the algorithm through one cycle
 /// &amp;lt;/summary&amp;gt;
 /// &amp;lt;returns&amp;gt;Returns a new population of chromosones.&amp;lt;/returns&amp;gt;
 public List&amp;lt;Host&amp;gt; ProcessToNextGeneration(List&amp;lt;Host&amp;gt; oldPopulation)
 {
 //assign the given population to the classes population
 this.Population = oldPopulation;

 //reset the appropriate variables
 this.Reset();

 //calculate best, worst, average and total fitness
 this.CalculateBestWorstAverageTotalFitnessScore(ref this.Population);

 //create a temporary storage to store new chromosones
 List&amp;lt;Host&amp;gt; newPopulation = new List&amp;lt;Host&amp;gt;();

 //Now to add a little elitism we shall add in some copies of the
 //fittest genomes. Make sure we add an EVEN number or the roulette
 //wheel sampling will crash
 if ((NeuralNetworks.NeuralNetworkParams.NumCopiesElite * NeuralNetworks.NeuralNetworkParams.NumElite % 2) == 0)
 {
 this.GrabNBest(NeuralNetworks.NeuralNetworkParams.NumElite, NeuralNetworks.NeuralNetworkParams.NumCopiesElite, ref this.Population, ref newPopulation, false);
 }

 // now we enter the GA loop
 //repeat until a new population is generated
 while(newPopulation.Count &amp;lt; this.PopulationSize)
 {
 Host mum = this.MonteCarloSelection(ref this.Population);
 Host dad = this.MonteCarloSelection(ref this.Population);

 Host baby1 = new Host(0, () =&amp;gt; { return RandomProvider.RandomClamped(); });
 Host baby2 = new Host(0, () =&amp;gt; { return RandomProvider.RandomClamped(); });

 this.CrossoverAtNeuralNetworkSplits(ref mum.Genome.Chromosomes, ref dad.Genome.Chromosomes, ref baby1.Genome.Chromosomes, ref baby2.Genome.Chromosomes, ref this.SplitPoints);

 this.MutateReplace(ref baby1.Genome.Chromosomes, () =&amp;gt; { return RandomProvider.RandomClamped() * NeuralNetworks.NeuralNetworkParams.MaxPerturbation; });
 this.MutateReplace(ref baby2.Genome.Chromosomes, () =&amp;gt; { return RandomProvider.RandomClamped() * NeuralNetworks.NeuralNetworkParams.MaxPerturbation; });

 //now copy into vecNewPop population
 newPopulation.Add(baby1);
 newPopulation.Add(baby2);
 }

 this.Population = newPopulation;

 return this.Population;
 }

 

Sweepers – NEAT – Neuro Evolution of Augmenting Topologies Neural Network example

NEAT Sweepers screen


In this demo the main object is similar to that of the minesweepers example with the exception that there are no mines. The main objective is to learn the following:

  1. Avoid hitting obstacles
  2. Traverse as many new positions in the game are as possible

Also the reason NEAT is used in this example is to try to avoid the pitfalls of using regular Neural Network implementation. This becomes more important in real-time applications like games.

The piece of code below is the main function in the NEAT algorithms. It goes through X amount if ticks before doing calculation and updates on the genomes and neural network to evolve the sweepers to be more “intelligent”.


/// &amp;lt;summary&amp;gt;
 /// This is the main workhorse. The entire simulation is controlled from here.
 /// This method is called each frame. The first half of the function iterates through the
 /// MinesweeperNEATs, calling their update functions and updating the MinesweeperNEATs’ fitness
 /// scores if a mine has been found.In addition, because m_vecThePopulation contains
 /// copies of all the genomes, the relevant fitness scores are adjusted here too.If the
 /// required number of frames has passed for the completion of a generation, the
 /// method runs an epoch of the genetic algorithm producing a new generation of
 /// weights.These weights are used to replace the old weights in the MinesweeperNEAT’s
 /// neural nets and each MinesweeperNEAT’s parameters are reset ready for a new generation.
 /// &amp;lt;/summary&amp;gt;
 /// &amp;lt;returns&amp;gt;&amp;lt;/returns&amp;gt;
 public bool PerformCalculations()
 {
 //Debug.Log("start PerformCalculations");
 //run the sweepers through NeuralNetworkParams.NumTicks amount of cycles. During
 //this loop each sweepers NN is constantly updated with the appropriate
 //information from its surroundings. The output from the NN is obtained
 //and the sweeper is moved. If it encounters a mine its fitness is
 //updated appropriately,
 if (this.TicksCount++ &amp;lt; NeuralNetworkParams.NumTicks)
 {
 //Debug.Log("Before start of normal tick processing");
 for (int i = 0; i &amp;lt; NeuralNetworkParams.UnityInstantiatedNumSweepers; ++i)
 {
 // TODO_: Optimize this by passing the targets and not collecting the positions
 var minePositions = (from mine in Mines
 select new Vector2(mine.transform.position.x, mine.transform.position.y)).ToList();
 //-----------------------------------------------------

 
 //update the NN and position
 if (!this.Sweepers[i].UpdateANN(minePositions))
 {
 //error in processing the neural net
 Debug.Log("Wrong amount of NN inputs!");

 return false;
 }

 //update the NNs of the last generations best performers 
 if (this.Generations &amp;gt; 0)
 {
 for (int u = 0; u &amp;lt; this.BestSweepers.Count; ++u)
 {
 //Debug.Log("Before: update the NN and position");
 //update the NN and position 
 if (!this.BestSweepers[u].UpdateANN(minePositions))
 {
 //error in processing the neural net 
 Debug.Log("Wrong amount of NN inputs!");

 return false;
 }
 }
 }

 ////see if it's found a mine
 //int GrabHit = this.Sweepers[i].CheckForMine(minePositions,
 // NeuralNetworkParams.MineScale);

 //// Fitness calculation for a sweeper
 //// ----------------------------------------
 //if (GrabHit &amp;gt;= 0)
 //{
 // //we have discovered a mine so increase fitness
 // this.Sweepers[i].IncrementFitness();

 // //mine found so replace the mine with another at a random 
 // //position
 // this.Mines[GrabHit].transform.position = GetNewMineLocation();
 //}

 //// increase the fitness by a ratio of total cells visited compared to total cells in memory map. In other words the more adventurous the sweeper is the better fitness score, the more new locations it explores the better fitness.
 //if(this.Sweepers[i].GetNumberOfVisitedCellsInMemoryMap() &amp;gt; 0)
 // this.Sweepers[i].IncrementFitness(this.Sweepers[i].GetRatioOfNumberOfVisitedCellsInMemoryMap());

 //// Prefer sweepers which do not hit obstacles
 //if (!this.Sweepers[i].HasHitObstacle)
 // this.Sweepers[i].IncrementFitnessMediumImpact();

 //// Prefer sweepers which do not rotate like crazy
 //if(this.Sweepers[i].Rotation &amp;gt; -this.Sweepers[i].RotationTolerance &amp;amp;&amp;amp; this.Sweepers[i].Rotation &amp;lt; this.Sweepers[i].RotationTolerance)
 // this.Sweepers[i].IncrementFitnessMediumImpact();

 // ----------------------------------------
 this.Sweepers[i].RealTimeRunCalculations();
 //update the chromos fitness score
 //this.ThePopulation[i].Genome.Fitness = this.Sweepers[i].Fitness;
 


 }
 foreach (MinesweeperNEAT mineS in this.Sweepers)
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.white;

 foreach (MinesweeperNEAT mineS in this.Sweepers.OrderByDescending(o =&amp;gt; o.RealTimeFitness).Take(10))
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.green;

 foreach (MinesweeperNEAT mineS in this.Sweepers.OrderByDescending(o =&amp;gt; o.RealTimeFitness).Take(5))
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.yellow;

 foreach (MinesweeperNEAT mineS in this.Sweepers.OrderByDescending(o =&amp;gt; o.RealTimeFitness).Take(1))
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.red;
 }

 //Another generation has been completed.

 //Time to run the GA and update the sweepers with their new NNs
 else
 {
 //Debug.Log("Before sweepers EndOfRunCalculations");
 //this.ThePopulation = this.GA.ProcessToNextGeneration(this.ThePopulation);

 //first add up each sweepers fitness scores. (remember for this task 
 //there are many different sorts of penalties the sweepers may incur 
 //and each one has a coefficient) 
 for (int swp = 0; swp &amp;lt; this.Sweepers.Count; ++swp)
 {
 this.Sweepers[swp].EndOfRunCalculations();
 }
 //Debug.Log("Before sweepers Sort");
 this.Sweepers.Sort(delegate (MinesweeperNEAT x, MinesweeperNEAT y)
 {
 if (x.Fitness == y.Fitness)
 return 0;

 if (x.Fitness &amp;lt; y.Fitness)
 return 1;

 return -1;
 });

 //this.MapperGridForVisualization.Mapper = this.Sweepers[0].MemoryMap;
 //this.MapperGridForVisualization.Generate();
 //Debug.Log("Before Epoch");
 //perform an epoch and grab the new brains 
 List&amp;lt;NeuralNet&amp;gt; pBrains = this.GA.Epoch(GetFitnessScores());

 //insert the new brains back into the sweepers and reset their 
 //positions 
 for (int i = 0; i &amp;lt; pBrains.Count; ++i)
 {
 this.Sweepers[i].InsertNewBrain(pBrains[i]);

 this.Sweepers[i].Reset();
 }

 foreach (GameObject gObject in VisibleUnityNeurons)
 {
 DestroyImmediate(gObject);
 }
 VisibleUnityNeurons.Clear();

 //grab the NNs of the best performers from the last generation 
 List&amp;lt;NeuralNet&amp;gt; pBestBrains = this.GA.GetBestPhenotypesFromLastGeneration();
 // Delete the old unity neural network on screen
 for (int i = 0; i &amp;lt; pBestBrains.Count; ++i)
 {
 

 pBestBrains[i].DrawNet(
 Camera.main.ScreenToWorldPoint(new Vector3(Camera.main.pixelWidth, Camera.main.pixelHeight, Camera.main.transform.position.z)),
 Camera.main.ScreenToWorldPoint(new Vector3(0, 0, Camera.main.transform.position.z)), this.VisibleUnityNeurons);
 }

 //Debug.Log("after neural network draw");

 //put them into our record of the best sweepers 
 //for (int i = 0; i &amp;lt; this.BestSweepers.Count; ++i)
 //{


 // this.BestSweepers[i].InsertNewBrain(pBestBrains[i]);



 // this.BestSweepers[i].Reset();
 //}

 //update the stats to be used in our stat window
 //this.AverageFitnessValuesInGeneration.Add(this.GA.getAverageFitness());
 //this.BestFitnessValuesInGeneration.Add(this.GA.BestFitness());
 this.BestFitnessValuesInGeneration.Add(this.GA.GetBestEverFitness());
 //Debug.Log("This Gen average=&amp;gt; " + this.AverageFitnessValuesInGeneration[this.AverageFitnessValuesInGeneration.Count - 1]);
 Debug.Log("This Gen best=&amp;gt; " + this.BestFitnessValuesInGeneration[this.BestFitnessValuesInGeneration.Count - 1]);
 //StringBuilder sb = new StringBuilder();
 ////foreach (double d in this.AverageFitnessValuesInGeneration)
 //// sb.AppendFormat("{0};", d);
 ////sb.AppendLine();
 //foreach (double d in this.BestFitnessValuesInGeneration)
 // sb.AppendFormat("{0};", d);
 //sb.AppendLine();
 //Debug.Log(sb.ToString());

 //increment the generation counter
 ++this.Generations;

 //reset cycles
 this.TicksCount = 0;

 foreach (MinesweeperNEAT mineS in this.Sweepers)
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.white;

 foreach (MinesweeperNEAT mineS in this.Sweepers.OrderByDescending(o =&amp;gt; o.Fitness).Take(10))
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.green;

 foreach (MinesweeperNEAT mineS in this.Sweepers.OrderByDescending(o =&amp;gt; o.Fitness).Take(5))
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.yellow;

 foreach (MinesweeperNEAT mineS in this.Sweepers.OrderByDescending(o =&amp;gt; o.Fitness).Take(1))
 mineS.GetComponent&amp;lt;SpriteRenderer&amp;gt;().color = Color.red;

 //run the GA to create a new population


 //insert the new (hopefully)improved brains back into the sweepers
 //and reset their positions etc
 //for (int i = 0; i &amp;lt; NeuralNetworkParams.NumSweepers; ++i)
 //{
 // this.Sweepers[i].PutWeights(ref this.ThePopulation[i].Genome.Chromosomes);

 // this.Sweepers[i].Reset();
 //}
 }

 
 //Debug.Log("Before main loop wend");
 return true;
 }

This is the sweepers main update function. Here the function gathers and calculates world related data before and after the  data is inserted as inputs to neural network.


public bool UpdateANN(List&lt;Vector2&gt; mines)
 {
 this.acceleration = Vector2.zero;
 this.velocity = Vector2.zero;
 //this.Rotation = 0;
 //Debug.Log("Before: UpdateANN start");

 //this will store all the inputs for the NN
 List&lt;double&gt; inputs = new List&lt;double&gt;();
 //this.Rotation = UnityEngine.Random.Range(0, AIConstants.TWO_PI);
 /*
 First of all, the function calculates a vector to the closest mine and then normalizes
 it. (Remember, when a vector is normalized its length becomes 1.) The
 minesweeper’s look-at vector doesn’t need to be normalized in this way because its
 length is always 1. Because both vectors have been effectively scaled to within the
 same limits, the inputs can be considered to be standardized.
 */
 //get vector to closest mine
 Vector2 vectorClosestMine = GetClosestMine(mines);

 //normalise it
 vectorClosestMine.Normalize();

 float dot = Vector2.Dot(this.LookAt, vectorClosestMine);
 int sign = -1;

 if (this.LookAt.y * vectorClosestMine.x &gt; this.LookAt.x * vectorClosestMine.y)
 {
 sign= 1;
 }
 else
 {
 sign = - 1;
 }

 /*
 The look-at vector and the vector to the closest mine are then input into the neural
 network. The NeuralNet Update function updates the minesweeper’s network with
 this information and returns a List of doubles as the output.
 */

 //add in vector to closest mine
 //inputs.Add(vectorClosestMine.x);
 //inputs.Add(vectorClosestMine.y);

 //add in sweepers look at vector
 //inputs.Add(this.LookAt.x);
 //inputs.Add(this.LookAt.y);
 //if (HasHitObstacle)
 //{
 // int y = 0;
 // Debug.Log("#####################################################");
 // Debug.Log(dot);
 // Debug.Log("item count: " + this.sweeperCollisionSensorData.Count);
 // foreach (double d in this.sweeperCollisionSensorData)
 // Debug.Log("sw: " + d);
 //}

 // TODO: Add mines to the neural network
 //inputs.Add(dot*sign);
 inputs.Add(this.HasHitObstacle ? 1 : 0);
 inputs.AddRange(this.sweeperCollisionSensorData);
 inputs.AddRange(this.sweeperMemoryMapSensorData);

 //Debug.Log("update the brain and get feedback");
 //update the brain and get feedback
 List&lt;double&gt; output = this.Brain.Update(inputs, RunType.Active);


 //make sure there were no errors in calculating the 
 //output
 if (output.Count &lt; NeuralNetworkParams.NumOutputs)
 {
 return false;
 }


 //assign the outputs to the sweepers left &amp; right tracks
 this.LeftTrack = output[0];
 this.RightTrack = output[1];

 /*
 After checking to make sure there are no errors when updating the neural network,
 the program assigns the outputs to LeftTrack and RightTrack. These values represent the
 forces being exerted on the left track and right track of the minesweeper.
 */

 //calculate steering forces
 double RotForce = this.LeftTrack - this.RightTrack;

 //clamp rotation
 Mathf.Clamp((float)RotForce, -(float)NeuralNetworkParams.MaxTurnRate, (float)NeuralNetworkParams.MaxTurnRate);

 /*
 The vehicle’s rotational force is calculated by subtracting the force exerted by the
 right track from the force exerted by the left track. This is then clamped to make
 sure it doesn’t exceed the maximum turn rate specified in the ini file. The vehicle’s
 speed is simply the sum of the left track and right track. Now that we know the
 minesweeper’s rotational force and speed, its position and rotation can be updated
 accordingly.
 */

 //update the minesweepers rotation
 this.Rotation += RotForce;
 //if (Rotation &lt; 0)
 // Rotation = AIConstants.TWO_PI;

 //if (Rotation &gt; AIConstants.TWO_PI)
 // Rotation = 0;

 if(this.HasHitObstacle)
 {
 this.Rotation += RotForce * 100;
 }

 this.Speed = (this.LeftTrack + this.RightTrack);
 if(this.Speed &gt; NeuralNetworkParams.MaxSpeed)
 this.Speed = NeuralNetworkParams.MaxSpeed;
 //this.Speed *= 0.5f;
 //update Look At 
 
 this.LookAt.x = Mathf.Cos((float)this.Rotation);
 this.LookAt.y = -Mathf.Sin((float)this.Rotation);

 this.acceleration += (this.LookAt * (float)this.Speed);
 this.velocity += this.acceleration;
 var previousPosition = this.transform.position;

 var newPosition = previousPosition + (Vector3)this.velocity;
 var movementThisStep = newPosition - previousPosition;
 var movementLastStep = previousPosition - this.sweeperLastPosition;
 var previousPositionContinuedDirection = (previousPosition + movementLastStep) - previousPosition;
 var forward = transform.forward;
 float angle = Vector3.Angle(movementThisStep, previousPositionContinuedDirection);
 // Rotate the object towards the movement direction. NOTICE: the -90 degree turn is to point the sprite to the right direction
 transform.rotation = Quaternion.Euler(new Vector3(0, 0, (Mathf.Atan2(movementThisStep.y, movementThisStep.x) * Mathf.Rad2Deg) + -90));
 var movementThisStepSensorLength = movementThisStep * 4;

 this.DetectObstacles(previousPosition, movementThisStepSensorLength);
 this.ProcessMemoryMapWithSensors(previousPosition, movementThisStepSensorLength);
 

 // Move the object only if it has not hitted any obstacles
 if (!this.HasHitObstacle)
 {
 this.transform.position += (Vector3)this.velocity;


 //wrap around window limits
 if (this.transform.position.x &gt; maxScreenTopRight.x)
 this.transform.position = new Vector3(minScreenBottomLeft.x, this.transform.position.y, 0);
 if (this.transform.position.x &lt; minScreenBottomLeft.x)
 this.transform.position = new Vector3(maxScreenTopRight.x, this.transform.position.y, 0);
 if (this.transform.position.y &gt; maxScreenTopRight.y)
 this.transform.position = new Vector3(this.transform.position.x, minScreenBottomLeft.y, 0);
 if (this.transform.position.y &lt; minScreenBottomLeft.y)
 this.transform.position = new Vector3(this.transform.position.x, maxScreenTopRight.y, 0);
 this.sweeperLastPosition = previousPosition;
 }

 //if (this.GetComponent&lt;SpriteRenderer&gt;().color == Color.red || this.GetComponent&lt;SpriteRenderer&gt;().color == Color.yellow || this.GetComponent&lt;SpriteRenderer&gt;().color == Color.magenta)
 {
 Debug.DrawRay(previousPosition, movementThisStep, this.GetComponent&lt;SpriteRenderer&gt;().color, 1.7f);


 // Draw rays from current new position forward, this can be used for collision detection
 //--------------------------------------------------------

 // Points forward
 Debug.DrawRay(this.transform.position, movementThisStepSensorLength, Color.green);

 var sensorIn45DegreeForwardAngle = Quaternion.Euler(0, 0, 45) * movementThisStepSensorLength;
 var sensorInMinus45DegreeForwardAngle = Quaternion.Euler(0, 0, -45) * movementThisStepSensorLength;
 // Point 45 degrees forward
 Debug.DrawRay(this.transform.position, sensorIn45DegreeForwardAngle, Color.cyan);
 Debug.DrawRay(this.transform.position, sensorInMinus45DegreeForwardAngle, Color.cyan);

 var sensorIn90DegreeForwardAngle = Quaternion.Euler(0, 0, 90) * movementThisStepSensorLength;
 var sensorInMinus90DegreeForwardAngle = Quaternion.Euler(0, 0, -90) * movementThisStepSensorLength;
 // Points to the side of the object
 Debug.DrawRay(this.transform.position, sensorIn90DegreeForwardAngle, Color.yellow);
 Debug.DrawRay(this.transform.position, sensorInMinus90DegreeForwardAngle, Color.yellow);

 // Points backwards
 Debug.DrawRay(this.transform.position, movementThisStepSensorLength * -1, Color.red);


 //--------------------------------------------------------
 }

 this.MemoryMap.Update(this.transform.position.x, this.transform.position.y);
 return true;
 }


This is the NEAT Neural Network main update function which will calculate the outputs.


public List<double> Update(List<double> inputs, RunType type)
 {
 //create a vector to put the outputs into 
 List<double> outputs = new List<double>();

 //if the mode is snapshot then we require all the neurons to be 
 //iterated through as many times as the network is deep. If the 
 //mode is set to active the method can return an output after 
 //just one iteration 
 int FlushCount = 0;

 if (RunType.Snapshot == type)
 {
 FlushCount = this.Depth;
 }
 else
 {
 FlushCount = 1;
 }

 //iterate through the network FlushCount times 
 for (int i = 0; i < FlushCount; ++i)
 {
 //clear the output vector 
 outputs.Clear();

 //this is an index into the current neuron 
 int cNeuron = 0;

 //first set the outputs of the 'input' neurons to be equal 
 //to the values passed into the function in inputs 
 while (this.Neurons[cNeuron].NeuronTypeValue == NeuronType.Input)
 {
 this.Neurons[cNeuron].Output = inputs[cNeuron];

 ++cNeuron;
 }

 //set the output of the bias to 1 
 this.Neurons[cNeuron++].Output = 1;

 //then we step through the network a neuron at a time 
 while (cNeuron < this.Neurons.Count)
 {
 //this will hold the sum of all the inputs x weights 
 double sum = 0;

 //sum this neuron's inputs by iterating through all the links into 
 //the neuron 
 for (int lnk = 0; lnk < this.Neurons[cNeuron].LinksIn.Count; ++lnk)
 {
 //get this link's weight 
 double Weight = this.Neurons[cNeuron].LinksIn[lnk].Weight;

 //get the output from the neuron this link is coming from 
 double NeuronOutput =
 this.Neurons[cNeuron].LinksIn[lnk].Input.Output;

 //add to sum 
 sum += Weight * NeuronOutput;
 }

 //now put the sum through the activation function and assign the 
 //value to this neuron's output 
 this.Neurons[cNeuron].Output =
 Sigmoid(sum, this.Neurons[cNeuron].ActivationResponse);
 if(double.IsNaN(this.Neurons[cNeuron].Output))
 {
 int yyy = 0;
 }

 if (this.Neurons[cNeuron].NeuronTypeValue== NeuronType.Output)
 {
 //add to our outputs 
 outputs.Add(this.Neurons[cNeuron].Output);
 }

 //next neuron 
 ++cNeuron;
 }

 }//next iteration through the network 

 //the network needs to be flushed if this type of update is performed 
 //otherwise it is possible for dependencies to be built on the order 
 //the training data is presented 
 if (type == RunType.Snapshot)
 {
 for (int n = 0; n < this.Neurons.Count; ++n)
 {
 this.Neurons[n].Output = 0;
 }
 }

 //return the outputs 
 return outputs;

 }


This piece of code is the genetic algorithm main function which will operate on the NEAT Genome genes and links to produce evolution in the neural network.



///

<summary>
 /// This function performs one epoch of the genetic algorithm and returns a vector of pointers to the new phenotypes 
 /// </summary>


 /// <param name="FitnessScores"></param>
 /// <returns></returns>
 public List<NeuralNet> Epoch(List<double> FitnessScores)
 {
 // 21.10.2015 TODO: IF THE FITNESS IF ZERO THE GA WILL NOT WORK AND BEHAVE UN EXPECTEDLY THIS NEEDS FAIL SAFE MACHANISM
 //first check to make sure we have the correct amount of fitness scores 
 if (FitnessScores.Count != this.Genomes.Length)
 {
 Debug.Log("Cga::Epoch(scores/ genomes mismatch)!");
 }
 //Debug.Log(" Befiore ResetAndKill");
 //reset appropriate values and kill off the existing phenotypes and 
 //any poorly performing species 
 ResetAndKill();

 //Debug.Log("ResetAndKill");
 /*
 First of all, any phenotypes created during the previous generation are deleted. The
 program then examines each species in turn and deletes all of its members apart
 from the best performing one. (You use this individual as the genome to be tested
 against when the compatibility distances are calculated). If a species hasn’t made
 any fitness improvement in CParams::iNumGensAllowedNoImprovement generations, the
 species is killed off.*/
 //update the genomes with the fitnesses scored in the last run 
 // BUG HERE WITH C# value not set???
 for (int gen = 0; gen < this.Genomes.Length; ++gen)
 {
 this.Genomes[gen].SetFitness(FitnessScores[gen]);
 }
 

 //sort genomes and keep a record of the best performers 
 SortAndRecord();

 //separate the population into species of similar topology, adjust 
 //fitnesses and calculate spawn levels 
 SpeciateAndCalculateSpawnLevels();
 
 //Debug.Log("SpeciateAndCalculateSpawnLevels");
 /*
 SpeciateAndCalculateSpawnLevels commences by calculating the compatibility distance
 of each genome against the representative genome from each live species. If the
 value is within a set tolerance, the individual is added to that species. If no species
 match is found, then a new species is created and the genome added to that.
 When all the genomes have been assigned to a species
 SpeciateAndCalculateSpawnLevels calls the member function AdjustSpeciesFitnesses to
 adjust and share the fitness scores as discussed previously.
 
 Next, SpeciateAndCalculateSpawnLevels calculates how many offspring each individual
 is predicted to spawn into the new generation. This is a floating-point value calculated
 by dividing each genome’s adjusted fitness score with the average adjusted
 fitness score for the entire population. For example, if a genome had an adjusted
 fitness score of 4.4 and the average is 8.0, then the genome should spawn 0.525
 offspring. Of course, it’s impossible for an organism to spawn a fractional part of
 itself, but all the individual spawn amounts for the members of each species are
 summed to calculate an overall spawn amount for that species. Table 11.3 may help
 clear up any confusion you may have with this process. It shows typical spawn values
 for a small population of 20 individuals. The epoch function can now simply iterate
 through each species and spawn the required amount of offspring.
*/

 //this will hold the new population of genomes 
 Genome[] NewPop = new Genome[this.PopSize];
 int currentNewGenomeIndex = 0;

 //request the offspring from each species. The number of children to 
 //spawn is a double which we need to convert to an int. 
 int NumSpawnedSoFar = 0;

 Genome baby = null;

 //now to iterate through each species selecting offspring to be mated and 
 //mutated 
 for (int spc = 0; spc < this.Species.Count; ++spc)
 {
 //because of the number to spawn from each species is a double 
 //rounded up or down to an integer it is possible to get an overflow 
 //of genomes spawned. This statement just makes sure that doesn't 
 //happen 
 if (NumSpawnedSoFar < NeuralNetworkParams.UnityInstantiatedNumSweepers) { //this is the amount of offspring this species is required to // spawn. Rounded simply rounds the double up or down. int NumToSpawn = Mathf.RoundToInt((float)this.Species[spc].NumToSpawn()); bool bChosenBestYet = false; while (NumToSpawn-- > 0)
 {
 //first grab the best performing genome from this species and transfer 
 //to the new population without mutation. This provides per species 
 //elitism 
 if (!bChosenBestYet)
 {
 baby = this.Species[spc].GetLeader();

 bChosenBestYet = true;
 }

 else
 {
 //if the number of individuals in this species is only one 
 //then we can only perform mutation 
 if (this.Species[spc].NumMembers() == 1)
 {
 //spawn a child 
 baby = this.Species[spc].Spawn();
 }

 //if greater than one we can use the crossover operator 
 else
 {
 //spawn1 
 Genome g1 = this.Species[spc].Spawn();

 if (RandomProvider.RandomFloat() < NeuralNetworkParams.CrossoverRate) { //spawn2, make sure it's not the same as g1 Genome g2 = this.Species[spc].Spawn(); //number of attempts at finding a different genome int NumAttempts = 5; while ((g1.GetID() == g2.GetID()) && (NumAttempts-- >= 0))
 {
 g2 = this.Species[spc].Spawn();
 }

 if (g1.GetID() != g2.GetID())
 {
 baby = Crossover(g1, g2);
 
 }

 /*Because the number of individuals in a species may be small and because only the
 best 20% (default value) are retained to be parents, it is sometimes impossible (or
 slow) to find a second genome to mate with. The code shown here tries five times to
 find a different genome and then aborts.*/
 }

 else
 {

 baby = g1;
 }
 }

 

 ++this.NextGenomeID;

 baby.SetID(this.NextGenomeID);

 //now we have a spawned child lets mutate it! First there is the 
 //chance a neuron may be added 
 if (baby.GetNumNeurons() < NeuralNetworkParams.MaxPermittedNeurons)
 {
 baby.AddNeuron(NeuralNetworkParams.ChanceAddNode,
 Innovation,
 NeuralNetworkParams.NumTrysToFindOldLink);
 }

 ////now there's the chance a link may be added 
 baby.AddLink(NeuralNetworkParams.ChanceAddLink,
 NeuralNetworkParams.ChanceAddRecurrentLink,
 Innovation,
 NeuralNetworkParams.NumTrysToFindLoopedLink,
 NeuralNetworkParams.NumAddLinkAttempts);

 //mutate the weights 
 baby.MutateWeights(NeuralNetworkParams.MutationRate,
 NeuralNetworkParams.ProbabilityWeightReplaced,
 NeuralNetworkParams.MaxWeightPerturbation);

 baby.MutateActivationResponse(NeuralNetworkParams.ActivationMutationRate,
 NeuralNetworkParams.MaxActivationPerturbation);
 }

 //sort the babies genes by their innovation numbers 
 baby.SortLinkGenes();

 //add to new pop 
 NewPop[currentNewGenomeIndex]= baby;
 currentNewGenomeIndex++;

 ++NumSpawnedSoFar;

 if (NumSpawnedSoFar == NeuralNetworkParams.UnityInstantiatedNumSweepers)
 {
 NumToSpawn = 0;
 }

 }//end while 

 }//end if 

 }//next species 
 //Debug.Log("SPECIES COMPLETE");

 //if there is an underflow due to the rounding error and the amount 
 //of offspring falls short of the population size additional children 
 //need to be created and added to the new population. This is achieved 
 //simply, by using tournament selection over the entire population. 
 if (NumSpawnedSoFar < NeuralNetworkParams.UnityInstantiatedNumSweepers) { //calculate amount of additional children required int Rqd = NeuralNetworkParams.UnityInstantiatedNumSweepers - NumSpawnedSoFar; //grab them while (Rqd-- > 0)
 {
 NewPop[currentNewGenomeIndex] = TournamentSelection(this.PopSize / 5);
 currentNewGenomeIndex++;
 }
 }

 //Debug.Log("numspawned");
 
 //replace the current population with the new one 
 // BUG HERE
 //this.Genomes = NewPop.ToArray();

 //create the new phenotypes 
 List<NeuralNet> new_phenotypes = new List<NeuralNet>();
 for (int gen = 0; gen < this.Genomes.Length; ++gen)
 {
 //calculate max network depth 
 int depth = CalculateNetDepth(this.Genomes[gen]);

 NeuralNet phenotype = this.Genomes[gen].CreatePhenotype(depth);

 new_phenotypes.Add(phenotype);
 }


 //Debug.Log("before gen counter");
 //increase generation counter 
 ++this.Generation;
 
 return new_phenotypes;
 }


Basics

 

“A neural network is a “connectionist” computational system. The computational systems we write are procedural; a program starts at the first line of code, executes it, and goes on to the next, following instructions in a linear fashion. A true neural network does not follow a linear path. Rather, information is processed collectively, in parallel throughout a network of nodes (the nodes, in this case, being neurons).” (Shiffman, 2015)

“One of the key elements of a neural network is its ability to learn. A neural network is not just a complex system, but a complex adaptive system, meaning it can change its internal structure based on the information flowing through it. Typically, this is achieved through the adjusting of weights. In the diagram above, each line represents a connection between two neurons and indicates the pathway for the flow of information. Each connection has a weight, a number that controls the signal between the two neurons. If the network generates a “good” output (which we’ll define later), there is no need to adjust the weights. However, if the network generates a “poor” output—an error, so to speak—then the system adapts, altering the weights in order to improve subsequent results.” (Shiffman, 2015)

Architecture

“As mentioned previously, NNs are made up of units and weights, which represent biological neurons and synapses, respectively. NNs generally consist of an input layer, zero or more hidden layers, and an output layer. The input layer consists of units that represent the input to the network. Choosing the variables from the game environment that will be used as inputs can be a very labor-intensive process, as there is a lot of information to choose from, which can make selecting a set of relevant variables difficult. It is also important to keep the number of variables to a minimum to prevent the search space from becoming too large.

Each input unit has one or more weights that feed into the first hidden layer or the output layer. Each weight allows an input unit to provide an excitatory or inhibitory influence on the unit to which it is connected. The output layer consists of one or more units that compose the output of the network. With one output unit, the network can be used to classify its input as being in one of two categories: 1/0, yes/no, true/false. With multiple output units, the system can classify the input into one of many categories. For example, with 26 output units, the system could classify the input as being a letter in the alphabet. Finally, the hidden layers are used to make the network more powerful by extracting features from the data. Each hidden unit also as an associated set of weights that feed into the next hidden layer or the output layer. There is no rule to designate how many hidden units to use. The best way is to start with a small number, between 5 and 10, and then add or remove units until the desired level of performance is achieved. Usually, only one hidden layer is required to adequately model the training data. The following code shows the data structures used for the input, hidden and output layers, as well as the training set and the weights of the network.” (Rabin, 2003)

The Artificial Neuron

“Each unit in the hidden and output layers has an adder for combining their input signal and an activation function for determining their level of activation. The adder sums the input entering the unit, where each input value is calculated by multiplying the input unit by its associated weight. This gives the activation of the unit as shown in Equation, where a is the activation, n is the number of units, xi is the i:th unit and wi is the i:th weight.

e1

After the sum of the input to the unit has been calculated, this value is then fed into an activation function that determines the level of activation of the unit. The unit then “fires” and propagates its activation onto the next layer. The most common activation functions include the threshold function, the piecewise-linear function, the family of sigmoid functions, and the Gaussian function. Another important part of the activation function is the bias, which determines the shift of the activation function along the input axis. It is usually implemented as an extra node in the input and hidden layers, with weights that feed into each node in the next layer. “ (Rabin, 2003)

Design decisions

“The design decisions that need to be made when building an NN include the, architecture of the network, the type of units, the learning rule, the representation of inputs and outputs, the data that will be used to train the network, the testing procedure, and the values or various network                               parameters.

There are many choices to make when designing your NN. First, you must decide on the architecture of your network, including what type of network you will use and how many input, hidden, and output units you will have and how they will be connected. The number of input units will be equal to the number of game variables that are being fed to the network and should be kept to the fewest possible, to reduce the complexity of the problem. The number of output units will equal the number of different outcomes, whether classes or decisions, that are available to the network. The number of hidden nodes is arbitrary and the usual approach is to start with a few and add more depending on the network’s performance. Second, you need to decide what type of units will be used, such as linear or sigmoid, by choosing the activation function that you will use. The example in this article used a type of sigmoid function, namely a logistic function. This function is commonly used in networks that use backpropagation learning.

Third, you need to choose how to represent the network’s inputs and outputs; will they be real numbers or a string of bits? In a game situation, where the game variables are real numbers, it would generally be best to represent the inputs to the net- work as real numbers. The outputs could map directly to a decision or action that is to be made or could represent some intermediate classification. In these cases, the output could be represented as integers that correspond to the different choices, or each output could correspond to a variable, so that each returns a value between 0 and 1. Fourth, a suitable learning rule needs to be chosen, such as the backpropagation rule used in this article. Fifth, you need to decide on the training data you will use to train the network; this is discussed further in the next section. Next, the network will need to be tested to find a suitable point to stop training, where accuracy and the ability to generalize to new data are maximized. This is usually based on a measure such as the mean square error (MSE).

Finally, there are several parameters that need to be set, including learning rate, momentum, and initial weight values. Learning rate is usually set to around 0.2, momentum is set to 0.9, and initial weights are randomly chosen within a range, such as between positive and negative 1. These variables often need to be tuned to attain optimal performance. Designing the best NN for your application is done through trial, error, and experience.” (Rabin, 2003)

Types of neural networks

“The most common type of NN is the Feedforward network, in which each layer of units feeds its output forward to the next layer. In these NNs, each unit in one layer can be fully connected to every unit in the next layer, or the units can be sparsely connected. There are two types of Feedforward networks, the Single-Layer Perceptron and the Multi-Layer Perceptron. In the Single-Layer Perceptron, the input units map directly to the output layer. However, in Multi-Layer Perceptron’s, which is the type of network used as an example in this article, there are one or more hidden layers in addition to the inputs and outputs.

There are many other types of networks that each perform well on certain problems. Some of the more popular types include Hopfield networks and Kohonen Featuure Maps. In a Hopfield network, each unit is connected to every other unit and there is no differentiation between input and output units. Hopfield networks and used for storage and recognition of patterns, such as images. A Kohonen Feature map is a type of self organizing map, in which there is only one layer of units, Other the inputs, that organize themselves according to input values. Kohonen maps can be used to detect patterns in complex sets of data.” (Rabin, 2003)

Single Layer Feedforward Network

“This type of network comprises of two layers, namely the input layer and the output layer. The input layer neurons receive the input signals and the output layer neurons receive the output signals. The synaptic links carrying the weights connect every input neuron to the output neuron   but not vice-versa. Such a network is said to be feedforward in type or acyclic in nature. Despite   the two layers, the network is termed single layer since it is the output layer, alone which   performs computation. The input layer merely transmits the signals to the output layer. Hence, the   name single layer feedforward network.” (Rajashekaran, 2004)

Multilayer Feedforward Network

“This network, as its name indicates is made up of multiple layers. Thus, architectures of this class besides possessing an input and an output layer also have one or more intermediary layers called hidden layers. The computational units of the hidden layer are known as the hidden neurons or hidden units. The hidden layer aids in performing useful intermediary computations before directing the input to the output layer. The input layer neurons are linked to the hidden layer neurons and the weights on these links are referred to as input-hidden layer weights. Again, the hidden layer neurons are linked to the output layer neurons and the corresponding weights are referred to as hidden-output layer weights. A multilayer feedforward network with 1 input neurons, inn neurons in the first hidden layer, m2 neurons in the second hidden layer and n output neurons in the output layer is written as 1 – ml – in2 n.” (Rajashekaran, 2004)

Recurrent Networks

“These networks differ from feedforward network architectures in the sense that there is at least one feedback loop. Thus, in these networks, for example, there could exist one layer with feedback connections. There could also be neurons with self-feedback links, i.e. the output of a neuron is fed back into itself as input.” (Rajashekaran, 2004)

CHARACTERISTICS OF NEURAL NETWORKS

  1. The NNs exhibit mapping capabilities, that is, they can map input patterns to their associated output patterns.
  2. The NNs learn by examples. Thus, NN architectures can be ‘trained’ with known examples of a problem before they are tested for their ‘inference’ capability on unknown instances of the problem. They can, therefore, identify new objects previously untrained.
  3. The NNs possess the capability to generalize. Thus, they can predict new outcomes from past trends.
  4. The NNs are robust systems and are fault tolerant. They can, therefore, recall full patterns from incomplete, partial or noisy patterns.
  5. The NNs can process information in parallel, at high speed, and in a distributed manner.

“ (Rajashekaran, 2004)

TAXONOMY OF NEURAL NETWORK ARCHITECTURES

  • ADALINE (Adaptive Linear Neural Element)
  • ART (Adaptive Resonance Theory)
  • AM (Associative Memory)
  • BAM (Bidirectional Associative Memory)
  • Boltzmann Machine
  • BSB (Brain-State-in-a-Box)
  • CCN (Cascade Correlation)
  • Cauchy Machine
  • CPN (Counter Propagation Network)
  • Hamming Network
  • Hopfield Network
  • LVQ (Learning Vector Quantization)
  • MADALINE (Many ADALINE)
  • MLFF (Multilayer Feedforward Network)
  • Neocognitron
  • Perceptron
  • RBF (Radial Basis Function)
  • RNN (Recurrent Neural Network)
  • SOFM (Self-organizing Feature Map)

Classification of NN systems with respect to learning methods and architecture types

Type of architecture Gradient descent Hebbian Competitive Stochastic
Single-layer feedforward ADALINE

Hopfield

Perceptron

AM

Hopfield

LVQ

SOFM

Multilayer feedforward CCN

MLFF

RBF

Neocognitron
Recurrent neural network RNN BAM

BSB

Hopfield

ART Boltzmann machine

Cauchy machine

 

 

Neural network anatomy

2

“The w’s in the gray circles represent floating-point numbers called weights. Each input into the artificial neuron has a weight associated with it and it’s these weights that determine the overall activity of the neural network. For the moment, imagine that all these weights are set to small random values—let’s say between -1 and 1. Because a weight can be either positive or negative, it can exert an excitory influence over the input it’s associated with, or it can exert an inhibitory influence. As the inputs enter the neuron, they are multiplied by their respective weights.

A function in the nucleus—the activation function—then sums all these new, weight-adjusted input values to give the activation value (again a floating-point number, which can be negative or positive). If this activation value is above a certain threshold, let’s use the number one as an example, the neuron outputs a signal and will output a one. If the activation is less than one, the artificial neuron outputs a zero. This is one of the simplest types of activation functions found in artificial neurons and it’s called a step function.” (Buckland, 2002 )

The Perceptron

“a perceptron is the simplest neural network possible: a computational model of a single neuron. A perceptron consists of one or more inputs, a processor, and a single output.” (Shiffman, 2015)

“A perceptron follows the “feed-forward” model, meaning inputs are sent into the neuron, are processed, and result in an output. … this means the network (one neuron) reads from left to right: inputs come in, output goes out.” (Shiffman, 2015)

2.1

Perceptron processing steps

  1. Receive inputs
  2. Weight inputs

“Each input that is sent into the neuron must first be weighted, i.e. multiplied by some value (often a number between -1 and 1). When creating a perceptron, we’ll typically begin by assigning random weights. ” (Shiffman, 2015)

  1. Sum inputs
    1. The weighted inputs are then summed
  2. Generate output

“The output of a perceptron is generated by passing that sum through an activation function. “ (Shiffman, 2015)

The Perceptron Algorithm:

  1. For every input, multiply that input by its weight.
  2. Sum all of the weighted inputs.
  3. Compute the output of the perceptron based on that sum passed through an activation function (the sign of the sum).

Neuron

“An artificial neuron … can have any number of inputs numbered from one to n—where n is the total number of inputs.” (Buckland, 2002 )

The sum of each input – weight multiplication can be expressed mathematically as:

3

“… if the activation exceeds the threshold, the neuron outputs a one; if the activation is below the threshold, the neuron outputs a zero. This is equivalent to a biological neuron firing or not firing. Imagine a neuron with five inputs, and all its weights initialized to random values (-1 < w < 1).” (Buckland, 2002 )

4

“Just as biological neurons in the brain connect to other neurons, these artificial neurons are connected together in some way to create the neural network. There are many, varied ways of connecting neurons but the easiest to understand and the most widely used is by connecting the neurons together in layers … This type of ANN is called a feedforward network. It gets its name from the way each layer of neurons feed their outputs into the next layer until an output is given.” (Buckland, 2002 )

5

“As you can see, each input is sent to every neuron in the hidden layer, and then the output from each neuron in the hidden layer is connected to every neuron in the next layer. There can be any number of hidden layers within a feedforward network, but one is usually enough to cope with most of the problems you will tackle. In fact, some problems don’t require any hidden units at all; you can simply connect the inputs straight into the output neurons. … There can be any number of neurons in each layer; it all depends on the problem. Because the speed of the network decreases as more neurons are added,…, it’s desirable to keep the network as small as possible.” (Buckland, 2002 )

Pattern recognition example

“Once the neural network architecture has been created, it must be trained to recognize the character “4”. One way of doing this is to initialize the neural net with random weights and then feed it a series of inputs that represent, in this example, the different panel configurations. For each configuration, we check to see what its output is and adjust the weights accordingly. If the input pattern we feed it is not a “4”, then we know the neural network should output a zero. So for every non “4” character, the weights are adjusted slightly so the output tends toward zero. When it’s presented with a pattern that represents the character “4”, the weights are adjusted so the output tends toward the number one.

For each character, the network is trained to recognize many different versions of that letter. Eventually the network will not only be able to recognize the letters it has been trained with, but it will also show the remarkable property of being able to generalize.

This type of training is called supervised learning and the data the network is trained with is called a training set. There are many different ways of adjusting the weights; the most common for this type of problem is called backpropagation. I’ll be talking about backprop later in the book when I show you how you can train a neural network to recognize mouse gestures. However, the rest of this chapter will be focused on a type of training that requires little or no supervision at all: unsupervised learning.” (Buckland, 2002 )

How many hidden neurons

“Basically, it comes down to trial and error. You will normally find that one hidden layer is plenty for most problems you encounter, so the skill is mostly about choosing the best number of neurons for that single layer. The fewer the better because, as I’ve already mentioned, fewer neurons make for a faster network.” (Buckland, 2002 )

Bias 

 

“Like others have said, I think that biases are almost always helpful. In effect, a bias value allows you to shift the activation function to the left or right, which may be critical for successful learning.

 

It might help to look at a simple example. Consider this 1-input, 1-output network that has no bias:

6

The output of the network is computed by multiplying the input (x) by the weight (w0) and passing the result through some kind of activation function (e.g. a sigmoid function.)

 

Here is the function that this network computes, for various values of w0:

7

Changing the weight w0 essentially changes the “steepness” of the sigmoid. That’s useful, but what if you wanted the network to output 0 when x is 2? Just changing the steepness of the sigmoid won’t really work — you want to be able to shift the entire curve to the right.

 

That’s exactly what the bias allows you to do. If we add a bias to that network, like so:

8

…then the output of the network becomes sig(w0*x + w1*1.0). Here is what the output of the network looks like for various values of w1:

9

Having a weight of -5 for w1 shifts the curve to the right, which allows us to have a network that outputs 0 when x is 2.” (Stackoverflow – Role of Bias in Neural Networks, 2015)

 

“A bias unit is meant to allow units in your net to learn an appropriate threshold (i.e. after reaching a certain total input, start sending positive activation), since normally a positive total input means a positive activation.

For example if your bias unit has a weight of -2 with some neuron x, then neuron x will provide a positive activation if all other input adds up to be greater then -2.

So, with that as background, your answers:

  1. No, one bias input is always sufficient, since it can affect different neurons differently depending on its weight with each unit.
  2. Generally speaking, having bias weights going to every non-input unit is a good idea, since otherwise those units without bias weights would have thresholds that will always be zero.
  3. Since the threshold, once learned should be consistent across trials. Remember the bias represented how each unit interacts with the input; it isn’t an input itself.
  4. You certainly can and many do. Any squashing function generally works as an activation function.

” (Stackoverflow – why Bias is necessory in NN , and should we have seperate bias for each layer, 2015)

 

“Remember that the activation was the sum of all the inputs×weights and that the output of the neuron was dependent upon whether this activation exceeded a threshold value (t). This can be represented as the equation:

10

where the above is the condition for outputting a one. Because all the weights for the network have to be evolved, it would be great if the threshold amount could be evolved too. To make this easy, you use a simple trick to get the threshold to appear as a weight. Subtract the t from either side of the equation:

11

Written another way, this equation can be made to look like this:

12

So I hope you can see how the threshold can now be thought of as a weight that is always multiplied by an input of -1. This is usually referred to as the bias and this is why each neuron is initialized with an additional weight. Now when you evolve the network, you don’t have to worry about the threshold value because it is built in with the weights and will take care of itself. ” (Buckland, 2002 )

13

Neural Network learning methods

Supervised Learning

“Supervised Learning —Essentially, a strategy that involves a teacher that is smarter than the network itself. For example, let’s take the facial recognition example. The teacher shows the network a bunch of faces, and the teacher already knows the name associated with each face. The network makes its guesses, then the teacher provides the network with the answers. The network can then compare its answers to the known “correct” ones and make adjustments according to its errors. Our first neural network in the next section will follow this model.” (Shiffman, 2015)

“An input pattern is presented to the network and the output examined and compared to the target output. If the output differs from the target output, then all the weights are altered slightly so the next time the same pattern is presented, the output will be a little closer to the expected outcome. This is repeated many times with each pattern the network is required to learn until it performs correctly.” (Buckland, 2002 )

“In this, every input pattern that is used to train the network is associated with an output pattern, which is the target or the desired pattern. A teacher is assumed to be present during the learning process, when a comparison is made between the network’s computed output and the correct expected output, to determine the error. The error can then be used to change network parameters, which result in an improvement in performance.” (Rajashekaran, 2004)

Backpropagation

How Does Backpropagation Work

“Backpropagation, or backprop for short, works like this: First create a network with one or more hidden layers and randomize all the weights—say to values between -1 and 1. Then present a pattern to the network and note its output. The difference between this value and the target output value is called the error value. This error value is then used to determine how the weights from the layer below the output layer are adjusted so if the same input pattern is presented again, the output will be a little closer to the correct answer. Once the weights for the current layer have been adjusted, the same thing is repeated for the previous layer and so on until the first hidden layer is reached and all the weights for every layer have been adjusted slightly. If done correctly, the next time the input pattern is presented, the output will be a little bit closer to the target output. This whole process is then repeated with all the different input patterns many times until the error value is within acceptable limits for the problem at hand. The network is then said to be trained.” (Buckland, 2002 )

“This set of matched input/output patterns is used to train the network as follows:

  1. Initialize weights to small random values.
  2. For each pattern, repeat Steps a to e.
    1. Present to the network and evaluate the output, o.
    2. Calculate the error between o and the target output value (t).
    3. Adjust the weights in the output layer.

For each hidden layer repeat d and e.

  1. Calculate the error in the hidden layer.
  2. Adjust the weights in the hidden layer.
  1. Repeat Step 2 until the sum of all the errors in Step b is within an acceptable limit.” (Buckland, 2002 )

 

“There are basically two sets of equations: one to calculate the error and weight adjustment for the output layer and the other to calculate the error and weight adjustments for the hidden layers.” (Buckland, 2002 )

 

“The idea is to keep iterating through the learning process until the error value drops below an acceptable value. The number of iterations can be very large and is proportional to the size of the learning rate: the smaller the learning rate, the more iterations backprop requires. However, when increasing the learning rate, you run the risk of the algorithm falling into a local minima.

The example shown only ran one input pattern (1,1) through the algorithm. In practice, each pattern would be run through the algorithm every iteration. The entire process goes like this:

  1. Create the network.
  2. Initialize the weights to small random values with a mean of 0.
  3. For each training pattern: calculate the error value for the neurons in the output layer adjust the weights of the output layer calculate the error value for neurons in the hidden layer adjust the weights of the hidden layer
  4. Repeat Step 3 until the error is below an acceptable value.” (Buckland, 2002 )

“In training, the NN’s ‘weights are initially set to random values. Then, random sets of called the training set, are fed into the system. For each training example, the actual output of the network is compared to the desired output, and the network’s weights are adjusted to minimize this difference. This type of learning is called supervised learning, in which the network is taught to mimic the teacher who provides the training set, until it has been learned satisfactorily, at which point the network can function on its own.

Then the training loop begins; in this case, the training continues for N iterations. The examples in the training set are taken one at a time and propagated through the network. First, the input units propagate the input to the hidden layer, which then uses the sigmoid function to determine the extent to which each unit will propagate the signal, as described in the previous section. Next, the hidden units propagate the information to the output layer, which determines which out will become activated, thus generating the output of the network.

After the network has generated its output for a particular training example, the network’s error needs to be calculated and the weights adjusted accordingly. The function that is used to do this is called the backpropagation learning rule. This rule works by calculating the difference between the actual output, which is the output generated by the network, and the expected output, which is the correct output from the training example. The backpropagation learning rule then back propagates this error back through the system, adjusting each weight according to its influence on the output.

As learning progresses, the weights in the network are adjusted to minimize the errors made by the network. The weights from the bias nodes are adjusted in the same way, except that the bias nodes always equal 1. Another important aspect in backpropagation is the momentum term, which reduces the chance that the network will find local maxima or that the learning will plateau. There are two other types of learning used in NNs: reinforcement learning and unsupervised learning. In reinforcement learning, the network is not explicitly given desired outputs in the form of a training set, but is rewarded when it does the right thing, while unsupervised learning looks for statistical regularities in the data” (Rabin, 2003)

Learn quicker and generalize better

 

Adding Momentum

“As you’ve seen, the backprop algorithm attempts to reduce the error of the neural network a little each epoch. You can imagine the network having an error landscape, similar to the fitness landscapes of genetic algorithms. Each iteration, backprop determines the gradient of the error at the current point in the landscape and attempts to move the error value toward a global minimum.

Unfortunately, most error landscapes are not nearly so smooth … Therefore, if you are not careful, your algorithm can easily get stuck in a local minima.” (Buckland, 2002 )

14

Finding the global minimum of the error landscape

15

Stuck in a local minima

“One way of preventing this is by adding momentum to the weight update. To do this, you simply add a fraction of the previous time-step’s weight update to the current weight update. This will help the algorithm zip past any small fluctuations in the error landscape, thereby giving a much better chance of finding the global minimum. Using momentum also has the added bonus of reducing the number of epochs it takes to train a network.” (Buckland, 2002 )

Overfitting

“As you may have realized by now, a neural network is basically a function approximator. Given a training set, the ANN attempts to find the function that will fit the input data to the output data. One of the problems with neural networks is that they can learn to do this too well and lose the ability to generalize.” (Buckland, 2002 )

“With a network like this, although it’s done a great job of fitting the data it has been trained with, it will have great difficulty predicting exactly where any new data presented to it may fit. So what can you do to prevent overfitting? Here are a few techniques you can try:

Minimizing the number of neurons: The first thing you should do is reduce the number of hidden neurons in your network to a minimum. As previously mentioned, there is no rule of thumb for judging the amount; as usual, you’ll need to determine it by good old trial and error.

Adding jitter: In this context, jitter is not some long-forgotten dance from the ’50s, but a way of helping the network to generalize by adding noise (random fluctuations around a mean of zero) to the training data. This prevents the network from fitting any specific data point too closely and therefore, in some situations can help prevent overfitting.

Early stopping: Early stopping is another simple technique and is a great one to use when you have a large amount of training data. You split the training data into two sets: a training set and a validation set. Then, using a small learning rate and a network with plenty of hidden neurons—there’s no need to worry about having too many in this case—train the network using the training set, but this time make periodic tests against the validation set. The idea is to stop the training when the error from testing against the validation set begins to increase as opposed to reducing the SSE below a predefined value. This method works well when you have a large enough data set to enable splitting and can be very fast.” (Buckland, 2002 )

Softmax Activation Function

“Some problems, like the mouse gesture application, are classification problems. That is to say, given some data, the network’s job is to place it into one of several categories. … the neural network has to decide which category of pattern the user’s mouse gestures fall into. So far we’ve just been choosing the output with the highest value as the one representing the best match.

This is fine, but sometimes it’s more convenient if the outputs represent a probability of the data falling into the corresponding category. To represent a probability, all the outputs must add up to one. To achieve this, a completely different activation function must be used for the output neurons: the softmax activation function.” (Buckland, 2002 )

For a network with n output units, the activation of output neuron oi is given by:

16

 

in which wixi is the sum of all the inputs × weights going into that neuron.

This can be a fairly confusing equation, so let me run through it again to make sure you understand what’s going on. To get the output from any particular output neuron, you must first sum all the weights × inputs for every output neuron in the neural network. Let’s call that total A. Once you’ve done that, to calculate the output, you iterate through each output neuron in turn and divide the exponential of that neuron’s A with the sum of the exponentials of all the output neurons’ As.” (Buckland, 2002 )

“Although you can use the sum squared error function (SSE), as used previously, a better error function to use when utilizing softmax is the cross-entropy error function. You don’t have to worry where this equation comes from, just be assured that this is the better error function to apply when your network is designed to produce probabilities.

It looks like this:

17

Where n is the number of output neurons, t is the target value, and y is the actual output.” (Buckland, 2002 )

 

Unsupervised Learning

“Unsupervised Learning —Required when there isn’t an example data set with known answers. Imagine searching for a hidden pattern in a data set. An application of this is clustering, i.e. dividing a set of elements into groups according to some unknown pattern. (Shiffman, 2015)

“In this learning method, the target output is not presented to the network. It is as if there is no teacher to present the desired patterns and hence, the system learns of its own by discovering and adapting to structural features in the input patterns.” (Rajashekaran, 2004)

Reinforcement Learning

“Reinforcement Learning —A strategy built on observation. Think of a little mouse running through a maze. If it turns left, it gets a piece of cheese; if it turns right, it receives a little shock. (Don’t worry, this is just a pretend mouse.) Presumably, the mouse will learn over time to turn left. Its neural network makes a decision with an outcome (turn left or right) and observes its environment (yum or ouch). If the observation is negative, the network can adjust its weights in order to make a different decision the next time. Reinforcement learning is common in robotics. At time t, the robot performs a task and observes the results. Did it crash into a wall or fall off a table? Or is it unharmed? (Shiffman, 2015)

“In this method, a teacher though available, does not present the expected answer but only indicates if the computed output is correct or incorrect. The information provided helps the network in its learning process. A reward is given for a correct answer computed and a penalty for a wrong answer. But, reinforced learning is not one of the popular forms of learning.

Supervised and unsupervised learning methods, which are most popular forms of learning, have found expression through various rules. Some of the widely used rules have been presented below:

Hebbian learning

This rule was proposed by Hebb (1949) and is based on correlative weight adjustment. This is the oldest learning mechanism inspired by biology. In this, the input–output pattern pairs (Xi, Yi) are as the correlation matrix. Here, YT is the transpose of the associated output vector Yi.

Gradient descent learning

This is based on the minimization of error E defined in terms of weights and the activation function of the network. Also, it is required that the activation function employed by the network is differentiable, as the weight update is dependent on the gradient of the error E.

Competitive learning

In this method, those neurons which respond strongly to input stimuli have their weights updated. When an input pattern is presented, all neurons in the layer compete and the winning neuron undergoes weight adjustment. Hence, it is a “winner-takes-all” strategy.

Stochastic learning

In this method, weights are adjusted in a probabilistic fashion. An example is evident in simulated annealing—the learning mechanism employed by Boltzmann and Cauchy machines, which are a kind of NN systems.” (Rajashekaran, 2004)

Classification of learning algorithms

18

Activation methods

Also known as:

  • non-linear filter
  • transfer function
  • squash function

“To generate the final output y, the sum is passed on to a non-linear filter 0 called Activation  function, or Transfer function, or Squash function which releases the output.” (Rajashekaran, 2004)

19

Thresholding function

“A very commonly used Activation function is the Thresholding function. In this, the sum is compared with a threshold value . If the value of a is greater than  then the output is 1 else it is 0.

20

 

where, 0 is the step function known as Heaviside function and is such that 21 “ (Rajashekaran, 2004)

 

illustrates the Thresholding function. This is convenient in the sense that the  output signal is either 1 or 0 resulting in the neuron being on or off.” (Rajashekaran, 2004)

22

Signum function

“Also known as the Quanlizer function, the function   is defined as:

23

“ (Rajashekaran, 2004)

24

Sigmoidal function

“This function is a continuous function that varies gradually between the asymptotic values 0 and 1 or —1 and +1 and is given by:

25

Sigmoidal functions are differentiable, which is an important where,  is the slope parameter, which adjusts the abruptness of the function as it changes between the two asymptotic values.  Sigmoidal functions are differentiable, which is an important feature of NN theory.” (Rajashekaran, 2004)

26

Hyperbolic tangent function

 

“The function is given by

27

can produce negative output values.

The first mathematical model of a biological neuron was presented by McCulloch and Pitts (1943). The model, known as McCulloch-Pitts model does not exhibit any learning but just serves as a basic building block which has inspired further significant work in NN research. The model makes use of a bias term whose weight is w0 but with a fixed input of x0 = 1. This is besides the other inputs xi and weights wi. The bias is an external parameter for the artificial neuron but serves the purpose of increasing or decreasing the net input of the activation function depending on whether it is positive or negative. Other modelling schemes for the neuron have also been proposed (Macgregor, 1987).” (Rajashekaran, 2004)

 

Evolving networks

 

This means the evolution of the neural network weights values which will have an impact of the inputted values when the outputs are calculated.

Offline

Offline evolution happens outside your main application loop. This means that calculations are not done in real time as the users of your application does something but after the user has done something. This may be after you application closes or changes scenes etc.

These calculation are good in situation where real time calculations are too expensive for you application to perform. This would mean that this is shown in slowness and wait time to your application user.

Data may be gathered in real time but it is used offline to evolve your neural networks.

This again means that the results of the evolved networks can be then applied in real time without the costly calculations. Or you can use your neural network data calculated of line to get a real time value how your application acts. Again here I speak of the evolution of the neural network which is done outside the main application loop.

Online

 

Online evolution of networks happen in real time as the user done something. Data is gathered in real time, neural network calculations are done and based on the outputs actions are taken.

“So far, you’ve learned how to evolve behavior that progresses through a series of epochs. This is fine if it’s acceptable to develop the behavior of your game agents offline or via epochs that are undertaken during natural breaks in a game (such as between levels), but now I’m going to show you a simple technique that you can use to evolve genomes while the game is being played. This can be used wherever you have a large number of game agents constantly getting destroyed and created. The advantage of this type of evolution is that it can adapt to accommodate varying game dynamics, such as different human players or changes to the game environment it may not have encountered offline. For example, the tank units in your favorite real-time strategy game could learn to adapt their behavior according to the playing style of their opponents.

The technique I’m going to describe is a breeze to implement. In short, to evolve a population online, all you have to do is keep a pool of genomes (the population) stored in a container that is always kept sorted. Individuals used in the game are spawned from this pool. Immediately after an individual is killed off in the game, it’s replaced by mutating one of the better performers in the population (chosen from amongst the top 20%, say). In this way, the population doesn’t evolve in waves as each epoch is processed, but rather, continuously, in a constant cycle of birth and death. For this reason, this technique requires a fast turnaround of game agents in order to work properly. If your game agents die off at too slow a rate, then it’s unlikely they will evolve at a satisfactory pace. If, however, your game agents get killed off swiftly, like in a shoot-em-up or some types of units in real-time strategy games, this method of evolution may be used to good effect.” (Buckland, 2002 )

Evolving Neural Network Topology

 

Requirements and problems of neural networks

 

Desired requirements

  • networks to evolve to find the best topology along with the network weights
  • A network that is simple enough to learn whatever it is you want it to learn, yet not so simple that it loses its ability to generalize

Problems

 

Competing Conventions Problem

 

“One of the main difficulties with encoding candidate networks is called the competing conventions problem—sometimes referred to as the structural-functional mapping problem. Simply put, this is where a system of encoding may provide several different ways of encoding networks that exhibit identical functionality. For example, imagine a simple encoding scheme where a network is encoded as the order in which the hidden neurons appear in a layer.

Using the simple scheme I’ve just proposed, Network 1 may be encoded as:

A B C D

and Network 2 as:

D C B A

If you look carefully, you’ll notice that, although the order of the neurons is different— and therefore the genomes are different—both networks are essentially identical. They will both exhibit exactly the same behavior. And this is where the problem lies, because if you now attempt to apply a crossover operator to these two networks, lets say at the midpoint of the genome, the resultant offspring will be:

A B B A or D C C D

This is an undesirable result because not only have both offspring inherited duplicated neurons, they have also lost 50% of the functionality of their parents and are unlikely to show a performance improvement.

Obviously, the larger the networks are, the more frequently this problem is encountered. And this results in a more negative effect on the population of genomes. Consequently, it is a problem researchers do their best to avoid when designing an encoding scheme.” (Buckland, 2002 )

Possible solutions attempts

 

Constructive or destructive networks

 

“A destructive algorithm commences with an oversized ANN with many neurons, layers, and links and attempts to reduce its size by systematically pruning the network during the training process. A constructive process is one that approaches the problem from the opposite end, by starting with a minimal network and adding neurons and links during training. However, these methods have been found to be prone to converging upon local optima and, what’s more, they are still usually fairly restrictive in terms of network architecture. That is to say, only a fraction of the full spectrum of possible topologies is usually available for these techniques to explore.” (Buckland, 2002 )

EANN – Evolutionary Artificial Neural Network

 

“The goal of an EANN (Evolutionary Artificial Neural Network), therefore, is to traverse that landscape as best it can before alighting upon the global optima.” (Buckland, 2002 )

“As with every other problem tackled with evolutionary algorithms, any potential solution has to figure out a way of encoding the networks, a way of assigning fitness scores, and valid operators for performing genome mutation and/or crossover. I say or crossover because a few methods dispose with this potentially troublesome operator altogether, preferring to rely entirely on mutation operators to navigate the search space.” (Buckland, 2002 )

Direct Encoding

“There are two methodologies of EANN encoding: direct encoding and indirect encoding. The former attempts to specify the exact structure of the network by encoding the number of neurons, number of connections, and so on, directly into the genome. The latter makes use of growth rules, which may even define the network structure recursively.” (Buckland, 2002 )

GENITOR

“GENITOR is one of the simplest techniques to be found and is also one of the earliest. A typical version of this algorithm encodes the genome as a bit string. Each gene is encoded with nine bits. The first bit indicates whether there is a connection between neurons and the rest represent the weight (-127 to 127).

The disadvantage of this technique, as with many of the encoding techniques developed to date, is that a maximal network topology must be designed for each problem addressed in order for all the potential connectivity to be represented within the genome. Additionally, this type of encoding will suffer from the competing conventions problem.” (Buckland, 2002 )

Binary Matrix Encoding

“One popular method of direct encoding is to use a binary adjacency matrix. As you can see, the connectivity for this network can be represented as a matrix of binary digits, where a 1 represents a connection between neurons and a 0 signifies no connection. The chromosome can then be encoded by just assigning each row (or column) of the matrix to a gene. Like so:

00110 00010 00001 00001 00000

However, because the network shown is entirely feedforward, this encoding is wasteful because half the matrix will always contain zeros. Realizing this, we can dispose of one-half of the matrix , and encode the chromosome as:

0110 010 01 1

which, I’m sure you will agree, is much more efficient!

Once encoded, the bit strings may be run through a genetic algorithm to evolve the topologies. Each generation, the chromosomes are decoded and the resultant networks initialized with random weights. The networks are then trained and a fitness is assigned. If, for example, backdrop is used as the training mechanism, the fitness function could be proportional to the error generated, with an additional penalty as the number of connections increases in order to keep the network size at a minimum.

Obviously, if your training approach can handle any form of connectivity, not just feedforward, then the entire matrix may be represented.

A genetic algorithm training approach would be okay with this type of network, but standard backpropagation would not. “ (Buckland, 2002 )

Some Related Problems

 

“It has been demonstrated that when using matrix encoding (and some other forms of direct encoding), performance deteriorates as the size of the chromosome increases. Because the size increases in proportion to the square of the number of neurons, performance deteriorates pretty quickly. This is known as the scalability problem. Also, the user still has to decide how many neurons will make up the maximal architecture before the matrix can be created. In addition, this type of representation does not address the competing conventions problem discussed earlier. It’s very likely, when using this encoding, that two or more chromosomes may display the same functionality. If these chromosomes are then mated, the resultant offspring has little chance of being fitter than either parent. For this reason, it’s quite common for the crossover operator to be dismissed altogether with this technique.” (Buckland, 2002 )

Node-Based Encoding

“Node-based encoding tackles the problem by encoding all the required information about each neuron in a single gene. For each neuron (or node), its gene will contain information about the other neurons it is connected to and/or the weights associated with those connections. Some node-based encoding schemes even go so far as to specify an associated activation function and learning rate. (A learning rate, don’t forget, is used when the network is trained using a gradient descent method like backpropagation.)

Mutation operators using this sort of encoding can be varied and are simple to implement. They include such mutations as adding a link, removing a link, adding a node, or removing a node. The crossover operator, however, is a different beast altogether. Care must be taken to ensure valid offspring are produced and that neurons are not left stranded without any incoming and outgoing connections.

Once valid genetic algorithm operators have been defined, the neural networks encoded using the described scheme may be evolved as follows (assuming they are trained using a training set in conjunction with a gradient descent algorithm like backpropagation):

  1. Create an initial random population of chromosomes.
  2. Train the networks and assign a fitness score based on the overall error value of each network (target output – best trained output). It is also feasible to penalize the score as the networks grow in size. This will favor populations with fewer neurons and links.
  3. Choose two parents using your favorite selection technique (fitness proportionate, tournament, and so on).
  4. Use the crossover operator where appropriate.
  5. Use the mutation operator/s where appropriate.
  6. Repeat Steps 3,4, and 5 until a new population is created.
  7. Go to Step 2 and keep repeating until a satisfactory network is evolved.” (Buckland, 2002 )

 

Path-Based Encoding

“Path-based encoding defines the structure of a neural network by encoding the routes from each input neuron to each output neuron. For example:

1 →A → C→ 3

1 → D → B → 4

1 → D → C → 3

2 → D → C → 3

2 → D → B → 4

Because each path always begins with an input neuron and always ends with an output neuron, this type of encoding guarantees there are no useless neurons referred to in the chromosome. The operator used for recombination is two-point crossover. (This ensures the chromosomes are always bound with an input and output neuron). Several mutation operators are typically used:

  • Create a new path and insert into the chromosome.
  • Choose a section of path and delete.
  • Select a path segment and insert a neuron.
  • Select a path segment and remove a neuron.

Because the networks defined by this type of encoding are not restricted to feedforward networks (links can be recurrent), a training approach such as genetic algorithms must be used to determine the ideal connection weights.”

Indirect Encoding

“Indirect encoding methods more closely mimic the way genotypes are mapped to phenotypes in biological systems and typically result in more compact genomes. Each gene in a biological organism does not give rise to a single physical feature; rather, the interactions between different permutations of genes are expressed. Indirect encoding techniques try to emulate this mechanism by applying a series of growth rules to a chromosome. These rules often specify many connections simultaneously and may even be applied recursively.” (Buckland, 2002 )

Grammar-Based Encoding

“This type of encoding uses a series of developmental rules that can be expressed as a type of grammar. The grammar consists of a series of left-hand side symbols (LHS) and right-hand side symbols (RHS). Whenever a LHS symbol is seen by the development process, it’s replaced by a number of RHS symbols. The development process starts off with a start symbol (a LHS symbol) and uses one of the production rules to create a new set of symbols. Production rules are then applied to these symbols until a set of terminal symbols has been reached. At this point, the development process stops and the terminal symbols are expressed as a phenotype.

A genetic algorithm is used to evolve the growth rules. Each rule can be expressed in the chromosome by four positions corresponding to the four symbols in the RHS of the rule. The actual position (its loci) of the rule along the length of the chromosome determines its LHS. The number of non-terminal symbols can be in any range. The inventors of this technique used the symbols A through Z and a through p. The rules that had terminal symbols as their RHS were predefined, so the chromosome only had to encode the rules consisting of non-terminal symbols.” (Buckland, 2002 )

Bi-Dimensional Growth Encoding

“This is a rather unusual type of encoding. The neurons are represented by having a fixed position in two-dimensional space, and the algorithm uses rules to actually grow axons, like tendrils reaching through the space. A connection is made when an axon touches another neuron.

The designers of this technique use a genome encoding which consists of 40 blocks, each representing a neuron. There are five blocks at the beginning of the genome to represent input neurons, five at the end to represent output neurons, and the remaining thirty are used as hidden neurons.

As you can imagine, this technique is tricky to implement and also pretty slow to evolve.” (Buckland, 2002 )

Promising solution: NEAT – Neuro Evolution of Augmenting Topologies

“NEAT is short for Neuro Evolution of Augmenting Topologies and has been developed by Kenneth Stanley Owen and Risto Miikkulainen at the University of Texas. It uses node-based encoding to describe the network structure and connection weights, and has a nifty way of avoiding the competing convention problem by utilizing the historical data generated when new nodes and links are created. NEAT also attempts to keep the size of the networks it produces to a minimum by starting the evolution using a population of networks of minimal topology and adding neurons and connections throughout the run. Because nature works in this way—by increasing the complexity of organisms over time—this is an attractive solution and is partly the reason I’ve chosen to highlight this technique in this chapter.” (Buckland, 2002 )

“a technique for evolving neural networks for complex reinforcement learning tasks using an evolutionary algorithm (EA). NEAT combines the usual search for the appropriate network weights with complexification of the network structure, allowing the behavior of evolved neural networks to become increasingly sophisticated over generations. The NEAT method consists of solutions to three fundamental challenges in evolving neural network topology:

  1. What kind of genetic representation would allow disparate topologies to cross over in a meaningful way? The solution is to use historical markings to line up genes with the same origin.
  2. How can topological innovation that needs a few generations to optimize be protected so that it does not disappear from the population prematurely? The solution is to separate each innovation into a different species.
  3. How can topologies be minimized throughout evolution so the most efficient solutions will be discovered?

The solution is to start from a minimal structure and add nodes and connections incrementally. This section explains how each of these solutions is implemented in NEAT, using the genetic encoding described in the first subsection.” (Stanley, Real-Time Neuroevolution in the NERO Video Game, 2005)

NEAT genome

 

“The NEAT genome structure contains a list of neuron genes and a list of link genes. A link gene, as you may have guessed, contains information about the two neurons it is connected to, the weight attached to that connection, a flag to indicate whether the link is enabled, a flag to indicate if the link is recurrent, and an innovation number (more on this in a moment). A neuron gene describes that neuron’s function within the network—whether it be an input neuron, an output neuron, a hidden neuron, or a bias neuron. Each neuron gene also possesses a unique identification number.” (Buckland, 2002 )

28

“A NEAT genotype to phenotype mapping example. A genotype is depicted that produces the shown phenotype. There are three input nodes, one hidden node, one output node, and seven connection definitions, one of which is recurrent. The second gene is disabled, so the connection that it specifies (between nodes 2 and 4) is not expressed in the phenotype. The genotype can have arbitrary length, and thereby represent arbitrarily complex networks. Innovation numbers, which allow NEAT to identify which genes match up between different genomes, are shown on top of each gene. This encoding is efficient and allows changing the network structure during evolution.” (Stanley, Real-Time Neuroevolution in the NERO Video Game, 2005)

29

Genetic Encoding

 

“Evolving structure requires a flexible genetic encoding. In order to allow structures to complexity, their representations must be dynamic and expandable. Each genome in NEAT includes a list of connection genes, each of which refers to two node genes being connected (Figure 1). Each connection gene specifies the in-node, the out-node, the weight of the connection, whether or not the connection gene is expressed (an enable bit), and an innovation number, which allows finding corresponding genes during crossover.

Mutation in NEAT can change both connection weights and network structures. Connection weights mutate as in any NE system, with each connection either perturbed or not. Structural mutations, which form the basis of complexification, occur in two ways (Figure 2). Each mutation expands the size of the genome by adding genes. In the add connection mutation, a single new connection gene is added connecting two previously unconnected nodes. In the add node mutation, an existing connection is split and the new node placed where the old connection used to be. The old connection is disabled and two new connections added to the genome.

The connection between the first node in the chain and the new node is given a weight of one, and the connection between the new node and the last node in the chain is given the same weight as the connection being split. Splitting the connection in this way introduces a nonlinearity (the sigmoid function) where there was none before. This nonlinearity changes the function only slightly, and the new node is immediately integrated into the network. Old behaviors encoded in the preexisting network structure are not destroyed and remain qualitatively the same, while the new structure provides an opportunity to elaborate on these original behaviors.

Through mutation, the genomes in NEAT will gradually get larger. Genomes of varying sizes will result, sometimes with different connections at the same positions. Any crossover operator must be able to recombine networks with differing topologies, which can be difficult (Radcliffe 1993). The next section explains how NEAT addresses this problem.” (Stanley, Real-Time Neuroevolution in the NERO Video Game, 2005)

“Now that you’ve seen how a network structure is encoded, let’s have a look at the ways a genome may be mutated. There are four mutation operators in use in this implementation of NEAT: a mutation to add a link gene to the genome, a mutation to add a neuron gene, a mutation for perturbing the connection weights, and a mutation that can alter the response curve of the activation function for each neuron. The connection weight mutation works very similarly to the mutation operators you’ve seen in the rest of the book, so I’ll not show you the code. It simply steps through the connection weights and perturbs each one within predefined limits based on a mutation rate. There is one difference however, this time there is a probability the weight is replaced with a completely new weight.” (Buckland, 2002 )

30

31

“The two types of structural mutation in NEAT. In each genome, the innovation number is shown on top, the two nodes connected by the gene in the middle, and the “disabled” symbol at the bottom; the weights and the node genes are not shown for simplicity. A new connection or a new node is added to the network by adding connection genes to the genome. Assuming the node is added after the connection, the genes would be assigned innovation numbers 7, 8, and 9, as the figure illustrates. NEAT can keep an implicit history of the origin of every gene in the population, allowing matching genes to be identified even in different genome structures.” (Stanley, Real-Time Neuroevolution in the NERO Video Game, 2005)

“To add a neuron to a network, first a link must be chosen and then disabled. Two new links are then created to join the new neuron to its neighbors. This means that every time a neuron is added, three innovations are created (or repeated if they have already been discovered): one for the neuron gene and two for the connection genes.

Early on in the development of the networks, a problem can occur where the same link is split repeatedly creating a chaining effect, as shown in

Obviously, this is undesirable, so the following code checks the number of neurons in the genome to see if the structure is below a certain size threshold. If it is, measures are taken to ensure that older links are selected in preference to newer ones.

When a link is disabled and two new links are created, the old weight from the disabled link is used as the weight for one of the new links, and the weight for the other link is set to 1. In this way, the addition of a neuron creates as little disruption as possible to any existing learned behavior.” (Buckland, 2002 )

 

Node link types

  • A forward link
  • A recurrent link
  • A looped recurrent link

32

Tracking Genes through Historical Markings

 

“The historical origin of each gene can be used to determine exactly which genes matchup between any individuals in the population. Two genes with the same historical origin represent the same structure (although possibly with different weights), since they were both derived from the same ancestral gene at some point in the past. Thus, in order to properly align and recombine any two disparate topologies in the population the system only needs to keep track of the historical origin of each gene.

Tracking the historical origins requires very little computation. Whenever a new gene appears (through structural mutation), a global innovation number is incremented and assigned to that gene. The innovation numbers thus represent a chronology of every gene in the population. As an example, say the two mutations in Figure 2 occurred one after another. The new connection gene created in the first mutation is assigned the number 7, and the two new connection genes added during the new node mutation are assigned the numbers 8 and 9. In the future, whenever these genomes cross over, the offspring will inherit the same innovation numbers on each gene. Thus, the historical origin of every gene is known throughout evolution.

A possible problem is that the same structural innovation will receive different innovation numbers in the same generation if it occurs by chance more than once. However, by keeping a list of the innovations that occurred in the current generation, it is possible to ensure that when the same structure arises more than once through independent mutations in the same generation, each identical mutation is assigned the same innovation number.

Through innovation numbers, the system now knows exactly which genes match up with which.

Genes that do not match are either disjoint or excess, depending on whether they occur within or outside the range of the other parent’s innovation numbers.

When crossing over, the genes with the same innovation numbers are lined up. The offspring is then formed in one of two ways: In uniform crossover, matching genes are randomly chosen for the offspring genome. In blended crossover (Wright 1991), the connection weights of matching genes are averaged. These two types of crossover were found to be most effective in NEAT in extensive testing compared to one-point crossover.

The disjoint and excess genes are inherited from the more fit parent, or if they are equally fit, from both parents. Disabled genes have a chance of being re-enabled during crossover, allowing networks to make use of older genes once again.

Historical markings allow NEAT to perform crossover without analyzing topologies. Genomes of different organizations and sizes stay compatible throughout evolution, and the variable-length genome problem is essentially avoided. This methodology allows NEAT to complexify structure while different networks still remain compatible.

However, it turns out that it is difficult for a population of varying topologies to support new innovations that add structure to existing networks. Because smaller structures optimize faster than larger structures, and adding nodes and connections usually initially decreases the fitness of the network, recently augmented structures have little hope of surviving more than one generation even though the innovations they represent might be crucial towards solving the task in the long run. The solution is to protect innovation by speciating the population, as explained in the next section.” (Stanley, Real-Time Neuroevolution in the NERO Video Game, 2005)

33

Matching up genomes for different network topologies using innovation numbers. Although Parent 1 and Parent 2 look different, their innovation numbers (shown at the top of each gene) indicate that several of their genes match up even without topological analysis. A new structure that combines the overlapping parts of the two parents as well as their different parts can be created in crossover. In this case, the two parents are assumed to have equal fitness, and therefore the offspring inherits all such genes from both parents. Otherwise these genes would be inherited from the more fit parent only. The disabled genes may become enabled again in future generations: There is a preset chance that an inherited gene is enabled if it is disabled in either parent. By matching up genes in this way, it is possible to determine the best alignment for crossover between any two arbitrary network topologies in the population.” (Stanley, Real-Time Neuroevolution in the NERO Video Game, 2005)

 

“An innovation occurs whenever new structure is added to a genome, either by adding a link gene or by adding a neuron gene, and is simply a record of that change. A global database of all the innovations is maintained—each innovation having its own unique identification number. Each time a link or neuron addition occurs, the database is referenced to see if that innovation has been previously created. If it has, then the new gene is assigned the existing innovation ID number. If not, a new innovation is created, added to the database, and the gene is tagged with the newly created innovation ID.

Because NEAT grows structure by adding neurons and links, all the genomes in the initial population start off representing identical minimal topologies (but with different connection weights). When the genomes are created, the program automatically defines innovations for all the starting neurons and connections.

Input and output neurons are assigned a value of -1 for the in and out values to avoid confusion. Similarly, new links are assigned a neuron ID of -1 .

If at any time in the future a different genome stumbles across this identical mutation, the innovation database is referenced and the correct innovation ID is assigned to the newly created gene. In this way, the genes contain a historical record of any structural changes. This information is invaluable for designing a valid crossover operator, as you shall see shortly.” (Buckland, 2002 )

How Innovations Help in the Design of a Valid Crossover Operator

“As I discussed at the beginning of this chapter, the crossover operator for EANNs can often be more trouble than it’s worth. In addition to ensuring that crossover does not produce invalid networks, care must also be taken to avoid the competing conventions problem. The designers of NEAT have managed to steer clear of both these evils by using the innovation IDs as historical gene markers. Because each innovation has a unique ID, the genes can be tracked chronologically, which means similar genes in different genomes can be aligned prior to crossover.

 

The genes shown are the link genes for each phenotype. As you can see, the phenotypes have very different topologies, yet we can easily create an offspring from them by matching up the innovation numbers of the genomes before swapping over the appropriate genes.

Those genes that do not match in the middle of the genomes are called disjoint genes, whereas those that do not match at the end are called excess genes. Crossover proceeds a little like multi-point crossover, discussed earlier in the book. As the operator iterates down the length of each genome, the offspring inherits matching genes randomly. Disjoint and excess genes are only inherited from the fittest parent.” (Buckland, 2002 )

Protecting Innovation through Speciation

“Speciation

NEAT speciates the population so that individuals compete primarily within their own niches instead of with the population at large. This way, topological innovations are protected and have time to optimize their structure before they have to compete with other niches in the population. Protecting innovation through speciation follows the philosophy that new ideas must be given time to reach their potential before they are eliminated. A secondary benefit of speciation is that is prevents bloating of genomes: Species with smaller genomes survive as long as their fitness is competitive, ensuring that small networks are not replaced by larger ones unnecessarily. Historical markings make it possible for the system to divide the population into species based on how similar they are topologically (figure 4). The distance between two network encodings can be measured as a linear combination of the number of excess (E) and disjoint (D) genes, as well as the average weight differences of matching genes (W):

34

The coefficients C1, C2, and C3 adjust the importance of the three factors, and the factor N, the number of genes in the larger genome, normalizes for genome size (N can be set to one unless both genomes are excessively large). Genomes are tested one at a time; if a genome’s distance to a randomly chosen member of the species is less than t, a compatibility threshold, the genome is placed into this species.

If a genome is not compatible with any existing species, a new species is created. The problem of choosing the best value for t can be avoided by making t dynamic; that is, given a target number of species, the system can slightly raise t if there are too many species, and lower t if there are too few. Each genome is placed into the first species from the previous generation where this condition is satisfied, so that no genome is in more than one species. Keeping the same set of species from one generation to the next allows NEAT to remove stagnant species, i.e. species that have not improved for several generations.

As the reproduction mechanism, NEAT uses explicit fitness sharing (Goldberg and Richardson 1987), where organisms in the same species must share the fitness of their niche. Thus, a species cannot afford to become too big even if many of its organisms perform well. Therefore, any one species is unlikely to take over the entire population, which is crucial for speciated evolution to support a variety of topologies. The adjusted fitness fi for organism i is calculated according to its distance  from every other organism j in the population:

35

The sharing function sh is set to 0 when distance (i;j)is above the threshold t; otherwise, sh((i;j)is set to 1 (Spears 1995). Thus,  37reduces to the number of organisms in the same species as organism i. This reduction is natural since species are already clustered by compatibility using the threshold t. Every species is assigned a potentially different number of offspring in proportion to the sum of adjusted fitnesses fi of its member organisms.

The net effect of fitness sharing in NEAT can be summarized as follows. Let Fk be the average fitness of species k kand |P| jPjbe the size of the population. Let 38  be the total of all species fitness averages.

The number of offspring allocatted to species is:

40

Species reproduce by first eliminating the lowest performing members from the population. The entire population is then replaced by the offspring of the remaining individuals in each species.

The main effect of speciating the population is that structural innovation is protected. The final goal of the system, then, is to perform the search for a solution as efficiently as possible. This goal is achieved through complexification from a simple starting structure, as detailed in the next section.” (Stanley, Real-Time Neuroevolution in the NERO Video Game, 2005)

“When structure is added to a genome, either by adding a new connection or a new neuron, it’s quite likely the new individual will be a poor performer until it has a chance to evolve and establish itself among the population. Unfortunately, this means there is a high probability of the new individual dying out before it has time to evolve any potentially interesting behavior. This is obviously undesirable—some way has to be found of protecting the new innovation in the early days of its evolution.

This is where simulating speciation comes in handy…

Speciation, as the name suggests, is the separation of a population into species. The question of what exactly is a species, is still one the biologists (and other scientists) are arguing over, but one of the popular definitions is:

A species is a group of populations with similar characteristics that are capable of successfully interbreeding with each other to produce healthy, fertile offspring, but are reproductively isolated from other species.

In nature, a common mechanism for speciation is provided by changes in geography. Imagine a widespread population of animals, let’s call them “critters”, which eventually come to be divided by some geographical change in their environment, like the creation of a mountain ridge, for example. Over time, these populations will diversify because of different natural selection pressures and because of different mutations within their chromosomes. On one side of the mountain, the critters may start growing thicker fur to cope with a colder climate, and on the other, they may adapt to become better at avoiding the multitude of predators that lurk there.

Eventually, the two populations will have changed so much from each other that if they ever did come into contact again, it would be impossible for them to mate successfully and have offspring. It’s at this point they can be considered two different species.

NEAT simulates speciation to provide evolutionary niches for any new topological change. This way, similar individuals only have to compete among themselves and not with the rest of the population. Therefore, they are protected somewhat from premature extinction. A record of all the species created is kept in a class called— wait for it—CSpecies. Each epoch, every individual is tested against the first member in each species and a compatibility distance is calculated. If the compatibility distance” (Buckland, 2002 )

“Once an individual has been assigned to a species, it may only mate with other members of the same species. However, speciation alone does not protect new innovation within the population. To do that, we must somehow find a way of adjusting the fitnesses of each individual in a way that aids younger, more diverse genomes to remain active for a reasonable length of time. The technique NEAT uses to do this is called explicit fitness sharing.

… fitness sharing is a way of retaining diversity by sharing the fitness scores of individuals with similar genomes. With NEAT, fitness scores are shared by members of the same species. In practice, this means that each individual’s score is divided by the size of the species before any selection occurs. What this boils down to is that species which grow large are penalized for their size, whereas smaller species are given a “foot up” in the evolutionary race, so to speak.

In addition, young species are given a fitness boost prior to the fitness sharing calculation. Likewise, old species are penalized. If a species does not show an improvement over a certain number of generations (the default is 15), then it is killed off. The exception to this is if the species contains the best performing individual found so far, in which case the species is allowed to live.” (Buckland, 2002 )

The Genome Loop

  • The Genome Loop:
    • Take the next genome gfrom population P
    • The Species Loop:
      • If all species in S have been checked,
        • create new species snewand place gin it
      • Else
        • Get the next species sfrom S
        • If gis compatible with s, add gto s
      • If ghas not been placed,
        • continue the Species Loop
      • Else exit the Species Loop
    • If not all genomes in Ghave been placed,
      • continue the Genome Loop
    • Else exit the Genome Loop
Minimizing Dimensionality through Complexification

“Other systems that evolve network topologies and weights begin evolution with a population of random topologies (Angeline et al. 1993; Gruau et al. 1996; Yao 1999; Zhang and Muhlenbein 1993). In contrast, NEAT begins with a uniform population of simple networks with no hidden nodes, differing only in their initial random weights. Speciation protects new innovations, allowing diverse topologies to gradually accumulate over evolution. Thus, NEAT can start minimally, and grow the necessary structure over generations.

New structures are introduced incrementally as structural mutations occur, and only those structures survive that are found to be useful through fitness evaluations. In this way, NEAT searches through a minimal number of weight dimensions, significantly reducing the number of generations necessary to find a solution, and ensuring that networks become no more complex than necessary. This gradual increase in complexity over generations is similar to complexification in biology (Amores et al. 1998; Carroll 1995; Force et al. 1999; Martin 1999). In effect, then, NEAT searches for the optimal topology by incrementally complexifying existing structure.” (Stanley, Real-Time Neuroevolution in the NERO Video Game, 2005)

Neural network uses

  • Pattern Recognition—We’ve mentioned this several times already and it’s probably the most common application. Examples are facial recognition, optical character recognition, etc.
  • Time Series Prediction—Neural networks can be used to make predictions. Will the stock rise or fall tomorrow? Will it rain or be sunny?
  • Signal Processing—Cochlear implants and hearing aids need to filter out unnecessary noise and amplify the important sounds. Neural networks can be trained to process an audio signal and filter it appropriately.
  • Control—You may have read about recent research advances in self-driving cars. Neural networks are often used to manage steering decisions of physical vehicles (or simulated ones).
  • Soft Sensors—A soft sensor refers to the process of analyzing a collection of many measurements. A thermometer can tell you the temperature of the air, but what if you also knew the humidity, barometric pressure, dewpoint, air quality, air density, etc.? Neural networks can be employed to process the input data from many individual sensors and evaluate them as a whole.
  • Anomaly Detection—Because neural networks are so good at recognizing patterns, they can also be trained to generate an output when something occurs that doesn’t fit the pattern. Think of a neural network monitoring your daily routine over a long period of time. After learning the patterns of your behavior, it could alert you when something is amiss.

” (Shiffman, 2015)

Tips and thoughts

 

My own observations on Neural Networks

 

  • Input
    • The inputs are a starting place for the network, like a players position
    • To dramatically affect the output value so you must provide a value which you know will have a dramatic effect of the output. Such as is a bot is moving and just about to hit a wall, inserting an input value which will make the bot turn quickly. This is more relevant in unsupervised learning.
    • Modified by:
      • Usually by an application logic or some object parameters like a position of a bot in a game.
    • Output
      • Could be in the same information “category” or exactly the same as the startup inputs.The output is used to make a decision and/or take an action. Could also be used as inputs to different Neural to achieve a grander result.
    • Neuron layers
      • Are used to use weight values to help the inputs converge towards a desired output – unsupervised learning:
        • Modifying weights through GA to give variation and achieve a “desired” outcome, this is usually determined by a fitness function
        • Notice that the inputs can act as fitness functions, especially if they are done in such a way that are pre calculated based on a logic.
        • Neuron layers weights can also be recalculated until a desired outcome is achieved within certain error limit – supervised learning
      • Weights
        • Modified by:
          • Genetic Algorithms
          • Fuzzy logic
          • Backpropagation
          • Or any other logic you have in mind
        • Fitness functions
          • Unsupervised learning: it is defined based on the output outcome and how it relates to the world, for example after the network has finished the outcome is used to determine what happens in the world, values can be derived and updated to create a fitness function which can be used in a GA to help the NN converge for better results.
            • Eventually the “fitness” of the weight values determine how well the network will perform and be closes to the desired output based on the fitness calculation.
          • Supervised learning: in this case it is the desired target output value within the error limit plus the logic which advances and performs calculation on the network to get closer to the desired target output.

 

Tips

 

“Sometimes you will get the best performance from your neural networks if you rescale the input data so that it centers on zero. This little tip is always worth considering when designing your networks. I haven’t done it this way for this minesweeper project because I wanted to use a more intuitive approach.” (Buckland, 2002 )

“It’s always a good exercise to try and figure out a way of using the least amount of inputs that still convey the information required for the network to solve the problem. The fewer inputs your networks use, the fewer neurons are required. Fewer neurons mean faster training and fewer calculations, which makes for a speedier network.” (Buckland, 2002 )

“In my experience, I have found that treating the neurons as individual units when implementing crossover gives better results than splitting the genomes at random points along the length of the chromosome.” (Buckland, 2002 )

“So, when designing your own networks, you have to carefully balance pre-calculating a lot of the input data (which may be heavy on the CPU but leads to faster evolution times) and letting the network figure out the complex relationships between the input data (which usually takes longer to evolve but can often be much less CPU intensive).” (Buckland, 2002 )

“Some tasks may benefit from a small amount of very short-term memory. This can be achieved simply and quickly by feeding back the neural network’s output. For example, with the minesweepers, you would create a network with an additional two inputs, and then use the previous generation’s outputs (m_lTrack and m_rTrack) as the additional two inputs. This type of network, one that feeds back to itself in someway, is called a recurrent network. This idea can be extended to feedback any number of the previous generation’s outputs, although, this will slow down the processing of the network a great deal and is best avoided. In a game, you want your networks to be as speedy as possible.” (Buckland, 2002 )

“Neural networks, in my opinion, are better used in a modular way. For example, you could train up separate networks for particular sorts of behavior, such as pursuit, flee, explore, and gather, and then use another neural network as a sort of state machine to choose which of the behaviors is relevant at any given time. Or even use a simple finite state machine to choose which network is appropriate.” (Buckland, 2002 )

 

Bibliography

Buckland, M. (2002 ). AI Techniques For Game Programming. Premier Press.

Rabin, S. (2003). AI Game Programming Wisdom 2. Charles River Media.

Rajashekaran, S. (2004). Neural Networks, Fuzzy Logic and Genetic Algorithms.

Shiffman, D. (2015, 10 22). Nature of Code. Retrieved from Nature of Code: http://natureofcode.com/

Stackoverflow – Role of Bias in Neural Networks. (2015, 10 23). Retrieved from Stackoverflow: http://stackoverflow.com/questions/2480650/role-of-bias-in-neural-networks

Stackoverflow – why Bias is necessory in NN , and should we have seperate bias for each layer. (2015, 10 23). Retrieved from Stackoverflow : http://stackoverflow.com/questions/7175099/why-bias-is-necessory-in-nn-and-should-we-have-seperate-bias-for-each-layer

Stanley, K. O. (2005). Real-Time Neuroevolution in the NERO Video Game. Austin: Department of Computer Sciences – University of Texas.

Stanley, K. O. (2005). Real-Time Neuroevolution in the NERO Video Game. Austin, Texas: Department of Computer Sciences University of Texas at Austin.

 

 

Learning AI – Part 3: Genetic Algorithms – Improving the algorithms and more advanced topics

 

Introduction

In this part and final (for the moment) on Genetic Algorithms I will introduce some new topic, operators and ways of thinking and improving on your Genetic Algorithm.

Most of the topics discussed here I gathered from the book AI Game Programming Wisdom 2 in the section regarding Genetic Algorithms.

Previous parts:

Learning AI – Part 1: Genetic Algorithms Intro

Learning AI – Part 2: Genetic Algorithms Continued

Source codes:

I do have to warn though because I am moving at the moment to the neural network so I only created the base codes based on the books and C++ source codes for my Unity project to be used later. So there are some problems at the moment with the code but the code samples can work as an example to you to modify and use how it best fits you.

Also keep looking at this GitHub address for update to the GA sample classes used in the previous posts and this one: https://github.com/lionadi/NatureOfCodePlayground/tree/master/AIEngineNew/Assets/Scripts/AI

Contents

Introduction. 1

Niching techniques. 1

Explicit fitness sharing. 1

Speciation. 2

The compatibility function. 2

Co-evolution. 2

The Michalewicz method. 2

Mutation operators. 3

Crossover operators. 3

Genetic programming. 3

Growth in Genetic Algorithms. 3

Growth. 3

Environment. 4

Neutral network. 4

Comparing parametrization and growth. 4

Few helper functions

Bibliography. 5

 

Niching techniques

“Can be great for retaining population diversity, and are particularly useful where fitness landscape might contain multiple peaks or where it is essential to protect new innovation within a population.” (Rabin, 2003)

Explicit fitness sharing

“Is a mechanism where individuals with similar genetic properties are grouped together. Each individual’s score is then divided by the number of genomes within its group.

Newfitness = oldfitness / numberofneighboors

This punishes the fitness scores of individuals who have many similar neighbors, thereby preventing any one group from growing too large and taking over the population.” (Rabin, 2003)

Speciation

“Goes one step further by separating the genomes into groups in the same way as explicit fitness sharing, but this time individuals are only allowed to breed with members of their own species. Typically, a species is killed when either its size decreases to zero or its fitness has not increased within a user-defined number of generations. This means that the individuals that would normally have died out early in the evolution of a population remain active for much longer, protected among their species members. Because of the protection you can experiment with much larger mutation rates than normal.” (Rabin, 2003)

The compatibility function

“To determine if one genome should belong in the same species as another, you must use a function that compares two genes strings and returns a compatibility distance. If the distance is below a user defined threshold, then the genomes are considered to be in the same species. This compatibility function varies considerably depending on the encoding representation.

Dist= (x-y) / n

N = the number of genes in each chromosome

X and y= represent two different individuals in the population

Each iteration of the genetic algorithm, the compatibility function is used to test every individual against the first member in each species. If the distance is within a user defined threshold, then the individual is added to the appropriate species. Id the individual is incompatible with all the current species, then a new species is created and the individual is added to that.” (Rabin, 2003)

Sample code on the species class which will hold different species:



public class Species
 {
 //this is the genome all other genomes in the population are
 //compared to see if they should be included in this species or not
 Host SampleGenome;

 List&lt;Host&gt; Members;

 //the number of generations that has passed without the fittest
 //member in the species showing an improvement.
 int numGensNoImprovement;

 float expectedNumberOfOffspring;

 float bestEverFitness;

 //the combined fitness scores of every member
 float totalFitness;

 //it's often useful to have an identity number for the species
 int id;



 public Species(Host firstMember, int id)
 {
 this.Members = new List&lt;Host&gt;();
 this.id = id;
 this.SampleGenome = firstMember;
 this.expectedNumberOfOffspring = 0;
 this.numGensNoImprovement = 0;
 Members.Add(firstMember);

 bestEverFitness = firstMember.Fitness();

 totalFitness += firstMember.Fitness();
 }

 public void AddGenome(Host genome)
 {
 Members.Add(genome);

 totalFitness += genome.Fitness();

 if (genome.Fitness() &gt; bestEverFitness)
 {
 bestEverFitness = genome.Fitness();

 //fitness has improved so this can be reset
 numGensNoImprovement = 0;
 }
 }

 ///
&lt;summary&gt;
 /// selects a genome from the species using tournament selection. 
 /// this method uses tournament selection to spawn genomes from the 
 /// species.
 /// 
 /// As it is set presently it uses a high selection pressure.
 /// &lt;/summary&gt;

 /// &lt;returns&gt;&lt;/returns&gt;
 public Host SpawnGenome()
 {
 //first chose the number in the tournament. selection_pressure must be
 //between zero and 1.0
 int NumInComp = 0; float selection_pressure = 0.5F;

 while (NumInComp &lt; 1)
 {
 NumInComp = (int)(NumMembers() * selection_pressure);

 selection_pressure += 0.1F;
 }

 int winner = 0;

 for (int i = 0; i &lt; NumInComp; ++i) { int ThisTry = RandomProvider.RND.Next(0, Members.Count() - 1); if (Members[ThisTry].Fitness() &gt; Members[winner].Fitness())
 {
 winner = i;
 }
 }

 return Members[winner];
 }


 ///
&lt;summary&gt;
 /// makes sure the sample genome is always the genome with the highest fitness found so far
 /// &lt;/summary&gt;

 public void UpdateSampleGenome()
 {
 if (Members.Count &gt; 0)
 {
 if (Members.Last().Fitness() &gt; SampleGenome.Fitness())
 {
 SampleGenome = Members.Last();
 }

 else
 {
 Members[0] = SampleGenome;
 }
 }

 ++numGensNoImprovement;
 }

 public void Clear()
 {
 SampleGenome = Members[0];
 expectedNumberOfOffspring = 0.0F;
 Members.Clear();
 totalFitness = 0.0F;
 }

 public Host Sample() { return SampleGenome; }

 public float ExpectedOffspring() { return expectedNumberOfOffspring; }

 ///
&lt;summary&gt;
 /// adjusts the fitness scores so they are set to the value of their expected number of offspring
 /// &lt;/summary&gt;

 /// &lt;param name="totalFitnessForPopoulation"&gt;&lt;/param&gt;
 /// &lt;param name="PopSize"&gt;&lt;/param&gt;
 public void SetExpectedOffspring(float totalFitnessForPopoulation, int PopSize)
 {
 //check that we have some fitness scores to work with
 if (totalFitnessForPopoulation == 0.0) return;

 expectedNumberOfOffspring = 0.0F;

 for (int gen = 0; gen &lt; Members.Count(); ++gen)
 {
 float ExpectedForThisIndividual =

 (Members[gen].Fitness() / totalFitnessForPopoulation) * PopSize;

 expectedNumberOfOffspring += ExpectedForThisIndividual;
 }
 }

 public int GenerationsNoImprovement() {return numGensNoImprovement;}

 public bool Empty() {return (Members.Count() == 0);}

 public float BestEverFitness() {return bestEverFitness;}
 public float TotalFitness() {return totalFitness;}

 ///
&lt;summary&gt;
 /// this method applies explicit fitness sharing by dividing each member's
 /// fitness by the number of members in the species
 /// &lt;/summary&gt;

 public void FitnessShare()
 {
 float NewTotal = 0.0F;

 //divide each member's fitness by the number in the species
 for (int m = 0; m &lt; Members.Count(); ++m)
 {
 Members[m].SetFitness(Members[m].Fitness() / NumMembers());

 NewTotal += Members[m].Fitness();
 }

 totalFitness = NewTotal;
 }

 public int ID() {return id;}
 int NumMembers() {return Members.Count();}

 public bool IsLessThan(Species species)
 {
 return (this.BestEverFitness() &lt; species.BestEverFitness());
 }

}


The helper function to be used with the Species class.


///
&lt;summary&gt;
 /// Separate the population into species. This separates the individuals into species of similar genomes.
 /// &lt;/summary&gt;

 public void Speciate(ref List&lt;Host&gt; population)
 {
 //first clear the existing members and kill off any non developing
 //species
 this.Species.Clear();

 //now separate the population into species
 for (int gen = 0; gen &lt; population.Count; ++gen)
 {
 bool bAdded = false;

 foreach(Species curSpecies in this.Species)
 {
 //calculate the compatibility score
 double cs = Compatibility(population[gen], curSpecies.Sample());

 //if the compatibility score is less than our tolerance then
 //this genome is added to the species
 if (cs &lt; CompatibilityTolerance) { curSpecies.AddGenome(population[gen]); bAdded = true; break; } }//next species if (!bAdded) { //not compatible with any current species so create a new //species Species.Add(new Species(population[gen], NextSpeciesID++)); } }//next genome //update all the species to make sure their sample member is set //to the best genome found so far. Kill off any empty species //foreach (Species curSpecies in this.Species) for(int x = this.Species.Count -1; x &gt;= 0; --x)
 {
 var curSpecies = this.Species[x];
 curSpecies.UpdateSampleGenome();

 if ((curSpecies.Empty() ||
 (curSpecies.GenerationsNoImprovement() &gt; GenerationsAllowedWithoutImprovement)) &amp;&amp;
 (Species.Count &gt; 1))
 {
 Species.RemoveAt(x);
 }
 }
 }

 ///
&lt;summary&gt;
 /// this allocates a compatibility score between two genomes. If the
 /// score is below a certain threshold then the two genomes are &lt;/summary&gt;

 /// considered to be of the same species&lt;param name="g1"&gt;&lt;/param&gt;
 /// &lt;param name="g2"&gt;&lt;/param&gt;
 /// &lt;returns&gt;&lt;/returns&gt;
 public float Compatibility(Host g1, Host g2)
 {
 if (g1.DNA.Genes.Count != g2.DNA.Genes.Count) return 0;

 float RunningTotal = 0.0F;

 for (int gene = 0; gene &lt; g1.DNA.Genes.Count; ++gene)
 {
 //RunningTotal += Mathf.Abs(g1.Genes[gene] - g2.Genes[gene]);
 RunningTotal += Vector2.Distance(g1.DNA.Genes[gene], g2.DNA.Genes[gene]);
 }

 return RunningTotal / g1.DNA.Genes.Count;
 }

 ///
&lt;summary&gt;
 /// this method calculates the amount of offspring each species
 /// should produce.&lt;/summary&gt;

 /// &lt;param name="AmountNeeded"&gt;&lt;/param&gt;
 public void CalculateExpectedOffspring(int AmountNeeded)
 {
 //first calculate the total fitness of all active genomes
 float TotalFitness = 0.0F;

 foreach (Species curSpecies in this.Species)
 {
 //apply fitness sharing first
 curSpecies.FitnessShare();

 TotalFitness += curSpecies.TotalFitness();
 }

 //now it is necessary to calculate the expected amount of offspring
 //from each species
 double expec = 0.0;

 foreach (Species curSpecies in this.Species)
 {
 curSpecies.SetExpectedOffspring(TotalFitness, AmountNeeded);

 expec += curSpecies.ExpectedOffspring();
 }
 }

 ///
&lt;summary&gt;
 /// this sorts the species and assigns a color to each one.
 /// The color is just cosmetic to be used as a visual aid.&lt;/summary&gt;

 public void SortAndAssignVisualAid()
 {
 if (this.Species.Count &lt; 0) return; this.Species.OrderByDescending(o =&gt; o.BestEverFitness());
 }



Co-evolution

“If you have different species competing with each other, they have to work harder at solving the problem. If the fitness of one is somehow inversely proportional to the fitness of the other, you have competition. This can greatly increase the speed and quality of the evolution process.” (Rabin, 2003)

The Michalewicz method

“Contains several mutation and crossover operators that are used in combination to fully exploit the characteristics of real value encoding GAs.

Mutation operators

  • Boundary mutation: With probability p, this operator changes the value of a gene to either its minimum possible value, Gmin, or its maximum possible value Gmax.
  • Replace mutation: With probability p, this operator resets a gene to a uniform random between Gmin and Gmax.
  • Non-Uniform mutation: With probability p, this operator adjusts a gene’s size by a small random amount, the limits of which decrease over time.

Crossover operators

  • Arithmetical crossover: This simply averages the values of the genes at each locus.
  • Simple crossover: this operator is the same as a single point crossover.
  • Heuristics crossover: Given the parents G1 and G2 this operator creates an offspring according to Equation: Child = r(G2 – G1) + G2
    • Variable G2 is the fitter of the two parents, and r is a random number between 0 and 1.

Alone these operators produce bad results but combined together they have a tendency to produce fitter offspring’s.

Tip: Using adaptive probability distribution for the operators can be speedier and lose little in performance. This means that each operator uses the same equal probability.” (Rabin, 2003)


/// &lt;summary&gt;
 /// displaces a gene's value by a small random amount (limited by
 /// MutationDelta)
 /// &lt;/summary&gt;
 /// &lt;param name="genes"&gt;&lt;/param&gt;
 public void MutateUniform(ref List&lt;Vector2&gt; genes)
 {
 for (int i = 0; i &lt; genes.Count; i++)
 {
 //flip this bit?
 if ((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &lt; MutationRate)
 {
 float angle = UnityEngine.Random.Range(0, AIConstants.TWO_PI);
 genes[i] = ((new Vector2(UnityEngine.Mathf.Cos(angle), UnityEngine.Mathf.Sin(angle))) * UnityEngine.Random.Range(0, (float)RandomProvider.RandomClamped() * this.MutationDelta));
 }
 }
 }

 /// &lt;summary&gt;
 /// displaces the genes value by an amount described by a normal distribution
 /// &lt;/summary&gt;
 /// &lt;param name="genes"&gt;&lt;/param&gt;
 public void MutateGaussian(ref List&lt;Vector2&gt; genes)
 {
 for (int i = 0; i &lt; genes.Count; i++)
 {
 //flip this bit?
 if ((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &lt; MutationRate)
 {
 //genes[i] =
 
 /*
 //do we mutate this gene?
 if (RandFloat() &lt; m_dMutationRate)
 {
 gen.vecGenes[gene] += RandGaussian(0.0, 0.1);

 //make sure the value stays within the desired lims
 Clamp(gen.vecGenes[gene], 0.0, 1.0); 
 */
 }
 }
 }

 /// &lt;summary&gt;
 /// Sets a gene to either the min or max possible value (0 or 1 in this
 /// implementation)
 /// &lt;/summary&gt;
 /// &lt;param name="genes"&gt;&lt;/param&gt;
 public void MutateBoundary(ref List&lt;Vector2&gt; genes)
 {
 for (int i = 0; i &lt; genes.Count; i++)
 {
 float angle = UnityEngine.Random.Range(0, AIConstants.TWO_PI);
 //flip this bit?
 Vector2 tempVector = new Vector2(UnityEngine.Mathf.Cos(angle), UnityEngine.Mathf.Sin(angle)) * UnityEngine.Random.Range(0, AIConstants.maxforce);
 if (tempVector.x &lt; mutationBoundryValueMin.x &amp;&amp; tempVector.y &lt; mutationBoundryValueMin.y)
 {
 genes[i] = Vector2.zero;
 }
 else
 {
 genes[i] = this.mutationBoundryValueMax;
 }
 }
 } 
 
 

 public void MutateMichalewicz(ref List&lt;Vector2&gt; genes)
 {
 float chance = (float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1);

 if (chance &lt;= 0.333)
 {
 MutateBoundary(ref genes);
 }

 else if (chance &gt;= 0.667)
 {
 MutateUniform(ref genes);
 }

 else
 {
 MutateReplace(ref genes);
 }
 }

/// &lt;summary&gt;
 /// the Michalewicz crossover operator choses one of three different
 /// crossover operators based on an even probability
 /// &lt;/summary&gt;
 /// &lt;param name="mum"&gt;&lt;/param&gt;
 /// &lt;param name="dad"&gt;&lt;/param&gt;
 /// &lt;param name="baby1"&gt;&lt;/param&gt;
 /// &lt;param name="baby2"&gt;&lt;/param&gt;
 public void CrossoverMichalewicz(ref List&lt;Vector2&gt; mum, ref List&lt;Vector2&gt; dad, ref List&lt;Vector2&gt; baby1, ref List&lt;Vector2&gt; baby2)
 {
 if (((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &gt; CrossoverRate) || (mum == dad) || mum.Count &lt;= 0 || dad.Count &lt;= 0)
 {
 baby1 = mum;
 baby2 = dad;
 return;
 }

 float chance = (float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1);

 if (chance &lt;= 0.333)
 {
 CrossoverTwoPoint(ref mum, ref dad, ref baby1, ref baby2);
 }

 else if (chance &gt;= 0.667)
 {
 CrossoverAverage(ref mum, ref dad, ref baby1, ref baby2);
 }

 else
 {
 CrossoverHeuristic(ref mum, ref dad, ref baby1);
 CrossoverHeuristic(ref mum, ref dad, ref baby2);
 }
 }

/// &lt;summary&gt;
 /// This crossover operator simply averages the genes at each locus
 /// &lt;/summary&gt;
 /// &lt;param name="mum"&gt;&lt;/param&gt;
 /// &lt;param name="dad"&gt;&lt;/param&gt;
 /// &lt;param name="baby1"&gt;&lt;/param&gt;
 /// &lt;param name="baby2"&gt;&lt;/param&gt;
 public void CrossoverAverage(ref List&lt;Vector2&gt; mum, ref List&lt;Vector2&gt; dad, ref List&lt;Vector2&gt; baby1, ref List&lt;Vector2&gt; baby2)
 {
 for (int gen = 0; gen &lt; mum.Count; ++gen)
 {
 baby1.Add((mum[gen] + dad[gen]) * 0.5F);
 baby2.Add((mum[gen] + dad[gen]) * 0.5F);
 }
 }

 /// &lt;summary&gt;
 /// this operator creates a child whos genes are biased towards the 
 /// fitter parent.
 ///
 /// The heuristic used is r(V1-V2) + V1 where V1 is the fitter parent
 /// &lt;/summary&gt;
 /// &lt;param name="mum"&gt;&lt;/param&gt;
 /// &lt;param name="dad"&gt;&lt;/param&gt;
 /// &lt;param name="baby1"&gt;&lt;/param&gt;
 /// &lt;param name="baby2"&gt;&lt;/param&gt;
 public void CrossoverHeuristic(ref List&lt;Vector2&gt; fittest, ref List&lt;Vector2&gt; not_so_fit, ref List&lt;Vector2&gt; baby1)
 {

 float rate = (float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1);

 //iterate down the length of the genome using the heuristic
 for (int gene = 0; gene &lt; fittest.Count; ++gene)
 {
 Vector2 NewGeneValue = fittest[gene] + rate *
 (fittest[gene] - not_so_fit[gene]);
 baby1.Add(NewGeneValue);
 }
 }

Genetic programming

“Genetic programming is a powerful extension to evolutionary computing. They allow considerable flexibility, allowing the application programmer to develop solutions of more diverse structure that those provided by genetic algorithms. Grammatical evolution is one way to implement genetic programming while minimizing the computation expense related to the creation and subsequent elimination of nonsense organism.” (Rabin, 2003)

Growth in Genetic Algorithms

Idea: Enhancements through flexibility

  • Growth
  • Neutral networks
  • Variable-length genome
  • Speciation
  • Co-evolution.

Growth

Look at nature for examples on how to give more “life” to Gas and not look to static created by a mechanical code. In nature things grow rather than are strictly parametrized. Look at this growth methods from biology, chemistry etc. (Rabin, 2003)

Environment

Such example would be to look at the environment something lives in and how they affect one another. What factors, things and properties of both the environment and the entity play into the role of environment based growth? When do the growth stop for a living organism? Take into consideration how the growth is going to be terminated. Look again into nature. (Rabin, 2003)

Neutral network

A concept that increases evolvability. Have some junk DNA switched on inside an important host. This junk DNA can then be subject to the same rules of evolution. This might not produce great results at first but every now and then might help be of advantage. Increases the probability of finding a better solution.

Implementation ideas:

  • Scanning through the genome with a logic that determines an interaction values by a single mutation, for example.
  • Variable-length genomes: Have unequal crossover points. Both parents have their own crossover points so a child can have a genome much bigger or smaller than its two parents, which allows evolution to control the complexity of the solutions.
  • Another example would be to duplicate a gene once it is identified or to just make a random duplications during crossover.

This would mean that the system cannot be a simple parametrization system.

(Rabin, 2003)

Comparing parametrization and growth

Aspect Parametrization Growth
Encoding scheme +Intuitive (explicit) -Incomprehensible
+/- Environment independent +/- Environment dependence
+ Immediate mapping ·         Needs growth period
Evolvability ·         Restricted/fixed complexity + Potentially limitless
·         Designer biased + Evolution free to play
·         Mutation effect fixed + Neutral networks
·         Complexity DNA length + Controllable mutation
+/- Just optimization + Specialization

(Rabin, 2003)

Few helper functions


/// &lt;summary&gt;
 /// this function calculates the variance of the population
 /// &lt;/summary&gt;
 /// &lt;param name="hosts"&gt;&lt;/param&gt;
 /// &lt;returns&gt;&lt;/returns&gt;
 float CalculateVariance(ref List&lt;Host&gt; hosts)
 {
 float RunningTotal = 0.0F;

 //first iterate through the population to calculate the standard
 //deviation
 for (int gen = 0; gen &lt; hosts.Count; ++gen)
 {
 RunningTotal += (hosts[gen].DNA.Fitness - this.AverageFitnessScore) *
 (hosts[gen].DNA.Fitness - this.AverageFitnessScore);
 }

 return RunningTotal / hosts.Count;
 }

 /// &lt;summary&gt;
 /// calculates the fittest and weakest genome and the average/total 
 /// fitness scores.
 /// &lt;/summary&gt;
 /// &lt;param name="source"&gt;&lt;/param&gt;
 public void CalculateBestWorstAverageTotalFitnessScore(ref List&lt;Host&gt; source)
 {
 this.TotalFitnessScore = 0;
 this.BestFitnessScore = 0;
 this.WorstFitnessScore = float.MaxValue;
 foreach (Host host in source)
 {
 float normalizedFitnessScore = host.DNA.Fitness;

 if (normalizedFitnessScore &lt; this.WorstFitnessScore)
 this.WorstFitnessScore = normalizedFitnessScore;

 if (normalizedFitnessScore &gt; this.BestFitnessScore)
 this.BestFitnessScore = normalizedFitnessScore;

 this.TotalFitnessScore += normalizedFitnessScore;
 }

 this.AverageFitnessScore = this.TotalFitnessScore / source.Count;
 }


Bibliography

Rabin, S. (2003). AI Game Programming Wisdom 2.

 

 

 

 

 

 

Learning AI – Part 2: Genetic Algorithms Continued

Introduction

OK, in the last post I wrote some basics on Genetic Algorithms and I showed an example which solved a text “puzzle”. In this post I will go a bit more in-depth into Genetic Algorithms and show you an example of a Genetic Algorithm solving a “best” possible path to different targets while avoiding obstacles.

I will start by showing the target seeking Genetic Algorithm in action. Then I will go through the code explaining the important parts. After that I will spend some time on general GA related topics and give some explanations and sample codes.

This post is more about gathering as much details as possible into on location. This works as notes for me and hopefully is someone else is looking at this post he or she might find something useful. This is a work in progress so I apologize for any possible errors in this post. I’ll fix them when I become aware of them and when I can.

Updated 16.9.2015: Made some additions to the descriptions to existing operators and scaling techniques.

Links:

Part 1: LEARNING AI – PART 1: GENETIC ALGORITHMS INTRO

Contents

Introduction. 2

Sample application. 2

The update function. 3

Sample code. 3

The fitness score calculation. 4

Sample code. 4

Images on the path solving application. 5

Genetic algorithms explained. 5

What is a Genetic Algorithm.. 5

Genetic Algorithms Overview.. 6

Outline of the Basic Genetic Algorithm.. 7

Search Space. 7

Implementation Details. 8

Applications of GA.. 9

Strengths of GAs. 10

Limitations of GAs. 15

Genetic algorithm operators, selectors, ranking and encoding. 19

Selection. 19

Steady State Selection. 19

Fitness Proportionate Selection. 20

Elitism.. 20

Roulette Wheel Selection. 20

Stochastic Universal Sampling. 20

Tournament Selection. 21

Crossover. 21

Partially-Mapped Crossover. 22

Order-Based Crossover. 22

Position-Based Crossover. 23

Single-Point Crossover. 23

Two-Point Crossover. 23

Multi-Point Crossover (parameterized uniform crossover). 24

Alternative crossover methods. 24

Mutation. 24

Scramble Mutation (SM). 24

Exchange Mutation Operator. 24

Displacement Mutation. 25

“Normal mutation”(Don’t know the proper name for this one J ). 25

Insertion Mutation. 25

Inversion Mutation. 25

Displaced Inversion Mutation. 25

Encoding. 25

Scaling Techniques. 26

Rank Scaling. 26

Sigma Scaling. 26

Boltzmann Scaling. 26

Optimization tips. 27

Data handling. 27

Bibliography. 27

Sample application

The sample application is rather simple. It has the following tasks to perform.

  1. The object which is the focus of our attention is to find target
  2. Arrange the targets by how close they are from the initial starting position
  3. Then chose the closest target
  4. Next calculate the best possible path to the target. Things to take into consideration:
    1. Avoiding obstacles
    2. Finding the fastest route with least amount of steps
    3. Favoring paths which last location is closest to a target
    4. Favoring paths which travel the least amount of space
  5. When the best possible path has been found to the target using the path.
  6. Go to the next target until no more targets are left and repeat steps 4-6

Here are the link to the source codes for those whom are interesting in poking around :). I warn though that the code and the solution is raw and unpolished. It does the job when I am learning GAs at the moment:

Sample unity project for those who like to use unity: Download

Github source code

The GA solution most important piece of codes are:

  1. The main class named GA which is attached to an object in unity and start the GA operations to find an optimal path: Source
  2. The Host class (also known as chromosome or phenotype) class which is responsible calculations on the DNA data: Source
  3. The Genome class(also known as genotype or DNA) this is the actual data container for an optimal path: Source

The update function

Under the hood the following things happen:

  1. First certain values are initialized to help a quick and solid paths finding using GA
  2. Generate a starting population and calculate initial fitness scores.
  3. Start the cycles for solving best path to a target
    1. Check to see if there is a fittest path that has reached the target without hitting any obstacles.
      1. If this is so then draw the path and move the object to the target and go to the next target.
    2. If there is no fittest path yet solved then start solving the best path
      1. start the generation processing
        1. Start selection process based on fitness score
        2. Create offspring’s to populate with parents data
        3. Do a crossover
        4. Mutate
        5. Add the offspring’s to the mating pool
        6. Repeat the step until max population size has been reached for the mating pool
      2. Assign the mating pool as the new population
  • Calculate new fitness score based on the new population
  1. Perform a possible scaling operation
  2. Draw the current generations best path

 

As you can see the sample GA application follow similar steps found in GA algorithms. Later I’ll go more deep into the details of GA specific functionalities and how to apply them.

Sample code

For now take a look at the update function which performs these GA related operation:

float step = 0;


 // Check to see if the target has been reached
 if (FittestGenome != null && this.HitTarget && !this.HitObstacle)
 {
 if (pathPosition < (this.FittestGenome.DNALocations.Genes.Count))
 {
 {
 Debug.Log("target reached and no more calculations will be done. this path is to be drawn");
 // Move the object to the next position
 pathPosition++;

 if (pathPosition >= this.FittestGenome.DNALocations.Genes.Count - 1)
 return;

 step = speed * Time.deltaTime;

 // Some simple waypoints drawing on the screen for the fittest genome
 if (pathPosition > 0 && (pathPosition - 1) < this.FittestGenome.DNA.Genes.Count - 1)
 {
 this.previousPosition = this.FittestGenome.DNALocations.Genes[pathPosition - 1];
 Debug.DrawLine(previousPosition, this.FittestGenome.DNALocations.Genes[pathPosition], Color.red, 60);
 waypoints.Add(GameObject.CreatePrimitive(PrimitiveType.Cube));
 waypoints[waypoints.Count - 1].transform.position = this.FittestGenome.DNALocations.Genes[pathPosition];
 waypoints[waypoints.Count - 1].transform.localScale *= 0.05F;
 }


 StartCoroutine(MoveObject(transform, transform.position, this.FittestGenome.DNALocations.Genes[pathPosition], time, pathPosition, this.FittestGenome.DNALocations.Genes.Count - 1));
 }
 return;
 }
 // If the target has reached it's position then do not do anything else or reset the data
 else if (pathPosition >= this.FittestGenome.DNALocations.Genes.Count)
 {
 var d = Vector2.Distance(transform.position, this.FittestGenome.DNALocations.Genes[pathPosition - 1]);
 if (this.myRigidbody.IsSleeping() && Vector2.Distance(transform.position, this.FittestGenome.DNALocations.Genes[pathPosition - 1]) < 1)
 this.ResetGAData();

 return;
 }
 }
 else
 {
 List<Host> matingPool = new List<Host>();
 
 int NewBabies = 0;

 var host = this.Hosts;

 while (NewBabies < PopSize)
 {
 Host mum = MonteCarloSelection();
 Host dad = MonteCarloSelection();

 Host baby1 = new Host(0, this.transform.position, sqrMinimumExtent, layerMask);
 Host baby2 = new Host(0, this.transform.position, sqrMinimumExtent, layerMask);
 this.Crossover(ref mum.DNA.Genes, ref dad.DNA.Genes, ref baby1.DNA.Genes, ref baby2.DNA.Genes);

 Mutate(ref baby1.DNA.Genes);
 Mutate(ref baby2.DNA.Genes);

 matingPool.Add(baby1);
 matingPool.Add(baby2);

 NewBabies += 2;
 }
 this.Hosts = matingPool;
 this.UpdateFitnessScores();
 var hosts = this.Hosts;
 this.FitnessScaleRankingToFloatRangeZeroToOne(ref hosts);
 ++this.Generation;

 this.DrawFailedPaths();

 step = speed * Time.deltaTime;

 }

The fitness score calculation

But currently I will only show you the calculations which define the fitness values and plays the major role in determining a valid path to a target.

In this sample there are two classes which hold the actual data for the paths. One is named as genome which holds the travel data. The other is named Host which holds the genome data and operates on it.

Sample code

public Vector2 CalcualteEndLocationOfHost(Vector2 targetLocation)
 {
 Color rayColor = Color.yellow;
 float rayLenght = 0.5F;
 this.EndLocation = this.StartLocation;
 for(int x = 0; x &amp;amp;lt; this.DNA.Genes.Count; ++x) { // Update a new position for the host acceleration += this.DNA.Genes[x]; velocity += acceleration; Vector2 previousPosition = this.EndLocation; this.EndLocation += velocity; // Check to see if the new position has moved to another location Vector2 movementThisStep = this.EndLocation - previousPosition; float movementSqrMagnitude = movementThisStep.sqrMagnitude; if (movementSqrMagnitude &amp;amp;gt; sqrMinimumExtent)
 {
 float movementMagnitude = Mathf.Sqrt(movementSqrMagnitude);

 // Check to see if the host has hit something
 RaycastHit2D hitInfo = Physics2D.Raycast(previousPosition, movementThisStep, movementMagnitude, layerMask.value);
 //Debug.DrawRay(previousPosition, movementThisStep, rayColor, rayLenght);
 var distanceToTarget = Vector2.Distance(targetLocation, this.EndLocation);

 this.DistanceTraveled += distanceToTarget;
 
 //if (!hitInfo.collider)
 {
 this.DNALocations.Genes.Add(this.EndLocation);
 
 }
 // If a hit occured check to see is it the target or some other obstacle
 if(hitInfo.collider)
 {
 

 // this is must the the target
 if (distanceToTarget &amp;amp;lt; 0.2 &amp;amp;amp;&amp;amp;amp; !this.HitObstacle)
 {
 rayColor = Color.green;
 //this.DNALocations.Genes.Add(this.EndLocation);
 this.HitTarget = true;
 
 break;
 }
 // We have hit an obstacle this stop processing
 else
 {
 rayColor = Color.red;
 this.HitObstacle = true;
 this.obstaclesHit++;
 //break;
 }
 }
 
 if(!this.HitTarget)
 this.finnishTime++;
 }
 acceleration *= 0;
 }

 return this.EndLocation;
 }

 


public float CalculateFitnessAndDistance(Vector2 targetLocation)
 {
 if(this.EndLocation != this.StartLocation)
 {
 this.DistanceToTarget = Vector2.Distance(targetLocation, this.EndLocation);
 float distanceToTargetFromStartLocation = Vector2.Distance(targetLocation, this.StartLocation);
 // The target has been reached and make sure we are not dividing by zero.
 if (this.DistanceToTarget == 0)
 this.DistanceToTarget = 1;

 // This means only the target was hit and make sure that we do not end up diving by zero
 if (this.obstaclesHit == 0)
 this.obstaclesHit = 1;

 /* The fitness score is based on four things. 
 1. The time it takes a path to reach its target, if time is not taken into consideration the slowest and safest path will win
 2. the distance from the path, if distance is not taken into consideration the result would be a long path
 3. and how many obstacles hit along the path, if obstacles are not taken into consideration the GA will not know if a path is good or bad even if it hits obstacles and how bad it is. The more obstacles a path hits the more unlikely it is to get reproduced.
 4. The travel distance. The smaller the distance is the better the fitness score will be.
 In each of the values the lower the time, or the distance or the obstacles hit the better the fitness score is. That is the score will be closer to 1 or above it for the best possible path.
 The higher any value is the more likely it is to not be the most optimal path. The worst path is the one that hits obstacles.
 */

 

 var calculation = (this.finnishTime) * this.DistanceToTarget * this.obstaclesHit * this.DistanceTraveled;
 this.DNA.Fitness = 1 / calculation;
 }
 // We have not reached the target yet, this is another obstacle and the fitness must be reduced. We want to penalize the path for any obstacles. This is not what we want in the population for possible solutions.
 if(this.HitObstacle)
 {
 this.DNA.Fitness *= 0.1F;
 }

 // Award the path for hitting the target.
 if(this.HitTarget)
 {
 this.DNA.Fitness += 1;
 }

 return this.DNA.Fitness;
 }

The genome code above is rather simple. All it does is store the data and initializes the genome with random vectors pointing to direction where to go next.

The host data is the actual place where the main fitness calculation takes place based on the genome data.

Now take a look at the function: CalcualteEndLocationOfHost. This function is called before the fitness calculation function named: CalculateFitnessAndDistance. In the CalcualteEndLocationOfHost function pre fitness calculation operations are done such as determining if the object has hit obstacles, how many of them, has it hit the target and also calculates the path for the object.

The fitness score is then calculated in the CalculateFitnessAndDistance function. The fitness score is based on four things:

  1. The time it takes a path to reach its target, if time is not taken into consideration the slowest and safest path will win
  2. the distance from the path, if distance is not taken into consideration the result would be a long path
  3. and how many obstacles hit along the path, if obstacles are not taken into consideration the GA will not know if a path is good or bad even if it hits obstacles and how bad it is. The more obstacles a path hits the more unlikely it is to get reproduced.
  4. The travel distance. The smaller the distance is the better the fitness score will be.

In each of the values the lower the time, or the distance or the obstacles hit the better the fitness score is. That is the score will be closer to 1 or above it for the best possible path.

The higher any value is the more likely it is to not be the most optimal path. The worst path is the one that hits obstacles. This is by the way a crude fitness score calculation method. There is definitely room for improvement. Currently it does the job.

This is basically it. There are of course more details such as the mutation operators, crossover and selection operators but I will cover these later since these are common to Genetic Algorithms and not specific to this path finding GA.

Also as with the previous GA example solving the text puzzle the same GA related parameters need to be defined and tuned for optimal performance. These are:

  1. The Population size
  2. Crossover rate (this is a new one, simply determined if a crossover should be performed by a random floating point value between 0 and 1.)
  3. Mutation rate
  4. Genome genes amount(in other words how many steps in a path)

Images on the path solving application

Now it’s time to look at some cool visual images on how the path finding operates.

In this first image you can see how the very first generation has no specific knowledge where to go yet. It goes all over the place in a circular path. The yellow lines represent path steps taken which do not collide with obstacles while red lines represent the path hitting an obstacle.

start failed generations

The next image shows you close to the very last generation in the path solving GA. Here you can see that the algorithms has converged towards the target and is just about to find the proper path based on the fitness score.

end near the resolution

In this last image you can see the algorithm in play later just searching for possible best path (the green lines). While the red lines represent paths traveled by accepted paths.

normal path seeking sample

Genetic algorithms explained

 

Here I have gathered some explanations from other sources to help you grasp and get a better idea of GAs. These also work for me as notes for later usage.

What is a Genetic Algorithm

“Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetics. As such they represent an intelligent exploitation of a random search used to solve optimization problems. Although randomised, GAs are by no means random, instead they exploit historical information to direct the search into the region of better performance within the search space. The basic techniques of the GAs are designed to simulate processes in natural systems necessary for evolution, specially those follow the principles first laid down by Charles Darwin of “survival of the fittest.”. Since in nature, competition among individuals for scanty resources results in the fittest individuals dominating over the weaker ones.” http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol1/hmw/article1.html

“Concisely stated, a genetic algorithm (or GA for short) is a programming technique that mimics biological evolution as a problem-solving strategy. Given a specific problem to solve, the input to the GA is a set of potential solutions to that problem, encoded in some fashion, and a metric called a fitness function that allows each candidate to be quantitatively evaluated. These candidates may be solutions already known to work, with the aim of the GA being to improve them, but more often they are generated at random.

 

The GA then evaluates each candidate according to the fitness function. In a pool of randomly generated candidates, of course, most will not work at all, and these will be deleted. However, purely by chance, a few may hold promise – they may show activity, even if only weak and imperfect activity, toward solving the problem.

 

These promising candidates are kept and allowed to reproduce. Multiple copies are made of them, but the copies are not perfect; random changes are introduced during the copying process. These digital offspring then go on to the next generation, forming a new pool of candidate solutions, and are subjected to a second round of fitness evaluation. Those candidate solutions which were worsened, or made no better, by the changes to their code are again deleted; but again, purely by chance, the random variations introduced into the population may have improved some individuals, making them into better, more complete or more efficient solutions to the problem at hand. Again these winning individuals are selected and copied over into the next generation with random changes, and the process repeats. The expectation is that the average fitness of the population will increase each round, and so by repeating this process for hundreds or thousands of rounds, very good solutions to the problem can be discovered.

 

As astonishing and counterintuitive as it may seem to some, genetic algorithms have proven to be an enormously powerful and successful problem-solving strategy, dramatically demonstrating the power of evolutionary principles. Genetic algorithms have been used in a wide variety of fields to evolve solutions to problems as difficult as or more difficult than those faced by human designers. Moreover, the solutions they come up with are often more efficient, more elegant, or more complex than anything comparable a human engineer would produce. In some cases, genetic algorithms have come up with solutions that baffle the programmers who wrote the algorithms in the first place!” http://www.talkorigins.org/faqs/genalg/genalg.html

 

Genetic Algorithms Overview

“GAs simulate the survival of the fittest among individuals over consecutive generation for solving a problem. Each generation consists of a population of character strings that are analogous to the chromosome that we see in our DNA. Each individual represents a point in a search space and a possible solution. The individuals in the population are then made to go through a process of evolution.

GAs are based on an analogy with the genetic structure and behavior of chromosomes within a population of individuals using the following foundations:

  • Individuals in a population compete for resources and mates.
  • Those individuals most successful in each ‘competition’ will produce more offspring than those individuals that perform poorly.
  • Genes from `good’ individuals propagate throughout the population so that two good parents will sometimes produce offspring that are better than either parent.

 

Thus each successive generation will become more suited to their environment.” http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol1/hmw/article1.html

Outline of the Basic Genetic Algorithm

  1. [Start] Generate random population of n chromosomes (suitable solutions for the problem)
  2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
  3. [New population] Create a new population by repeating following steps until the new population is complete
    1. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
    2. [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
    3. [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
    4. [Accepting] Place new offspring in a new population
  4. [Replace] Use new generated population for a further run of algorithm
  5. [Test] If the end condition is satisfied, stop, and return the best solution in current population
  6. [Loop] Go to step 2

http://www.obitko.com/tutorials/genetic-algorithms/ga-basic-description.php

Search Space

“A population of individuals are maintained within search space for a GA, each representing a possible solution to a given problem. Each individual is coded as a finite length vector of components, or variables, in terms of some alphabet, usually the binary alphabet {0,1}. To continue the genetic analogy these individuals are likened to chromosomes and the variables are analogous to genes. Thus a chromosome (solution) is composed of several genes (variables). A fitness score is assigned to each solution representing the abilities of an individual to `compete’. The individual with the optimal (or generally near optimal) fitness score is sought. The GA aims to use selective `breeding’ of the solutions to produce `offspring’ better than the parents by combining information from the chromosomes.

The GA maintains a population of n chromosomes (solutions) with associated fitness values. Parents are selected to mate, on the basis of their fitness, producing offspring via a reproductive plan. Consequently highly fit solutions are given more opportunities to reproduce, so that offspring inherit characteristics from each parent. As parents mate and produce offspring, room must be made for the new arrivals since the population is kept at a static size. Individuals in the population die and are replaced by the new solutions, eventually creating a new generation once all mating opportunities in the old population have been exhausted. In this way it is hoped that over successive generations better solutions will thrive while the least fit solutions die out.

New generations of solutions are produced containing, on average, better genes than a typical solution in a previous generation. Each successive generation will contain more good `partial solutions’ than previous generations. Eventually, once the population has converged and is not producing offspring noticeably different from those in previous generations, the algorithm itself is said to have converged to a set of solutions to the problem at hand.” http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol1/hmw/article1.html

 

Implementation Details

Based on Natural Selection

After an initial population is randomly generated, the algorithm evolves the through three operators:

  1. Selection which equates to survival of the fittest;
  2. Crossover which represents mating between individuals;
  3. Mutation which introduces random modifications.

 

  1. Selection Operator
  • key idea: give preference to better individuals, allowing them to pass on their genes to the next generation.
  • The goodness of each individual depends on its fitness.
  • Fitness may be determined by an objective function or by a subjective judgement.
  1. Crossover Operator
  • Prime distinguished factor of GA from other optimization techniques
  • Two individuals are chosen from the population using the selection operator
  • A crossover site along the bit strings is randomly chosen
  • The values of the two strings are exchanged up to this point
  • The two new offspring created from this mating are put into the next generation of the population
  • By recombining portions of good individuals, this process is likely to create even better individuals

 

  1. Mutation Operator
  • With some low probability, a portion of the new individuals will have some of their bits flipped.
  • Its purpose is to maintain diversity within the population and inhibit premature convergence.
  • Mutation alone induces a random walk through the search space
  • Mutation and selection (without crossover) create a parallel, noise-tolerant, hill-climbing algorithms

 

Effects of Genetic Operators

  • Using selection alone will tend to fill the population with copies of the best individual from the population
  • Using selection and crossover operators will tend to cause the algorithms to converge on a good but sub-optimal solution
  • Using mutation alone induces a random walk through the search space.
  • Using selection and mutation creates a parallel, noise-tolerant, hill climbing algorithm” http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol1/hmw/article1.html

 

Applications of GA

I think this quote is rather good at explaining uses for Genetic Algorithms:

“Genetic algorithms has been used for difficult problems (such as NP-hard problems), for machine learning and also for evolving simple programs. They have been also used for some art, for evolving pictures and music.

Advantage of GAs is in their parallelism. GA is travelling in a search space with more individuals (and with genotype rather than phenotype) so they are less likely to get stuck in a local extreme like some other methods.

They are also easy to implement. Once you have some GA, you just have to write new chromosome (just one object) to solve another problem. With the same encoding you just change the fitness function and it is all. On the other hand, choosing encoding and fitness function can be difficult.

Disadvantage of GAs is in their computational time. They can be slower than some other methods. But with todays computers it is not so big problem.

To get an idea about problems solved by GA, here is a short list of some applications:

  • Nonlinear dynamical systems – predicting, data analysis
  • Designing neural networks, both architecture and weights
  • Robot trajectory
  • Evolving LISP programs (genetic programming)
  • Strategy planning
  • Finding shape of protein molecules
  • TSP and sequence scheduling
  • Functions for creating images

http://www.obitko.com/tutorials/genetic-algorithms/recommendations.php

Other usages for GAs:

Strengths of GAs

 

  • “The first and most important point is that genetic algorithms are intrinsically parallel. Most other algorithms are serial and can only explore the solution space to a problem in one direction at a time, and if the solution they discover turns out to be suboptimal, there is nothing to do but abandon all work previously completed and start over. However, since GAs have multiple offspring, they can explore the solution space in multiple directions at once. If one path turns out to be a dead end, they can easily eliminate it and continue work on more promising avenues, giving them a greater chance each run of finding the optimal solution.However, the advantage of parallelism goes beyond this. Consider the following: All the 8-digit binary strings (strings of 0’s and 1’s) form a search space, which can be represented as ******** (where the * stands for “either 0 or 1”). The string 01101010 is one member of this space. However, it is also a member of the space 0*******, the space 01******, the space 0******0, the space 0*1*1*1*, the space 01*01**0, and so on. By evaluating the fitness of this one particular string, a genetic algorithm would be sampling each of these many spaces to which it belongs. Over many such evaluations, it would build up an increasingly accurate value for the average fitness of each of these spaces, each of which has many members. Therefore, a GA that explicitly evaluates a small number of individuals is implicitly evaluating a much larger group of individuals – just as a pollster who asks questions of a certain member of an ethnic, religious or social group hopes to learn something about the opinions of all members of that group, and therefore can reliably predict national opinion while sampling only a small percentage of the population. In the same way, the GA can “home in” on the space with the highest-fitness individuals and find the overall best one from that group. In the context of evolutionary algorithms, this is known as the Schema Theorem, and is the “central advantage” of a GA over other problem-solving methods (Holland 1992, p. 68; Mitchell 1996, p.28-29; Goldberg 1989, p.20).
  • Due to the parallelism that allows them to implicitly evaluate many schema at once, genetic algorithms are particularly well-suited to solving problems where the space of all potential solutions is truly huge – too vast to search exhaustively in any reasonable amount of time. Most problems that fall into this category are known as “nonlinear”. In a linear problem, the fitness of each component is independent, so any improvement to any one part will result in an improvement of the system as a whole. Needless to say, few real-world problems are like this. Nonlinearity is the norm, where changing one component may have ripple effects on the entire system, and where multiple changes that individually are detrimental may lead to much greater improvements in fitness when combined. Nonlinearity results in a combinatorial explosion: the space of 1,000-digit binary strings can be exhaustively searched by evaluating only 2,000 possibilities if the problem is linear, whereas if it is nonlinear, an exhaustive search requires evaluating 21000 possibilities – a number that would take over 300 digits to write out in full.Fortunately, the implicit parallelism of a GA allows it to surmount even this enormous number of possibilities, successfully finding optimal or very good results in a short period of time after directly sampling only small regions of the vast fitness landscape (Forrest 1993, p. 877). For example, a genetic algorithm developed jointly by engineers from General Electric and Rensselaer Polytechnic Institute produced a high-performance jet engine turbine design that was three times better than a human-designed configuration and 50% better than a configuration designed by an expert system by successfully navigating a solution space containing more than 10387 possibilities. Conventional methods for designing such turbines are a central part of engineering projects that can take up to five years and cost over $2 billion; the genetic algorithm discovered this solution after two days on a typical engineering desktop workstation (Holland 1992, p.72).
  • Another notable strength of genetic algorithms is that they perform well in problems for which the fitness landscape is complex – ones where the fitness function is discontinuous, noisy, changes over time, or has many local optima. Most practical problems have a vast solution space, impossible to search exhaustively; the challenge then becomes how to avoid the local optima – solutions that are better than all the others that are similar to them, but that are not as good as different ones elsewhere in the solution space. Many search algorithms can become trapped by local optima: if they reach the top of a hill on the fitness landscape, they will discover that no better solutions exist nearby and conclude that they have reached the best one, even though higher peaks exist elsewhere on the map.Evolutionary algorithms, on the other hand, have proven to be effective at escaping local optima and discovering the global optimum in even a very rugged and complex fitness landscape. (It should be noted that, in reality, there is usually no way to tell whether a given solution to a problem is the one global optimum or just a very high local optimum. However, even if a GA does not always deliver a provably perfect solution to a problem, it can almost always deliver at least a very good solution.) All four of a GA’s major components – parallelism, selection, mutation, and crossover – work together to accomplish this. In the beginning, the GA generates a diverse initial population, casting a “net” over the fitness landscape. (Koza (2003, p. 506) compares this to an army of parachutists dropping onto the landscape of a problem’s search space, with each one being given orders to find the highest peak.) Small mutations enable each individual to explore its immediate neighborhood, while selection focuses progress, guiding the algorithm’s offspring uphill to more promising parts of the solution space (Holland 1992, p. 68).However, crossover is the key element that distinguishes genetic algorithms from other methods such as hill-climbers and simulated annealing. Without crossover, each individual solution is on its own, exploring the search space in its immediate vicinity without reference to what other individuals may have discovered. However, with crossover in place, there is a transfer of information between successful candidates – individuals can benefit from what others have learned, and schemata can be mixed and combined, with the potential to produce an offspring that has the strengths of both its parents and the weaknesses of neither. This point is illustrated in Koza et al. 1999, p.486, where the authors discuss a problem of synthesizing a lowpass filter using genetic programming. In one generation, two parent circuits were selected to undergo crossover; one parent had good topology (components such as inductors and capacitors in the right places) but bad sizing (values of inductance and capacitance for its components that were far too low). The other parent had bad topology, but good sizing. The result of mating the two through crossover was an offspring with the good topology of one parent and the good sizing of the other, resulting in a substantial improvement in fitness over both its parents.The problem of finding the global optimum in a space with many local optima is also known as the dilemma of exploration vs. exploitation, “a classic problem for all systems that can adapt and learn” (Holland 1992, p. 69). Once an algorithm (or a human designer) has found a problem-solving strategy that seems to work satisfactorily, should it concentrate on making the best use of that strategy, or should it search for others? Abandoning a proven strategy to look for new ones is almost guaranteed to involve losses and degradation of performance, at least in the short term. But if one sticks with a particular strategy to the exclusion of all others, one runs the risk of not discovering better strategies that exist but have not yet been found. Again, genetic algorithms have shown themselves to be very good at striking this balance and discovering good solutions with a reasonable amount of time and computational effort.
  • Another area in which genetic algorithms excel is their ability to manipulate many parameters simultaneously (Forrest 1993, p. 874). Many real-world problems cannot be stated in terms of a single value to be minimized or maximized, but must be expressed in terms of multiple objectives, usually with tradeoffs involved: one can only be improved at the expense of another. GAs are very good at solving such problems: in particular, their use of parallelism enables them to produce multiple equally good solutions to the same problem, possibly with one candidate solution optimizing one parameter and another candidate optimizing a different one (Haupt and Haupt 1998, p.17), and a human overseer can then select one of these candidates to use. If a particular solution to a multiobjective problem optimizes one parameter to a degree such that that parameter cannot be further improved without causing a corresponding decrease in the quality of some other parameter, that solution is called Pareto optimal or non-dominated (Coello 2000, p. 112).
  • Finally, one of the qualities of genetic algorithms which might at first appear to be a liability turns out to be one of their strengths: namely, GAs know nothing about the problems they are deployed to solve. Instead of using previously known domain-specific information to guide each step and making changes with a specific eye towards improvement, as human designers do, they are “blind watchmakers” (Dawkins 1996); they make random changes to their candidate solutions and then use the fitness function to determine whether those changes produce an improvement.The virtue of this technique is that it allows genetic algorithms to start out with an open mind, so to speak. Since its decisions are based on randomness, all possible search pathways are theoretically open to a GA; by contrast, any problem-solving strategy that relies on prior knowledge must inevitably begin by ruling out many pathways a priori, therefore missing any novel solutions that may exist there (Koza et al. 1999, p. 547). Lacking preconceptions based on established beliefs of “how things should be done” or what “couldn’t possibly work”, GAs do not have this problem. Similarly, any technique that relies on prior knowledge will break down when such knowledge is not available, but again, GAs are not adversely affected by ignorance (Goldberg 1989, p. 23). Through their components of parallelism, crossover and mutation, they can range widely over the fitness landscape, exploring regions which intelligently produced algorithms might have overlooked, and potentially uncovering solutions of startling and unexpected creativity that might never have occurred to human designers. One vivid illustration of this is the rediscovery, by genetic programming, of the concept of negative feedback – a principle crucial to many important electronic components today, but one that, when it was first discovered, was denied a patent for nine years because the concept was so contrary to established beliefs (Koza et al. 2003, p. 413). Evolutionary algorithms, of course, are neither aware nor concerned whether a solution runs counter to established beliefs – only whether it works.

http://www.talkorigins.org/faqs/genalg/genalg.html

Limitations of GAs

  • “The first, and most important, consideration in creating a genetic algorithm is defining a representation for the problem. The language used to specify candidate solutions must be robust; i.e., it must be able to tolerate random changes such that fatal errors or nonsense do not consistently result.There are two main ways of achieving this. The first, which is used by most genetic algorithms, is to define individuals as lists of numbers – binary-valued, integer-valued, or real-valued – where each number represents some aspect of a candidate solution. If the individuals are binary strings, 0 or 1 could stand for the absence or presence of a given feature. If they are lists of numbers, these numbers could represent many different things: the weights of the links in a neural network, the order of the cities visited in a given tour, the spatial placement of electronic components, the values fed into a controller, the torsion angles of peptide bonds in a protein, and so on. Mutation then entails changing these numbers, flipping bits or adding or subtracting random values. In this case, the actual program code does not change; the code is what manages the simulation and keeps track of the individuals, evaluating their fitness and perhaps ensuring that only values realistic and possible for the given problem result.In another method, genetic programming, the actual program code does change. As discussed in the section Methods of representation, GP represents individuals as executable trees of code that can be mutated by changing or swapping subtrees. Both of these methods produce representations that are robust against mutation and can represent many different kinds of problems, and as discussed in the section Some specific examples, both have had considerable success.This issue of representing candidate solutions in a robust way does not arise in nature, because the method of representation used by evolution, namely the genetic code, is inherently robust: with only a very few exceptions, such as a string of stop codons, there is no such thing as a sequence of DNA bases that cannot be translated into a protein. Therefore, virtually any change to an individual’s genes will still produce an intelligible result, and so mutations in evolution have a higher chance of producing an improvement. This is in contrast to human-created languages such as English, where the number of meaningful words is small compared to the total number of ways one can combine letters of the alphabet, and therefore random changes to an English sentence are likely to produce nonsense.
  • The problem of how to write the fitness function must be carefully considered so that higher fitness is attainable and actually does equate to a better solution for the given problem. If the fitness function is chosen poorly or defined imprecisely, the genetic algorithm may be unable to find a solution to the problem, or may end up solving the wrong problem. (This latter situation is sometimes described as the tendency of a GA to “cheat”, although in reality all that is happening is that the GA is doing what it was told to do, not what its creators intended it to do.) An example of this can be found in Graham-Rowe 2002, in which researchers used an evolutionary algorithm in conjunction with a reprogrammable hardware array, setting up the fitness function to reward the evolving circuit for outputting an oscillating signal. At the end of the experiment, an oscillating signal was indeed being produced – but instead of the circuit itself acting as an oscillator, as the researchers had intended, they discovered that it had become a radio receiver that was picking up and relaying an oscillating signal from a nearby piece of electronic equipment!This is not a problem in nature, however. In the laboratory of biological evolution there is only one fitness function, which is the same for all living things – the drive to survive and reproduce, no matter what adaptations make this possible. Those organisms which reproduce more abundantly compared to their competitors are more fit; those which fail to reproduce are unfit.
  • In addition to making a good choice of fitness function, the other parameters of a GA – the size of the population, the rate of mutation and crossover, the type and strength of selection – must be also chosen with care. If the population size is too small, the genetic algorithm may not explore enough of the solution space to consistently find good solutions. If the rate of genetic change is too high or the selection scheme is chosen poorly, beneficial schema may be disrupted and the population may enter error catastrophe, changing too fast for selection to ever bring about convergence.Living things do face similar difficulties, and evolution has dealt with them. It is true that if a population size falls too low, mutation rates are too high, or the selection pressure is too strong (such a situation might be caused by drastic environmental change), then the species may go extinct. The solution has been “the evolution of evolvability” – adaptations that alter a species’ ability to adapt. For example, most living things have evolved elaborate molecular machinery that checks for and corrects errors during the process of DNA replication, keeping their mutation rate down to acceptably low levels; conversely, in times of severe environmental stress, some bacterial species enter a state of hypermutation where the rate of DNA replication errors rises sharply, increasing the chance that a compensating mutation will be discovered. Of course, not all catastrophes can be evaded, but the enormous diversity and highly complex adaptations of living things today show that, in general, evolution is a successful strategy. Likewise, the diverse applications of and impressive results produced by genetic algorithms show them to be a powerful and worthwhile field of study.
  • One type of problem that genetic algorithms have difficulty dealing with are problems with “deceptive” fitness functions (Mitchell 1996, p.125), those where the locations of improved points give misleading information about where the global optimum is likely to be found. For example, imagine a problem where the search space consisted of all eight-character binary strings, and the fitness of an individual was directly proportional to the number of 1s in it – i.e., 00000001 would be less fit than 00000011, which would be less fit than 00000111, and so on – with two exceptions: the string 11111111 turned out to have very low fitness, and the string 00000000 turned out to have very high fitness. In such a problem, a GA (as well as most other algorithms) would be no more likely to find the global optimum than random search.The resolution to this problem is the same for both genetic algorithms and biological evolution: evolution is not a process that has to find the single global optimum every time. It can do almost as well by reaching the top of a high local optimum, and for most situations, this will suffice, even if the global optimum cannot easily be reached from that point. Evolution is very much a “satisficer” – an algorithm that delivers a “good enough” solution, though not necessarily the best possible solution, given a reasonable amount of time and effort invested in the search. The Evidence for Jury-Rigged Design in Nature FAQ gives examples of this very outcome appearing in nature. (It is also worth noting that few, if any, real-world problems are as fully deceptive as the somewhat contrived example given above. Usually, the location of local improvements gives at least some information about the location of the global optimum.)
  • One well-known problem that can occur with a GA is known as premature convergence. If an individual that is more fit than most of its competitors emerges early on in the course of the run, it may reproduce so abundantly that it drives down the population’s diversity too soon, leading the algorithm to converge on the local optimum that that individual represents rather than searching the fitness landscape thoroughly enough to find the global optimum (Forrest 1993, p. 876; Mitchell 1996, p. 167). This is an especially common problem in small populations, where even chance variations in reproduction rate may cause one genotype to become dominant over others.The most common methods implemented by GA researchers to deal with this problem all involve controlling the strength of selection, so as not to give excessively fit individuals too great of an advantage. Rank, scaling and tournament selection, discussed earlier, are three major means for accomplishing this; some methods of scaling selection include sigma scaling, in which reproduction is based on a statistical comparison to the population’s average fitness, and Boltzmann selection, in which the strength of selection increases over the course of a run in a manner similar to the “temperature” variable in simulated annealing (Mitchell 1996, p. 168).Premature convergence does occur in nature (where it is called genetic drift by biologists). This should not be surprising; as discussed above, evolution as a problem-solving strategy is under no obligation to find the single best solution, merely one that is good enough. However, premature convergence in nature is less common since most beneficial mutations in living things produce only small, incremental fitness improvements; mutations that produce such a large fitness gain as to give their possessors dramatic reproductive advantage are rare.
  • Finally, several researchers (Holland 1992, p.72; Forrest 1993, p.875; Haupt and Haupt 1998, p.18) advise against using genetic algorithms on analytically solvable problems. It is not that genetic algorithms cannot find good solutions to such problems; it is merely that traditional analytic methods take much less time and computational effort than GAs and, unlike GAs, are usually mathematically guaranteed to deliver the one exact solution. Of course, since there is no such thing as a mathematically perfect solution to any problem of biological adaptation, this issue does not arise in nature.

http://www.talkorigins.org/faqs/genalg/genalg.html

Genetic algorithm operators, selectors, ranking and encoding

Here you will find a brief explanation of some of the main operators, selectors, ranking and encoding in Genetic Algorithms. You will also find some code samples where I have some to provide. These code samples are in C#.

Selection

Here is a good quote from the book (Buckland, 2002):

“Selection is how you choose individuals from the population to provide a gene base from which the next generation of individuals is created. This might mean individuals are selected and placed into the new generation without modification ala elitism, as we discussed in the last chapter, but usually it means the chosen genomes are selected to be parents of offspring which are created through the processes of mutation and recombination. How you go about choosing the parents can play a very important role in how efficient your genetic algorithm is. Unlike choosing a soccer team, if you choose the fittest individuals all the time, the population may converge too rapidly at a local minima and get stuck there. But, if you select individuals at random, then your genetic algorithm will probably take a while to converge (if it ever does at all). So, the art of selection is choosing a strategy which gives you the best of both worlds—something that converges fairly quickly yet enables the population to retain its diversity.”

Steady State Selection

“Steady state selection works a little like elitism, except that instead of choosing a

small amount of the best individuals to go through to the new generation, steady

state selection retains all but a few of the worst performers from the current population.

The remainder are then selected using mutation and crossover in the usual

way. Steady state selection can prove useful when tackling some problems, but most

of the time it’s inadvisable to use it.

” (Buckland, 2002)

Sample code



Fitness Proportionate Selection

“Selection techniques of this type choose offspring using methods which give individuals

a better chance of being selected the better their fitness score. Another way

of describing it is that each individual has an expected number of times it will be

chosen to reproduce. This expected value equates to the individual’s fitness divided

by the average fitness of the entire population. So, if you have an individual with a

fitness of 6 and the average fitness of the overall population is 4, then the expected

number of times the individual should be chosen is 1.5.” (Buckland, 2002)

Sample code



 

Elitism

” elitism is a way of guaranteeing that the fittest members of a population are retained for the next generation.  … select n copies of the top m individuals of the population to be retained. I often find that retaining about 2-5% of the population size gives me good results. … you will discover that using elitism works well with just about every other technique described in this chapter (except stochastic universal sampling) ” (Buckland, 2002)

” Elitism helps the population to converge on a solution faster than if it is not present. It is easy to code.A typical figure for N best to be added to the population is around 1 – 10 % of the population size. Can be as high as 20 %. Too much elitism can cause the population to converge too quickly.” AI Game Programming Wisdom 2

Sample code

 

public void GrabNBest(int NBest, int numCopies, ref List&amp;amp;lt;Host&amp;amp;gt; source, ref List&amp;amp;lt;Host&amp;amp;gt; target)
 {
 var hostToGrab = source.OrderByDescending(o =&amp;amp;gt; o.DNA.Fitness).Take(NBest);

 foreach (Host host in hostToGrab)
 for (int x = 0; x &amp;amp;lt; numCopies; ++x)
 target.Add(host);
 }

 

 

Roulette Wheel Selection

“A common way of implementing fitness proportionate selection is roulette wheel selection, as I have already discussed. This technique does have its drawbacks, however. Because roulette wheel selection is based on using random numbers and because the population sizes of genetic algorithms are typically small (sizes between 50 and 200 are common), the number of children allocated to each individual can be far from its expected value. Even worse, it’s probable that roulette wheel selection could miss the best individuals altogether! This is one of the reasons elitism is a good idea when utilizing roulette wheel selection—it ensures you never lose the best individuals to chance.” (Buckland, 2002)

Sample code

 

public Host RouletteWheelSelection()
 {
 double fSlice = (float)RandomProvider.GetRandomNumber(RandomProvider.RND,0 ,1) * TotalFitnessScore;

 double cfTotal = 0;
 int SelectedGenome = 0;
 for (int i = 0; i &amp;amp;lt; PopSize; ++i) { cfTotal += this.Hosts[i].DNA.Fitness; if (cfTotal &amp;amp;gt; fSlice)
 {
 SelectedGenome = i;
 break;
 }
 }
 return this.Hosts[SelectedGenome];
 }

 

 

Stochastic Universal Sampling

“Stochastic Universal Sampling (SUS for short) is an attempt to minimize the problems of using fitness proportionate selection on small populations. Basically, instead of having one wheel which is spun several times to obtain the new population, SUS uses n evenly spaced hands, which are only spun once.

 

If you use SUS in your own genetic algorithms, it is inadvisable to use elitism with it because this tends to mess up the algorithm.” (Buckland, 2002)

 

Stochastic universal sampling (SUS) is a technique used in genetic algorithms for selecting potentially useful solutions for recombination. It was introduced by James Baker.[1]

SUS is a development of fitness proportionate selection (FPS) which exhibits no bias and minimal spread. Where FPS chooses several solutions from the population by repeated random sampling, SUS uses a single random value to sample all of the solutions by choosing them at evenly spaced intervals. This gives weaker members of the population (according to their fitness) a chance to be chosen and thus reduces the unfair nature of fitness-proportional selection methods.

Other methods like roulette wheel can have bad performance when a member of the population has a really large fitness in comparison with other members. Using a comb-like ruler, SUS starts from a small random number, and chooses the next candidates from the rest of population remaining, not allowing the fittest members to saturate the candidate space.

Described as an algorithm, pseudocode for SUS looks like:

SUS(Population, N)
F := total fitness of Population
N := number of offspring to keep
P := distance between the pointers (F/N)
Start := random number between 0 and P
Pointers := [Start + i*P | i in [0..(N-1)]]
return RWS(Population,Pointers)

 

RWS(Population, Points)
Keep = []
i := 0
for P in Points
while fitness sum of Population[0..i] < P
i++
add Population[i] to Keep
return Keep

 

Where Population[0..i] is the set of individuals with array-index 0 to (and including) i.

Here RWS() describes the bulk of fitness proportionate selection (also known as “roulette wheel selection”) – in true fitness proportional selection the parameter Points is always a (sorted) list of random numbers from 0 to F. The algorithm above is intended to be illustrative rather than canonical.

” (Wikipedia, 2015)

 

Sample code

public void SUSSelection(ref List&amp;amp;lt;Host&amp;amp;gt; source, ref List&amp;amp;lt;Host&amp;amp;gt; target)
 {
 //this algorithm relies on all the fitness scores to be positive so
 //these few lines check and adjust accordingly (in this example

 //Sigma scaling can give negative fitness scores
 if (WorstFitnessScore &amp;amp;lt; 0)
 {
 //recalculate
 for (int gen = 0; gen &amp;amp;lt; source.Count; ++gen)
 {
 source[gen].DNA.Fitness += Mathf.Abs(WorstFitnessScore);
 }
 CalculateBestWorstAverageTotalFitnessScore(ref source);
 }

 int curGen = 0;
 double sum = 0;

 //NumToAdd is the amount of individuals we need to select using SUS.
 //Remember, some may have already been selected through elitism
 int NumToAdd = this.PopSize - target.Count;

 //calculate the hand spacing
 float PointerGap = this.TotalFitnessScore / (float)NumToAdd;

 float ptr = UnityEngine.Random.Range(0, 1) * PointerGap;

 while (target.Count &amp;amp;lt; NumToAdd) { for (sum += source[curGen].DNA.Fitness; sum &amp;amp;gt; ptr; ptr += PointerGap)
 {
 target.Add(source[curGen]);
 if (target.Count == NumToAdd)
 {
 return;
 }
 }
 ++curGen;
 }
 }

 

 

Tournament Selection

“This technique is very efficient to implement because it doesn’t require any of the preprocessing or fitness scaling sometimes required for roulette wheel selection and other fitness proportionate techniques (discussed later in the chapter). Because of this, and because it’s a darn good technique anyway, you should always try this method of selection with your own genetic algorithms. The only drawback I’ve found is that tournament selection can lead to too quick convergence with some types of problems.” (Buckland, 2002)

Tournament selection is a good alternative to fitness proportionate selection with or without scaling. This technique is very fast due to lack of complex calculations.

Chose a random number of individuals at random and them choosing the fittest among them. This is repeated until the next generation of individuals are generated. The higher the number of selected individuals the higher pressure. The lower the more diverse the population will be. Typical selection number is between 2-10%.” AI Game Programming Wisdom 2

Sample code

public Host TournamentSelection(int N)
 {
 double BestFitnessSoFar = 0;

 int ChosenOne = 0;

 //Select N members from the population at random testing against
 //the best found so far
 for (int i = 0; i &amp;amp;lt; N; ++i) { int ThisTry = RandomProvider.RND.Next(0, this.PopSize - 2); if (this.Hosts[ThisTry].DNA.Fitness &amp;amp;gt; BestFitnessSoFar)
 {
 ChosenOne = ThisTry;
 BestFitnessSoFar = this.Hosts[ThisTry].DNA.Fitness;
 }
 }

 //return the champion
 return this.Hosts[ChosenOne];
 }

 

Crossover

Crossover involves creating a child out of the genetic code of two parents.

Partially-Mapped Crossover

”PMX Crossover is a genetic algorithm operator. For some problems it offers better performance than most other crossover techniques. Basically, parent 1 donates a swath of genetic material and the corresponding swath from the other parent is sprinkled about in the child. Once that is done, the remaining alleles are copied direct from parent 2.

  1. Randomly select a swath of alleles from parent 1 and copy them directly to the child. Note the indexes of the segment.
  2. Looking in the same segment positions in parent 2, select each value that hasn’t already been copiedto the child.
    • For each of these values:
      1. Note the index of this value in Parent 2. Locate the value, V, from parent 1 in this same position.
      2. Locate this same value in parent 2.
      3. If the index of this value in Parent 2 is part of the original swath, go to step i. using this value.
      4. If the position isn’t part of the original swath, insert Step A’s value into the child in this position.
  1. Copy any remaining positions from parent 2 to the child.” (http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/PMXCrossoverOperator.aspx, 2015)

 

Sample code


public void CrossoverPMX(ref List&amp;amp;lt;Vector2&amp;amp;gt; mum, ref List&amp;amp;lt;Vector2&amp;amp;gt; dad, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby1, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby2)
 {
 //just return dependent on the crossover rate or if the
 //chromosomes are the same.
 if (((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; CrossoverRate) || (mum == dad) || mum.Count &amp;amp;lt;= 0 || dad.Count &amp;amp;lt;= 0) { baby1 = mum; baby2 = dad; return; } baby1 = mum; baby2 = dad; int maxItemsCount = mum.Count; if (mum.Count &amp;amp;gt; dad.Count)
 maxItemsCount = dad.Count;

 //first we choose a section of the chromosome
 int begin = RandomProvider.RND.Next(0, maxItemsCount - 2);
 int end = begin;

 //find an end
 while (end &amp;amp;lt;= begin)
 {
 end = RandomProvider.RND.Next(0, maxItemsCount - 1);
 }

 //now we iterate through the matched pairs of genes from beg
 //to end swapping the places in each child
 for (int pos = begin; pos &amp;amp;lt; end + 1; ++pos) { //these are the genes we want to swap Vector2 gene1 = mum[pos]; Vector2 gene2 = dad[pos]; if (gene1 != gene2) { //find and swap them in baby1 int posGene1 = baby1.IndexOf(gene1); int posGene2 = baby1.IndexOf(gene2); if (posGene1 &amp;amp;gt;= 0)
 baby1[posGene1] = gene2;

 if (posGene2 &amp;amp;gt;= 0)
 baby2[posGene2] = gene1;

 //and in baby2
 posGene1 = baby2.IndexOf(gene1);
 posGene2 = baby2.IndexOf(gene2);

 if (posGene1 &amp;amp;gt;= 0)
 baby2[posGene1] = gene2;

 if (posGene2 &amp;amp;gt;= 0)
 baby2[posGene2] = gene1;
 }
 }//next pair
 }

 

 

Order-Based Crossover

“To perform order-based crossover, several elements are chosen at random from one parent and then the order of those elements is imposed on the respective elements in the other parent.” (Buckland, 2002)(With slight text alternation from book example to a more general description).

 

Order 1 Crossover 
Order 1 Crossover is a fairly simple permutation crossover. Basically, a swath of consecutive alleles from parent 1 drops down, and remaining values are placed in the child in the order which they appear in parent 2.

Parent 1: 8 4 7 3 6 2 5 1 9 0
Parent 2: 0 1 2 3 4 5 6 7 8 9

Child 1:  0 4 7 3 6 2 5 1 8 9

Step 1: Select a random swath of consecutive alleles from parent 1. (underlined)

Step 2: Drop the swath down to Child 1 and mark out these alleles in Parent 2.

Step 3: Starting on the right side of the swath, grab alleles from parent 2 and insert them in Child 1 at the right edge of the swath. Since 8 is in that position in Parent 2, it is inserted into Child 1 first at the right edge of the swath. Notice that alleles 1, 2 and 3 are skipped because they are marked out and 4 is inserted into the 2nd spot in Child 1.

Step 4: If you desire a second child from the two parents, flip Parent 1 and Parent 2 and go back to Step 1.

Order 1 Performance
Order 1 crossover is perhaps the fastest of all crossover operators because it requires virtually no overhead operations. On a generation by generation basis, edge recombination typically outperforms Order 1, but the fact that Order 1 runs between 100 and 1000 times faster usually allows the processing of more generations in a given time period.

http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperator.aspx

 

Sample code

public void CrossoverOBX(ref List&amp;amp;lt;Vector2&amp;amp;gt; mum, ref List&amp;amp;lt;Vector2&amp;amp;gt; dad, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby1, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby2)
 {
 //just return dependent on the crossover rate or if the
 //chromosomes are the same.
 if (((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; CrossoverRate) || (mum == dad) || mum.Count &amp;amp;lt;= 0 || dad.Count &amp;amp;lt;= 0)
 {
 baby1 = mum;
 baby2 = dad;
 return;
 }

 baby1 = mum;
 baby2 = dad;

 List&amp;amp;lt;Vector2&amp;amp;gt; tempGenes = new List&amp;amp;lt;Vector2&amp;amp;gt;();
 List&amp;amp;lt;int&amp;amp;gt; positions = new List&amp;amp;lt;int&amp;amp;gt;();

 //first chosen city position
 int Pos = RandomProvider.RND.Next(0, mum.Count - 2);

 //keep adding random cities until we can add no more
 //record the positions as we go
 while (Pos &amp;amp;lt; mum.Count)
 {
 positions.Add(Pos);

 tempGenes.Add(mum[Pos]);

 // next gene
 Pos += RandomProvider.RND.Next(1, mum.Count - Pos);
 }

 //so now we have n amount of cities from mum in the tempCities
 //vector we can impose their order in dad.
 int cPos = 0;

 for (int cit = 0; cit &amp;amp;lt; baby2.Count; ++cit)
 {
 for (int i = 0; i &amp;amp;lt; tempGenes.Count; ++i)
 {
 if (baby2[cit] == tempGenes[i])
 {
 baby2[cit] = tempGenes[cPos];
 ++cPos;
 break;
 }
 }
 }

 //now vice versa. Choose the same positioned cities from dad and impose
 //their order in mum
 tempGenes.Clear();
 cPos = 0;

 //first grab the cities from the same positions in dad
 for (int i = 0; i &amp;amp;lt; positions.Count; ++i)
 {
 tempGenes.Add(dad[positions[i]]);
 }

 //and impose their order in mum
 for (int cit = 0; cit &amp;amp;lt; baby1.Count; ++cit)
 {
 for (int i = 0; i &amp;amp;lt; tempGenes.Count; ++i)
 {
 if (baby1[cit] == tempGenes[i])
 {
 baby1[cit] = tempGenes[cPos];
 ++cPos;
 break;
 }
 }
 }
 }

 

 

Position-Based Crossover

” This is similar to Order-Based Crossover, but instead of imposing the order of the elements, this operator imposes the position. ” (Buckland, 2002)

 

Basically this mean that we swap positions between the parents when passing the elements down to the offspring’s.

Sample code

public void CrossoverPBX(ref List&amp;amp;lt;Vector2&amp;amp;gt; mum, ref List&amp;amp;lt;Vector2&amp;amp;gt; dad, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby1, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby2)
 {
 //just return dependent on the crossover rate or if the
 //chromosomes are the same.
 if (((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; CrossoverRate) || (mum == dad) || mum.Count &amp;amp;lt;= 0 || dad.Count &amp;amp;lt;= 0)
 {
 baby1 = mum;
 baby2 = dad;
 return;
 }

 //initialize the babies with minus values so we can tell which positions
 //have been filled later in the algorith
 for (int x = 0; x &amp;amp;lt; mum.Count; ++x)
 {
 baby1.Add(Vector2.zero);
 baby2.Add(Vector2.zero);
 }

 int l = baby2.Count;

 //holds the positions of the chosen elements
 List&amp;amp;lt;int&amp;amp;gt; positions = new List&amp;amp;lt;int&amp;amp;gt;();

 //first chosen city position
 int Pos = RandomProvider.RND.Next(0, mum.Count - 2);

 //keep adding random cities until we can add no more
 //record the positions as we go
 while (Pos &amp;amp;lt; mum.Count)
 {
 positions.Add(Pos);

 // next gene
 Pos += RandomProvider.RND.Next(1, mum.Count - Pos);
 }

 //now we have chosen some cities it's time to copy the selected cities
 //over into the offspring in the same position.
 for (int pos = 0; pos &amp;amp;lt; positions.Count; ++pos)
 {
 //baby1 receives from mum
 baby1[positions[pos]] = mum[positions[pos]];
 //baby2 receives from dad
 baby2[positions[pos]] = dad[positions[pos]];
 }

 //fill in the blanks. First create two position markers so we know
 //whereabouts we are in baby1 and baby2
 int c1 = 0, c2 = 0;
 for (int pos = 0; pos &amp;amp;lt; mum.Count; ++pos)
 {
 //advance position marker until we reach a free position
 //in baby2
 while ((baby2[c2] != Vector2.zero) &amp;amp;amp;&amp;amp;amp; (c2 &amp;amp;lt; mum.Count -1)) { ++c2; } Vector2 tempElement = mum[pos]; //baby2 gets the next city from mum which is not already //present if (!baby2.Exists(o =&amp;amp;gt; o == tempElement))
 {
 baby2[c2] = mum[pos];
 }
 //now do the same for baby1
 while ((baby1[c1] != Vector2.zero) &amp;amp;amp;&amp;amp;amp; (c1 &amp;amp;lt; mum.Count -1)) { ++c1; } tempElement = dad[pos]; //baby1 gets the next city from dad which is not already //present if (!baby1.Exists( o =&amp;amp;gt; o == tempElement))
 {
 baby1[c1] = dad[pos];
 }
 }
 }

 

 

Single-Point Crossover

 

“It simply cuts the genome at some random point and then switches the ends between parents. It is very easy and quick to implement and is generally effective to some degree with most types of problems.” (Buckland, 2002)

 

Sample code

public void Crossover(ref List&amp;amp;lt;Vector2&amp;amp;gt; mum, ref List&amp;amp;lt;Vector2&amp;amp;gt; dad, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby1, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby2)
 {
 if (((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; CrossoverRate) || (mum == dad) || mum.Count &amp;amp;lt;= 0 || dad.Count &amp;amp;lt;= 0)
 {
 baby1 = mum;
 baby2 = dad;
 return;
 }

 int cp = RandomProvider.RND.Next(0, this.GeneLength - 1);

 for (int i = 0; i &amp;amp;lt; cp; i++)
 {
 baby1.Add(mum[i]);
 baby2.Add(dad[i]);
 }
 for (int i = cp; i &amp;amp;lt; mum.Count; i++)
 {
 baby1.Add(dad[i]);
 baby2.Add(mum[i]);
 }
 }

 

 

Two-Point Crossover

“Instead of cutting the genome at just one point, two-point crossover (you guessed it) cuts the genome at two random points and then swaps the block of genes between those two points. … Two-point crossover is sometimes beneficial because it can create combinations of genes that single-point crossover simply cannot provide. With single point, the end genes are always swapped over and this may not be favorable for the problem at hand. Two-point crossover eliminates this problem. ” (Buckland, 2002)

 

Sample code

public void CrossoverTwoPoint(ref List&amp;amp;lt;Vector2&amp;amp;gt; mum, ref List&amp;amp;lt;Vector2&amp;amp;gt; dad, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby1, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby2)
 {
 if (((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; CrossoverRate) || (mum == dad) || mum.Count &amp;amp;lt;= 0 || dad.Count &amp;amp;lt;= 0 || mum.Count != dad.Count)
 {
 baby1 = mum;
 baby2 = dad;
 return;
 }

 int cp = RandomProvider.RND.Next(0, this.GeneLength - 1);
 int cp2 = RandomProvider.RND.Next(0, this.GeneLength - 1);

 while(cp2 == cp)
 cp2 = RandomProvider.RND.Next(0, this.GeneLength - 1);

 baby1.AddRange(mum);
 baby2.AddRange(dad);

 for (int i = cp; i &amp;amp;lt; cp2; i++)
 {
 baby1[i] = dad[i];
 baby2[i] = mum[i];
 }
 }

 

 

Multi-Point Crossover (parameterized uniform crossover)

“There’s no need to limit the amount of crossover points you can have. Indeed, for some types of encoding, your genetic algorithm may perform better if you use multiple crossover points. The easiest way of achieving this is to move down the length of the parents, and for each position in the chromosome, randomly swap the genes based on your crossover rate. For some types of problems, multi-point crossover works very well, but on others it can jumble up the genes too much and act more like an over enthusiastic mutation operator. Common values for the crossover rate using this type of crossover operator are between 0.5 and 0.8.” (Buckland, 2002)

 

Sample code

public void CrossoverMultiPoint(ref List&amp;amp;lt;Vector2&amp;amp;gt; mum, ref List&amp;amp;lt;Vector2&amp;amp;gt; dad, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby1, ref List&amp;amp;lt;Vector2&amp;amp;gt; baby2)
 {
 if ((mum == dad) || mum.Count &amp;amp;lt;= 0 || dad.Count &amp;amp;lt;= 0)
 {
 baby1 = mum;
 baby2 = dad;
 return;
 }

 //iterate down the length of the genomes swapping genes
 //depending on the crossover rate
 for (int gen = 0; gen &amp;amp;lt; mum.Count; ++gen)
 {
 if (((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;lt; CrossoverRate))
 {
 //swap the genes
 baby2.Add(mum[gen]);
 baby1.Add(dad[gen]);
 }
 else
 {
 //don't swap the genes
 baby1.Add(mum[gen]);
 baby2.Add(dad[gen]);
 }
 }
 }

 

 

 

Alternative crossover methods

  • Alternating-Position Crossover
  • Maximal-Preservation Crossover
  • Edge-Recombination Crossover
  • Subtour-Chunks Crossover
  • Intersection Crossover

 

Mutation

Scramble Mutation (SM)

Choose two random points and “scramble” the elements located between them.

Sample code

public void MutateSM(ref List&amp;amp;lt;Vector2&amp;amp;gt; genes)
 {
 //return dependent upon mutation rate
 if ((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; MutationRate) return;

 //first we choose a section of the chromosome
 const int MinSpanSize = 3;

 //these will hold the beginning and end points of the span
 int beg = 0, end = 0;
 ChooseSection(ref beg, ref end, genes.Count - 1, MinSpanSize);

 int span = end - beg;

 //now we just swap randomly chosen genes with the beg/end
 //range a few times to scramble them
 int NumberOfSwapsRqd = span;

 while (--NumberOfSwapsRqd &amp;amp;gt;= 0)
 {
 //choose two loci within the range
 int pos1 = beg + RandomProvider.RND.Next(0, span);
 int pos2 = beg + RandomProvider.RND.Next(0, span);


 //exchange them
 if (pos1 != pos2)
 {
 Vector2 temp = genes[pos1];
 genes[pos1] = genes[pos2];
 genes[pos2] = temp;
 }
 }//repeat
 }

 

 

Exchange Mutation Operator

The Exchange Mutation operator does this by choosing two genes in a chromosome and swapping them.

Sample code

public void MutateEM(ref List&amp;amp;lt;Vector2&amp;amp;gt; genes)
 {
 //return dependent upon mutation rate
 if ((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; MutationRate) return;

 //choose first gene
 int pos1 = RandomProvider.RND.Next(0, genes.Count - 1);

 //choose second
 int pos2 = pos1;
 while (pos1 == pos2)
 {
 pos2 = RandomProvider.RND.Next(0, genes.Count - 1);
 }

 Vector2 temp = genes[pos1];
 genes[pos1] = genes[pos2];
 genes[pos2] = temp;
 }

 

 

Displacement Mutation

Select two random points, grab the chunk of chromosome between them, and then reinsert at a random position displaced from the original.

Sample code

public void MutateDM(ref List&amp;amp;lt;Vector2&amp;amp;gt; genes)
 {
 //return dependent upon mutation rate
 if ((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; MutationRate) return;

 //first we choose a section of the chromosome
 const int MinSpanSize = 3;

 //these will hold the beginning and end points of the span
 int beg = 0, end = 0;
 ChooseSection(ref beg, ref end, genes.Count - 1, MinSpanSize);

 // Calculate how many items to get and later remove
 int span = end - beg;

 //hold on to the section we are moving
 List&amp;amp;lt;Vector2&amp;amp;gt; aSectionOfGenes = genes.GetRange(beg, span);

 //erase from current position
 genes.RemoveRange(beg, span);

 int newInsertPosition = RandomProvider.RND.Next(0, genes.Count - 1);

 genes.InsertRange(newInsertPosition, aSectionOfGenes);

 }

“Normal mutation”(Don’t know the proper name for this one 🙂 )

Goes through every genes in a chromosome and based on the mutation rate a new gene data is generated at that position.

Sample code

public void Mutate(ref List&amp;amp;lt;Vector2&amp;amp;gt; genes)
 {
 for (int i = 0; i &amp;amp;lt; genes.Count; i++)
 {
 //flip this bit?
 if ((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;lt; MutationRate)
 {
 float angle = UnityEngine.Random.Range(0, AIConstants.TWO_PI);
 genes[i] = ((new Vector2(UnityEngine.Mathf.Cos(angle), UnityEngine.Mathf.Sin(angle))) * UnityEngine.Random.Range(0, AIConstants.maxforce));
 }
 }
 }

Insertion Mutation

This is a very effective mutation and is almost the same as the DM operator, except here only one gene is selected to be displaced and inserted back into the chromosome. In tests, this mutation operator has been shown to be consistently better than any of the alternatives mentioned here.

Sample code

public void MutateIM(ref List&amp;amp;lt;Vector2&amp;amp;gt; genes)
 {
 //return dependent upon mutation rate
 if ((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; MutationRate) return;

 int newInsertPosition = RandomProvider.RND.Next(0, genes.Count - 1);

 //erase from current position
 Vector2 gene = genes[newInsertPosition];

 genes.RemoveAt(newInsertPosition);

 newInsertPosition = RandomProvider.RND.Next(0, genes.Count - 1);

 genes.Insert(newInsertPosition, gene);
 }

Inversion Mutation

Select two random points and reverse the elements between them.

Sample code

public void MutateIVM(ref List&amp;amp;lt;Vector2&amp;amp;gt; genes)
 {
 //return dependent upon mutation rate
 if ((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; MutationRate) return;

 //first we choose a section of the chromosome
 const int MinSpanSize = 3;

 //these will hold the beginning and end points of the span
 int beg = 0, end = 0;
 ChooseSection(ref beg, ref end, genes.Count - 1, MinSpanSize);

 // Calculate how many items to reverse
 int span = end - beg;

 genes.Reverse(beg, span);
 }

Displaced Inversion Mutation

Select two random points, reverse the element order between the two points, and then displace them somewhere along the length of the original chromosome. This is similar to performing IVM and then DM using the same start and end points.

Sample code

public void MutateDIVM(ref List&amp;amp;lt;Vector2&amp;amp;gt; genes)
 {
 //return dependent upon mutation rate
 if ((float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1) &amp;amp;gt; MutationRate) return;

 //first we choose a section of the chromosome
 const int MinSpanSize = 3;

 //these will hold the beginning and end points of the span
 int beg = 0, end = 0;
 ChooseSection(ref beg, ref end, genes.Count - 1, MinSpanSize);

 // Calculate how many items to reverse
 int span = end - beg;

 genes.Reverse(beg, span);

 //hold on to the section we are moving
 List&amp;amp;lt;Vector2&amp;amp;gt; aSectionOfGenes = genes.GetRange(beg, span);

 //erase from current position
 genes.RemoveRange(beg, span);

 int newInsertPosition = RandomProvider.RND.Next(0, genes.Count - 1);

 genes.InsertRange(newInsertPosition, aSectionOfGenes);
 }

Encoding

Encoding is simply the way a problem is presented in such a way that the computer can solve the problem desired by someone.

Scaling Techniques

“Although using selection on the raw (unprocessed) fitness scores can give you a genetic algorithm that works (it solves the task you’ve designed it for), often your  genetic algorithm can be made to perform better if the fitness scores are scaled in some way before any selection takes place. “ (Buckland, 2002)

 

Rank Scaling

“Rank scaling can be a great way to prevent too quick convergence, particularly at the start of a run when it’s common to see a very small percentage of individuals outperforming all the rest. The individuals in the population are simply ranked according to fitness, and then a new fitness score is assigned based on their rank.  … Once the new ranked fitness scores have been applied, you select individuals for the next generation using roulette wheel selection or a similar fitness proportionate selection method. … This technique avoids the possibility that a large percentage of each new generation is being produced from a very small number of highly fit individuals, which can quickly lead to premature convergence. In effect, rank scaling ensures your population remains diverse. The other side of the coin is that the population may take a lot longer to converge, but often you will find that the greater diversity provided by this technique leads to a more successful result for your genetic algorithm. “ (Buckland, 2002)

A cheap and easy method of retaining population diversity, while slowing down convergence. The drawback due to low variance is that it might take a long type to converge upon a solution. Used with elitism is a good approach.” AI Game Programming Wisdom 2

Sample code

public void FitnessScaleRanking(ref List&amp;amp;lt;Host&amp;amp;gt; pop)
 {
 // Arrange the population according to the highest fitness score currently
 var population = pop.OrderByDescending(o =&amp;amp;gt; o.DNA.Fitness);

 // The highest ranking value will be the max count of hosts in the population, while the minimum is for the least fittest memeber will have the fit score of one.
 int populationSize = pop.Count;
 foreach(Host host in population)
 {
 // Apply a new fittness score based on the raking value which is determined by the population size.
 host.DNA.Fitness = populationSize;
 // Go to the next ranking value for the next host
 populationSize--;
 }
 }

Another example of ranking with the ranking value converted into a float value ranging from 0 to 1.

public void FitnessScaleRanking(ref List&amp;amp;amp;lt;Host&amp;amp;amp;gt; pop)
 {
public void FitnessScaleRankingToFloatRangeZeroToOne(ref List&lt;Host&gt; pop)
 {
 // Arrange the population according to the highest fitness score currently
 var population = pop.OrderByDescending(o =&gt; o.DNA.Fitness);

 // The highest ranking value will be the max count of hosts in the population, while the minimum is for the least fittest memeber will have the fit score of one.
 int populationSize = pop.Count;
 foreach (Host host in population)
 {
 // Apply a new fittness score based on the raking value which is determined by the population size.
 host.DNA.Fitness = Mathf.Abs((1 / (float)populationSize) - 1);
 // Go to the next ranking value for the next host
 populationSize--;
 }
 }

Sigma Scaling

“If you use raw fitness scores as a basis for selection, the population may converge too quickly, and if they are scaled as in rank selection, the population may converge too slowly. Sigma scaling is an attempt to keep the selection pressure constant over many generations. At the beginning of the genetic algorithm, when fitness scores can vary wildly, the fitter individuals will be allocated less expected offspring. Toward the end of the algorithm, when the fitness scores are becoming similar, the fitter individuals will be allocated more expected offspring.” (Buckland, 2002)

“Keeping selection pressure constant over many generations.” 

AI Game Programming Wisdom 2

Sample code

public void FitnessScaleSigma(ref List&amp;amp;lt;Host&amp;amp;gt; pop)
 {

 float RunningTotal = 0;
 //first iterate through the population to calculate the standard
 //deviation
 for (int gen = 0; gen &amp;amp;lt; pop.Count; ++gen)
 {
 RunningTotal += (pop[gen].DNA.Fitness - this.AverageFitnessScore) *
 (pop[gen].DNA.Fitness - this.AverageFitnessScore);
 }
 float variance = RunningTotal / (float)this.PopSize;
 //standard deviation is the square root of the variance
 Sigma = Mathf.Sqrt(variance);
 //now iterate through the population to reassign the fitness scores

 for (int gen = 0; gen &amp;amp;lt; pop.Count; ++gen)
 {
 float OldFitness = pop[gen].DNA.Fitness;
 pop[gen].DNA.Fitness = (OldFitness - this.AverageFitnessScore) /
 (2 * Sigma);
 }
 //recalculate values used in selection
 this.CalculateBestWorstAverageTotalFitnessScore(ref pop);

 }

 

 

Boltzmann Scaling

”… sometimes you may want the selection pressure to vary. A common scenario is one in which you require the selection pressure to be low at the beginning so that diversity is retained, but as the genetic algorithm converges closer toward a solution, you want mainly the fitter individuals to produce offspring.

One way of achieving this is by using Boltzmann scaling. This method of scaling uses a continuously varying temperature to control the rate of selection. …

Each generation, the temperature is decreased by a small value, which has the effect of increasing the selection pressure toward the fitter individuals.” (Buckland, 2002)

Sometimes, it’s preferable for selection pressure to be low at the begging and high toward the end. This ensures that your population remains diverse at the commencement of the algorithm. As the algorithm converges toward a solution, the fitter individuals are given preference.” AI Game Programming Wisdom 2

Sample code

public void FitnessScaleBoltzmann(ref List&amp;amp;lt;Host&amp;amp;gt; pop)
 {
 //reduce the temp a little each generation
 this.BoltzmannTemperature -= BOLTZMANN_DT;
 //make sure it doesn't fall below minimum value
 if (this.BoltzmannTemperature &amp;amp;lt; BOLTZMANN_MIN_TEMP)
 {
 this.BoltzmannTemperature = BOLTZMANN_MIN_TEMP;
 }
 //first calculate the average fitness/Temp
 float divider = this.AverageFitnessScore / this.BoltzmannTemperature;
 //now iterate through the population and calculate the new expected
 //values
 for (int gen = 0; gen &amp;amp;lt; pop.Count; ++gen)
 {
 float OldFitness = pop[gen].DNA.Fitness;
 pop[gen].DNA.Fitness = (OldFitness / this.BoltzmannTemperature) / divider;
 }
 //recalculate values used in selection
 this.CalculateBestWorstAverageTotalFitnessScore(ref pop);
 }

Optimization tips

Data handling

To minimize the impact of accessing data in memory and also memory management I would recommend that you get to know these two concepts:

 

Bibliography

Buckland, M. (2002). AI Techniques for Game Programming.

http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/PMXCrossoverOperator.aspx. (2015, 9). Retrieved from http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/PMXCrossoverOperator.aspx.

Nystrom, R. (2015, 9). Game programming patterns. Retrieved from Game programming patterns: http://gameprogrammingpatterns.com/contents.html

SHIFFMAN, D. (2015, 9). Nature of code. Retrieved from Nature of code: http://natureofcode.com/book/

Wikipedia. (2015, 9). https://en.wikipedia.org/wiki/Stochastic_universal_sampling. Retrieved from https://en.wikipedia.org/wiki/Stochastic_universal_sampling.

AI Game Programmin Widsom 2

 

 

Learning AI – Part 1: Genetic Algorithms Intro

Hi,

This is my first post in a series of Artificial Intelligence posts on AI learning. I got interested in the subject a few weeks ago when I started to work on some ideas for a game prototype I had in my mind. I was reading a book on game AI and turned the pages to a section of the book about AI learning It was fascinating :)! Anyways I remembered one of my older project where I played around with physics and nature I decided to back to it and the book that inspired me to nature and how it works.

So in this first post I’ll show you guys some sample C# code for a simple Genetic Algorithm that solves a text puzzle. On in other words I am using a GA algorithm so find the fastest solution to get the same text output from the algorithm that is input to the algorithm.

To start with if you are not familiar with Genetic Algorithms this source is a good place to start. My sample code at the moment is based on this page. This is where I will continue from later in the future parts of these upcoming blog posts on learning AI: http://natureofcode.com/book/chapter-9-the-evolution-of-code/

Logic and code

So lets start, ouh and remember I am just starting to learn this so double check the info and test for yourself :):

To put it in simple words GA algorithm is about inheriting data from generation to generation where the best candidate from the desired goal is chosen until the desired outcome generations later is achieved. Now this is a simplification of what is going on and there are more variables to take into consideration. I will keep things as simple as I can and hope that you refer to the link above or to more technical sources for more in-depth knowledge.

To start with a GA algorithm needs two things:

  1. genotype => Digital information that is passed down from generation to generation
  2. phenotype => this is the expression of data, how the data is going to be represented. This could be data that tells a system where an object is on the screen.

In this first part where the code sample is trying to solve a text problem the genotype and phenotype are one and the same called: DNA

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AIEngine.DataStructures
{
 public class DNA : IDNA
 {
 public List<Char> Genes { get; set; }
 public float Fitness { get; set; }
 public String Target { get; set; }

 public DNA()
 {
 this.Genes = new List<char>();
 }

 public DNA(int genesCount, String target)
 {
 this.InitializeGenes(genesCount);
 this.Target = target;
 }

 public void InitializeGenes(int genesCount)
 {
 this.Genes = new List<char>();
 if (genesCount < 0)
 throw new Exception("The genesCount must be larger than 0");
 else if (genesCount == 0)
 return;

 int index = 0;
 do
 {
 this.Genes.Add((char)RandomProvider.RND.Next(32, 128));
 index++;
 } while (index < genesCount);
 }

 public void EvalutateFitness()
 {
 int score = 0;
 for (int i = 0; i < this.Genes.Count; i++) 
 {

 if (this.Target[i] == this.Genes[i])
 score++;
 }

 this.Fitness = (float)score/this.Target.Length;
 }

 public IDNA Crossover(IDNA partner)
 {
 DNA child = new DNA(0, this.Target);
 int midpoint = RandomProvider.RND.Next(this.Genes.Count);

 for(int x = 0; x < this.Genes.Count; ++x) { if (x > midpoint)
 child.Genes.Insert(x,this.Genes[x]);
 else
 child.Genes.Insert(x, partner.Genes[x]);
 }

 return child;
 }

 public void Mutate(float mutationRate)
 {
 for (int i = 0; i < this.Genes.Count; i++) {
 float rndValue = (float)RandomProvider.GetRandomNumber(RandomProvider.RND, 0, 1);
 if (rndValue < mutationRate)
 {
 this.Genes[i] = (char)RandomProvider.RND.Next(32, 128);
 }
 }
 }

 public override string ToString()
 {
 return new StringBuilder().Append(this.Genes.ToArray()).ToString();
 }
 }
}

What this class will do is generate a random number of character between a certain ASCII range. It will also evaluate a fitness for a DNA object to be used when deciding if the DNA will reproduce. Also to keep variation and increase the changes of a faster solution solving a crossover between two DNA objects are made. Also as a last measure to ensure that the best possible solution is achieved mutation to the DNA is introduced where a random character at random times is replaced in a DNA sequence of characters.

Next we will look at the population control class 😀

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using AIEngine.DataStructures;

namespace AIEngine
{
 public class Population
 {
 ///
<summary>
 /// Change this value to alter how fast a problem is solved
 /// </summary>

 private int populationCount = 1000;
 private String target = "TO BE OR NOT TO BE";
 private List<DNA> population;
 private List<DNA> matingPool;
 private int perfectScore;
 private Boolean finished;
 private int generations;

 ///
<summary>
 /// Change this value to alter how fast a problem is solved
 /// </summary>

 private float mutationRate = 0.01F; // This value of 0.01 with a population count of 1000 seems to be generating the fastest result with monte carlo mating

 ///
<summary>
 /// 
 /// </summary>

 /// <param name="target"></param>
 /// <param name="mutationRate"></param>
 /// <param name="populationCount"></param>
 public Population(String target, float mutationRate, int populationCount)
 {
 this.target = target;
 this.mutationRate = mutationRate;
 this.populationCount = populationCount;

 population = new List<DNA>();
 matingPool = new List<DNA>();
 for (int x = 0; x < this.populationCount; x++)
 {
 population.Add(new DNA(target.Length, target.ToUpper()));
 }

 this.CalculateFitness();

 this.finished = false;
 this.generations = 0;
 this.perfectScore = 1;
 }

 ///
<summary>
 /// In each iteration we calculate the fitness of each DNA sequence to be used later in the algorithm logic
 /// </summary>

 public void CalculateFitness()
 {
 for (int x = 0; x < population.Count; x++)
 {
 population[x].EvalutateFitness();
 }
 }

 ///
<summary>
 /// Here the algorithm implements a selection method for chosing the best DNA sequences from the population.
 /// </summary>

 public void NaturalSelection()
 {
 bool duplicateFound = true;
 matingPool.Clear();

 for (int x = 0; x < population.Count; x++) { //while (duplicateFound) { // Monte carlo method(Faster than the below commented approach) int a = RandomProvider.RND.Next(population.Count); int b = RandomProvider.RND.Next(population.Count); int populationIndexChosen = -1; if (population[a].Fitness > population[b].Fitness)
 {
 populationIndexChosen = a;
 }
 else
 {
 populationIndexChosen = b;
 }

 matingPool.Add(population[populationIndexChosen]);

 //if (!matingPool.Exists( o => o.ToString() == population[populationIndexChosen].ToString()))
 //{
 // matingPool.Add(population[populationIndexChosen]);
 // duplicateFound = false;
 //}

 //int n = (int)(population[x].Fitness * 100);
 //for (int j = 0; j < n; j++)
 //{

 // matingPool.Add(population[x]);
 //}
 }
 }
 }

 ///
<summary>
 /// Next we will generate a new population based on algorithmic logic of crossover between two random DNA sequences and adding some mutation into it.
 /// </summary>

 public void Generate()
 {
 for (int i = 0; i < population.Count; i++)
 {
 {
 int a = RandomProvider.RND.Next(matingPool.Count);
 int b = RandomProvider.RND.Next(matingPool.Count);
 // TODO: Avoid duplicates
 DNA partnerA = matingPool[a];
 DNA partnerB = matingPool[b];

 DNA child = (DNA)partnerA.Crossover(partnerB);
 child.Mutate(mutationRate);
 child.EvalutateFitness();
 population[i] = child;
 }
 }
 this.generations++;
 }

 public String GetBest()
 {
 float worldrecord = 0.0F;
 int index = 0;
 for (int i = 0; i < population.Count; i++) { if (population[i].Fitness > worldrecord)
 {
 index = i;
 worldrecord = population[i].Fitness;
 }
 }

 if (worldrecord == perfectScore) finished = true;
 return population[index].ToString();
 }

 public Boolean Finished()
 {
 return this.finished;
 }

 public int GetGenerations()
 {
 return generations;
 }

 // Compute average fitness for the population
 public float GetAverageFitness()
 {
 float total = 0;
 for (int i = 0; i < population.Count; i++) { total += population[i].Fitness; } return total / (population.Count); } public String AllPhrases() { StringBuilder everything = new StringBuilder(); for (int i = population.Count -1; i > population.Count - 11; i--)
 {
 everything.AppendLine(population[i].ToString());
 }
 return everything.ToString();
 }
 }
}

The Population classes main function is to hold the main population of DNA sequences and the mating pool used to generate the next generation of population (or to replace the current generation of population with the next generation). Also some statistical data can be retrieved from the class itself along with the information when the problem has been solved. In this case when the output is the same as the input.

Next is actual main program which will run the population to solve a problem.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using AIEngine.DataStructures;
using AIEngine;

namespace GeneticAlgoritmTextTest
{
 class Program
 {
 ///
<summary>
 /// Change this value to alter how fast a problem is solved
 /// </summary>

 public static int PopulationCount = 1000;
 public static String target = "TO BE OR NOT TO BE";

 ///
<summary>
 /// Change this value to alter how fast a problem is solved
 /// </summary>

 public static float mutationRate = 0.01F;
 static void Main(string[] args)
 {
 bool exit = false;

 // Create the population which is responsible for solving the problem.
 Population population = new Population(target, mutationRate, PopulationCount);
 while (!exit)
 {
 // In each iteration we calculate the fitness of each DNA sequence to be used later in the algorithm logic
 population.CalculateFitness();
 // Here the algorithm implements a selection method for chosing the best DNA sequences from the population.
 population.NaturalSelection();
 // Next we will generate a new population based on algorithmic logic of crossover between two random DNA sequences and adding some mutation into it.
 population.Generate();
 

 Console.WriteLine();
 Console.WriteLine(population.AllPhrases());
 Console.WriteLine("Cycle average fitness: " + population.GetAverageFitness());
 Console.WriteLine("Total generations: " + population.GetGenerations());
 Console.WriteLine("Best fitness in cycle: " + population.GetBest());

 // And before we go to the next iteration we check to see if the text puzzle has been solved.
 exit = population.Finished();
 }
 Console.ReadLine();
 }
 }
}

The code above simple creates a population which will try to solve the a text puzzle. A fitness is calculated for each member of the population. A selection method is applied for the population and a mutation is introduced at random population members.

The end result should be something like this:

GABasicDNAStart

GABasicDNAEnd

There are two images above. The first one shows the very first populations in the algorithm. The last image show the very last population generations up until the very last one which solved the problem.

Optimization

There are two things to do if you want to optimize the algorithm in this example:

  1. Changing the mutation rate and population count variables.
    1. By playing around with these values you can find out the most “optimal” values to solve your desired problem. You can do this manually or you can write a piece of code which will do this for you based on the telemetry from the algorithm.
      1. Notice that having to a too large mutation rate will make the algorithm unsolvable and like wise having a too small or way too large population count will cause your algorithm to take longer or a very long time.
  2. The fitness function logic
    1. Here I will simply quote Daniel Shiffman from The Nature of code: “If you cannot define your problem’s goals and evaluate numerically how well those goals have been achieved, then you will not have successful evolution in your simulation.” So defining a good fitness function will go a long way towards creating a better result. Also each problem will most likely have a very unique fitness function. Similarities can occur(Still learning 🙂 ).

The source code for this project you will find here: https://github.com/lionadi/NatureOfCodePlayground/tree/master/NatureOfCodeCSharp%20AI%20Project

Also as you can see the code is a work in progress, not pretty and not ready :). So changes in the github versions are due to come in the future.