Moduł AI::Genetic

Uniwersytet Gdański - Instytut Matematyki - Zakład Informatyki - Strona domowa

Spis treści

Nazwa
Jak używać
Opis
Możliwe zastosowania AG
Metody
Funkcja Fitness
Strategie
Szybkość/sprawność algorytmu
Błędy
Instalacja
Autor modułu
Autor opisu
Prawa autorskie

⇑ Nazwa

AI::Genetic - Perlowa implementacja algorytmu genetycznego.

⇑ Jak używać

use AI::Genetic;
    my $ga = new AI::Genetic(
        -fitness    => \&fitnessFunc,
        -type       => 'bitvector',
        -population => 500,
        -crossover  => 0.9,
        -mutation   => 0.01,
        -terminate  => \&terminateFunc,
       );

     $ga->init(10);
     $ga->evolve('rouletteTwoPoint', 100);
     print "Best score = ", $ga->getFittest->score, ".\n";

     sub fitnessFunc {
         my $genes = shift;

         my $fitness;
         # assign a number to $fitness based on the @$genes
         # ...
     
         return $fitness;
      }

      sub terminateFunc {
         my $ga = shift;

         # terminate if reached some threshold.
         return 1 if $ga->getFittest->score > $THRESHOLD;
         return 0;
      }

Poniżej jest przykład wpełni działającego kody. Pogrubiona część to finkcja sprawdzająca przystosowanie osobnika, czyli inaczej mówiąc jakość rozwiązania. Ta finkcja jest bardzo prosta. Sprawdza geny osobnika (będące dziesięcioma bitami) i rozwiązanie uznaje za tym lepsze, im wyższą liczbę reprezentują geny (liczba w układzie dwujkowym).

use Test;
BEGIN { plan tests => 1 };
use AI::Genetic;

my $ga = new AI::Genetic(
  -fitness    => \&fitnessFunc,
  -type       => 'bitvector',
  -population => 150,
  -crossover  => 0.9,
  -mutation   => 0.01,
  -terminate  => \&terminateFunc,
);

$ga->init(10);
$ga->evolve('rouletteTwoPoint', 100);
print "Najlepszy wynik = ", $ga->getFittest->score, ".\n";
print "Najlepsze geny = ", $ga->getFittest->genes, ".\n";


sub fitnessFunc {
  my $pi=3.14159265;
  my $genes = shift;
  my $r=0;  

  foreach(@$genes){
    $r=$r+2*$_;
  }
  print $r." "."@$genes"."\n";
  my $fitness=$r;

  return $fitness;
}


sub terminateFunc {
  my $ga = shift;

  return 1 if $ga->getFittest->score > $THRESHOLD;
  return 0;
}

Przedstawiony przykład jest banalny i na dobrą sprawę można go rozwiązać, bez użycia Algorytmów Genetycznych. Aby dowiedzieć się ciekawszych rzeczy na temat możliwości AG zobacz Możliwe zastosowania AG

⇑ Opis

Ten moduł implementuje Algorytm Genetyczny (Genetic Algorithm). Tem moduł nie jest jedynym możliwym perlowym modułem implementującym AG. Na CPANie znajdują się inne (być może lepsze, być może gorsze), które realizują podobne zadania.

Uwaga: Począwszy od wersji 0.02 AI::Genetic został zmieniony, aby miał bardziej modularną budowę i był łatwiejszy do rozbudowy. Aby to osiągnąć zmodyfikowane zostało API, tak że nie jest już kompatybilne z wesją 0.01. Z tego powodu wersja 0.01 nie będzie dalej rozwijana.

Poniżej opisane są podstawowe zagadnienia związane z AG. Na sieci można znaleźć wiele informacji o tym algorytmie, więc nie ma potrzeby opisywania ich tutaj szczegółowo.

W AG populacja osobników współzawodniczy o przetrwanie. Każdy z osobników jest określony zestawem genów określającym jego zachowanie. Najlepiej przystosowane osobniki (to przystosowanie okesla funkcja fittness) mają największą szansę połączenia się w pary. Jeśli dwa osobniki połączą się w parę, to mieszają swoje geny tworząc dzieci. Przy tworzeniu nowych osobników (dzieci) może zachodzić mutacja, czyli niespodziewane i losowe zmiany w genach, co z kolei wprowadza nowe geny do populacji. Jeśli wszystko jest odpowiednio zdefiniowane, to po kilku (kilkudziesięciu) pokoleniach powinniśmy dostać "odpowiednio dobre", choć pewnie nie najlepsze, z możliwych rozwiązań problemu.

To co dzieje się podczas każdego pokolenia zależy od przyjętej strategi (zobacz "Strategie" aby dowiedzieć się więcej). Zazwyczaj podczas każdego z pokoleń zachodzą następujące czynności:

Selekcja
Obliczana jest jakość każdego osobnika (rozwiązania) i wybierane są osobniki do stworzenia kolejnego pokolenia.
Crossover
Tu następuje mieszanie się genów sparowanych osobników w celu tworzenia nowych osobników wstawianych do obecnego pokolenia.
Mutacja
W tym kroku każdy osobnik ma szansę zmutowania obliczaną na podstawie "prawdopodobieństwa mutacji". Jeśli osobnik ma zmutować, to każdy z jego genów ma szansę aby zmienić swoją wartość.

⇑Możliwe zastosowania AG

Algorytmy genetyczne to świat pełen cudów. Zabawa nimi może nie raz przypominać zabawę w Boga, mamy bowiem w rękach narzędzie, dzięki któremu kreujemy wirtualne byty, a co więcej kierujemy ich rozwojem. Podczas pracy z AG można naprawdę nabawić się megalomanii :)

Oto przykład istniejącego (choć trochę akademickiego) zastosowania AG. Jest on niestety zbyt rozbudowany, aby przedstawić go szczegółowo w tym opisie:

Założenia: Poprawić kompresję JPEG dostosowując, do każdego z kompresowanych obrazów, zestaw tablic kwantyzacji. Tablice kwantyzacji, używane podczas kompresji i dekompresji, odpowiedzialne są za jakość obrazu i za możliwość jego kompresji. Grupa JPEG podarowała użytkownikom zestaw tablic, które stworzyła za pomocą wielu doświadczeń na różnych obrazach, jadnak pomysł polega na dobraniu jak najlepszych tablic do konkretnego obrazu, a nie stosowaniu tablic oryginalnych. W dalsze szczegóły techniczne nie będe się zagłębiał, bo temat jest bardzo rozbudowany. Należy tylko wspomnieć, że tablice (po dwia na każdy obraz) mają wymiary 8x8 i 255 możliwych wartości w każdej z komórek, co daje ok 1,089e+308 możliwych kombinacji... a jak widać daje to DUŻO kombinacji do sprawdzenia. Jako, że tylko nabawiliśmy się kompleksu Boga, a Nim tak naprawdę nie jesteśmy, to nie mamy całej wieczności aby oczekiwać na wynik. Dlatego zastosujemy algorytmy genetyczne.

Jako funkcji fitness będziemy używać funkcji porównującej dwie pary obrazów: obraz oryginalny i skompresowany tablicamy JPEG oraz obraz oryginalny i skompresowany naszymi tablicami. W tan sposób dowiemy się czy nasz obraz jest lepszy, czy gorszy od obrazu JPEG. Dla zaciekawionych tym tematem polecam zabawę w znalezienie szybkiej i sprawnej funkcji porównującej dwa obrazy. Jest to nie lada wyzwanie :)

I to właściwie wszystko. Implementacja w JAVA zajęła mi 4 miesiące i kolejne 5 miesięcy na testy i poprawę programu. Po 2 godzinach działania programu mogę poprawić kompresję obrazu (400x300 pixeli) o średnio 17%-18%. Czy w perlu można uzyskać lepsze wyniki? Sprawdzenie tego polecam jako rozrywkę na długie zimowe wieczory.

⇑ Metody

$ga->new(opcje)

konstruktor, który akceptuje następujące opcje z tablic hash:

Opcje:

population
określa ilość osobników w każdym pokoleniu. Domyślnie jest to 100 osobników.
crossover
Definiuje wartość crossover. Domyślnie jest to 0.95
mutation
Definiuje wartość mutacji. Domyślnie jest to 0.05
fittness
Definiuje funkcję fittness. Oczekuje referencji do funkcji. Więcej detali można znaleźć w "Funkcja Fittness"

type

Określa typ genomu. Aktualnie, AI::Genetic wspiera trzy następujące typy:

bitvector
Genami są bity, czyli każdy z genów może być liczbą 0 lub 1.
listvector
Kazdy z genów może być jednym ze stringów określonych w liście możliwych wartości.
rangevector
Kazdy z genów może być wartością integer (wartość jest ograniczona oczywiście typem integer). Jeśli chcemy aby program za geny wziął inne liczby niż całkowite, to musimy je przekształcić do typu integer (np mnorząc przez 10).

Domyślnie wybierany jest bitvector.

terminate

Definniuje funkcę uruchamianą na koniec każdego pokolenia. Oczekuje referencji do funkcji. Funkcja zostanie wywołana z jednym argumentem: obiektem AI::Genetic.

$ga->createStrategy(strategy_name, sub_ref)

Ta metoda pozwala na stworzenie nowej strategii używanej podczas ewolucji. Wymaga unikalnej nazwy i referencji do funkcji jako argumentu. Fynkcja będzie wywoływana z jednym argumentem: obiektem AI::Genetic.

$ga->init(initArgs)

Ta metoda inicjalizuje populację losowymi osobnikami. MUSI być wywołana przed metodami evolve() i inject(). Dodatkowym efektem działania tej funkcji jest usunięcie istniejących już osobników populacji. Oczekuje jednego argumentu bazującego na typie osobników:

bitvectors
po prostu ilość genów.
$ga->init(10); to inicjalizuje populację osobników o 10 bitowych genach.
listvectors
jest to aninimowa lista list. Liczba podlist odpowiada liczbie genów osobnika. Każda podlista zawiera możliwe wartości stringów dla danego genu.
$ga->init([ [qw/red blue green/], [qw/big medium small/], [qw/very_fat fat fit thin very_thin/], ]); inicjalizuje populację osobników o trzech genach, gdzie każdy z genów ma jedną z możliwych wartości.
rangevectors
jest to aninimow lista list. Liczba poslist odpowiada liczbie genów osobnika. Każda podlista definiuje minimum i maximum wartości jakie dany gen może osiągnąć.
$ga->init([ [1, 5], [0, 20], [4, 9], ]); inicjalizuje populację osobników o trzech genach, gdzie każdy z genów ma jedną z możliwych wartości z podanego prfzedziału.

$ga->inject(N, ?args?)

Ta metoda dodaje kolejne osobniki do populacji. Nowe osobniki mogą być stworzone losowo lub być odgórnie zdefiniowane. Pierwszy argument określa listę osobników do dodania. Drugi argument to lista tych osobników (jest to lista list genów każdego z osobników). Jeśli lista zawiera mniej niż N osobników, to pozostałe są tworzone losowo, z użyciem tych samych wartości co w funcji init(). Przykład:

$ga->inject(5,
              [qw/red big thin/],
              [qw/blue small fat/],
             );

dodaje pięć osobników, w tym 2 są zdefiniowane, a trzy dodane losowo.

$ga->evolve(strategy, ?num_generations?)

Ta metoda każe stworzyć nowe pokolenie używając odpowiedniej strategii, którwej nazwa jest określona w pierwszym argumencie. Drugi argument jest opcjonalny i określa liczbę pokoleń do stworzenia. Domyślnie jest to 1 pokolenie. Zobacz "STRATEGIE" aby dowiedzieć się więcej.

Każde pokolenie wymaga następujących kroków:

Populacja jest sortowana wg wartości fitness
Funcja o podanej nazwie wymaga podania argumentu - obiektu AI::Genetic. Ta funkca sama w sobie ma zmieniać ten obiekt.
Jeśli zakończenie finkcji jest dane, to zwracana wartość jest sprawdzana. Ewolucja kończy się gdy zwrócona wartość to true

$ga->getFittest(?N?)

Zwraca N najlepszych osobników. Domyślnie jest to 1. Efektem ubocznym jest sortowanie populacji względem wartości fitness. Zwracane są aktualne obiekty typu AI::Genetic::Individual. Można użyć metod genes() i score() aby otrzymać geny i wartość fitness osobnika. Zobacz AI::Genetic::Individual aby dowiedzieć się więcej.

$ga->sortPopulation

Sortuje populację względem wartości fitness.

$ga->sortIndividuals(?[ListOfIndividuals]?)

Pobiera listę osobników a następnie zwracą ją posortowaną.

$ga->people()

Zwraca anonimową listę osobników aktualnego pokolenia.

$ga->size(?newSize?)

Służy do ustalenia wielkości populacji.

$ga->inject(N, ?args?)

Służy do ustalenia wartości crossover. Domyślnie jest to 0.95

$ga->mutProb(?newProb?)

Służy do ustalenia wartości mutacji. Domyślnie jest to 0.05

$ga->indType()

Zwraca typ osobnika.

$ga->generation()

Zwraca aktualne pokolenie.

⇑ FUNKCJA FITNESS

Poprawne zdefiniowanie funkcji fitness jest bardzo istotne. Musi być szybka i skutecznie sprawdzać jakość rozwiązania. AI::Genetic prubuje minimalizować potrzebny czas caschując rezultaty dla konkretnych osobników, ale nie zawsze działa to sprawnie. Należy więc polegać na poprawnym stworzeniu funkcji fitness.

Funkcja powinna pobierać tylko listę genów osobnika, a następnie obliczać i zwracać watrość określającą jakość osobnika.

⇑ Strategie

AI::Genetic ma 9 predefiniowanych strategii. Oto one:

rouletteSinglePoint
Ta strategia implementuje selekcję ruletkową i jedno punktowy crossover.
rouletteTwoPoint
Ta strategia implementuje selekcję ruletkową i dwu punktowy crossover.
rouletteUniform
Ta strategia implementuje selekcję ruletkową i crossover typu "uniform".
tournamentSinglePoint
Ta strategia implementuje selekcję turniejową i jedno punktowy crossover.
tournamentTwoPoint
Ta strategia implementuje selekcję turniejową i dwu punktowy crossover.
tournamentUniform
Ta strategia implementuje selekcję turniejową i crossover typu "uniform".
randomSinglePoint
Ta strategia implementuje selekcję losowa i jedno punktowy crossover.
randomTwoPoint
Ta strategia implementuje selekcję losowa i dwu punktowy crossover.
randomUniform
Ta strategia implementuje selekcję losowa i crossover typu "uniform".

Więcej informacji na temat tech strategii (oraz tworzenia nowych) można znaleźć w AI::Genetic::OpSelection, AI::Genetic::OpCrossover i AI::Genetic::OpMutation.

⇑ Szybkość/sprawniść algorytmu

GA są zasadniczo wolne. Dodatkowo kod perla, nawet pomimo optymalizacji, nigdy nie osiągnie sprawności np. zoptymalizowanego kodu C. Powyższy algorytm ciągle jest rozwijany i udoskonalany aby działał coraz sprawniej.

Aby to osiągnąć zaimplementowałem kilka popularnych trików (przekazywanie referencji do list zamiast samych list) i cachowanie wyników.

Należy zwrócić szczególną uwagę na budowę funkcji fitness, która może mieć ogromne znaczenia dla szybkości działania programu. Nawet najmniejsza oszczędność w tym miejscu może znacznie skrócić czas działania programu.

⇑ Błędy

Zasadniczo podczas testów nie znaleziono żadnych błędów, ale jeśli takie się pojawią to proszę poinformować autora.

⇑ Instalacja

Zwyczajowe:

perl Makefile.PL
make
make install

lub po prostu wklej gdzieś do @INC aby perl to znalazł. Moduł jest napisany w czystym perlu więc nie będzie w tym miejscu problemów.

⇑ Autor modułu

Ala Qumsieh (aqumsieh@cpan.org.)

⇑ Autor opisu

Łukasz Łoza

⇑ Prawa autorskie

Ta biblioteka jest objęta prawami wolnego oprogramowania i może być udostępniana i modyfikowana pod takimi samymi warunkami jak sam Perl.