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.

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
• F# Squirrel Brains: Adding Actors and Getting Functional
• F# Unit Testing – Refining the Squirrel Simulation
• WPF Core with F# Libraries

If you’d like to follow along with the code, our starting point is the Article 4 branch on my GitHub repository. The finished code from this article will be available in the Article 5 branch.

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:

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.

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.

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

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:

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:

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:

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:

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:

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:

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

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:

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:

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:

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.

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:

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 appeared first on Kill All Defects.