Języki

You are here

Adaptacyjny system klasyfikatorowy

Ogólny opis i wprowadzenie teoretyczne

Program jest demonstracją zachowania Adaptacyjnego Systemu Klasyfikatorowego (LCS – Learning Classifier System). Zadaniem przedstawianego tu systemu klasyfikatorowego jest zgadywanie koloru kwadratów na planszy. Dopasowanie do wzoru istniejącego na planszy, a więc zwiększenie precyzji odpowiedzi systemu, osiągane jest poprzez złożenie kilku prostych mechanizmów.

System składa się z listy reguł nazywanych klasyfikatorami. Po zapytaniu systemu o pole planszy niektóre klasyfikatory uaktywniają się. Ten klasyfikator, który w przeszłości był najtrafniejszy – odpowiada. Jeżeli odpowiedź jest poprawna, zostaje on nagrodzony (w ten sposób rośnie jego przydatność – siła). Klasyfikatory które odpowiadały wcześniej i pomogły bieżącemu w poprawnej odpowiedzi, także otrzymują zapłatę. W każdej turze wszystkie reguły płacą – ze swojej siły – za istnienie (co po kilku turach eliminuje reguły zupełnie nieprzydatne). Drugim mechanizmem jest algorytm ewolucyjny, który działa na podstawie sił klasyfikatorów. Zabija te najsłabsze oraz stara się powielać dobre wzorce z tych najsilniejszych krzyżując je, oraz wprowadzając dodatkowo element losowego zróżnicowania w postaci mutacji.

CFS (Classifier System) – Podstawowy system klasyfikatorowy

W ujęciu Johna Hollanda taki system składa się z:

  • środowiska
  • wejścia
  • wyjścia
  • algorytmu, który na podstawie wejścia generuje wyjście i w ten sposób działa w środowisku

Najprostszy taki system posiada wejścia, wyjścia i wiadomości przechodzące pomiędzy nimi, generowane zgodnie ze zbiorem prostych reguł. Reguły te nazywane są klasyfikatorami. Wiadomości to wyrazy zbudowane na alfabecie {0, 1} – są to ciągi binarne.

Klasyfikatory mają postać: JEŻELI Warunek-1 AND Warunek-2 AND ... AND ... Warunek-N TO akcja.
Dla uproszczenia zapisujemy: Warunek-1,Warunek-2,...,Warunek-N / akcja.

Warunki i akcje to wyrazy zbudowane na alfabecie {0, 1, #}. Mówimy, że wiadomość pasuje do części warunkowej klasyfikatora, jeżeli wszystkie zera i jedynki są na tych samych pozycjach w obu ciągach znaków. Operator # w części warunkowej klasyfikatora "pasuje" do 0 i 1. Na przykład wiadomość "00110011" pasuje do klasyfikatora "0011#0## / ####1000".

Jeżeli klasyfikator dopasuje się jakiejś wiadomości na głównej liście wiadomości, emituje on wiadomość zapisaną w jego akcji. Znak "#" jest znakiem przepisania: w pozycji, na której jest "#", w akcji będzie cyfra z tej pozycji w wiadomości. Używając przykładu z poprzedniego akapitu, zostanie wygenerowana następująca wiadomość: "00111000".


Rys. 1. Schemat podstawowego Systemu Klasyfikatorowego.

Cykl wykonania takiego CFS wygląda następująco:

  1. Aktywuj interfejsy wejściowe – wprowadź nadchodzące ze środowiska wiadomości na listę wiadomości.
  2. Sprawdź dopasowanie każdego klasyfikatora do wszystkich wiadomości.
  3. Wprowadź wiadomości wygenerowane przez akcje wszystkich dopasowanych klasyfikatorów na listę wiadomości.
  4. Aktywuj interfejsy wyjściowe. Interfejsy wyjściowe konsumują wszystkie wiadomości wyjściowe z listy wiadomości. Wróć do punktu 1.

LCS (Learning Classifier Systems) – Adaptacyjny System Klasyfikatorowy.

Jest to system CFS z mechanizmem adaptacyjnym. Możliwe są dwa sposoby adaptacji:

  • zmianę w jaki sposób używane są klasyfikatory – zmienianie ich siły (credit assignment),
  • dodawanie nowych klasyfikatorów do systemu.

Pierwszy mechanizm adaptacji

W tradycyjnym CFS wszystkie klasyfikatory dopasowane do istniejących w systemie wiadomości są aktywowane – emitują wiadomości. Aby zwiększyć efektywność CFS stosuje się priorytety, dające pierwszeństwo emisji nowych wiadomości dobrym klasyfikatorom.

Jakość klasyfikatora determinują dwa parametry:

  • Siła = użyteczność klasyfikatora w przeszłości.
  • Dokładność = (długość – liczba_#) / długość.
Oba te parametry łączone są do jednej miary – stawki, jaką klasyfikator stawia w turnieju decydującym o możliwości emisji wiadomości:
stawka = k * siła * dokładność
(k – stała ~ 0.1).

Adaptacja siły klasyfikatorów – algorytm Bucket Brigade.

  1. Jeżeli środowisko nagrodziło (lub ukarało) odpowiedź, dodaj nagrodę/karę do siły wszystkich aktywnych klasyfikatorów.
  2. Każdy aktywny klasyfikator płaci stawkę klasyfikatorom, które przygotowały dla niego odpowiednie warunki (tzn. wygenerowały wiadomości do których się on dopasował).
  3. Każdy klasyfikator w każdej turze musi zapłacić podatek od istnienia.

Drugi mechanizm adaptacji

Algorytm Genetyczny – generowanie nowych klasyfikatorów. AG wprowadza różnorodność do systemu klasyfikatorów. Jest to tradycyjny algorytm genetyczny (w podejściu Michigan – każdy klasyfikator to pojedynczy osobnik). Siła klasyfikatora to jego przystosowanie w funkcji oceniającej algorytmu genetycznego.

Opis działania programu

Program implementuje LCS z algorytmem Bucket Brigade (BB) i Algorytmem Genetycznym (GA).


Rys. 2. Główne okno programu.

Zadaniem systemu klasyfikatorowego jest nauczenie się zgadywania koloru kwadratów na planszy w zależności od współrzędnych pola. Każdy kwadrat może być czarny lub biały. Odpowiedź systemu prezentowana jest jako malutki kwadracik w środku pola, o które się pytamy (kwadracik ten może być biały, czarny lub szary – gdy system nie zna odpowiedzi ). Zapytanie systemu następuję poprzez kliknięcie na interesujące użytkownika pole prawym klawiszem myszy.

Proces odpytywania i adaptacji będzie odbywał się automatycznie po naciśnięciu przycisku "Start". Program zaczyna wtedy odpytywać LCS po kolei o kolejne pola planszy. Jeżeli system odpowie poprawnie, zostaje on nagradzany przez środowisko – w ten sposób system uczy się planszy zgodnie z regułami opisanymi powyżej.

Regulując wartości pól "Nagroda" i "Kara" określamy o ile wzrośnie siła klasyfikatora po poprawnej odpowiedzi, a o ile spadnie przy błędnej. Można zaobserwować, że system uczy się dużo sprawniej, gdy odpowiadając źle traci przynajmniej tyle, ile by zyskał odpowiadając dobrze.

Użytkownik może zmieniać zadanie systemu w trakcie działania poprzez zmianę kolorów pól – klik lewym przyciskiem myszy na wybranym polu, lub wybór gotowego wzoru na dole zakładki "Panel Kontrolny".

Obsługa programu

Po wybraniu języka interfejsu i pojawieniu się głównego okna programu (patrz zrzut ekranu wyżej), wybieramy interesujący nas wzór z rozwijalnej listy w prawym dolnym rogu. Możemy również narysować własny wzór, klikając lewym przyciskiem myszy na polach planszy. Ustawienia domyślne innych parametrów pozwalają na w miarę skuteczne działanie systemu. Klikamy przycisk "Start". Główny algorytm zaczyna działać. Odpytuje system, wysyłając zapytania o każde pole planszy po kolei, co możemy zaobserwować po zmieniających się małych kwadracikach w środku odpytywanych pól. Podczas odpytywania działają opisane powyżej algorytmy i system uczy się wzoru na planszy, z każdym krokiem zwiększając globalną dokładność odpowiedzi. Po pewnym czasie system powinien się ustabilizować i dawać za każdym razem te same odpowiedzi. Spróbujmy zmienić teraz kolor kilku pól na planszy. Zauważymy, że globalna dokładność spadnie i na planszy pojawi się kilka pól ze złymi odpowiedziami. Jednak po kilku cyklach systemu zaadaptuje się do nowego zadania i znów się ustabilizuje.

Moment ustabilizowania jest dobry, aby poeksperymentować z opcjami algorytmu genetycznego i Bucket Brigade. Zwiększając "Próg siły" w AG zmieniamy wartość siły, od której klasyfikatory zostają eliminowane. W ten sposób możemy zmniejszyć liczbę klasyfikatorów i sprawdzić, czy "szum" (słabe, nieskuteczne klasyfikatory) w dolnej części tabeli klasyfikatorów są potrzebne. Drugim sposobem na zmniejszenie liczby klasyfikatorów jest zwiększenie podatku, jaki muszą płacić. Zwiększmy podatek od istnienia i obserwujmy, jak spada ich liczba.

Ciekawą opcją algorytmu BB jest możliwość zwiększenia liczby zwycięzców każdego turnieju. System odpowiada wtedy z pewnym prawdopodobieństwem, jaki jest kolor danego pola. Jakość tej odpowiedzi podana jest w nawiasie za odpowiedzią.

Zaawansowany, techniczny opis programu

Plansza to interfejs wejściowy LCS. Odpytanie systemu o dane pole to wyemitowanie odpowiedniej wiadomości na listę wiadomości według szablonu:
10 xxx yyy

  • Pierwsze 2 bity to "kod" informacji wejściowej.
  • Bity 2–4 to numer kolumny, w której znajduje się dane pole, w zapisie binarnym.
  • Bity 5–7 to numer wiersza, w którym znajduje się dane pole, w zapisie binarnym.

Interfejs wyjściowy systemu to po prostu filtrowanie wiadomości rozpoczynających się od prefiksu "00" (jest to kod wiadomości wyjściowej). Jedynym interesującym bitem takiej wiadomości jest bit ostatni. Jeżeli ma on wartość 0 – odpowiedź systemu to "czarne", jeżeli 1 – to "białe".

Jeżeli w opcjach BB ustawiona zostanie możliwość wygranej turnieju przez więcej niż jeden klasyfikator, odpowiedzią systemu będzie uśredniona wartość ze wszystkich wiadomości wyjściowych. System wypowiada się wtedy z pewnym prawdopodobieństwem o kolorze pola.

Algorytm genetyczny:

  • Generuje z każdym cyklem jeden nowy klasyfikator o sile 1, będący efektem krzyżowania jednorodnego pomiędzy dwoma najsilniejszymi klasyfikatorami.
  • Posiada opcjonalny elitaryzm – dany procent najsilniejszych klasyfikatorów jest bezpośrednio kopiowany do nowej populacji.
  • Zabija wszystkie klasyfikatory o sile poniżej pewniej, ustawione przez użytkownika wartości.
  • Mutuje pewien procent osobników (zmieniając jeden bit).
Program i tekst: Jakub Misiorny
Ulepszenia: Jędrzej Potoniec
Opiekun: Maciej Komosiński