TSP with GeneticSharp and Unity3D

16/05/2018

8 minutes to read

In this post I will show how to use GeneticSharp and Unity3D 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 Unity3D using GeneticSharp.

Prerequisites

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

Unity3D (beginner)
Genetic algorithms (beginner).

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

Creating the Unity3D project

Using Unity 2018.1+, create a new project called TspSample.

Using .NET Standard 2.0

Go to “Player settings” / “Other settings” / “Configuration”, select “.NET 4.x Equivalent” on “Scripting Runtime Version”. Unity will ask to restart, you can confirm.

After restart, go back to “Player settings”, select “.NET Standard 2.0” on “Api Compability Level”.

Installing GeneticSharp

Install GeneticSharp using the .unitypackage available on GeneticSharp release page.

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 C# script called “TspChromosome.cs”:

	using GeneticSharp.Domain.Chromosomes;
	using GeneticSharp.Domain.Randomizations;

	public class TspChromosome : ChromosomeBase
	{
	private readonly int m_numberOfCities;

	public TspChromosome(int numberOfCities) : base(numberOfCities)
	{
	m_numberOfCities = numberOfCities;
	var citiesIndexes = RandomizationProvider.Current.GetUniqueInts(numberOfCities, 0, numberOfCities);

	for (int i = 0; i < numberOfCities; i++)
	{
	ReplaceGene(i, new Gene(citiesIndexes[i]));
	}
	}

	public double Distance { get; internal set; }

	public override Gene GenerateGene(int geneIndex)
	{
	return new Gene(RandomizationProvider.Current.GetInt(0, m_numberOfCities));
	}

	public override IChromosome CreateNew()
	{
	return new TspChromosome(m_numberOfCities);
	}

	public override IChromosome Clone()
	{
	var clone = base.Clone() as TspChromosome;
	clone.Distance = Distance;

	return clone;
	}
	}

view raw TspChromosome.cs hosted with ❤ by GitHub

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 C# script called “City.cs”:

	using UnityEngine;

	public class TspCity
	{
	public Vector2 Position { get; set; }
	}

view raw City.cs hosted with ❤ by GitHub

The fitness function

Now we need to evaluate the TspChromosome.

Our fitness function will evaluate the TspChromosome 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 C# script called “TspFitness.cs”:

	using System;
	using System.Collections.Generic;
	using System.Globalization;
	using System.Linq;
	using GeneticSharp.Domain.Chromosomes;
	using GeneticSharp.Domain.Fitnesses;
	using GeneticSharp.Domain.Randomizations;
	using UnityEngine;

	public class TspFitness : IFitness
	{
	private Rect m_area;

	public TspFitness(int numberOfCities)
	{
	Cities = new List<TspCity>(numberOfCities);

	var size = Camera.main.orthographicSize - 1;
	m_area = new Rect(-size, -size, size * 2, size * 2);

	for (int i = 0; i < numberOfCities; i++)
	{
	var city = new TspCity { Position = GetCityRandomPosition() };
	Cities.Add(city);
	}
	}

	public IList<TspCity> Cities { get; private set; }

	public double Evaluate(IChromosome chromosome)
	{
	var genes = chromosome.GetGenes();
	var distanceSum = 0.0;
	var lastCityIndex = Convert.ToInt32(genes[0].Value, CultureInfo.InvariantCulture);
	var citiesIndexes = new List<int>();
	citiesIndexes.Add(lastCityIndex);

	// Calculates the total route distance.
	foreach (var g in genes)
	{
	var currentCityIndex = Convert.ToInt32(g.Value, CultureInfo.InvariantCulture);
	distanceSum += CalcDistanceTwoCities(Cities[currentCityIndex], Cities[lastCityIndex]);
	lastCityIndex = currentCityIndex;

	citiesIndexes.Add(lastCityIndex);
	}

	distanceSum += CalcDistanceTwoCities(Cities[citiesIndexes.Last()], Cities[citiesIndexes.First()]);

	var fitness = 1.0 - (distanceSum / (Cities.Count * 1000.0));

	((TspChromosome)chromosome).Distance = distanceSum;

	// There is repeated cities on the indexes?
	var diff = Cities.Count - citiesIndexes.Distinct().Count();

	if (diff > 0)
	{
	fitness /= diff;
	}

	if (fitness < 0)
	{
	fitness = 0;
	}

	return fitness;
	}

	private Vector2 GetCityRandomPosition()
	{
	return new Vector2(
	RandomizationProvider.Current.GetFloat(m_area.xMin, m_area.xMax + 1),
	RandomizationProvider.Current.GetFloat(m_area.yMin, m_area.yMax + 1));
	}

	private static double CalcDistanceTwoCities(TspCity one, TspCity two)
	{
	return Vector2.Distance(one.Position, two.Position);
	}
	}

view raw TspFitness.cs hosted with ❤ by GitHub

Running 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 C# script called “GAController.cs”:

	using System.Threading;
	using GeneticSharp.Domain;
	using GeneticSharp.Domain.Crossovers;
	using GeneticSharp.Domain.Mutations;
	using GeneticSharp.Domain.Populations;
	using GeneticSharp.Domain.Selections;
	using GeneticSharp.Domain.Terminations;
	using GeneticSharp.Infrastructure.Framework.Threading;
	using UnityEngine;

	public class GAController : MonoBehaviour
	{
	private GeneticAlgorithm m_ga;
	private Thread m_gaThread;

	public int m_numberOfCities = 20;

	private void Start()
	{
	var fitness = new TspFitness(m_numberOfCities);
	var chromosome = new TspChromosome(m_numberOfCities);

	// This operators are classic genetic algorithm operators that lead to a good solution on TSP,
	// but you can try others combinations and see what result you get.
	var crossover = new OrderedCrossover();
	var mutation = new ReverseSequenceMutation();
	var selection = new RouletteWheelSelection();
	var population = new Population(50, 100, chromosome);

	m_ga = new GeneticAlgorithm(population, fitness, selection, crossover, mutation);
	m_ga.Termination = new TimeEvolvingTermination(System.TimeSpan.FromHours(1));

	// The fitness evaluation of whole population will be running on parallel.
	m_ga.TaskExecutor = new ParallelTaskExecutor
	{
	MinThreads = 100,
	MaxThreads = 200
	};

	// Everty time a generation ends, we log the best solution.
	m_ga.GenerationRan += delegate
	{
	var distance = ((TspChromosome)m_ga.BestChromosome).Distance;
	Debug.Log($"Generation: {m_ga.GenerationsNumber} - Distance: ${distance}");
	};

	// Starts the genetic algorithm in a separate thread.
	m_gaThread = new Thread(() => m_ga.Start());
	m_gaThread.Start();
	}

	private void OnDestroy()
	{
	// When the script is destroyed we stop the genetic algorithm and abort its thread too.
	m_ga.Stop();
	m_gaThread.Abort();
	}
	}

view raw GAController.v1.cs hosted with ❤ by GitHub

Create a GameObject called “GAController” in the scene and add the GAController.cs to it.

Save the scene.

Run the scene on editor and take a look on the 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 Unity3D, but it need to display the cities route better. We need to create a visual representation to the cities.

City prefab

We will create a prefab based on a sprite of a pin. You can use an icon as this one from www.flaticon.com.

Download it to inside your Unity3D project.

Maybe you will need to change the ‘Pixels Per Unit’ to 1000 to get a good pin size on screen.

Drag it to the hierarchy panel, rename the new GameObject to CityPrefab and drag it back to your Assets folder on Project panel. Now our CityPrefab is created.

Delete the CityPrefab game object from the current scene.

Instantiating the cities prefabs

Add the following field to the GAController.cs

public Object CityPrefab;

view raw GAController.change1.cs hosted with ❤ by GitHub

Then, create the method DrawCities:

	void DrawCities()
	{
	var cities = ((TspFitness)m_ga.Fitness).Cities;

	for (int i = 0; i < m_numberOfCities; i++)
	{
	var city = cities[i];
	var go = Instantiate(CityPrefab, city.Position, Quaternion.identity) as GameObject;
	go.name = "City " + i;
	}
	}

view raw GAController.change2.cs hosted with ❤ by GitHub

And then call it from Start method:

	...
	DrawCities();

	m_gaThread = new Thread(() => m_ga.Start());
	m_gaThread.Start();

view raw GAController.change3.cs hosted with ❤ by GitHub

Now, select the GAController game object on hierarchy and set the CityPrefab property.

Try to run the scene, 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.

One of the simplest ways to draw some lines in Unity3D is using the LineRenderer component.

Add the following code to the GAController.cs:

	private LineRenderer m_lr;

	private void Awake()
	{
	m_lr = GetComponent<LineRenderer>();
	m_lr.positionCount = m_numberOfCities + 1;
	}

view raw GAController.change4.cs hosted with ❤ by GitHub

Create the method DrawRoute:

	void DrawRoute()
	{
	var c = m_ga.Population.CurrentGeneration.BestChromosome as TspChromosome;

	if (c != null)
	{
	var genes = c.GetGenes();
	var cities = ((TspFitness)m_ga.Fitness).Cities;

	for (int i = 0; i < genes.Length; i++)
	{
	var city = cities[(int)genes[i].Value];
	m_lr.SetPosition(i, city.Position);
	}

	var firstCity = cities[(int)genes[0].Value];
	m_lr.SetPosition(m_numberOfCities, firstCity.Position);
	}
	}

view raw GAController.change5.cs hosted with ❤ by GitHub

Then call it from Update method:

	private void Update()
	{
	DrawRoute();
	}

view raw GAController.change6.cs hosted with ❤ by GitHub

Before run the scene, we need to add a LineRenderer component to our GAController game object.

Change the width property of the LineRenderer from 1 to 0.1.

Run the scene again, now you should see the route been optimizing as the generations are ran:

Changing the cities positions

Our sample could be considered done, but would it be nice if we you could change the cities positions while the genetic algorithm are running and see how it manages these cities positions changes.

CityController

Create a C# script called “CityController.cs”:

	using UnityEngine;

	[RequireComponent(typeof(BoxCollider2D))]
	public class CityController : MonoBehaviour
	{
	private Vector3 screenPoint;
	private Vector3 offset;

	public TspCity Data { get; set; }

	void OnMouseDown()
	{
	screenPoint = Camera.main.WorldToScreenPoint(gameObject.transform.position);
	offset = gameObject.transform.position - Camera.main.ScreenToWorldPoint(new Vector3(Input.mousePosition.x, Input.mousePosition.y, screenPoint.z));
	transform.localScale *= 2f;
	}

	void OnMouseUp()
	{
	transform.localScale /= 2f;
	}

	void OnMouseDrag()
	{
	Vector3 curScreenPoint = new Vector3(Input.mousePosition.x, Input.mousePosition.y, screenPoint.z);
	Vector3 curPosition = Camera.main.ScreenToWorldPoint(curScreenPoint) + offset;
	transform.position = curPosition;

	Data.Position = transform.position;
	}

	void Update()
	{
	transform.position = Data.Position;
	}
	}

view raw CityController.cs hosted with ❤ by GitHub

I won’t getting in details about how this is script works, but it’s allow the user to drag the cities’ pin using the mouse or the finger touch if build it to mobile.

Add the CityController.cs to the CityPrefab.

Change the GAController.cs script adding the line below to the end of the for loop of DrawCities method:

go.GetComponent<CityController>().Data = city;

view raw GAController.change7.cs hosted with ❤ by GitHub

Finally, our sample is really done and you should be capable to change the cities positions, by dragging the pins around, and genetic algorithm will try to figure out the best route in real time.

Conclusion

With only 5 C# scripts and 1 prefab we built a pretty nice sample of genetic algorithms using in Unity3D with GeneticSharp. Now you can improve it with your own ideas or use some of mine ;):

How about make it 3D and using a Vector3 instead of Vector2 on City.Position?
Maybe let user change the number of cities or change the genetic algorithm operators?
Move the DrawCities and DrawRoutes methods to a script responsible to only draw the GA.

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

Let’s evolve!

Icons made by Freepik from www.flaticon.com is licensed by CC 3.0 BY

geneticsharp unity3d tsp dotnet

Loading comments...