|
|
|
You are hereAdaptacyjny system klasyfikatorowyOgólny opis i wprowadzenie teoretyczneProgram 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 klasyfikatorowyW ujęciu Johna Hollanda taki system składa się z:
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ć:
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".
Cykl wykonania takiego CFS wygląda następująco:
LCS (Learning Classifier Systems) – Adaptacyjny System Klasyfikatorowy.Jest to system CFS z mechanizmem adaptacyjnym. Możliwe są dwa sposoby adaptacji:
Pierwszy mechanizm adaptacjiW 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:
stawka = k * siła * dokładność (k – stała ~ 0.1). Adaptacja siły klasyfikatorów – algorytm Bucket Brigade.
Drugi mechanizm adaptacjiAlgorytm 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 programuProgram 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 programuPo 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 programuPlansza to interfejs wejściowy LCS. Odpytanie systemu o dane pole to wyemitowanie odpowiedniej wiadomości na listę wiadomości według szablonu:
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:
|
