Nadszedł dzień sądu! Dzisiaj czas na pierwsze uruchomienie easyGALib! Bierzemy się zatem za opracowanie problemu i jego rozwiązania przy pomocy algorytmu genetycznego.
Tak jak zapowiedziałem w ostatnim poście, mamy już wszystkie metody potrzebne do uruchomienia algorytmu działającego na liczbach całkowitych. Możemy więc teraz wymyślić jakiś problem, który da się rozwiązać przy ich pomocy i zaimplementować jego rozwiązanie za pomocą easyGALib. Pierwszym pomysłem, który przyszedł mi do głowy, jest rozwiązanie problemu komiwojażera, który dosyć często jest używany przy okazji różnych zadań na studiach.
Problem komiwojażera
Jak mówi ciocia Wikipedia, jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym. Mówiąc po polsku, pewien wędrowny sprzedawca ma wyznaczone N miast, które musi odwiedzić, każde tylko raz. Na GPSie może sprawdzić sobie odległość pomiędzy poszczególnymi miejscówkami, ale urządzenie jest tak ograniczone, że nie pokazuje optymalnej trasy. Naszym zadaniem jest wyznaczyć mu kolejność odwiedzania miast, aby cała droga była jak najkrótsza. No to do roboty!
Implementacja rozwiązania problemu w easyGALib
Do solucji dodałem projekt aplikacji konsolowej, którą przetestujemy działanie biblioteki. W celu problemu, po pierwsze musimy zaimplementować interfejs IGeneticAlgorithmInput, który ma być danymi wejściowymi algorytmu. Jak pewnie pamiętasz, znajdziemy w nim funkcję dopasowania podaną przez użytkownika, a także wszystkie parametry wejściowe. W przypadku problemu komiwojażera implementacja wygląda następująco:
class Salesman : IGeneticAlgorithmInput
{
public IGAParameters Parameters { get; set; }
public double GetFitness(IChromosome chromosome)
{
var cities = new int[4, 4] { {0, 130, 180, 300 },
{130, 0, 320, 350 },
{ 180, 320, 0, 360},
{ 300, 350, 360, 0} };
var genes = chromosome.Genes as List<int>;
//Cities can't repeat
if (genes.Distinct().Count() != Parameters.GenesQuantity)
{
return 0;
}
//Genes should be in <0,3>
if (genes.Count(g => g < 0 || g > 3) > 0)
{
return 0;
}
var distance = 0;
for (int i = 1; i < 4; i++)
{
distance += cities[genes[i], genes[i - 1]];
}
if (distance == 0)
{
return 0;
}
return 1 / distance;
}
public Salesman()
{
Parameters = new Parameters()
{
ChromosomesQuantity = 200,
CromosomeType = easyGALib.Types.ChromosomeType.IntChromosome,
CrossoverChance = 80,
CrossoverType = easyGALib.Types.CrossoverType.TwoPt,
GenerationsLimit = 5000,
GenesQuantity = 4,
MutationChance = 5,
RandomSelectionChance = 6
};
}
}
Mamy tutaj dwie rzeczy, na które należy zwrócić uwagę. Pierwszą z nich jest funkcja GetFitness, czyli obliczająca dopasowanie danego chromosomu. Jak powinniśmy to robić w przypadku problemu komiwojażera? Najpierw musimy wprowadzić dwuwymiarową tablicę odległości pomiędzy poszczególnymi miastami. Dalej rzutujemy sobie geny naszego chromosomu na odpowiedni typ – tutaj będzie to lista int’ów, no i zaczynamy badać dopasowanie.
- Wybieramy reprezentację rozwiązania problemu, za pomocą chromosomu. W naszym przypadku jego geny, to lista liczb całkowitych, więc każdy z nich będzie reprezentował numer miasta. Tym sposobem, każdy chromosom będzie rozwiązaniem problemu w postaci kolejnych numerów do odwiedzenia, np. [0, 3, 2, 1].
- Wiemy, że miasta nie mogą się powtarzać, więc jeżeli liczba unikalnych numerów w chromosomie jest mniejsza od liczby jego genów, od razu zwracamy 0. Tym sposobem algorytm wie, że takie rozwiązanie nas nie satysfakcjonuje.
- Analogicznie postępujemy w przypadku, gdy liczby wychodzą poza zakres <0,3>. W naszym przykładzie mamy tylko 4 miasta, więc indeksy nie mogą wychodzić poza ten przedział.
- Obliczamy sumaryczny dystans pomiędzy kolejnymi miastami.
- Zwracamy odwrotność dystansu, jako wartość dopasowania. Dlaczego tak? Dlatego, że sumaryczną odległość chcemy minimalizować. Gdybyśmy zwracali bezpośrednio dystans, algorytm zwróciłby nam kolejność miast, dla których droga będzie jak najdłuższa.
Czy tym sposobem napisaliśmy jakiś bardzo skomplikowany algorytm na rozwiązanie problemu? No nie, podaliśmy tylko sposób na obliczenie wartości danego chromosomu.
Drugim elementem, na który należy zwrócić uwagę w powyższym kodzie, jest konstruktor, gdzie podajemy parametry, według których ma działać nasz algorytm, czyli na przykład wielkość populacji, rodzaj krzyżowania i szansę na wystąpienie różnych operacji genetycznych. Za pomocą podanych wartości będziemy w stanie sterować działaniem całego algorytmu. Dla przykładu wielkość populacji i ilość genów znacząco będą wpływać na czas działania, ale z drugiej strony mogą dać lepszy wynik. Podane powyżej wartości są póki co wpisane „z czapy”, ale do testów powinny być OK.
Pierwsze uruchomienie easyGALib
Mamy już gotową implementację problemu, pozostało jedynie wywołanie algorytmy w aplikacji konsolowej. Możemy to zrobić w następujący sposób:
static void Main(string[] args)
{
var salesmanProblem = new Salesman();
var ga = new GAMain(salesmanProblem);
var result = ga.Execute();
Console.WriteLine("Best chromosome: " + string.Join(", ", result.BestChromosome.Genes as List<int>));
Console.WriteLine("Fitness: " + result.BestChromosome.Fitness.ToString());
Console.WriteLine("Distance: " + (1 / result.BestChromosome.Fitness).ToString());
Console.ReadKey();
}
Wielkiej filozofii tutaj nie ma. Budujemy obiekt danych wejściowych algorytmu, instancję GAMain i wywołujemy na niej metodę Execute. Następnie w konsoli wypisujemy wszystko co wiemy o najlepszym chromosomie, który wyszedł z algorytmu.
No to co, czas na końcowe odliczanie:
5… 4… 3… 2… 1… F5!
NullReferenceException… No tak, zapomniałem zainicjować listy odpowiedzialnej za przechowywanie obecnej i kolejnej generacji. No to jeszcze raz!
5… 4… 3… 2… 1… F5!
NonImplementedException… Znowu coś?! W sumie prawda, zapomniałem dopisać metodę kopiowania chromosomu. Ale teraz to już się uda!
5… 4… 3… 2… 1… F5!
Victoria! Ale chwila… zaraz… czekaj, czekaj… dlaczego same zera wszędzie? Co się stało? No jeszcze chyba czegoś nam zabrakło 🙂 Jesteś ciekawy o co chodzi? Wszystko będzie jak w dobrym serialu – dowiesz się w następnym odcinku!
Dodaj komentarz