Skip to content

Instantly share code, notes, and snippets.

@giacomelli
Last active May 31, 2019 00:31
Show Gist options
  • Save giacomelli/94721a46d33c6bcb1f3ae11117b7f888 to your computer and use it in GitHub Desktop.
Save giacomelli/94721a46d33c6bcb1f3ae11117b7f888 to your computer and use it in GitHub Desktop.
using UnityEngine;
public class TspCity
{
public Vector2 Position { get; set; }
}
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;
}
}
public Object CityPrefab;
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;
}
}
...
DrawCities();
m_gaThread = new Thread(() => m_ga.Start());
m_gaThread.Start();
private LineRenderer m_lr;
private void Awake()
{
m_lr = GetComponent<LineRenderer>();
m_lr.positionCount = m_numberOfCities + 1;
}
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);
}
}
private void Update()
{
DrawRoute();
}
go.GetComponent<CityController>().Data = city;
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();
}
}
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;
}
}
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment