easyGALib działa, więc czas popracować trochę nad jego ulepszeniem. W ostatnim poście widziałeś, że nie zawsze otrzymany wynik jest najlepszy, lub w ogóle poprawny. Musieliśmy zawężać zakres początkowych liczb, aby móc go uzyskać. Czas więc popracować jeszcze nad tematem, którym dzisiaj jest inicjalizacja populacji.

Jak pewnie pamiętasz, w tym poście pisałem już o inicjalizacji populacji chromosomów. Ograniczyłem się wtedy do opisania sposobu generowania początkowych wartości genów dla liczb całkowitych. Wystarczyło to, aby przy odpowiednich warunkach otrzymać prawidłowy wynik dla problemu wędrownego sprzedawcy. Musieliśmy jednak wtedy interweniować i zmieniać zakres generowanych liczb. Lepiej jednak unikać takich sytuacji, więc jeszcze raz zajmiemy się tematem inicjalizacji populacji i jej ulepszenia.

Lepsza inicjalizacja populacji

Co więc możemy zrobić, aby zwiększyć szansę, że w startowej populacji chromosomów, będzie więcej osobników, które doprowadzą do powstania optymalnego rozwiązania danego problemu? W przypadku gdy uruchamialiśmy ostatnio algorytm, albo się udało trafić na jakiś osobnik, który wyewoluował i otrzymaliśmy wynik, albo wcale taki nie wystąpił i działanie zakończyło się porażką. Może więc odpowiednią drogą będzie kilkukrotna inicjalizacja populacji i wybranie za każdym razem najlepszych genów, które później wezmą udział w operacjach genetycznych.

W celu realizacji tego zadania proponuję więc następujący kod w metodzie PopulationInit:

private void PopulationInit()
{
    for (int i = 0; i < _input.Parameters.InitRunsQuantity; i++)
    {
        ChildrenInit();

        CalculateFitness();

        InitChromosomes.AddRange(CurrentGeneration.Skip(Math.Max(0, CurrentGeneration.Count() - _input.Parameters.BestChromosomesPerRun)));
    }
            
    CurrentGeneration.RemoveRange(0, _input.Parameters.BestChromosomesPerRun * _input.Parameters.InitRunsQuantity);
    CurrentGeneration.AddRange(InitChromosomes);
}

W powyższym kodzie dodałem 2 dodatkowe parametry do biblioteki, a mianowicie:

  • InitRunsQuantity – odpowiada za liczbę testowych inicjalizacji populacji
  • BestChromosomesPerRun – liczba najlepszych chromosomów wybieranych z każdej testowej inicjalizacji

Tym razem nie inicjalizujemy więc populacji tylko raz, a tyle, ile wskaże użytkownik biblioteki. Za każdym razem tworzymy nowy zestaw osobników i liczymy jego dopasowanie do rozwiązania. Następnie wybieramy N najlepszych chromosomów z danej populacji i na końcu działania metody dodajemy je wszystkie do generacji, która rozpocznie właściwe działanie algorytmu.

Wpływ na wynik problemu podróżnika

Czy takie ulepszenie pozwoliło na rozwiązanie problemu podróżnika dla wartości początkowej genów losowanej od 0 do 1000? No niestety nie. Mimo, że inicjalizując kilka razy znacznie zwiększamy szansę na wystąpienie prawidłowej sekwencji, to niestety w przypadku tego konkretnego problemu, nadal jest ona za mała. To co może w tym przypadku pomóc, to:

  • ograniczenie początkowych wartości do mniejszego zakresu, np.  <0,10>.
  • inny zapis problemu w chromosomie. Można by na przykład stworzyć chromosom, który będzie sekwencją znaków z pewnej określonej puli.

Morał z tego jest jeden – trzeba mieć podstawową wiedzę jak coś działa pod spodem, aby wiedzieć dlaczego nie działa 🙂 Jak widać problemy dotyczące sekwencji liczb rozwiążemy algorytmem genetycznym tylko wtedy, gdy działamy na odpowiednim zakresie. No chyba, że akurat będziemy mieć dużo szczęścia. Chromosom składający się z liczb całkowitych zdecydowanie lepiej sprawdzi się w problemach, gdzie każda z liczb będzie składnikiem jakiegoś działania matematycznego, przez co każda jej zmiana będzie miała widoczny wpływ na wartość dopasowania. Algorytm będzie wtedy wiedział w którą stronę ma podążać.

Tym sposobem zakończyliśmy temat problemu wędrownego sprzedawcy. Na jego przykładzie przekonaliśmy się o tym, że reprezentację problemu w postaci chromosomu trzeba dobrać odpowiednio, aby algorytm miał szansę na znalezienie rozwiązania.