Pewnie zastanawiasz się o co chodzi z tymi puzzlami w miniaturce? A o to, że dzisiaj uzupełniamy ostatnie metody potrzebne do działania biblioteki! To czym się zajmiemy teraz, to inicjalizacja populacji i obliczenie dopasowania.
Wreszcie udało się dotrzeć do tego momentu, gdzie skończy się pewien etap prac nad biblioteką. Zakończymy implementację kodu odpowiedzialnego za działanie biblioteki na liczbach całkowitych! Tym samym, będziemy mogli już przejść do pierwszego testu easyGALib. Zanim to jednak nastąpi, bloczki naszego algorytmu musimy uzupełnić o dwa zagadnienia, czyli inicjalizacja populacji i obliczanie dopasowania.
Inicjalizacja populacji
Jak powszechnie wiadomo, wszystko ma swój początek i koniec i nie inaczej jest w przypadku algorytmów genetycznych. Żeby w ogóle rozpocząć jego działanie, musimy stworzyć tę pierwszą generację, takiego Adama i Ewę wśród pokoleń chromosomów, od których wszystko się zacznie. Jest to o tyle istotne zadanie, że decyduje o tym, jak dobre będzie końcowe rozwiązanie i czy w ogóle do niego dotrzemy. Tutaj też objawia się jednocześnie wada i zaleta algorytmów genetycznych – każde ich uruchomienie to inna generacja startowa, a co za tym idzie, inny wynik.
Jak więc inicjalizacja została rozwiązana w easyGALib? W bazowej metodzie obsługującej działanie algorytmu korzystamy z następującej funkcji:
private void PopulationInit()
{
ChildrenInit();
}
Odpowiada ona póki co tylko za wywołanie metody abstrakcyjnej, której implementacje znajdziemy w klasie dziedziczącej. Dlaczego tak? Po pierwsze jest możliwość, że kiedyś w tej metodzie jeszcze będziemy chcieli dorzucić jakieś wstępne obiegi algorytmu. Po drugie, wywołanie metody abstrakcyjnej jest w tej sytuacji wymagane, gdyż inaczej będziemy inicjować gen składający się z liczb całkowitych, a inaczej ze stringów. Póki co przygotowujemy bibliotekę pod inty, więc dla nich implementacja wygląda następująco:
public override void ChildrenInit()
{
for (int i = 0; i < _input.Parameters.ChromosomesQuantity; i++)
{
var chromosome = new IntChromosome();
for (int j = 0; j < _input.Parameters.GenesQuantity; j++)
{
Random rdm = new Random();
int val = rdm.Next(0, 1000) / rdm.Next(1, 1000);
if (rdm.Next(0, 1) == 1)
{
val = -val;
}
chromosome.Genes.Add(val);
}
CurrentGeneration.Add(chromosome);
}
}
W powyższym kodzie wykorzystujemy dwie pętle. Pierwsza z nich, zależna od liczebności populacji, dodaje odpowiednią ilość chromosomów. Druga natomiast, kontrolowana przez ilość genów w chromosomie, inicjalizuje każdy z nich. W praktyce po prostu losujemy liczbę z przedziału 0 do 1000, a następnie decydujemy czy ma być ona dodania, czy ujemna i dodajemy ją do listy genów. Podobnie będziemy postępować w przypadku innych rodzajów chromosomów, jednak oczywiście operację mogą nieco się różnić.
Obliczanie dopasowania
Kolejnym brakującym elementem układanki jest obliczanie dopasowania. Wiemy już, że to użytkownik dostarcza za pomocą interfejsu końcową metodę, którą wskaże algorytmowi wartość danego chromosomu. To co należy zrobić w bibliotece, to w odpowiedni sposób ją wykorzystać:
private void CalculateFitness()
{
foreach (var chromosome in CurrentGeneration)
{
chromosome.Fitness = _input.GetFitness(chromosome);
}
CurrentGeneration = CurrentGeneration.OrderBy(g => g.Fitness).ToList();
for (int i = 0; i < CurrentGeneration.Count; i++)
{
CurrentGeneration[i].FitnessRank = i;
}
BestChromosome = CurrentGeneration.Last();
}
Jak widać w powyższym kodzie, metodę dostarczaną przez użytkownika uruchamiamy dla każdego chromosomu w obecnej generacji i zapisujemy jego dopasowanie. Następnie sortujemy listę według zwróconej wartości. Kolejnym krokiem jest przypisanie każdemu chromosomowi miejsca w rankingu od 0 dla najgorszego, do N dla najlepszego. Ostatniego wyróżniamy oczywiście podstawiając go pod właściwość BestChromosome.
Coś tu się nie zgadza, prawda? Mówiłem o metodzie ruletki, a tu nagle ranking. Zdecydowałem się na zmianę, bo jednak końcowo ta metoda wydaje mi się lepsza do implementacji. W związku z tym nastąpiła mała zmiana w funkcji wybierającej chromosomy do kolejnego pokolenia, przez co obecnie wygląda ona tak:
private IChromosome FindChromosome()
{
Random rdm = new Random();
bool found = false;
int index = -1;
while (!found)
{
index = rdm.Next(0, _input.Parameters.ChromosomesQuantity - 1);
//We should give some random selection chance by parameter
if (_input.Parameters.RandomSelectionChance > rdm.Next(0, 100))
{
found = true;
}
else if (CurrentGeneration[index].FitnessRank > rdm.Next(0, _input.Parameters.ChromosomesQuantity)) //Better chromosome = bigger chance to go to the next generation
{
found = true;
}
}
return CurrentGeneration[index];
}
Jedyna zmiana, to większa szansa na wylosowanie chromosomu, który zajmuje wyższe miejsce w rankingu. Wcześniej miało to działać na zasadzie większy procent, większa szansa. Procenty każdy lubi, jednak tutaj postanowiłem z nich zrezygnować 🙂
Podsumowując, mamy już wszystkie potrzebne klocki do uruchomienia algorytmu dla liczb całkowitych. Bardzo chętnie napisałbym już teraz przykładowe rozwiązanie problemu za pomocą easyGALib, jednak tę przyjemność zostawię na kolejny post!
Dodaj komentarz