Bazowe krzyżowanie i extension method

Mamy już za sobą teorię, jeżeli chodzi o krzyżowanie w algorytmach genetycznych, więc pora na świeżą porcję informacji jak zostało to zaimplementowane w easyGALib. Dzisiaj na pulpicie mamy bazowe krzyżowanie i extension method, w ramach rozszerzania wiedzy!

Dlaczego bazowe krzyżowanie? Ano bo mówimy na razie o tej części, która została zrealizowana w klasie bazowej i jest wspólna, niezależnie od tego na jakich chromosomach będziemy działać. Dla przypomnienia, idąc po kolei po bloczkach tworzących serce algorytmu genetycznego, ostatnio implementowaliśmy selekcję osobników. Skończyliśmy na tym, że mamy listę chromosomów, które będą tworzyć nową generację. Teraz pora na modyfikację osobników, które się na niej znajdują, abyśmy mogli w kolejnych pokoleniach widzieć jakąkolwiek zmianę. Z ostatniego posta wiesz, że umożliwi nam to operacja krzyżowania, a później mutacji. Kod tej pierwszej prezentuje się następująco:

private void Crossover()
{
    Random rdm = new Random();

    NextGeneration.Shuffle();

    int length = NextGeneration.Count;
    if (length % 2 == 1)
    {
        length--;
    }

    for (int i = 0; i < length; i += 2)
    {
        var parentA = NextGeneration[i];
        var parentB = NextGeneration[i + 1];

        if (rdm.Next(0, 100) < _input.Parameters.CrossoverChance)
        {
            switch (_input.Parameters.CrossoverType)
            {
                case Types.CrossoverType.OnePt:
                    parentA.OnePtCrossover(parentB);
                    break;
                case Types.CrossoverType.TwoPt:
                    parentA.TwoPtCrossover(parentB);
                    break;
                case Types.CrossoverType.Uniform:
                    parentA.UniformCrossover(parentB);
                    break;
                default:
                    break;
            }
        }
    }
}

Być może pierwsza Twoja myśl jest teraz taka: „Panie, przydałaby się refaktoryzacja, bo za dużo zagnieżdżeń”. Odpowiem – będzie później, bo w takiej formie lepiej wyjaśnić co tu się odbywa.

Na początku mamy więc listę chromosomów, które tworzą nową generację. Ostatnio dodaliśmy do niej najlepszy chromosom, a dalej odpowiednią metodą selekcji wybieraliśmy kolejne. W jakiś sposób są one losowo poukładane, ale pomyślałem, że dobrze będzie nieco jeszcze potasować naszą listę, stąd na początku to tajemnicze NextGeneration.Shuffle(). „Ale przecież lista nie ma domyślnie takiej metody…”. No nie ma, ale możemy ją dodać, i omówię to w dalszej części posta.

Idąc dalej, chcemy przechodzić po potasowanej liście parami, więc liczymy jej długość do ostatniego parzystego indeksu. W pętli for zaczynamy całą zabawę – przechodzimy po kolei po parach i jeżeli tak się zdarzy, że wylosowana liczba będzie mniejsza od zadeklarowanej szansy na wystąpienie krzyżowania, to uruchamiamy działanie na naszych rodzicach. Pojawił się więc kolejny parametr, którym możemy sterować losowość w działaniu biblioteki. Dalej w instrukcji switch decydujemy jakiego typu krzyżowanie chcemy uruchomić i wywołujemy odpowiednią metodę chromosomu. Jej implementacja będzie zależna od rodzaju osobnika, na którym działamy, jednak zawsze operacja krzyżowania będzie zastępować rodzica A i B, przekazanego jako parametr, dwoma nowymi, które w niej powstaną.

Zauważyłeś jakąś nieścisłość? Na liście był najlepszy chromosom, a teraz jest szansa, że został zmiksowany z jakimś innym. To w sumie dobrze, bo w jakiś sposób wpłynie na populację, jednak dla pewności w głównym algorytmie, w każdej generacji, będziemy usuwać ostatni chromosom i zastępować go najlepszym z ostatniego pokolenia.

Extension methods

Tak jak widziałeś wcześniej, na liście chromosomów z danej generacji użyłem metody Shuffle(). Jak to możliwe, skoro przecież lista generyczna nie ma takiej metody? W .NET 3.5 pojawił się mechanizm extension methods, który nam to umożliwia. Dzięki niemu jesteśmy w stanie dodać nowe funkcjonalności do już istniejących, skompilowanych klas. W naszym przypadku metoda rozszerzająca wygląda następująco:

public static void Shuffle<T>(this IList<T> list)
{
    int length = list.Count;
    while (length > 1)
    {
        length--;
        int k = rng.Next(length + 1);
        T value = list[length];
        list[k] = list[length];
        list[length] = value;
    }
}

Jedyne co ją wyróżnia wśród tłumu innych metod, to słowo kluczowe this przed pierwszym parametrem. Dzięki niemu kompilator wykrywa, że mamy do czynienia z metodą rozszerzającą i traktuje jej wywołanie jak użycie klasycznej metody statycznej. Dla środowiska uruchomieniowego to żadna różnica, a dla nas znacznie czytelniejszy kod, więc zdecydowanie warto używać!

Mamy więc za sobą implementację bazowego algorytmu krzyżowania, a w jednym z kolejnych postów zajmiemy się szczegółami zależnymi od konkretnego chromosomu. Pisząc kod warto pamiętać też o różnych udogodnieniach, takich jak metody rozszerzające,  o których więcej możesz poczytać tutaj i tutaj (radzę zmienić język na oryginalny!).