F# Genetic Algorithm – Defining Squirrel Genes
Tags: dotnet, fsharp, ai, csharp
Published: 2019-11-04 04:59:48

---
title: F# Genetic Algorithm – Defining Squirrel Genes
published: true
date: 2019-11-04 04:42:43 UTC
series: Emulating Squirrel Brains in F# with Genetic Algorithms
tags: dotnet, fsharp, ai, csharp
cover_image: https://i1.wp.com/killalldefects.com/wp-content/uploads/2019/11/image-4.png?fit=768%2C470&ssl=1
canonical_url: https://killalldefects.com/2019/11/03/f-genetic-algorithm-defining-squirrel-genes/
---

In this article, we’ll implement the chromosome of a digital squirrel. If that sounds unusual, well, I suppose it is. We’ll be taking a previous app that was a player-controlled simulation and converting it to something with the beginnings of AI. Our ultimate goal here is to set ourselves up for implementing a full genetic algorithm in the next article.

![The application at the end of this article](https://i0.wp.com/killalldefects.com/wp-content/uploads/2019/11/image-9.png?w=770&ssl=1)

## Learning Objectives

We’ll be starting with a WPF Core 3.0 C# app that uses F# logic for game simulation. We’ll strip out player input and instead connect an artificial intelligence system that the simulation will use to get commands for the squirrel.

By the end of this article you should learn:

- Basic concepts of genetic algorithms (we will go into more depth next article)
- The concept of a Chromosome and a Gene at a high level as they apply to Genetic Algorithms
- How immutability and functions can simplify artificial intelligence
- How to create and use WPF User Controls to organize user interfaces

## Series Overview

This article is a part 5 in a series on implementing a genetic algorithm in F#. Our ultimate goal is to simulate a 2D world where a squirrel can learn to navigate to an acorn and then get to its tree without starving to death or being eaten by the dog. The dog will be stationary for the purposes of this simulation and there is also a rabbit that will act randomly.

Previous articles in the series include:

- [Creating a .NET Core 3.0 F# Console App](https://killalldefects.com/2019/09/29/creating-a-net-core-fsharp-console-app/)
- [F# Squirrel Brains: Adding Actors and Getting Functional](https://killalldefects.com/2019/10/05/f-sharp-squirrel-brains-adding-actors-and-getting-functional/)
- [F# Unit Testing – Refining the Squirrel Simulation](https://killalldefects.com/2019/10/22/f-unit-testing-refining-the-squirrel-simulation/)
- [WPF Core with F# Libraries](https://killalldefects.com/2019/10/23/wpf-core-with-fsharp-libraries/)

If you’d like to follow along with the code, our starting point is [the Article 4 branch](https://github.com/IntegerMan/FSharpGeneticAlgorithm/tree/article4) on my GitHub repository. The finished code from this article will be available in [the Article 5 branch](https://github.com/IntegerMan/FSharpGeneticAlgorithm/tree/article5).

## Genetic Algorithm 101

While we’ll be getting into the nuts and bolts of genetic algorithms next article, we should discuss them at a high level here.

Essentially, genetic algorithms are all about finding an optimal solution to a particular problem. Genetic algorithms (GAs for short) involve a **population** of a given number of **chromosomes**.

Each chromosome is essentially a potential solution to the optimization problem the genetic algorithm is trying to solve. Chromosomes have one or more **gene** inside of them, which are specific data about the solution in codified form. A gene might be a boolean value or some form of number.

For example, our chromosome will contain numeric genes from -1 to +1. These values indicate how attractive or unattractive a tile is to an actor based on distance to other actors:

![A sample chromosome that foolheartedly runs towards the dog](https://i0.wp.com/killalldefects.com/wp-content/uploads/2019/11/image-2.png?w=770&ssl=1)

Getting back to the population concept, a population is composed of a number of chromosomes in a given **generation**. At the end of a simulation, each chromosome is evaluated by a **fitness function** and given a numerical score. This score represents _how well the chromosome represents a solution to the optimization problem_.

At the end of a generation, low-performing chromosomes are typically killed off while higher performing ones are kept on into the next generation. The population of that next generation is then created by creating a few completely random chromosomes as well as descendants of the high performing chromosomes.

![Generation 2 keeps top performers, some of their offspring, and random chromosomes](https://i1.wp.com/killalldefects.com/wp-content/uploads/2019/11/image-5.png?w=770&ssl=1)

Chromosomes can also have multiple parents and will have genetic **crossover** where half of the chromosome is composed of genes from one parent while half have genes from the other parent.

![An example of genetic Crossover](https://i2.wp.com/killalldefects.com/wp-content/uploads/2019/11/image-3.png?w=770&ssl=1)

Additionally, values can be **mutated** after crossover, which introduces a further degree of randomness to one or more genes.

![An example of mutation after crossover](https://i1.wp.com/killalldefects.com/wp-content/uploads/2019/11/image-4.png?w=770&ssl=1)

This combination of randomness and mutation helps find better solutions over time as generations continue forward.

## Adding Genes and Chromosomes

Our Squirrel’s genes are going to be how much it desires to be near a specific type of object. Because of that, we can define the following F# code:

{% gist https://gist.github.com/IntegerMan/75b134411c5e5b443862dd20f0fa9ff0 %}

In this block, we define the `ActorChromosome` type with 6 double-based genes. This will hold immutable state related to a chromosome.

We then define `getRandomGene` as a function to get a value between -1 and 1. `getRandomChromosome` will use this function to build out a completely random `ActorChromosome` for us to use later.

Okay, cool. That’s pretty easy. Next, let’s look at how to integrate this into our existing simulation logic.

## Evaluating Tiles for Chromosomes

Next, we need to add code to evaluate a game move for a given `ActorChromosome`. The theory behind this is that if our we evaluate all available moves an actor has, the actor should pick the most attractive option. Attractiveness here is defined by proximity to things it likes minus proximity to things it doesn’t like.

For example, the squirrel in the picture below might evaluate its options as follows:

![An image of a squirrel avoiding moving next to a dog and favoring to move closer to the acorn](https://i1.wp.com/killalldefects.com/wp-content/uploads/2019/11/image-7.png?w=770&ssl=1)

In this case, the squirrel would go down, because 6 was the highest scoring option available to it as it wants to get to the acorn while avoiding the dog. Note that the squirrel _can_ wait, but this option was not represented on the image above.

We can code this tile evaluation using a pair of functions:

{% gist https://gist.github.com/IntegerMan/f8f172e1842fe9825f205b023dcf4d2a %}

In the `evaluateProximity` function, we calculate the distance to a tile and amplify that by the weight. This weight is sent in from `evaluateTile` based on a specific _gene_.

Note that if an actor is not active, it will not be scored. This keeps the dead rabbit or the already picked up acorn from impacting the squirrel.

We also introduce an opportunity for randomness to play a role by having a gene specifically for the impact of randomness in the simulation. Randomness can offer a degree of flexibility in finding solutions, so it can be helpful in including it as an option in the genes.

One final note here is how F# allows us to use multi-line statements on lines 8 – 13. I wasn’t sure when writing this code if it would work, but it does. My point of concern was that F# uses indentation and line breaks for some of its logical evaluation instead of semicolons.

## Simulating Chromosomes

Next, let’s look at `Simulator.fs` from our prior articles and add a pair of functions:

{% gist https://gist.github.com/IntegerMan/2db33c960ccc0639035e3d97b67a123b %}

The `handleChromosomeMove` function grabs a list of candidate moves for the squirrel using the `getCandidates` function. The `true` parameter indicates that we want to include the squirrel’s current position.

With that list of options, we call `evaluateTile` for each and take the largest result as our new position. The function then calls `moveActor` which actually moves the squirrel and mutates the state.

Finally, `simulateActors` is called to allow the rabbit and dog to get their turns and return the final modified state for the turn to the caller.

Because we no longer want to allow the player to move, we can rip out any player-control specific logic, tests, and data structures. I’ll not cover it in this article, but I removed the Commands type, a number of simulation methods, the console app from earlier units, and a pair of tests.

## Implementing the User Interface

Okay, so now that we have some AI controls, we need to implement a way of updating our WPF app to use them.

Previously we had a 3×3 grid of movement buttons as pictured below:

![The old user interface, featuring a movement button grid](https://i0.wp.com/killalldefects.com/wp-content/uploads/2019/10/image-16.png?w=770&ssl=1)<figcaption>The old user interface, featuring a movement button grid</figcaption>

Since the player controls are no longer relevant, let’s hook this up instead to our new logic.

Since our UI is mostly staying the same, I’ll simply share the new command area section of the XAML:

{% gist https://gist.github.com/IntegerMan/a51001a84916bebe91881dc8138b67fc %}

Here we have three buttons bound to commands in our `MainViewModel`. Let’s take a look at that now:

{% gist https://gist.github.com/IntegerMan/eb88c04262e15e2425efb390b6c96120 %}

This new code is fairly simple.

`RandomizeBrain` calls to our `getRandomChromosome` F# function and uses it to replace the `_brain` instance. Note that we’re using a `BrainInfoViewModel` here. I’ll get to that in a bit.

`GetArtificialIntelligenceMove` calls directly to our `handleChromosomeMove` function from `Simulator.fs` and passes the concrete `ActorChromosome` instance from the `BrainInfoViewModel`.

Because all we’re changing here is how the simulation is invoked, not much else needs to change. The UI is still built around displaying the current state, the only difference is what chooses where the squirrel goes.

Pretty cool, huh?

## Visualizing Squirrel Brains

I couldn’t resist the heading.

It’s one thing to fire up the simulation and trust that a randomized squirrel brain is controlling the squirrel. It’s another thing entirely to see the individual genes that comprise the squirrel’s behavior.

In this section, we’re going to make a WPF _user control_ to hold information about the `ActorChromosome`. This will help us understand what’s going on as well as give us a way of viewing chromosomes in the next article.

In WPF, a User Control is a custom region of XAML and C# code that presents something on the screen in a potentially repeatable manner. You can use User Controls to re-use assets in different screens, or even just to simplify and organize your view logic.

We’ll add one by right clicking on the WPF project in solution explorer, choosing Add \> New Item… and then selecting User Control (WPF) as pictured below:

![Visual Studio 2019's Add Item Dialog with a new User Control (WPF) selected and a name of BrainInfoControl.xaml](https://i2.wp.com/killalldefects.com/wp-content/uploads/2019/11/image-8.png?fit=770%2C533&ssl=1)<figcaption>Visual Studio 2019’s Add Item Dialog</figcaption>

Name your control something meaningful and click add.

We won’t need to add any custom C# code to the new control, but go into its XAML file and add the following code:

{% gist https://gist.github.com/IntegerMan/d11bf261581d9eb7935ace0550a6e18c %}

This creates a series of progress bars with values from -1 to 1 to visualize our individual genes. These progress bars have their `Value` bound to properties on the `BrainInfoViewModel`.

Note that this binding is defined with `Mode=OneWay`. This tells WPF that the value won’t need to update the view model ever, which prevents errors since our view model won’t have property setters.

Next, let’s go back into MainWindow.xaml and we can then add the following declaration to the top:

`xmlns:me="clr-namespace:MattEland.FSharpGeneticAlgorithm.WindowsClient"`

This tells the app that wherever it sees `me:` before a control, it refers to something in the referenced namespace.

This lets us replace our command panel XAML with the following:

{% gist https://gist.github.com/IntegerMan/5f5f20740d33ba1ee4a0cbc8d762e1bd %}

Note line 8 here where we explicitly include the new user control and bind its `DataContext` to the `Brain` property on our `MainViewModel`. This property points to an instance of `BrainInfoViewModel`.

`BrainInfoViewModel` is a very simple read-only view model that exposes information from the `ActorChromosome` class.

{% gist https://gist.github.com/IntegerMan/7a3ebd0f2bbac59f9fff34396baab858 %}

This view model is ultimately not adding much, but it’s a good practice in many cases not to bind directly to models from other libraries. This class gives us an adapter and allows us to rename properties or do custom logic as needed.

## Putting it All Together

Once the app is up and running, you can start to see the potential:

![A squirrel exhibiting different behavior after its brain is changed](https://i0.wp.com/killalldefects.com/wp-content/uploads/2019/11/BrainRandomization.gif?w=770&ssl=1)

Here we start with a chromosome that wants to pursue the rabbit. After I randomize the brain, we wind up with a brain that goes straight to the dog. While this squirrel is predictably short-lived, you can see how a few parameters drastically change the behavior of the squirrel.

Next time, we’ll put it all together into a genetic algorithm that looks to evolve a squirrel that can grab the acorn and go to the tree without getting eaten by the dog.

Stay tuned.

The post [F# Genetic Algorithm – Defining Squirrel Genes](https://killalldefects.com/2019/11/03/f-genetic-algorithm-defining-squirrel-genes/) appeared first on [Kill All Defects](https://killalldefects.com).