Skip to content

Instantly share code, notes, and snippets.

@giacomelli

giacomelli/Tsp.razor

Last active February 6, 2020 05:09
Show Gist options
  • Save giacomelli/9addc5182943ba25eb82201e30c76418 to your computer and use it in GitHub Desktop.
Save giacomelli/9addc5182943ba25eb82201e30c76418 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
canvas-helper.js
var _canvas;
var _canvasContext;
function initializeCanvas()
{
_canvas = document.getElementById('canvas');
_canvasContext = _canvas.getContext('2d');
_canvas.width = window.innerWidth * .8;
_canvas.height = window.innerHeight * .8;
return [_canvas.width, _canvas.height];
}
function clearCanvas()
{
_canvasContext.clearRect(0, 0, _canvas.width, _canvas.height);
}
function drawRect(x, y, width, height)
{
_canvasContext.beginPath();
_canvasContext.rect(x, y, width, height);
_canvasContext.stroke();
}
function drawCircle(x, y, radius)
{
_canvasContext.fillStyle = "#000000";
_canvasContext.beginPath();
_canvasContext.arc(x, y, radius, 0, 2 * Math.PI);
_canvasContext.fill();
}
function drawLine(x1, y1, x2, y2)
{
_canvasContext.beginPath();
_canvasContext.moveTo(x1, y1);
_canvasContext.lineTo(x2, y2);
_canvasContext.stroke();
}
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width" />
<title>GeneticSharp Blazor runner app</title>
<base href="/" />
<link href="css/bootstrap/bootstrap.min.css" rel="stylesheet" />
<link href="css/site.css" rel="stylesheet" />
<script src="js/canvas-helper.js"></script>
</head>
<body>
<app>Loading...</app>
<script src="_framework/blazor.webassembly.js"></script>
</body>
</html>
Raw
Tsp.razor
@page "/tsp"
@inject IJSRuntime _js
<div class="container">
<div class="row">
<div>
Cities: <input type="text" @bind=@_numberOfCities onblur=@ResetGA disabled=@_tspGA.IsRunning />
</div>
<div>
<button onclick=@ResetGA disabled=@_tspGA.IsRunning >Reset</button>
</div>
<div>
<button onclick=@_tspGA.Run disabled=@_tspGA.IsRunning >Run</button>
</div>
<div>
<button onclick=@StopGA disabled=@(!_tspGA.IsRunning)>Stop</button>
</div>
</div>
<div class="row">
<div class="col alert alert-info">Generations: @_tspGA.GenerationsNumber</div>
<div class="col alert alert-info">Distance: @_tspGA.BestChromosome?.Distance</div>
</div>
</div>
<canvas id="canvas" style="border:1px solid #d3d3d3;">Your browser does not support the HTML5 canvas tag.</canvas>
<br>
<span class="alert alert-warn">Post <a href="http://diegogiacomelli.com.br/tsp-with-geneticsharp-and-blazor">"TSP with GeneticSharp and Blazor"</a></span>
@code {
int _numberOfCities = 10;
int _canvasWidth;
int _canvasHeight;
bool _initialized;
TspGA _tspGA = new TspGA();
async Task InitializeGAAsync()
{
// This need to be called after the first render to get
// the size of the canvas.
var size = await _js.InvokeAsync<int[]>("initializeCanvas");
_canvasWidth = size[0];
_canvasHeight = size[1];
_tspGA.GenerationRan += HandleGenerationRan;
ResetGA();
}
void HandleGenerationRan()
{
Console.WriteLine($"Generation: {_tspGA.GenerationsNumber} - Distance: {_tspGA.BestChromosome.Distance}");
StateHasChanged();
}
void ResetGA()
{
_tspGA.Initialize(_numberOfCities, _canvasWidth, _canvasHeight);
StateHasChanged();
}
void StopGA()
{
_tspGA.Stop();
StateHasChanged();
}
protected override async Task OnAfterRenderAsync()
{
if (!_initialized) {
_initialized = true;
await InitializeGAAsync();
}
await _js.InvokeAsync<object>("clearCanvas");
await DrawCitiesAsync();
await DrawRouteAsync();
}
async Task DrawCitiesAsync()
{
foreach(var city in _tspGA.Fitness.Cities)
await _js.InvokeAsync<object>("drawCircle", city.X, city.Y, 10);
}
async Task DrawRouteAsync()
{
var bestChromosome = _tspGA.BestChromosome;
if(bestChromosome != null)
{
var genes = bestChromosome.GetGenes();
var fitness = _tspGA.Fitness;
var firstCity = fitness.Cities[(int)genes[0].Value];
var previousCity = firstCity;
for(var i = 1; i < genes.Length; i++)
{
var city = fitness.Cities[(int)genes[i].Value];
await _js.InvokeAsync<object>("drawLine", previousCity.X, previousCity.Y, city.X, city.Y);
previousCity = city;
}
await _js.InvokeAsync<object>("drawLine", previousCity.X, previousCity.Y, firstCity.X, firstCity.Y);
}
}
}
Raw
TspChromosome.cs
using GeneticSharp.Domain.Chromosomes;
using GeneticSharp.Domain.Randomizations;
public class TspChromosome : ChromosomeBase
{
private readonly int _numberOfCities;
public TspChromosome(int numberOfCities) : base(numberOfCities)
{
_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, _numberOfCities));
}
public override IChromosome CreateNew()
{
return new TspChromosome(_numberOfCities);
}
public override IChromosome Clone()
{
var clone = base.Clone() as TspChromosome;
clone.Distance = Distance;
return clone;
}
}
Raw
TspCity.cs
using System;
public class TspCity
{
public TspCity(float x, float y)
{
X = x;
Y = y;
}
public float X { get; }
public float Y { get; }
public double Distance(TspCity other)
{
return Math.Sqrt(
Math.Pow(X - other.X, 2) + Math.Pow(Y - other.Y, 2)
);
}
}
Raw
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;
public class TspFitness : IFitness
{
int _areaWidth;
int _areaHeight;
public TspFitness(int numberOfCities, int areaWidth, int areaHeight)
{
Cities = new List<TspCity>(numberOfCities);
_areaWidth = areaWidth;
_areaHeight = areaHeight;
for (int i = 0; i < numberOfCities; i++)
{
Cities.Add(GetRandomCity());
}
}
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 += Cities[currentCityIndex].Distance(Cities[lastCityIndex]);
lastCityIndex = currentCityIndex;
citiesIndexes.Add(lastCityIndex);
}
distanceSum += Cities[citiesIndexes.Last()].Distance(Cities[citiesIndexes.First()]);
var fitness = 1.0 - (distanceSum / (Cities.Count * 1000.0));
((TspChromosome)chromosome).Distance = distanceSum;
// Are there 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 TspCity GetRandomCity()
{
return new TspCity(
RandomizationProvider.Current.GetFloat(0, _areaWidth),
RandomizationProvider.Current.GetFloat(0, _areaHeight));
}
}
Raw
TspGA.cs
using System;
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;
public class TspGA
{
GeneticAlgorithm _ga;
Timer _timer;
public event Action GenerationRan;
public TspFitness Fitness { get; private set; }
public TspChromosome BestChromosome => _ga != null ? _ga.BestChromosome as TspChromosome : null;
public int GenerationsNumber => _ga != null ? _ga.GenerationsNumber : 0;
public bool IsRunning => _timer != null;
public void Initialize(int numberOfCities, int areaWidth, int areaHeight)
{
Stop();
Fitness = new TspFitness(numberOfCities, areaWidth, areaHeight);
var chromosome = new TspChromosome(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);
_ga = new GeneticAlgorithm(population, Fitness, selection, crossover, mutation);
}
public void Run()
{
if (!IsRunning)
{
// As there no way to use a new thread on WebAssembly right now, we wil use a timer
// to start a new generation each 1 microsecond.
_timer = new Timer(new TimerCallback(_ =>
{
_ga.Termination = new GenerationNumberTermination(_ga.GenerationsNumber + 1);
if (_ga.GenerationsNumber > 0)
_ga.Resume();
else
_ga.Start();
GenerationRan?.Invoke();
}), null, 0, 1);
}
}
public void Stop()
{
if (IsRunning)
{
_timer.Dispose();
_timer = null;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment