TSP with GeneticSharp and Blazor

In this post I will show how to use GeneticSharp and Blazor to solve the TSP (Travelling salesman problem).

Introduction

According to Wikipedia The travelling salesman problem (TSP) asks the following question:“Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?”

TSP is a classic sample to test some optimization techniques, as well it’s fairly used to demonstrate how to implement a genetic algorithm. For these reasons I will use it to show you how to implement a basic genetic algorithm in Blazor using GeneticSharp.

You can see the final result of this tutorial on http://diegogiacomelli/apps/geneticsharp-runner-blazorapp.

Prerequisites

To better understand this tutorial, you need to have some experiences/knowledges in:

• Blazor (beginner)
• Genetic algorithms (beginner).

We will perform a very basic use of Blazor and everything you need to complete this tutorial will be explained or provided by the code samples, but if you want to find out better what’s happening under the hood, take a look on Blazor Get Started page.

If you need an introduction to genetic algorithms, take a look at this tutorial Function optimization with GeneticSharp.

Creating the Blazor project

Open a terminal and type:

dotnet new -i Microsoft.AspNetCore.Blazor.Templates::3.0.0-preview6.19307.2

Now we’ll create a scaffold Blazor app using the blazor template:

dotnet new blazor -o TspWithGeneticSharp
cd TspWithGeneticSharp
dotnet watch run

Wait for the message Application started. Press Ctrl+C to shut down show up in terminal, then open the url http://localhost:5000 on your browser, you should see something like this:

Installing GeneticSharp

Open a new terminal in the same folder and type:

dotnet add package GeneticSharp

Opening the project

I recommend to you use Visual Studio Code to open the project. There are some cool VS Code extensions to work with Blazor.

In the same terminal where you added the GeneticSharp package, type:

code .

In the root folder of your Blazor project create a new subfolder called Tsp. We’ll add all our C# classes inside this folder.

Defining the TSP chromosome

The chromosome represents a solution of the problem we are trying to solve. In our case the TSP chromosome should represent “the shortest possible route that visits each city and returns to the origin city”.

To represent the cities route each gene of our chromosome will represent an index of a city in the route.

Create a file called TspChromosome.cs:

Representing a city

The next step is define our genetic algorithm fitness function, but first we need to create a simple class to represent a city on a 2D space.

Create a file called TspCity.cs:

The fitness function

Now we need to evaluate the TspChromosome.

Our fitness function will evaluate the chromosome fitness based on the total distance to reach all cities in the route represented by the chromosome. The shorter the distance, the better the chromosome.

Create a file called TspFitness.cs:

Configuring the Genetic Algorithm

In this step we need to configure our genetic algorithm using the TspChromosome, TspFitness and some classic GA operators already built in GeneticSharp.

Create a file called TspGA.cs:

Creating the Razor page

Inside the folder Pages create a file called Tsp.razor:

As we need to interop with JavaScript to manipulate DOM, we will use some helper JS functions. Add the file canvas-helper.js inside the folder wwwroot/js:

Open the file index.html and add the tag below inside the tag head:

Check your terminal window where the command dotnet watch run is running, if there is no error in that window you can access the url http://localhost:5000/tsp.

Hit the Run button and take a look on the browser console window, you will see the distance to reach all cities getting smaller as the generations ran.

Drawing the cities

Now our GA is running inside the browser, but it needs to display the cities route better. We need to create a visual representation to the cities.

In the Tsp.razor add the method DrawCitiesAsync:

Then call it from OnAfterRenderAsync method, after the clearCanvas call:

Reload the url http://localhost:5000/tsp.

Now you should see something like this:

Drawing the route

In the previous step we drawn the cities and we have the visual of the problem: the cities.

Now we need to draw the solution: the route represented by the best chromosome of each generation.

Add the following method to the Tsp.razor:

Then call it from OnAfterRenderAsync method, after the DrawCitiesAsync call:

Reload the url http://localhost:5000/tsp again, and hit the Run button, now you should see the route been optimizing as the generations are ran:

Conclusion

With only 4 C# classes, 1 JS file and 1 Blazor page we built a pretty nice sample of genetic algorithms using Blazor with GeneticSharp. Now you can improve it with your own ideas or use some of mine ;):

• Maybe let user change the genetic algorithm operators (crossover, mutation, selection, etc)?
• Move the DrawCitiesAsync and DrawRouteAsync to Blazor components responsible to only draw them?

The full source code used in this post can be download or fork from this Gist: https://gist.github.com/giacomelli/9addc5182943ba25eb82201e30c76418

Let’s evolve!

Icons made by Freepik, Vignesh Oviyan and Eucalyp from www.flaticon.com is licensed by Creative Commons BY 3.0