Święta świętami, ale praca nad projektem musi iść do przodu! Tym razem weźmiemy się za to jak będą wyglądały obiekty, na których operuje każdy algorytm genetyczny, czyli omówimy rodzaje chromosomów w easyGALib.

Poświęciłeś już jajka, posprzątałeś dom i upiekłeś placki? Być może ktoś jeszcze woła Cię do pomocy w pracach świątecznych, więc dzisiaj taki bardzo szybki post, bo przez Święta masz odpocząć od komputera!

Chromosomy w algorytmach genetycznych

Po co chromosomy w algorytmach genetycznych? Są niczym innym jak odzwierciedleniem rozwiązania danego problemu, które może być na bieżąco modyfikowane na różne sposoby. Co więcej, chromosomy muszą nam dodatkowo umożliwiać obliczenie ich wartości przy pomocy funkcji dopasowania, a także operacje takie jak krzyżowanie czy mutacje. Jak to więc wygląda w praktyce?

Weźmy na przykład problem komiwojażera. Wędrowny sprzedawca ma odwiedzić N miast w takiej kolejności, aby sumaryczna odległość była jak najmniejsza. W takim przypadku chromosom mógłby wyglądać na przykład tak:

ABCDEFGHIJKLMNOPQRST

gdzie litery to po prostu kolejne odwiedzane miasta, a funkcja dopasowania jest liczona jako odwrotność (bo chcemy mieć minimalną, a nie maksymalną) odległości między następującymi po sobie miejscowościami, czyli:

Dopasowanie = 1 / (Odległość(A,B) + Odległość(B,C) + Odległość(C,D) + … )

Im odległość będzie mniejsza, tym dopasowanie lepsze, więc algorytm będzie przestawiał litery tak, by iść w tym kierunku. Najlepsze rozwiązanie może więc mieć końcowo następującą postać:

TBCFGHIJKLDEMNOPQASR

W tym przypadku więc chromosom reprezentowany jest przez tablicę znaków. Możemy oczywiście wymyślać inne reprezentacje, byleby spełniany warunki podane wcześniej. Najpopularniejsze formy, z którymi się spotkałem to:

  • Tablica znaków
  • Tablica stringów
  • Tablica liczb zmiennoprzecinkowych
  • Tablica liczb całkowitych

Takie też planuję na początku wykorzystać w tworzonej bibliotece.

Rodzaje chromosomów w easyGALib

Widzisz więc, że chromosomy mogą przybrać różne formy. Najważniejsze dla mnie jest jednak to, by biblioteka była na tyle uniwersalna, aby w razie potrzeby dodać też inne reprezentacje. Postanowiłem więc wprowadzić abstrakcyjną klasę bazową, na której możemy tworzyć różne rodzaje chromosomów:

public abstract class Chromosome<T> : IChromosome
    where T : IChromosome
{
    public ICollection Genes { get; set; }
}

Jak widać pod zestaw genów będziemy mogli podstawić dowolną kolekcję, zależną już od konkretnej implementacji chromosomu. Co więcej dzięki generyczności będziemy w stanie również operować na konkretnych typach bez pakowania ich do object. Przykładowa implementacja chromosomu za pomocą takiej klasy bazowej wygląda więc w ten sposób:

internal class CharChromosome : Chromosome<ICharChromosome>, ICharChromosome
{
    public CharChromosome()
    {
        Genes = new List<char>();
    }
}

Do właściwości Genes wrzucamy w tym przypadku listę znaków i śmiało możemy na niej operować.

Mam nadzieję, że udało się wyjaśnić Ci jak wygląda bardzo prosty chromosom i w jaki sposób może on reprezentować jakiś problem. Teraz wracaj już do ostatnich porządków i życzę Ci wesołych i spokojnych Świąt, a także mokrego dyngusa ( ͡° ͜ʖ ͡°)!