Była już teoria, była metoda bazowa, to teraz czas sprawdzić jak wygląda krzyżowanie i mutacja chromosomu w szczegółowej implementacji. Dzisiaj zajmiemy się kodem stojącym za tymi operacjami dla chromosomu składającego się z liczb całkowitych.
W ostatnim tygodniu udało mi się opublikować tylko jeden post ze względu na dodatkowe projekty robione „po godzinach” i wyjazd „zagramaniczny”, więc w tym tygodniu na pewno zobaczysz 3 posty, żeby nieco nadrobić! Wydawało się, że 10 tygodni pisania bloga w ramach #dajsiepoznac to kupa czasu, a tymczasem zostało jeszcze tylko 2 tygodnie i 4 posty 🙂 Mam zamiar uruchomić jeszcze przed jego końcem easyGALib chociażby dla jednego rodzaju chromosomu, więc jedziemy z tematem!
Bazowa metoda mutacji
Ostatnio przedstawiłem Ci implementację bazowej metody krzyżowania, a zabrakło tej odpowiedzialnej za mutację. W gruncie rzeczy nie jest ona zbyt skomplikowana, więc szkoda było na nią poświęcać osobny post:
private void Mutate()
{
Random rdm = new Random();
foreach (IChromosome item in NextGeneration)
{
if (_input.Parameters.MutationChance > rdm.Next(0, 100))
{
item.Mutate();
}
}
}
Jak widać przechodzimy tutaj tylko po wszystkich elementach listy NextGeneration i jeżeli losowa liczba będzie mniejsza niż szansa na mutację, wtedy uruchamiamy abstrakcyjną metodę Mutate, którą posiada każdym chromosom za pośrednictwem interfejsu IChromosome. Mamy więc kolejny parametr, którym będziemy mogli sterować działanie algorytmu. Kolejny temat, którym powinniśmy się zająć, to szczegółowa implementacja krzyżowania i mutacji dla poszczególnych rodzajów chromosomów. Póki co zajmiemy się tylko metodami dla osobników składających się z liczb całkowitych.
Krzyżowanie IntChromosome
Jak pewnie pamiętasz, zdecydowaliśmy się na trzy dostępne rodzaje krzyżowania: jedno i dwu-punktowe, a także jednorodne. Przejdźmy zatem po kolei po każdym z nich:
- Krzyżowanie jednopunktowe
public override void OnePtCrossover(IChromosome parentB)
{
int crossoverPt = _rdm.Next(0, Genes.Count-1);
for (int i = crossoverPt; i < Genes.Count; i++)
{
swapGene(i, this, parentB);
}
}
private void swapGene(int i, IChromosome chromA, IChromosome chromB)
{
var temp = chromA.Genes[i];
chromA.Genes[i] = chromB.Genes[i];
chromB.Genes[i] = temp;
}
Mamy tutaj do czynienia z bardzo prostym kodem. W pierwszej kolejności losujemy punkt krzyżowania, a następnie od tego miejsca zamieniamy geny między rodzicami. W ten sposób powstaną dwa nowe chromosomy z odwrotnym krzyżowaniem.
- Krzyżowanie dwupunktowe
public override void TwoPtCrossover(IChromosome parentB)
{
int crossoverPtA = _rdm.Next(0, Genes.Count - 1);
int crossoverPtB = _rdm.Next(0, Genes.Count - 1);
if (crossoverPtA != crossoverPtB)
{
for (int i = crossoverPtA; i < crossoverPtB; i++)
{
swapGene(i, this, parentB);
}
}
}
W krzyżowaniu dwupunktowym postępujemy bardzo podobnie, jednak z tą różnicą, że losujemy dwa punkty i zamieniamy wszystko co jest pomiędzy nimi.
- Krzyżowanie jednorodne
public override void UniformCrossover(IChromosome parentB)
{
for (int i = 0; i < Genes.Count; i++)
{
if (_rdm.Next(0,1) == 1)
{
swapGene(i, this, parentB);
}
}
}
Krzyżowanie jednorodne jest już nieco inne. Tutaj przechodzimy po wszystkich genach i dla każdego rzucamy monetą. Jeżeli wypadnie orzeł, zamieniamy geny. Tym sposobem uzyskamy dwa chromosomy z genami pochodzącymi losowo od rodzica A i B.
Wszystko fajnie tylko nasuwa tu się jedno pytanie – po co to w szczegółowej implementacji dla liczb całkowitych, skoro metody są uniwersalne? No właśnie teraz to wyszło w praniu, ale zostawię to w tym miejscu, bo nie wiem czy operacje na innych typach nie wymuszą innej implementacji 🙂
Mutacja IntChromosome
Teraz pora na coś, co faktycznie przyczyni się do zmian w populacji chromosomów, czyli mutacje. Na chłopski rozum, jeżeli operujemy na liczbach całkowitych, to mutacja będzie polegała na jakiejś zmianie tych liczb. Kod może więc wyglądać następująco:
public override void Mutate()
{
int index = _rdm.Next(0, Genes.Count - 1);
int gene = (int)Genes[index];
int diff = gene * _rdm.Next(1, 1000) / 1000;
if (_rdm.Next(0, 1) == 1)
{
Genes[index] = gene + diff;
}
else
{
Genes[index] = gene - diff;
}
}
Na początku losujemy indeks genu, który będziemy modyfikować i wyciągamy jego wartość. Następnie mnożymy ją przez losową liczbę od 0,001 do 1, aby uzyskać różnicę między obecną wartością a nową. Dlaczego akurat tak? Dlatego żeby zachować jakiś rząd wielkości względem wartości, na której obecnie działamy. Dla przykładu, jeżeli gen ma wartość 1000, to co najwyżej różnica będzie wynosiła 1000, analogicznie wartość 30, to maksymalna różnica 30. Dalej już tylko losujemy, czy zostanie ona dodana, czy też odjęta od obecnej wartości genu, bo nie w każdym problemie większa wartość tej liczby będzie oznaczała lepszy chromosom.
Tym sposobem uzyskaliśmy szczegółową implementację jednego z rodzaju chromosomów. Widać, że krzyżowania i mutacja nie są skomplikowanymi operacjami, jednak zapewnią nam zmiany w populacjach. W następnych postach będziemy zabierać się za wypełnienie pomniejszych metod, aby móc uruchomić algorytm, gdyż mamy już wszystkie podstawowe implementacje!
Dodaj komentarz