Rozdział 7
Zastosowania genetycznych systemów uczących się

W poprzednim rozdziale omówiliśmy strukturę, zasady funkcjonowania oraz konkretną implementację pewnego typu genetycznych systemów uczących się - systemu klasyfikującego. Systemy klasyfikujące zostały tam przedstawione jakofaits accomplis, jako systemy tak pewne, jakby je uformowano z betonu. Co gorsza, nacisk, jaki położyliśmy na systemy klasyfikujące, mógł sprawić wrażenie, że są one jedynym rodzajem genetycznych systemów uczących się. W tym rozdziale odpokutujemy za grzech zaniedbania, którego się dopuściliśmy poprzednio, studiując korzenie, wczesną historię i aktualny stan systemów GBML. Omawiamy wczesne propozycje dotyczące samoreprodukujących się programów, procesorów schematów i systemów rozgłaszania. Przedstawiamy System Kognitywny 1 (CS-1) i zadania pokonywania labiryntu, których uczył się ten system. Dokonujemy przeglądu innych wczesnych systemów GBML i omawiamy kilka aktualnych teorii oraz zastosowań rozważanych technik.
7.1. PoczątkisystemówGBML
Na przełom lat czterdziestych i pięćdziesiątych przypadły natchnione czasy bujnego rozwoju teorii i praktycznych zastosowań komputerów. Intensywna - może nawet w większym stopniu niż dziś - współpraca teoretyków i praktyków przyczyniła się do skokowego postępu w sztuce obliczeniowej. W tym samym czasie inspiracje zaczerpnięte z analogii i koncepcji biologicznych osiągnęły swoje historyczne maksimum (w sensie względnym, nie zaś absolutnym), o czym świadczy ówczesna popularność cybernetyki, stopień aktywności w badaniach nad sieciami neuronowymi, wreszcie zainteresowanie automatami komórkowymi i programowymi odpowiednikami samoreprodukcji. Na tym tle pewna liczba badaczy rozpoczyna studia dotyczące związków między ewolucją
278
7, Zastosowania genetycznych systemów uczących się
naturalną a sztuczną adaptacją (Bledsoe, 1961; Bremermann, 1962; Friedman, 1959; Holland, 1962c; von Neumann, 1966). Kreśląc zarysy teorii systemów adaptacyjnych, Holland (1962c) czerpał natchnienie z naturalnych przykładów biologicznych. W swojej wizji przewidywał on gromady programów błąkających się w komórkowej przestrzeni obliczeniowej, zderzających się ze sobą i niekiedy łączących się w większe jednostki (Holland,1962c,str.306-307): , -^
Procedura swobodnej generacji [...] wymaga, aby generatory (i ich kombinacje) "przemieszczały się" i "łączyły" losowo w komputerze. Z najprostszą formą losowego przemieszczenia mamy do czynienia, gdy są spełnione następujące warunki: (1) dowolny generator w każdej chwili ma określone prawdopodobieństwo przemieszczenia się do jednego z sąsiadujących modułów; (2)jesli generator próbuje się przemieścić do modułu zajętego już przez inny generator, to taki ruchjest zabroniony [...]. Jeśli spełnione są warunki [...], to dwa lub więcej generatorów zajmujących sąsiednie moduły ("kontaktujące się") mogą się połączyć. Takie połączone zespoły generatorów będą się przemieszczać jako całość.
Wizja ta pozostawała w związku z jego wcześniejszym pomysłem tzw. iterative circuit computer (Holland, 1959, 1960) - "drobnoziarnistej", jednorodnej architektury przetwarzania współbieżnego, z adresacją względną opartą na procesie budowania ścieżek; gromady wałęsających się programów mogłyby być z łatwością zrealizowane na takich maszynach Hollanda.
7.1.1. Schematy i ich procesory
Choć tak intelektualnie pociągający pomysł programów zderzających się w komputerze komórkowym, niczym elastyczne plastikowe kule bilardowe, daleki był od realizacji w postaci jakiegokolwiek działającego systemu adaptacyjnego, jak wkrótce zdał sobie z tego sprawę sam jego twórca. Pragnąc uzyskać eksperymentalne potwierdzenie swoich koncepcji, Holland zwrócił uwagę na jedno ze szczególnie udanych ówczesnych przedsięwzięć w zakresie maszynowego uczenia się, jakim był program grający w warcaby Samuela (1957). Koncepcja Samuela niesprzecznego przewidywania [consistentpredic-tion] miała wskazać drogę ku rozwojowi algorytmów przyznawania ocen w późniejszych systemach GBML; wysiłki te nie spowodowały jednak wstrzymania poszukiwań teoretycznych podstaw adaptacji reprodukcyjnej. Oba kierunki badań skrystalizowały się w dwóch pracach, które wywarły głęboki wpływ na rozwój wszystkich późniejszych badań na polu systemów GBML. Pierwsza z tych prac, Hierarchical Descriptions, Uni-versal Spaces, andAdaptive Systems (Holland, 1968, 1970a), była poświęcona opisowi złożonych maszyn, zbudowanych z ograniczonej liczby ustalonych elementów oraz znaczeniu schematów, czy też wzorców strukturalnych w takich maszynach. Druga, węższa tematycznie (choć z punktu widzenia przyszłości systemów GBML bardziej interesująca) praca, Processing and Processorsfor Schemata (Holland, 1971), opisywała pierwsze konkretne propozycje uogólnionego systemu GBML. Holland zaproponował w niej skonstruowanie tzw. procesorów schematów [schemata processors], co miałoby nastąpić
7.1. Początki systemów GBML .
279
w czterech etapach. Złożoność prototypów wzrasta począwszy od prototypu I, będącego prostym urządzeniem działającym na zasadzie bodziec-reakcja, a skończywszy na prototypie IV, przedstawiającym złożony automat o wielu stanach wewnętrznych i zdolnych do modyfikacji detektorach i efektorach. Projekt ten, jak się później okazało, stał się punktem wyjścia dła pierwszego systemu klasyfikującego. "Ewolucyjna" metoda projektowania serii coraz bardziej złożonych sztucznych stworzeń, którą zastosował Holland, nie była czymś wyjątkowym na tle ówczesnej biologicznie ukierunkowanej literatury z dziedziny sztucznej inteligencji (patrz Braitenberg, 1984).
7.1.2. Język przekazu
Choć procesory schematów nigdy nie ujrzały światła dziennego na ekranie monitora, prace nad algorytmami genetycznymi i systemami GBML posuwały się. Jak wspomnieliśmy w rozdziale czwartym, na przełomie lat sześćdziesiątych i siedemdziesiątych nastąpiły ważne wydarzenia na polu zastosowań aigorytmów genetycznych w zadaniach optymalizacji i poszukiwania oraz ich podbudowy teoretycznej (Bagley, 1967; Cavic-chio, 1970; De Jong, 1975; Frantz, 1971; Hollstien, 1971;Rosenberg, 1967). Interesujący kierunek rozwoju badań w zakresie systemów GBML został wskazany w ósmym, często zapoznawanym rozdziale pracy Adaptation in Natural and Artificial Systems (ANAS) Hollanda (1975). W rozdziale tym Holland przedstawia projekt tzw. języka przekazu [broadcast language}, będącego odmianą systemu produkcji Posta (Minsky, 1967; Post, 1943) opartą na lO-elementowym alfabecie. Zaproponował on reguły zjednym lub dwoma poprzednikami (warunkami) i jednym następnikiem (akcją), które nazwał jednostkami przekazu [broadcast units]. Reguły i komunikaty, w postaci podzbioru słów języka przekazu, miały współistnieć w obrębie systemu wyposażonego w mechanizm równoległego sterowania wykonywaniem reguł. Chociaż do tej pory nikt nie dokonał implementacji języka przekazu, sam pomysł ma istotne znaczenie, gdyż wskazuje jeden z możliwych sposobów uogólnienia koncepcji procesorów schematów w kierunku uniwersalności obliczeniowej nie wychodzący jednak poza ramy umożliwiające stosowanie operacji genetycznych.
Aby lepiej zrozumieć koncepcję języka przekazu, przyjrzyjmy się bliżej jego alfabetowi i metodzie tworzenia jednostek przekazu z jego symboli. Alfabet składa się z następujących 10 symboli: ; -f ,
A = {0,l,*,:,0,V,Y,A,p,'} '^'" ""*'
Symbole 0 i 1 są tu podstawowymi symbolami do zapisywania sygnałów. Gwiazdka * (nie mylić z symbolem uniwersalnym używanym w poprzednich rozdziałach) pełni funkcję ogranicznikajednostek przekazu; wszystkie symbole znajdujące się między parą gwiazdek są interpretowanejakojednostka przekazu. Dwukropek (:) służy do oddzielania warunków i akcji wewnątrz jednostki przekazu. Istnieją cztery typy jednostek przekazu:
1) * 2)
*:/,:/2
Jeżeli pewien komunikat pasuje do /,, to wyślij komunikat /2. Jeżeli żaden komunikat nie pasuje do /" to wyślij komunikat /2.
280
7. Zastosowania genetycznych systemów uczących się
3) */,::/2 Jeżeli pewien komunikat pasuje do /,, to usuń trwały fo>ersistent] element
postaci /2.
4) *7,:/2:/3 Jeżeli pewien komunikat pasuje do /, i pewien komunikat pasuje do /2, to
wyślij komunikat /3.
Podciągi /,, /2, /3 są słowami utworzonymi z dowolnych symboli alfabetu, przy czym pozostałe symbole interpretuje się następująco:
0 Symbol uniwersalny pasujący do dowolnego pojedynczego symbolu (a na pozycji końcowej do dowolnego podciągu symboli)
V Symbol uniwersalny pasujący do dowolnego przedrostka lub końcówki (na innych pozycjach ignorowany) o własności przenoszenia fy>ass through] podciągów1'
T "Zapasowy" symbol V; umożliwia łączenie dwóch przenoszonych podciągów
A Symbol uniwersalny pasujący do dowolnego pojedynczego symbolu, o własności przenoszenia
p Komunikat poprzedzony symbolem p pozostaje na trwałe w systemie, póki nie zostanie usunięty przez jednostkę przekazu typu 3
' Symbol poprzedzony znakiem ' zostaje zinterpretowany literalnie.
Podobnie jak procesory schematów (a następnie systemy klasyfikujące), język przekazu został zaprojektowany z myślą o łatwym rozpoznawaniu wzorców podobieństwa. Hol-land przedstawił siedem przykładów zastosowania jednostek przekazu, obejmujących m. in. tak standardowe elementy maszyn liczących jak liczniki i sumatory, a także należące do specyficznie genetycznej problematyki operacje reprodukcji i krzyżowania. Zarysowane zostały możliwości zastosowania języka przekazu na tak rozmaitych polach, jak:
1) operonowy model regulacji genetycznej;
2) model limfocytowego układu odpornościowego;
3) modelcentralnegoukładunerwowego; ;,:v*
4) symulacja mechanizmu rozpoznawania wzorców;
5) modele falowych (elektromagnetycznych i dźwiękowych) systemów przekazu.
Być może pewnego dnia w świecie genetycznych technik obliczeniowych pojawi się praktyczny system o elastyczności języka przekazu Hollanda. Do tego czasu osiągnięcie jedności przetwarzającego i przetwarzanego pozostaje celem godnym naszych wysiłków (Holland, 1987b).
" Na przykład jednostka przekazu *JlV:V w obecności komunikatu 11010 wysyła komunikat 010 Qirzyp. ttum.).
7.2. Pierwszy system klasyfikujący CS-1
281
7.2. Pierwszy system klasyfikujący CS-1
Projekty procesorów schematów i języka przekazu przy jednoczesnym wykrystalizowaniu się podstawowych elementów teorii algorytmów genetycznych zaowocowały w krótkim czasie (trzy lata po publikacji ANAS) opracowaniem pierwszego systemu klasyfikującego. Opis tego systemu, który otrzymał miano "System Kognitywny 1" (CS-1), został opublikowany przez Hollanda i Reitmana (1978). Jego schemat ideowy jest przedstawiony na rys. 7.1. System został wyposażony w układ wykonawczy oparty na regułach (klasyfikatorach) o prostej składni, interwałowy algorytm oceniający oraz algorytm genetyczny. W ogólnych zarysach, CS-1 ma wiele wspólnego z generycznym systemem klasyfikującym, który był omówiony w rozdziale szóstym. Skupimy się tu na paru istotniejszych różnicach dotyczących struktury reguł i mechanizmów składania ofert oraz przyznawania ocen. Opiszemy także środowisko CS-1 i jego zachowanie w zadaniach pokonywania labiryntu.
Pamięć
Środowisko
' Ostatnia akcja (1111)'
\
Biezaoaakcja\(0111)
Rys. 7.1. SchematpierwszegosystemuklasyfikującegoCS-1 (HollandiReitman, 1978).Przedrukza zezwoleniem
Na rysunku 7.1 rozpoznajemy ogólną strukturę przypominającą w zarysie system klasyfikujący z rozdziału szóstego. W pamięci systemu znajduje się zbiór klasyfikatorów. Warunki klasyfikatorów (zwane tu taksonami) są zbudowane z symboli trójele-mentowego alfabetu {0, 1, #}, przy czym 0 i 1 są symbolami podstawowymi, a # - symbolem uniwersalnym. W systemie CS-1 warunki składają się z segmentów; poszczególne
282
7. Zastosowania genetycznych systemów uczących się
segmenty reagują na komunikaty zewnętrzne, ostatnio wykonaną akcje oraz komunikaty wewnętrzne z odrębnej listy. Jest to nieco odmienne rozwiązanie niż w generycznym systemie klasyfikującym, w którym cała wymiana informacji odbywa się za pośrednictwem listy komunikatów. Metoda wskazana w opisie generycznym ma być może bardziej jednolity charakter.
Z opisu generycznego pamiętamy również, że klasyfikatory oczekują na wypłaty, a wypłaty podlegają dystrybucji za pomocą algorytmu bucket brigade. W systemie CS-1 proces ten przebiega nieco inaczej. Przede wszystkim, system posiada odrębne rezerwuary zasobów odpowiadajacychjegopo?rze&wn; na przykładowym schemacie widzimy dwa rodzaje zasobów: żywność (głód) i wodę (pragnienie). Zapasy tych zasobów maleją jednostajnie w czasie i muszą być uzupełniane. Aktualny stan zapasów służy do określenia aktualnych potrzeb, a poziom potrzeb jest uwzględniany w procesie decyzyjnym dotyczącym uaktywniania reguł. Ponadto, CS-1 nie posługuje się algorytmem bucket brigade. Zamiast tego używany jest algorytm interwalowy [epochal algorithm]. Przez interwat rozumie się tu okres czasu upływający między dwiema kolejnymi wypłatami; aby uwzględnić historię wykorzystania poszczególnych reguł i ich trafności trzeba prowadzić rozbudowaną ewidencję. Informacje te są następnie używane do modyfikacji parametrów decyzyjnych reguły. Aby zrozumieć jak się to odbywa, przyjrzyjmy się parametrom i sposobowi ich wykorzystania.
Podstawowymi parametrami decyzyjnymi klasyfikatora w CS-1 są przewidywane wysokości wypłat u dotyczące każdego zasobu istotnego dla systemu (w naszym przykładzie - żywności i wody). Aby wybrać regułę lub reguły do uaktywnienia w danym cyklu, system CS-1 bierze pod uwagę przewidywane wysokości wypłat w, klasyfikatora oraz bieżące potrzeby systemu d, (wartość djest tym większa, im niższy poziom zasobu w rezerwuarze), w celu obliczenia wskaźnika odpowiedniości [appropriateness] oc dla każdego klasyfikatora zgodnie ze wzorem
gdzie sumowanie jest rozciągnięte na wszystkie zasoby i. Zwycięzca zostaje wyłoniony losowo, za pomocą mechanizmu ruletki o sektorach proporcjonalnych do iloczynu wskaźnika odpowiedniości a i wskaźnika zgodności M (będącego miarą szczegółowości reguły). W miarę rozwoju procesu uzgadniania i uaktywniania reguł, interwałowy algorytm oceniający śledzi trafność przewidywań klasyfikatorów, posługując się trzema parametrami zwanymi wiekiem, częstością i tlumieniem. Wiek klasyfikatora zwiększa się o 1 wraz z każdym cyklem obliczeniowym; jeśli jednak klasyfikator zdobywa nagrodę (na zakończenie interwału), jego wiek zostaje zredukowany o wielkość, która rośnie wraz ze wzrostem użyteczności reguły. Ten "algorytm Ponce'a de Leon"" przedłuża żywot użytecznej reguły, ponieważ klasyfikatory ulegają losowej wymianie, z prawdopo-dobieństwemzależnymodwieku.
" Juan Ponce de Leon, hiszpański konkwistador i odkrywca towarzyszący Kolumbowi w jego drugiej wyprawie, znany z poszukiwania ,,zdroju wiecznej młodości" fyrzyp. tlum.).
7.2. Pierwszy system klasyfikujący CS-1
283
0)
'c
OJ
'E
,3
Błąd e
Rys. 7.2. Czynnik tłumienia jako malejąca funkcja błędu w systemie CS-1 (Holland, ok. 1976). Adaptacja za zezwoleniem ,,. :
Częstość jest parametrem, który zwiększa się przy każdym uaktywnieniu reguły. Używa się jej przy określaniu wag klasyfikatorów w celu uprzywilejowania często używanych reguł. Tłumienie jest parametrem o wartościach między 0 a 1; jego wartość początkowa wynosi 1. Za każdym razem, gdy okazuje się, że dana reguła przewidziała wypłatę wyższą niż następna, parametr ten zostaje zmniejszony. Funkcja tłumienia, widoczna na rys. 7.2 określa czynnik zależny od wielkości błędu, służący do skorygowania wartości parametru. Kiedy ostatecznie system otrzymuje wypłatę, zostaje ona rozdzielona między klasyfikatory stosownie do ich tłumienia i częstości. Ten sam mechanizm działa w następnych interwałach (okresach między kolejnymi wypłatami), dzięki czemu przewidywane wypłaty zbliżają się coraz bardziej do rzeczywistych. itfr.
7.2.1. System CS-1 w działaniu
System CS-1 został zaprogramowany w Fortranie na maszynie IBM 1800 należącej do Uniwersytetu Michigan. W implementacji przyjęto następujące ograniczenia i uproszczenia: ����� �:�-,,.;.-.; ;�> ,--''pv' �. -' . .,
1. 25 pozycji na warunek, w tym 8 bitów na środowisko, 1 bit na ostatnią akcję oraz 16 bitównakomunikatywewnętrzne. >
2. Jeden efektor o dwóch stanach (akcjach), 0 i 1. ;: ;:
3. Dwa rezerwuary zasobów.
4. Ośmiobitowenazwywęzłów labiryntu. i
5. lOOklasyfikatorow,po50nakazdaakcje. (
Systemowi temu postawiono dwa zadania pokonywania labiryntu, zobrazowane schematycznie na rys. 7.3. Na rysunku 7.3a widzimy labirynt z siedmioma węzłami, przy czym przy jego lewym wyjściu znajduje się 18 jednostek żywności, a przy prawym - 36 jednostek wody. Na rysunku 7.3b ten sam labirynt został rozbudowany o sześć dodatkowych węzłów, po trzy z każdej strony.
284
7. Zastosowania genetycznych systemów uczących się
StanV
~ o o o o
b)
*Start.
2) 3) (4) (5 (6K7J8 19) (10) 11 (I
o o o o o o
_ - - o o o o -
o o o o o o o o o o
o o o o o o o o o o o
o o o o o o o o o
OJ
o - 2
Rys. 7.3. (a) Schemat labiryntu z siedmioma węzłami (test wstępny); (b) Schemat labiryntu z 13 węzłami (test przenoszenia wiedzy). Holland i Reitman, 1978. Przedruk za zezwoleniem
Wyniki uzyskane przez system CS-1 dla obu zadań zostały przedstawione graficznie odpowiednio na rys. 7.4 i 7.5. Na rysunku 7.4 porównano trzy warianty: błądzenie przypadkowe, system CS-1 bez algorytmu genetycznego i z algorytmem genetycznym. Wariant z algorytmem genetycznym okazał się lepszy niż bez algorytmu genetycznego, a obydwa warianty CS-1 wypadły lepiej niż błądzenie przypadkowe. Z uwagi na dwa razy niższą nagrodę żywnościową (18 jednostek żywności w porównaniu do 36 jednostek wody) powinniśmy oczekiwać, że system będzie poszukiwał żywności dwa razy częściej niż wody. Takie zachowanie było rzeczywiście obserwowane w prowadzonych eksperymentach.
W przypadku drugiego zadania, którego celem było badanie przekazywania wiedzy, widoczne są różnice między wynikami uzyskanymi przez system w wariantach "surowym" (reguły wygenerowane losowo) i "wytrenowanym" (po wstępnych ćwiczeniach w pokonywaniu prostszej wersji labiryntu). Wiedza zdobyta w pierwszym zestawie eksperymentów przenosi się istotnie na zadanie o większym stopniu trudności, o czym świadczy natychmiastowa zbieżność do niemal optymalnego zachowania, widoczna na wykresie.
Od czasu zaprojektowania systemu CS-1 Holland kontynuował teoretyczne i eksperymentalne badania systemów klasyfikujących (Holland, 1980a,b, 1981, 1983a,b, 1984, 1985a,b, 1986a,b, 1987a,b; Holland i Burks, 1985; Holland, Holyoak, Nisbett
7.2. Pierwszy system klasyfikujący CS-1
285
^5 > q
c L Algorytm losowy
~ 8 -
c
-o 7
"�,
s c ^ t
.* 6 ^ \ ^v bez AG
* 5 o a - \ Y-o-x/\ o /S>--< x-o~
0) \/\ ^ / x i
~ \ v B
vL V_ z AG Minimum
ó i i i i i i i i t i i i i i
20 40 60 80 100 120 140 160 Odcinki po 10 interwafów
Rys. 7.4. SprawnośćsystemuCS-1 wtesciewstepnym(labiryntzsiedmiomaweztemi)zuzyciemibez użycia algorytmu genetycznego (Holland i Reitman, 1978). Przedruk za zezwoleniem
i Thagard, 1986). W pracach tych zaleca się stosowanie algorytmu bucketbrigade przypominającego ten, który opisaliśmy w poprzednim rozdziale. Podobniejak algorytm interwa-łowy, dostarcza on estymatora przewidywanej wypłaty; majednak tę przewagę, że wymaga mniejszego nakładu czynności rejestracyjnych oraz czysto lokalnych obliczeń.
24 - n Algorytm losowy =36
i
22 _ i
i
"S i
| 20 - i i
0> i
.= 18 i i
n> i
c t
S 16 i
�0 i
e 14 i
x. '^ o Surowy
N ł2 \ Q ' / \
1 ' \
i 10 L >w 8 - \ / \ - V/ V\ � Wytrenowany v�"�--o
6 ' i i i i i i i ,� ( . .Mipimum=6
0 20 40 60 80 100 (20 140 160 ;.-,
Odcinki po 10 interwałów
Rys. 7.5. Porównanie wyników dla wersji ,,surowej" i ,,wytrenowanej" systemu CS-1 w teście przenoszenia wiedzy (labirynt z 13 węzłami). Holland i Reitman, 1978. Przedruk za zezwoleniem
286
7. Zastosowania genetycznych systemów uczących się
7.3. Program pokerowy Smitha
System CS-1 zrodził wielu następców. Jednym z pierwszych był program LS-1 opracowany przez S.F. Smitha (Smith, 1980, 1983, 1984). Chociaż LS-1 przetwarzał reguły za pomocą operacji genetycznych, nie byłjednak klonem CS-1. Architektura LS-1 różniła się zasadniczo od architektury CS-1 pod względem postaci reguł, sposobu funkcjonowania i operacji genetycznych. Punkt ten poświęcimy omówieniu tych różnic oraz wyników osiąganych przez LS-ł w grze w pokera.
Najważniejsze różnice między CS-1 a LS-1 zostały zilustrowane w postaci schematycznego diagramu na rys. 7.6. Z rysunku 7.6a przedstawiającego architekturę typu CS-1 widzimy, że podstawowymi obiektami podlegającymi genetycznym manipulacjom są tu indywidualne reguły; w cyklu obliczeniowym algorytm przyznawania ocen określa wartość poszczególnych reguł, a w cyklu reprodukcyjnym reguły kojarzą się i krzyżują ze sobą w sposób pokazany na rysunku. Natomiast architektura typu LS-1, przedstawiona na rys. 7.6b, kieruje naszą uwagę o poziom wyżej: przedmiotem oceny i manipulacji genetycznych są tym razem całe zestawy reguł. W ten sposób zestawy reguł podlegają ocenie grupowej po przeprowadzeniu pewnej ustalonej liczby rozgrywek. Następnie zestawy reguł kojarzą się, krzyżują, ulegają mutacjom lub innym modyfikacjom genetycznym w celu wytworzenia potencjalnie lepszych wariantów, które zostaną poddane ocenie w przyszłych rozgrywkach.
b)
System Hollanda
Populacja
REGUŁA r
reguła 2
REGUŁA 3,
TiEGUŁA
Przykład krzyżowania
System typu CS
System LS-1
Populacja Przykład krzyżowania

(gJJRS?3�5) (R9iR3iR4) (R9^J12) (jjliR2iRlg)
(^Zestaw reguł 1: R1:R2:R3:R4^>

(^""Zestaw regul2: R11:R22^"^>


(^Zestaw regut3: R1 0:R22:R13^)

r^"^Zestaw regut4: R9:R12~~"~^)

I
System typu LS
Rys. 7.6. Porównanie architektury systemów typu (a) CS i (b) LS. W systemach typu CS przedmiotem manipulacji genetycznych sąindywidualne reguty.Wsystemach typu LS sąnim całe zestawy reguł
7.3. Program pokerowy Smitha .
287
Te różnice poziomów działania mają charakter zasadniczy. Przenosząc operacje genetyczne o jeden szczebel wyżej, Smith jest w stanie (prawie) zupełnie uniknąć potrzeby oceny zasług poszczególnych reguł. Od kiedy cały zestaw reguł solidarnie utrzymuje się lub upada, pojedynczy miernik całkowicie wystarcza do kontynuacji obliczeń; nie potrzeba wysilać się w celu określenia indywidualnego wkładu reguł w łączny efekt. Z drugiej jednak strony, rezygnacja z przyznawania ocen jest też największą wadą tej metody. Ponieważ sprzężenie zwrotne oddziałuje teraz znacznie rzadziej, efekty uczenia się w systemie typu LS-1 dają się zaobserwować dopiero po stosunkowo dużej liczbie prób. Niemniej jednak wyniki osiągnięte przez program w dziedzinie gry w pokera są imponujące i warto poświęcić więcej miejsca na omó-wieniejego cech charakterystycznych.
Program LS-1 zawiera mechanizm wnioskowania oraz reguły, które stanowią interesującą mieszaninę "zwyczajnego" systemu produkcji i systemu klasyfikującego. W systemie Smitha występuje pamięć robocza, będąca zbiorem elementów binarnych o ustalonej długości. Element taki dzieli się na porcję sygnałową i porcję danych. Zbiór reguł zakodowanych w postaci ciągów o jednakowej długości tworzy pamięć produkcji. Poprzednik reguły (warunek) składa się z k ustalonych wzorców; pierwsze / spośród nich odpowiada i detektorom zewnętrznym, a pozostałe ki wzorców odpowiada sygnałom obecnym w pamięci roboczej. Podobniejak system klasyfikujący program Smitha stosuje równoległy mechanizm sterowania; wszystkie uzgodnione reguły odpalają jednocześnie, z wyjątkiem tych, które powodują wykonanie akcji w środowisku. Te ostatnie zostają oznakowane, a następnie podejmuje się na drodze probabilistycznej decyzję o wy-konaniujednej z akcji, przy czym prawdopodobieństwo wyboru danej akcjijest proporcjonalne do liczby reguł, które się za nią opowiadają.
Konkretny przykład pomoże nam łatwiej przyswoić zasady uzgadniania przyjęte w programie LS-1. Przypuśćmy, że mamy dwa zewnętrzne detektory oraz pamięć roboczą o zawartości pokazanej w tabl. 7.1. Przypuśćmy dalej, że jest dana następująca produkcja:
-l##00##0# l##XO#OXOOlY^OllREASSERT(Y)
Chociaż przypomina to trochę klasyfikatory z poprzedniego rozdziału, jest też parę różnic. Po pierwsze poprzednik reguły składa się z dwóch części - "środowiskowej" (-l##0 O##0#) i "wewnętrznej" (reszta lewej strony). Zauważamy występujące w klasyfikatorach symbole 0, 1 i #, ale są też i inne. Znak - stojący przed pierwszą grupą symboli jest interpretowany jak logiczna negacja: jeżeli wzorzec poprzedzony symbolem - nie pasuje do żadnego komunikatu, to przyjmujemy, że reprezentowany przezeń warunek jest spełniony. W rozważanym przykładzie zanegowany wzorzec jest zgodny z komunikatem, ponieważ komunikat zewnętrzny 1111 nie pasuje do wzorca l##0. Kontynuując omawianie przykładu (i posuwając się, tak jak LS-1, od lewa na prawo), stwierdzamy zgodność drugiego komunikatu zewnętrznego (01001) z drugim wzorcem (warunkiem) O##0#. Po uzgodnieniu ze środowiskiem przechodzimy do uzgadniania z pamięcią roboczą. W programie LS-1 każdy warunek "wewnętrzny" składa się z prefiksu, wzorca i sufiksu. Tak jak w przypadku części środowiskowej, wzorzec wchodzący w skład części wewnętrznej może być poprzedzony prefiksem negacji (-); może także wystąpić
288
7. Zastosowania genetycznych systemów uczących się
prefiks oznaczający pominięcie - w takim przypadku interpretator ignoruje dany warunek. Sufiks warunku może być pusty lub być jednym z symboli X lub Y. X oraz K są to nazwy dwóch zmiennych występujących w LS-1. Przy pierwszym napotkaniu podczas uzgadniania (idąc od lewa na prawo) zmienna przybiera wartość równą odpowiadającej jej porcji danych w pamięci roboczej. W naszym przykładzie sygnał 100 pasuje do wzorca 1##, a zatem zmiennej X zostaje przypisany podciąg 1111. Po tym przypisaniu każde następne wystąpienie X zostaje chwilowo zastąpione przypisanym podciągiem i proces uzgadniania jest kontynuowany. Wracając do przykładu, wzorzec 0#0 pasuje do następnego sygnału (010), ale pełne uzgodnienie w tym przypadku nie zachodzi, gdyż zmienna X reprezentuje teraz podciąg 1111, który nie pasuje do odpowiedniej porcji danych w pamięci roboczej na pozycji nr 2. Przeglądając dalej pamięć roboczą stwierdzamy, że warunek daje się uzgodnić z elementem nr 5, gdyż sygnał 000 pasuje do wzorca 0#0, a wartość zmiennej X (1111) pasuje do porcji danych tego elementu. Ostatni warunekjest zgodny z elementem nr 4 pamięci roboczej (001 pasuje do 001); zmienna Kotrzymuje przy tym wartość 101.
Tablica 7.1. Przykład działania mechanizmu wnioskowania w systemie LS-1 Stan pamięci w chwili T
Tablica detektorów zewnętrznych
Pamięć robocza
Sygnały Dane
1
1111 01001
Reguła
-l##0 O##0# l##X O#OX 001Y^011 REASSERT(Y) Element pamięci roboczej wygenerowany w chwili T+ 1
011 101
Źródło: Smith (1980). Przedruk za zezwoleniem
Zmienne X i Kdają systemowi LS-1 elementarną zdolność rozpoznawania identyczności elementów danych. Ponadto umożliwiają mu przekazywanie informacji "z lewej strony na prawą". Kiedy nastąpi całkowite dopasowanie po stronie poprzednika, reguła odpala, wykonując dwie rzeczy. Po pierwsze umieszcza swój sygnał na wolnej pozycji w pamięci roboczej. Następnie dokonuje wartościowania swej akcji i jej argumentu w celu określenia, jakie dane umieścić w pamięci roboczej w miejscu przeznaczonym na porcję danych. W rozpatrywanym przykładzie, po całkowitym dopasowaniu poprzednika, część sygnałowa następnika reguły wędruje do pamięci roboczej oraz
7.3. Program pokerowy Smitha
289
wykonuje się akcja (REASSERT). Akcja REASSERT polega po prostu na skopiowaniu wartości argumentu do pamięci roboczej jako porcji danych odpowiadającej wysłanej wcześniej porcji sygnałowej. W przypadku tego konkretnego uzgodnienia, reguła generuje element pamięci roboczej złożony z porcji sygnałowej 011 i porcji danych 101, jak pokazano w tabl. 7.1. Akcje po prawej stronie reguł mogą być niezależne od zadania [task-independent] Qak REASSERT) lub zależne od zadania [task-dependent] Qak np. "Wchodzęzapięćijeszczepięć").
Struktura reguł i mechanizm wnioskowania są tak samo proste, jak i przetwarzanie genetyczne. Algorytm genetyczny w systemie LS-1 opiera się na czterech operacjach:
1) reprodukcja;
2) mutacja;
3) krzyżowanie zmodyfikowane;
4) inwersja.
Operacje reprodukcji i mutacji są dość podobne do tych, które omawialiśmy w poprzednich rozdziałach. Natomiast w procesie kr/yżowania - z uwagi na zmienną długość struktur - trzeba zachować pewną ostrożność, aby zagwarantować wymianę sensownych "cegiełek". Zmodyfikowana operacja krzyżowania w programie LS-1 jest realizowana w trzech krokach:
1) wyrównywanie;
2) wybór punktu krzyżowania; <
3) wymiana. ;
Różni się to od krzyżowania prostego dodatkowym krokiem wyrównywania [alignment}. Przypuśćmy, że dane są dwa zestawy reguł RS{ i RS2:
RS{=Rl:R2:R3,
RS2 = R8:R9:R4:Rl:R6:R5 , :,
gdzie R-y oznaczają różne reguły, a dwukropki (:) służą do zaznaczenia granic między regułami. W czasie wyrównywania w każdej z dwóch struktur wybiera się losowo punkt na granicy reguł, po czym przesuwa się je tak, aby oba wybrane punkty ustawiły się w jednej linii. Przypuśćmy, na przykład, że wybraliśmy punkt graniczny 1 dla RS{ i punkt graniczny 3 dla RS2. Po wyrównaniu (poprzedzającym krzyżowanie) struktury ustawiają się względem siebie następująco:
RS}=
R\:R2:R3, = R8:R9:R4:Rl:R6:R5
Następnie dokonuje się wyboru punktu krzyżowania, który może wypaść na dowolnym styku reguł w obu wyrównanych strukturach bądź też wewnątrz sparowanych reguł. Dobierając odpowiednio wartość specjalnego parametru, można kontrolować stosunek liczby krzyżowań na poziomie reguły do liczby krzyżowań na poziomie bitu. Po ustaleniu punktu krzyżowania wymiana podstruktur przebiega tak, jak w przypadku krzyżowania prostego opisanego w rozdziale trzecim.
290
7. Zastosowania genetycznych systemów uczących się
Operacja inwersji przebiega zgodnie z opisem podanym w rozdziale piątym, z zastrzeżeniem, że punkty podziału muszą wypadać na granicach reguł. Tak wiec, jeśli wykonamy inwersję zaznaczonego niżej odcinka struktury RS2
R8:R9:R4:Rl:R6:R5,
A A ;: ' "'�--' **-'-"-'..- :,'1 ' . ' �. - - ..
to będzie ona polegała na przepisaniu w odwrotnej kolejności reguł wchodzących w skład odcinka, dając wynik następujący:
R8:R7:R4:R9:R6:R5
Opisane operacje, łącznie z normalną reprodukcją i mutacją, określają algorytm genetyczny zastosowany w programie LS-1.
7.3.1. Wyniki osiągnięte przez program LS-1
W swych oryginalnych badaniach Smith zastosował program LS-1 do poszukiwania dobrych zestawów reguł dla zadań pokonywania labiryntu Hollanda i Reitmana (1978)
1000 2000 3000
t - Liczba ewaluacji
4000
Rys. 7.7. Efektywność off-line systemu LS-1 w zadaniu pokonywania labiryntu Hollanda i Reitmana dla różnych wartości prawdopodobieństwa inwersji P, (Smith, 1980). Przedruk za zezwoleniem
7.3. Program pokerowy Smitha .
291
oraz gry w pokera. Niestety, Smith przyjął inne mierniki wydajności niż twórcy systemu CS-1, przez co bezpośrednie porównanie wyników uzyskanych przez oba systemy jest niemożliwe. Zadanie pokonywania labiryntu Smith traktował zasadniczo jako ćwiczenie mające na celu dostrojenie parametrów programu. W jednej z interesujących serii testów zmieniano prawdopodobieństwo inwersji, aby zbadać jej wpływ na tempo i poziom zbieżności. Wyniki tych testów zostały zreprodukowane na rys. 7.7. Stanowią one jedną z pierwszych jasnych wskazówek co do potrzeby użycia inwersji w zadaniach poszukiwania genetycznego.
Podstawowym testem dla programu LS-1 była gra w pokera. Smith oparł się tu na sformułowaniu podanym przez Watermana (1968) we wcześniejszej pracy na temat maszynowego uczenia się. Był tostandardowy poker dwuosobowy (po pięć kart na ręce), z tym, że decyzje na temat wymiany (zrzutek) były dokonywane algorytmicznie (przy użyciu stałego algorytmu; problem wymiany nie był dla systemu przedmiotem uczenia się) i można było dokupywać co najwyżej trzy karty. Detektorami systemu były następujące zmienne:
VDHAND Siła ręki
POT Wartość puli
LASTBET Wartość ostatniego zakładu
BLUFFO Miernik szansy sukcesu przy blefowaniu
POTBED Stosunek wartości puli do ostatniego zakładu
ORP Liczba kart dokupionych przez przeciwnika
OSTYLE Miernik konserwatyzmu przeciwnika
Dysponując powyższymi detektorami, program LS-1 miał do wyboru cztery decyzje:
CALL Sprawdź przeciwnika
DROP Pasuj
BET HIGH Postaw losową sumę od 10 do 20 jednostek
BET LOW Postaw losową sumę od 1 do 9 jednostek
Program LS-1 został przetestowany w grze przeciwko innemu programowi, opracowanemu przez Watermana jako "gracz porównawczy". Przeciwnik ten (zwany P[built-in]) był oceniany równorzędnie z dobrymi graczami zawodowymi, jednak stosowana przezeń strategia gry nie była adaptacyjna. W pierwszych partiach treningowych LS-1 szybko nauczył się "puszczać przeciwnika w skarpetkach". W wyniku późniejszych badań Smith odkrył słabą stronę programu P[built-in], która uniemożliwiała mu rozgrywanie długich serii rund niezbędnych w badaniach nad LS-1 jakieś 40 000 partii). Zmodyfikowana wersja P[built-in] lepiej dotrzymywała pola LS-1; jednak nawet grając z ulepszonym przeciwnikiem LS-1 potrafił wytworzyć zestawy reguł, które w 82% przypadkach zachowywały się zgodnie z dobrze znanymi "aksjomatami" pokera. Wynik tenjest porównywalny z osiągnięciami uzyskanymi przez adaptacyjny system Watermana. Skuteczność LS-1 zasługuje na uwagę tym bardziej, że program ten nie korzystał w procesie uczenia się z żadnych pomocniczych informacji. W przeciwieństwie do niego program Watermana dysponował jawną informacją pomocniczą w postaci macierzy decyzyjnej, która miała dopomagać mu w adaptacji.
292
7. Zastosowania genetycznych systemów uczących się
7.4. Inne wczesne próby z systemami GBML
System CS-1 zrodził LS-1, a oba systemy razem dały początek powiększającej się rodzinie przedsięwzięć z dziedziny genetycznych systemów uczących się. W tym punkcie dokonamy przeglądu kilku takich prób, a mianowicie systemu uczącego się Bookera, systemów EYE-EYE i ANIMAT Wilsona oraz mojego systemu klasyfikującego do sterowania dynamicznego.
7.4.1. Poszukiwanie pożywienia i unikanie trucizn
Booker w swej rozprawie doktorskiej (1982) przeprowadził badania dotyczące związków systemów klasyfikujących z inteligencjami naturalną i sztuczną. Jego praca utorowała drogę dalszym przedsięwzięciom z dziedziny GBML. Booker poświęcił uwagę trzem następującym tematom: ;
1) związkom między systemami klasyfikującymi a nauką o poznaniu;
2) modyfikacji algorytmów genetycznych służącej zastosowaniom w dziedzinie maszynowego uczenia się;
3) zastosowaniu systemów klasyfikujących w zagadnieniu poszukiwania pożywienia i unikania trucizn w przestrzeni dwuwymiarowej.
Praca Bookera była dobrze ugruntowana w teorii nauki o poznaniu i poświęconej jej literaturze. Zainteresowanego Czytelnika zachęcamy do zaczerpnięcia pełną garścią z jego obfitego plonu, ulegając jednak naszej skłonności do rzeczy praktycznych, ograniczymy się tylko do najbardziej dojrzałych (i nadających się do bezpośredniego spożycia) owoców. Skwpimy się zatem na wprowadzonych przez niego innowacjach do algorytmu genetycznego oraz na jego dwuwymiarowym poszukiwaczu.
Booker zastosował system klasyfikujący mający bezpośrednie korzenie w systemie CS-1. System ten posługiwał się klasyfikatorami na modłę Hollanda, algorytmem oceniającym bucket brigade oraz algorytmem genetycznym. Chcąc wniknąć głębiej w "szare komórki", Booker zmodyfikował architekturę CS-1 w sposób pokazany na rys. 7.8.
Wejście
sygnał +/-
Rys. 7.8. Architektura systemu klasyfikującego Bookera z podzieloną pamięcią klasyfikatorów i listą komunikatów (Booker, 1982). Przedruk za zezwoleniem
7.4. Inne wczesne próby z systemami GBML
293
Struktura systemu przypomina opis generyczny z rozdziału szóstego i system CS-1 pod względem obecności efektorów, detektorów, listy komunikatów i pamięci przeznaczonej na klasyfikatory; jednak na rysunku jest widoczna istotna różnica. System Bookera zawiera dwie pamięci klasyfikatorów i dwie listy komunikatów. Jest to kwestia wygody doświadczalnej; Booker interesował się bowiem wnioskami "wyciąganymi" przezjego system i oddzielił je od wynikających z nich akcji, dzieląc pamięć klasyfikatorów i listę komunikatów na dwie części.
Przed wypuszczeniem swego uczącego się systemu do karmicielsko-trucicielskiego środowiska Booker przeprowadził badania skuteczności różnych operacji genetycznych dla testowego zadania rozpoznawania wzorców. Tworzył on mianowicie populacje ciągów trójkowych (w alfabecie klasyfikatorów {0, 1, #}) i porównywałje z ciągami dwójkowymi o tej samej długości, wygenerowanymi losowo według określonych schematów. Na przykład w jednym z eksperymentów generował on losowo 16-elementowe ciągi dwójkowewedługwzorca � .......,
iiiiiiiiii****** ' ". , " ' ,;: ;�;�;�� ;::_�� ,,, �..;� �'�
Następnie używał populacji ciągów trójkowych (coś w rodzaju klasyfikatorów z warunkami pozbawionymi akcji) do klasyfikacji tych ciągów, stosując różne mierniki ocen w charakterze funkcji przystosowania przy dalszym przetwarzaniu genetycznym. Dla różnych eksperymentów opracował on i stosował różne mierniki ocen. Następnie wyniki otrzymane za pomocą algorytmu genetycznego przy różnych miernikach ocen zostały porównane na podstawie dwóch kryteriów poprawności klasyfikacji. Eksperymenty te ostatecznie skłoniły Bookera do przyjęcia następującego miernika ocen:
1NCARES + (długośćtaksonu) dlataksonuuzgodnionego 1 za każdy poprawny atrybut plus 0,75 za każdy # w przeciwnym przypadku
Trwają wciąż spory na temat użyteczności takiego częściowego dopasowania. Booker wprowadził inne mierniki ocen (Booker, 1985), które były odpowiedzią na niektóre zastrzeżenia co do jego pierwotnego miernika; jednak pewna grupa badaczy sprzeciwia się jakiejkolwiek postaci częściowego dopasowania. Wagę tego problemu można łatwiej docenić, jeśli rozpatrywać go od strony architektury. System klasyfikujący może być widziany jako sieć ściśle powiązanych elementów (podobnie jak np. sieć neuronowa). Od tego, co do czego pasuje (i w jakim stopniu), zależy, które elementy będą bezpośrednio ze sobą połączone. Dopasowanie częściowe daje odpowiedź mówiącą, że wszystkie elementy są wzajemnie połączone - do pewnego stopnia. Ścisłe dopasowanie nakłada ograniczenia na połączenia sieciowe. Kontrowersje te mogą ucichnąć dopiero wtedy, gdy zostaną przedstawione argumenty teoretyczne oparte na odpowiedniej podbudowie matematycznej (Holland, 1986b, 1987a), poparte pozytywnymi wynikami symulacyjnymi.
Chcąc zwiększyć efektywność algorytmu genetycznego w zadaniach z wieloma wzorcami, Booker wprowadził dwa mechanizmy: podział zasobów oraz bariery reprodukcyjne. Teoretyczne aspekty podziału zasobów rozważaliśmy już w rozdziale piątym.
294
7. Zastosowania genetycznych systemów uczących się
25 23 21 19
c o >o ��17
1.5
y>
LU
13
11
9
400 1200 2000 2300 3600 4400 5200 6000
Liczba prób
Rys. 7.9. Porównanie efektywności on-//neprzed (GO) i po (G2) wprowadzeniu ulepszeń do algorytmu , , genetycznego w eksperymentach Bookera (1982) z klasyfikacją ciągów. Przedruk za zezwoleniem
W implementacji Bookera, taksony (warunki) pasujące do tego samego wzorca dzieliły się wypłatą za uaktywnienie. Podział wypłaty uwzględniał uzyskane oceny. Powstająca w ten sposób wewnętrzna presja konkurencyjna miała ograniczać rozrost jakiejkolwiek klasy taksonów.
W rozdziale piątym omówiliśmy również racje stojące za tworzeniem barier reprodukcyjnych. Mówiąc zwięźle, w populacji klasyfikatorów służących rozmaitym wzorcom, krzyżowanie elementów należących do różnych klas nie rokuje wielkich szans znalezienia lepszych klasyfikatorów. Jeśli, na przykład, dane są dwa klasyfikatory - 000#1#:1 i 111##0:0 - służące rozpoznawaniu odpowiednio wzorców 000*** i 111***, to niewiele pożytku przyjdzie nam z krzyżowania tak radykalnie odmiennych reguł. Bariery reprodukcyjne odpowiadają zasadzie heurystycznej, którą można wyrazić następująco: "Jeżeli dwie koncepcje odnoszą się do tego samego szczególnego przypadku, to spróbuj dokonać ich syntezy". W celu probabilistycznej kontroli takich skojarzeń, Booker zaimplementował regułę kojarzenia podobnych z podobnymi (dodatniego kojarzenia selektywnego), dokonując kojarzenia w odpowiedzi na zaprezentowany wzorzec pochodzący ze środowiska. Partnerzy byli tu dobierani na podstawie ocen zgodności z przedstawionym wzorcem. Tak więc sprzężenia taksonów następowały za pośrednictwem komunikatów, które były przez nie klasyfikowane. Graficzne porównanie efektywności on-line osiąganej przez system przed wprowadzeniem ulepszeń do algorytmu genetycznego (plan GO) i po ich wprowadzeniu (plan G2 z podziałem wypłat i barierami reprodukcyjnymi) zostało przedstawione na rys. 7.9,
Po zbadaniu poprawek do algorytmu genetycznego Booker przeprowadził serię eksperymentów, polegających na symulowanej wędrówce systemu klasyfikującego w ob-
7.4. Inne wczesne próby z systemami GBML
295
szarze stanowiącym dwuwymiarową, heksagonalną siatkę (rys. 7.10). W obszarze tym występowały dwa rodzaje obiektów: pożywienie (kwadraty) i trucizna (kółka). Każdy rodzaj obiektów emanował wokół siebie swego rodzaju "zapach" o malejącej intensywności (rys. 7.11). Zbliżając się do danego obiektu, system klasyfikujący mógł podjąć jedną z trzech decyzji: APPROACH (podejdź), EXPLORE (zbadaj) i CONSUME (zjedz).
Rys. 7.10. Pożywienie (kwadraty) i trucizna (kółka) rozłożone na heksagonalnej siatce tworzą środowisko badane przez system klasyfikujący Bookera (1982)

� .. 111*111.
���12211221-
1 9 >4 9 9 *? >4 *5 1
���12211221-
� ��111.111.
-
*��111. *�10
���1221--124 � .19491. .1*5 21 ......
� � � 1 2 2 1 � - - l 1 1 .......





421 - -- -


Rys. 7.11. Pożywienieitruciznaemanują,,zapach"odczuwalnynaodległość(Booker, 1982). Przedruk za zezwoleniem
296
7. Zastosowania genetycznych systemów uczących się
2000
1800
1600
,| 1100
S^1200
co
^N 1000 o
ra 800
_& 600
400
200
0
10 20 30 40 50 60 70 80 90 100
Bloki po 100 prób
Rys. 7.12. Wyniki uczenia się przez system klasyfikującego Bookera dla różnych wartości parametru LEARNRATE (Booker, 1982). Przedruk za zezwoleniem
sooo
�000
^ 3500
S 3000 �
_Q
8 2500
| 3000
$1500
1000
500
0 10 20 30 V0 50 60 70 80 90 100
| Bloki po 100 prób
Rys. 7.13. Liczba błędów popełnianych przez system klasyfikujący z użyciem i bez użycia algorytmu genetycznego (Booker, 1982). Przedruk za zezwoleniem
Wjednym z eksperymentów (rys. 7.12), w których badano zdolność systemu do uczenia się, porównywano osiągane przezeń wyniki w zależności od wartości parametru LEARNRATE (tempo uczenia się). Parametr ten określa odstęp czasowy między kolejnymi wywołaniami algorytmu genetycznego. Jak można się przekonać z wykresów, w przypadku, gdy wartość LEARNRATE nie dorównywała nominalnemu okresowi mię-
7.4. Inne wczesne próby z systemami GBML
297
dzy wypłatami, zachowanie systemu było nieregularne i po osiągnięciu równowagi stochastycznej popełniał on błędy ze stałą intensywnością. Gdy odstęp między wywołaniami AG został wydłużony (co odpowiada wartościom LEARNRATE 20 i 30), przewidywania systemu zaczęły być bardziej trafne i liczba błędów spadła do zera. Innego rodzaju porównania przedstawiono na rys. 7.13, gdzie pokazane są wyniki uzyskane w eksperymentach bez i z użyciem algorytmu genetycznego. W przebiegu z użyciem AG system potrafił z czasem wytworzyć zestaw reguł, które zredukowały liczbę pomyłek do zera, natomiast w drugim przypadku nie był w stanie zaprzestać popełniania błędów.
7.4.2. Koordynacja systemu EYE-EYE
W tym samym czasie, kiedy Booker rozwijał swój system klasyfikujący, Wilson (1981, 1985a, doniesienie prywatne 1987) pracował nad koordynacją sensoryczno-motoryczną ruchomej wideokamery Qego system będziemy nazywać systemem EYE-EYE). Podstawowym zadaniem systemu było nabycie umiejętności ześrodkowania filmowanego obiektu w polu widzenia kamery (przez przesuwanie jej w odpowiednim kierunku). W przeciwieństwie do poprzednich systemów środowisko było tu faktycznie zrealizowane w postaci aparatury działającej w czasie rzeczywistym. Zdjęcie aparatury Wilsona zamieszczono na rys. 7.14. Praca pozostawała pod znacznym wpływem architektury CS-1 (Holland i Reitman, 1978), zawierałajednak kilka wartych odnotowania innowacji. Od strony niegenetycznej, Wilson posłużył się inspirowanym biologicznie odwzorowaniem siatkówkowo-korowym (Wilson, 1981, 1983), w celu uzyskania znormalizowanych, względnie niezmienniczych obrazów obiektów ześrodkowanych na siatkówce. Zastosował mianowicie zespoloną funkcję logarytmiczną w = \nz, gdzie w = u + iv w płaszczyźnie korowej, z=x + iy w płaszczyźnie siatkówkowej oraz t'=v-l. Kilka obrazów korowych
Rys. 7.14. Aparatura zastosowana w systemie EYE-EYE Wilsona. Przedruk za zezwoleniem
Rys. 7.15. Odwzorowanie logarytmiczne (zespolone) obrazów: normalnego, zbliżonego i obróconego. Zwraca uwagę podobieństwo obrazów korowych (po prawej stronie) mimo zmian powstatych w obrazach siatkówkowych (po lewej stronie). Za Wilsonem (1985a). Przedruk za zezwoleniem
Rys. 7.16. Odworowania logarytmiczne obrazów nie ześrodkowanych niezbyt przypominają swoje ześrodkowane odpowiedniki (rys. 7.15). Dlatego Wilson (1985a) postawił przed systemem EYE-EYEzadanieześrodkowaniaobrazu.Przedrukzazezwoleniem >
300
7. Zastosowania genetycznych systemów uczących się
otrzymanych za pomocą tego odwzorowania pokazano na rys. 7.15. Zwróćmy uwagę na podobieństwo obrazów korowych otrzymanych przez przekształcenie logarytmiczne obrazów siatkówkowych powstałych przez obrócenie i zbliżenie tego samego obiektu. Taka normalizacja jest istotnym warunkiem odniesienia sukcesu przy stosowaniu procedur uzgadniania wzorców, z którymi mamy do czynienia w systemach klasyfikujących. Zauważmy też, że obrazy nie ześrodkowane dają zupełnie różne obrazy korowe (rys. 7.16). To właśnie z tego powodu Wilson skupił pierwotnie uwagę na problemie ześrodkowania. Chociaż zespolona funkcja logarytmiczna, którą posłużył się Wilson, ma ograniczone zastosowanie w dziedzinie przetwarzania obrazów, to sam pomysł znalezienia odwzorowania dającego względnie niezmiennicze rejestracje obrazów może być przydatny na wielu polach.
Pod względem architektury system klasyfikujący Wilsona przypomina CS-1. Jednym z widocznych odstępstwjest przyjęta przez Wilsona postać reguł. Zamiast zwykłych jednowymiarowych ciągów kodowych reprezentujących warunki, Wilson użył macierzy trójkowych 4 x4 będących wzorcami obrazów. Tak więc reguła w systemie Wilsona mogłaby wyglądać na przykład tak:
#### ##11
###i ####
:3
Reguła powyższa odpala, jeśli w obrazie korowym zostanie wykryty trójkątny wzór złożony z jedynek. Aby móc posługiwać się tymi dwuwymiarowymi strukturami, Wilson wymyślił "dwuwymiarową" operację krzyżowania, którą nazwał krzyżowaniem szachownicowym [checkerboard crossover]. Podany przez niego opis tej operacji jest jednak cokolwiek niejasny; prócz tego nie są znane żadne teoretyczne oszacowania prawdopodobieństwa przeżycia oraz brak odpowiedniej definicji schematu.
Niemniej jednak przeprowadzono wiele udanych eksperymentów z koordynacją aparatury EYE-EYE, chociaż szczegółowe wyniki nigdy nie zostały opublikowane. System uczył się odpowiednich reguł przesuwania kamery, a tym samym ześrodkowania obiektu w jej polu widzenia. Prace te doprowadziły w krótkim czasie do eksperymentów w bardziej kontrolowanym środowisku i do opracowania prostszej architektury systemu klasyfikującego w postaci systemu ANIMAT Wilsona.
7.4.3. System klasyfikujący ANIMAT
Doświadczenia z systemem EYE-EYE przekonały Wilsona o potrzebie uproszczenia aparatury i przeprowadzenia prostych parametrycznych eksperymentów w dobrze kontrolowanym środowisku. Doprowadziło to do opracowania systemu ANIMAT (Wilson, 1985b,c, 1986d). Zainspirowany dwuwymiarowym "sztucznym zwierzęciem" Bookera, Wilson zaprojektował system klasyfikujący wędrujący po dwuwymiarowym lesie, poszukujący pożywienia i unikający przeszkód w postaci drzew. Rozpostarty na regularnej
7.4. Inne wczesne próby z systemami GBML
301
siatce prostokątnej 18x58, każdy las zawiera połacie porośnięte drzewami (T) oraz rozrzucone regularnie żerowiska (F). Typowy las jest przedstawiony na rys. 7.17. ANIMAT (reprezentowany niżej przez "*") ma zapewnioną orientację w swym bezpośrednim otoczeniu. Przypuśćmy na przykład, że ANIMATjest otoczony przez dwa drzewa (T), jedno żerowisko (F) oraz puste pola (B), jak pokazano niżej:
B T T B * F B B B
T TT T
TFT F F T F FT
T TT F
TT F T
F TFT TFT F TT F
TT T T
TT T TT T
TFT F TF F TFT F
T
TT T T TT T
F F T FT F TF TFT
T TF
T T ...: -.!t: � T .,v T
F F F FT F TF
T TT T T
T T
F TFT F ',..' F F TF
TT T TT T T
Rys. 7.17. Środowisko systemu ANIMAT. System uczy się wędrować po lesie w poszukiwaniu żerowisk (F), unikając drzew (T) (Wilson, 1985a). Przedruk za zezwoleniem
Wzorzec ten generuje komunikat zewnętrzny, który powstaje przez "rozwinięcie" zewnętrznego pierścienia, poczynając od punktu położonego na północ i posuwając się zgodnie z ruchem wskazówek zegara:
T T F B B B B B
Stosując odwzorowanie T ^> 01, F ^ 11, B ^ 00 (pierwszą pozycję można uważać za binarny detektor "zapachu", a drugą za binarny detektor "zacienienia"), otrzymujemy następujący komunikat:
0101110000000000
ANIMAT reaguje na komunikaty zewnętrzne, używając zwykłych klasyfikatorów z 16-pozycyjnymi warunkami (co odpowiada 16-pozycyjnym komunikatom) i ośmioma akcjami (akcje 0-7). Każda akcja reprezentuje pojedynczy ruch w jednym z ośmiu kierunków (O = polnoc, 1 =pomocny wschód, 2 = wschod itd.). Na przykład reguła
0#011#00000#0#:2
302
7. Zastosowania genetycznych systemów uczących się
jest zgodna z przytoczonym wyżej przykładowym komunikatem i określa krok (całkiem sensowny z punktu widzenia głodnego systemu klasyfikującego) w kierunku wschodnim, gdzie znajduje się pożywienie. ANIMAT został zaprogramowany tak, aby spożywać każdy posiłek znajdujący się w miejscu jego pobytu (czyżby automat kompulsywny?)
W systemie wprowadzono kilka innowacji pod względem sposobu funkcjonowania i operacji genetycznych:
1) grupa zgodna, grupa wykonawcza i podział nagród;
2) operacja kreacji;
3) operacja częściowego przecięcia;
4) szacowanie czasu oczekiwania na wypłatę. -
Podczas procesu uzgadniania zachodzącego w układzie wykonawczym określa się grupę zgodną [match set] [M], złożoną ze wszystkich klasyfikatorów pasujących do komunikatu zewnętrznego. Następnie za pomocą mechanizmu ruletki wykalibrowanej wg siły decyduje się o następnej akcji. Podzbiór tych reguł z [M], które specyfikują tę samą akcję, nazywa się grupą wykonawczą [action set] [A]. Siła tych klasyfikatorów zostaje zredukowana o pewien procent, a otrzymany w ten sposób zasób siły rozdziela się następnie pomiędzy elementy poprzednio aktywnej grupy wykonawczej [A],_,. W ten sposób Wilson wprowadza ukrytą formę algorytmu bucket brigade, dzięki czemu nagrody środowiska są pośrednio rozprowadzane wzdłuż "łańcuszka" odpalających reguł. Podobny mechanizm występował w systemie klasyfikującym SCS z rozdziału szóstego (choć nie był użyty w zadaniu z multiplekserem); jednak pamiętajmy, że w systemie SCS nie było podziału nagród. Poprzez mechanizm podziału Wilson wprowadza kontrolę wielkości podpopulacji klasyfikatorów, podobną do tej, którą zalecał Booker.
Kolejną nowością w systemie ANIMAT jest operacja kreacji. Kiedy ANIMAT odbiera ze środowiska komunikat nie pasujący do żadnego klasyfikatora, uruchamia wtedy operację kreacji. Polega ona na wykonaniu odbitki komunikatu i "uogólnieniu", z zadanym prawdopodobieństwem, każdej pozycji odbitki (tj. zastępowaniu zer ijedynek symbolem uniwersalnym #). W ten sposób zostaje utworzony takson, który z definicji pasuje do komunikatu zewnętrznego. Następnie losuje się jedną z dopuszczalnych akcji (od 0 do 7) i dołącza ją do nowego taksonu. Tak powstały nowy klasyfikator zastępuje któryś ze słabych klasyfikatorów przechowywanych w pamięci i system kontynuuje swoje normalne działania.
Operacja częściowego przecięcia jest czymś pośrednim między operacją krzyżowania a operacją przecięcia. Podczas częściowego przecięcia dwie wybrane reguły z tą samą akcją "ustawiają się" wzdłuż siebie. Przypuśćmy, na przykład, że dane są dwie następujące reguły:
1 0 0 # ł 0 0 1 : 6 0 1 # 1 1 0 1 # : 6
A A
W przypadku czystego przecięcia na każdej pozycji, w której występuje niezgodność umieszcza się znak #. W rozważanym przypadku otrzymalibyśmy w ten sposób regułę:
7.4. Inne wczesne próby z systemami GBML
303
# # # tt tt 0 # # : 6 ;, c .;>:, �:-�.�. . �
Wilson stwierdził, że czyste przecięcie może powodować nadmierną presję w kierunku zbytniej ogólności. Aby przezwyciężyć tę trudność, zaproponował on modyfikację operacji przecięcia wykazującą cechy krzyżowania. W tym przypadku dokonuje się losowego wyboru dwóch pozycji w obrębie warunków i przeprowadza operację przecięcia tylko w wyznaczonej przez nie strefie, podczas gdy reszta materiału genetycznego zostaje skopiowana od pierwszej z wybranych reguł rodzicielskich. Przyjmując, że punkty podziału w naszym przykładzie zostały wskazane za pomocą znaków ^, otrzymamy więc następujący wynik częściowego przecięcia:
1 tt # # # 0 0 1 : 6
Wilson eksperymentował również z mechanizmem mającym dopomagać w tworzeniu krótkich łańcuchów wypłat. W ramach tego mechanizmu zapamiętywano szacunkową liczbę kroków do zdobycia nagrody dla kolejnych grup wykonawczych. Dane te były następnie lokalnie uaktualniane, zaś przy wyborze aktywnych klasyfikatorów brano pod uwagę nie tyle siłę, co iloraz wypłaty i czasu oczekiwania na wypłatę. W ten sposób faworyzowano klasyfikatory zdobywające najwyższe wypłaty w najkrótszym czasie.
Typowe wyniki uzyskiwane przez system ANIMAT przedstawiono graficznie na rys. 7.18. W fazie początkowej średni czas poszukiwania pożywienia jest dość długi. Podczas pierwszego tysiąca prób system uczy się szybko, zbliżając się ostatecznie do średnio czterech kroków na posiłek. Dla tego typu lasów Qak na rys. 7.18) średni czas poszukiwania pożywienia przy błądzeniu przypadkowym wynosi 41 kroków, a minimalny średni czas poszukiwania przy pełnej wiedzy o położeniu żerowiskjest równy 2,2 kroku. Biorąc pod uwagę, jaką wiedzą dysponował w rzeczywistości ANIMAT, jego osiągnięcia
e 1 2 3 4 5 6
Liczba problemów x 1000
Rys. 7.18. ANIMAT potrzebuje coraz mniej kroków, by znaleźć pożywienie, w miarę postępów w nau ce przy rozwiązywaniu 8000 problemów (Wilson, 1985b). Przedruk za zezwoleniem
304
7. Zastosowania genetycznych systemów uczących się
wydają się godne uwagi. Aby osiągnąć znaczącą poprawę musiałby on bowiem skonstruować "mapę umysłową" lasu, żeby wiedzieć, w którym kierunku podążyć, gdy był otoczony przez same puste pola. Taki rodzaj modelowania jest możliwy do osiągnięcia w ramach systemów klasyfikujących, jednak prace na ten temat miały dotąd charakter głównie teoretyczny. Bez przeprowadzenia dalszych studiów nie możemy oczekiwać, że systemy klasyfikujące zaczną, tworzyć takie mapy poznawcze w drodze ewolucji.
7.4.4. System klasyfikujący do sterowania gazociągiem
Mniej więcej w tym samym czasie, kiedy Wilson kończył swoje eksperymenty z systemem EYE-EYE, rozpocząłem prace nad systemem klasyfikującym do sterowania adaptacyjnego symulowanym rurociągiem gazowym (Goldberg, 1983,1985a-c, 1987a,b). Zadawano mi często pytanie, dlaczego wybrałem właśnie rurociąg gazowy, a nie jakiś inny (być może bardziej ezoteryczny) system. Zanim powróciłem na uczelnię, pracowałem dla firmy zajmującej się wytwarzaniem oprogramowania inżynierskiego, która dostarczała programy modelowania numerycznego dla przemysłu gazociągowego. Kiedy modele te zaczęły być coraz powszechniej stosowane przy bieżącej eksploatacji (przy projektowaniu używano ich, w tej czy innej postaci, od 30 lat), zacząłem zdawać sobie sprawę z jaskrawego kontrastu między sposobami myślenia i podejmowania decyzji u doświadczonych operatorów gazociągów i u ludzi produkujących tradycyjne oprogramowanie inżynierskie (którzy "wbudowali" swoje podejście w programy). Ostatecznie mieliśmy tu do czynienia z gazo-wnikami, ludźmi o niewielkim lub żadnym wykształceniu technicznym, którzy pomyślnie - i dość wydajnie - radzili sobie z utrzymywaniem w ruchu systemu, na który składają się setki tysięcy mil wielkośrednicowych przewodów rurowych oraz kompresory zużywające tysiące kilowatogodzin dzień po dniu. W istocie ludzie ci kierowali swoimi rurociągami, tak jak my kierujemy naszymi rodzinnymi samochodami. Dla kontrastu, u podstaw inżynierskiego oprogramowania i procedur decyzyjnych leżą złożone modele i metody matematyczne. Metody te - służąc do rozwiązywania tych samych zadań - są mniej intuicyjne i mniej elastyczne (chociaż dokładniejsze). Takie właśnie cokolwiek naiwne rozważania popchnęły mnie do pracy nad czymś, co miałoby coś wspólnego ze sztuczną inteligencją i sterowaniem gazociągami. W tych okolicznościach trafiłem na wykłady Hollanda o systemach adaptacyjnych. Myślałem podówczas bardziej niż sceptycznie o tym, co może mieć wspólnego cała ta biologiczna gadanina z regulacją rurociągów gazowych, jednak z czasem urzekło mnie piękno tej przyrodniczej wizji (niestety, większość gazowników wciąż podziela mój ówczesny sceptycyzm).
Moja praca była poświęcona dwóm zagadnieniom dotyczącym gazociągów: optymalizacji czynności regulacyjnych za pomocą algorytmu genetycznego oraz regulacji adaptacyjnej przy użyciu systemu klasyfikującego. Pierwsza część pracy została krótko omówiona w rozdziale czwartym. W drugiej części zająłem się dwoma następującymi problemami:
1) sterowaniemukłademinercyjnym;
2) sterowaniem gazociągiem.
7.4. Inne wczesne próby z systemami GBML
305
Układ inercyjny, o którym mowa, jest przedstawiony schematycznie na rys. 7.19. Zadanie systemu klasyfikującego polega tu na doprowadzeniu układu poruszającego się bez tarcia do pozycji środkowej, przez przykładanie siły o ustalonej wielkości z jego lewej i prawej strony. Problem ten został wybrany ze względu na swą prostotę i dlatego, że zagadnienie optymalnego w czasie sterowania układem inercyjnym bez tarcia ma znane, chociaż niebanalne rozwiązanie. Problem układu inercyjnego okazał się być interesujący sam w sobie, gdyż stanowił jeden z pierwszych przykładów demonstrujących powstawanie hierarchii domniemań.
W przypadku problemu sterowania gazociągiem, jako dynamiczny model przepływu gazu zastosowano dyskretny układ pierwszego rzędu z nieliniowymi oporami.
QUAD tt
U U
Rys. 7.19. Pierwsze zadanie dla mojego systemu klasyfikującego (Goldberg, 1983) polegało na doprowadzeniu układu inercyjnego bez tarcia do pozycji środkowej
1,5,
.0)
0,0
00
Godzina
24
Rys. 7.20. W zadaniu sterowania pracą gazociągu zapotrzebowanie na gaz zmienia się w czasie zależnie od pory roku i pory dnia (Goldberg, 1983)
8
8
U5^
t:
i s
"
c
CL 0
0)
o o
8
I "0,00
zAG
bezAG
Algorytm losowy
100,00
200,00 Czas (dni)
300,00
400,00
Rys. 7.21. Eksperymenty z reakcjąsystemu klasyfikującego na wycieki w gazociągu. Wykresy uśrednionych ocen punktowych w zależności od czasu. Przebieg z użyciem algorytmu genetycznego "przewyższa" przebieg bez jego użycia, a oba warianty systemu klasyfikującego są lepsze od błądzenia przypadkowego (Goldberg, 1983)
�� p t CJ1
_nj f
iż
^
8
t,00
bezAG
Algorytm losowy
100,00
200,00
300,00
400,00
Czas (dni)
Rys. 7.22. Wskaźnik poprawnie sygnalizowanych awarii dla systemu klasyfikującego sterującego pracą gazociągu. Fakt, że wariant bez użycia AG daje lepsze wyniki niż wariant z użyciem AG wydajesię niezgodnyz intuicjądopóty, dopóki niespojrzymyna rys. 7.23(Goldberg, 1983)
7.4. Inne wczesne próby z systemami GBML
307
Zapotrzebowanie na gaz zmieniało się zależnie od pory roku i pory dnia (rys. 7.20). Informacja o stanie środowiska była przekazywana systemowi klasyfikującemu za pośrednictwem detektorów opisanych w tabl. 7.2. Obejmowała ona ciśnienie i wielkość przepływu u wlotu i wylotu, współczynnik ciśnienia nadmiarowego, porę dnia, porę roku i temperaturę. Ponadto w rurociągu zdarzały się losowe wycieki, podczas których następował ubytek (nie dający się bezpośrednio zmierzyć) znacznej części strumienia gazu wpływającego do systemu. , V'
Tablica 7.2. Struktura komunikatu zewnętrznego w zadaniu sterowania pracą gazociągu
1 1
I PI I QI I PO I QO I DP I TOD I TY I TP I TAG I
Zmienna Opis
Min
Max
Liczba pozycji
PI Ciśnienie wlotowe 0 2000 2
Qi Przepływ u wlotu Q 80 2
PO Ciśnienie wylotowe 0: 2000 2
Q0 Przepływ u wylotu 0 80 2
DP Współczynnik ciśnienia
nadmiarowego -200 200 ,2
TOD Pora dnia 0 24 2
TY Pora roku 0 1 1
TP Temperatura 0 1 1
Źródło: Goldberg (1983)
W jednej z serii eksperymentów gazociąg doznawał wycieków. System otrzymywał nagrodę, jeśli nauczył się zarówno sterować pracą rurociągu, jak i poprawnie alarmować o awariach. Na rysunku 7.21 wykreślono uśrednione w czasie oceny punktowe dla przebiegów z użyciem algorytmu genetycznego, bez użycia algorytmu genetycznego oraz z czystym błądzeniem przypadkowym. Dodatkowy miernik skuteczności, wskaźnik procentowy poprawnie sygnalizowanych awarii, został pokazany na rys. 7.22. Te ostatnie wyniki wydają się w pierwszej chwili niezgodne z intuicją, gdyż w przebiegu bez użycia AG system klasyfikujący zapisał na swoje konto większy procent poprawnych sygnalizacji (w rejestrowanym przedziale czasu), niż w przebiegu z użyciem AG. Tajemnica wyjaśnia się jednak, jeśli spojrzymy na uzupełniający wykres wskaźnika fałszywych alarmów (rys. 7.23). W przebiegu bez AG ceną za wysoki wskaźnik prawidłowych alarmów jest wysoki wskaźnik fałszywych alarmów. Przy zastosowaniu AG system klasyfikujący unika tego niepożądanego zachowania, ucząc się odpowiedniej "reguły wycieku" (bardzo zbliżonej do tego, co mógłby zaprogramować znawca przedmiotu), wiedząc w konsekwencji, kiedy podnosić alarm, a kiedy zachować spokój.
308
7. Zastosowania genetycznych systemów uczących się
!s
co M
g
o>
bezAG
Algorytm losowy
zAG
0,00
100,00
200,00 Czas (dni)
300,00
400,00
Rys. 7.23. Wskaźnik fałszywych alarmów dla systemu klasyfikującego sterującego pracą gazociągu. Wariant bez AG uzyskuje wysoki wskaźnik poprawnych alarmów kosztem dużej liczby fałszywych alarmów (Goldberg, 1983)
7.5. Przegląd wybranych zastosowań
Od czasu pojawienia się pierwszych zastosowań genetycznych systemów uczących się przeprowadzono wiele badań natury teoretycznej i obliczeniowej. W tym punkcie dokonamy przeglądu kilku takich prac, dzięki którym udało się znacznie poszerzyć obszar praktycznych zastosowań systemów GBML.
7.5.1. BOOLE: System klasyfikujący uczy się trudnej funkcji boolowskiej
Dalsze prace Wilsona w dziedzinie systemów klasyfikujących obejmowały eksperymenty z uczeniem się funkcji boolowskich (1986a,b, 1987a). Podejmując problem opisany w pracy (Barto, Anandan i Anderson, 1985) Wilson zaprojektował system BOOLE, którego zadaniem było uczenie się emulacji multiplekserów o rosnącej złożoności. W poprzednim rozdziale, omawiając uproszczony system klasyfikujący, rozważaliśmy zadanie dotyczące multipleksera z sześcioma liniami wejściowymi. W bardziej abstrakcyjnym sformułowaniu mieliśmy tam do czynienia z funkcją boolowską, którą można przedstawić w postaci normalnej alternatywno-koniunkcyjnej jak następuje:
Ffi = a'0a\d(} + a'^
7.5. Przegląd wybranych zastosowań
309
gdzie mnożenie oznacza koniunkcję logiczną, dodawanie - alternatywę logiczną, a pri-mowanie reprezentuje logiczną negację. Zadanie to można rozszerzyć na przypadek większych multiplekserów. Ogólnie, dla k linii adresowych istnieją multipleksery o k + 2k liniach wejściowych. Wilson wykonał doświadczenia z muliplekserami o 6, 11 i 20 liniach wejściowych.
W systemach ANIMAT i BOOLE zastosowano niemal identyczne systemy klasyfikujące. Klasyfikatory w systemie BOOLE składają się z pojedynczych warunków (po jednej pozycji na linię) i jednobitowych akcji (0 lub 1). Podział wypłat odbywa się tak jak w systemie ANIMAT; jednak w systemie BOOLE nie ma potrzeby stosowania algorytmu przyznawania ocen w żadnej postaci, gdyż każdy klasyfikator otrzymuje nagrodę natychmiast po wykonaniu akcji (albo wcalejej nie otrzymuje).
-co
c
cc
0.
1000
800
600
400
10
30
40
50
60
f. Liczbaprob(x103) i
Rys. 7.24. Wyniki osiągnięte przez system BOOLE dla zadania z multiplekserem (6 linii wejściowych). Krzywa u góry przedstawia średni wynik (Śred) z 50 prób. Krzywa środkowa reprezentuje stosunek procentowy symboli uniwersalnych # (SymUn). Krzywa u dołu opisuje liczbę poprawnych reguł (PReg) (na 400 ogółem) w populacji reguł (Wilson, 1987a). Przedruk za zezwoleniem
Wyniki dla sześciu linii zostały przedstawione graficznie na rys. 7.24. Wykres górny obrazuje średnie ruchome z 50 prób wskaźnika procentowego poprawnych odpowiedzi. Dolny wykres przedstawia liczbę reguł w bieżącej populacji należących do ośmioelementowego zbioru reguł idealnych. W tablicy 7.3 zamieszczono obraz migawkowy populacji uporządkowanej według malejącej siły reguł. Zwróćmy uwagę, że osiem pierwszych reguł to dokładnie te reguły, które są potrzebne do emulacji multipleksera. Warto tu podkreślić skuteczność procesu uczenia się wobec faktu, że w początkowej, wygenerowanej losowo populacji 400 reguł nie /nalazła się ani jedna z tych ośmiu. Skuteczność ta wydaje się imponująca w porównaniu do wyników osiągniętych przez system uczący się Barto i innych (1985). Aby osiągnąć ten sam poziom sprawności,
310
7. Zastosowania genetycznych systemów uczących się
system BOOLE potrzebował o rząd wielkości mniej kroków czasowych niż specjalnie zaprojektowanasiećjednostekuczącychsię.
Tablica 7.3. Obraz migawkowy populacji klasyfikatorów w systemie BOOLE (emulacja multipleksera z 6 liniami wejściowymi) po 15000 prób
Reguła
Liczba egzemplarzy
Takson
Akcja
Siła całkowita
56 0 1 #0## / 0 7655
52 01#1## / ',' , : 1 7541
48 '''''"' 000### f U,.'4;, i''"0'- 7056
46 1 0##0# / 0 7095
45 00 1 ### / 1 6665
41 .:� 1 1 # # # 0 / 0 '' : 5964
39 1 1###1 / 1 6323
35 1 0## 1# / 1 ;. 5145
7 # 1 # 1 # 1 / 1 v 1044
4 1 1 # # # # / 1 522
3 #0## 1 # / 1 293
3 1 1 ##0# / 0 ; 210
�., - -- � 2 # 0 1 # # # /-.,. . .. ,. 1 330
2 0 1 1 # # # 1 1 212
2 1 00#0# / 0 150
2 00#### / 1 219
2 1 ### 1 # / 1 i 326
2 1 0#0## / 0 238
1 # 1 #0## / 0 129
; �' � -1 . 1 0#### / 0 168
1 1 1 #### / 0 97
1 1 0##00 / 0 100
1 00##1# '\ r ;/�/., �'� �.-...� 1 � 81
1 1 ####0 /,.- o 212
.. 1 1 0##0 1 ' ..... ' /'�' ' . 1 ,,.��; .�.'.;;'�- '�.- �. .- *�..� .-� 56
1 0 1 #### 116
Źródło: Wilson (1987a). Przedruk za zezwoleniem
W eksperymentach z 11 liniami wejściowymi Wilson dołączył mechanizm kontroli krzyżowania oparty na znormalizowanym mierniku entropii populacji Hc:
H =
lnN
gdzie S: oznacza sumaryczną siłę z'-tego podzbioru złożonego z identycznych klasyfikatorów, ST jest sumaryczną siłą wszystkich klasyfikatorów, a W - liczbą klasyfikatorów w populacji. Ten rodzaj sterowania można uważać za regulację progową. Jeśli zmiana entropii systemu osiągnie dostatecznie dużą wartość dodatnią lub ujemną, to prawdopo-
7.5. Przegląd wybranych zastosowań
311
dobieństwo krzyżowania zostaje odpowiednio zmniejszone lub zwiększone o ustalony wskaźnik procentowy (10%). W przeciwnym razie prawdopodobieństwo krzyżowania nie zmienia się. Wynikł tych eksperymentów są zilustrowane na rys. 7.25. Porównano tam przebiegi ze stałymi prawdopodobieństwami krzyżowania 0,5 (linia kropkowana) i 0,12 (linia przerywana) w stosunku do przebiegu z regulacją progową (linia ciągła). Wilson był w stanie złapać dwie sroki za ogon za pomocą swego mechanizmu krzyżowania adaptacyjnego, który łączy szybką eksplorację przy wysokim tempie krzyżowania z końcową zbieżnością przy niskim tempie krzyżowania, kiedy populacja zaczyna krzepnąć. Dla potwierdzenia ogólności tej techniki niezbędne są jednak dalsze eksperymenty.
400
300
L u
<0 200
CL O Q.
ioo
10 20 30 40 60
Liczbaprób (x103)
60
Rys. 7.25. Wyniki osiągnięte przez system BOOLE z mechanizmem kontroli krzyżowania dla zadania z multiplekserem (11 linii wejściowych). Linia kropkowana odpowiada prawdopodobieństwu krzyżowania pc=0,5. Linia przerywana odpowiada pc = 0,12. Linia ciągła odpowiada zmiennemu pc (Wilson, 1987a). Przedruk za zezwoleniem
Przeprowadzono również wstępne doświadczenia z 20 liniami wejściowymi. W eksperymentach tych system BOOLE osiągnął 90-procentową poprawność po 70 000 prób, a liczba poprawnych reguł wyniosła 1200 na 1600 możliwych po 120000 prób. Brzmi to zachęcająco, jeśli uświadomimy sobie rozmiar problemu. W przypadku multipleksera z 20 liniami wejściowymi istnieje 220 = l,05xl06 - ponad milion - ciągów wejściowych oraz 2-32()s6,97xl09 - niespełna 7 miliardów - reguł. Tak więc, po 120000 prób system BOOLE miał okazję zetknąć się z mniej niż jedną ósmą wszystkich możliwych ciągów wejściowych, a mimo to program okazał się skuteczny w ponad 90% przypadków i wykazywał ciągłą poprawę. Próby rozwiązania tego samego problemu przy użyciu kilku popularnych, tradycyjnych technik uczenia się nie przyniosły wyraźnego sukcesu (S.W. Wilson, doniesienie prywatne, 1987). ;:. ,;
r
312
7. Zastosowania genetycznych systemów uczących się
7.5.2. Równoległe sieci semantyczne na bazie klasyfikatorów: system CL-ONE____
Wyznawcy kierunku symbolicznego w sztucznej inteligencji mieli zwyczaj występować od czasu do czasu z krytyką koncepcji genetycznych systemów uczących się, jako zbyt prymitywnej, aby objaśnić procesy powstawania pojęć wyższego rzedu i posługiwania się nimi. S. Forrest (1982, 1985b,c, 1986) zdemaskowała ten symboliczny szowinizm w swej rozprawie doktorskiej, prezentując sieć semantyczną wysokiego poziomu zrealizowaną w ramach systemu klasyfikującego. Forrest skupiła się na części wykonawczej systemu klasyfikującego (którą nazwaliśmy układem przetwarzania komunikatów), usuwając z niej algorytm bucket brlgade i algorytm genetyczny. Opracowała też kompilator do tłumaczenia specyfikacji napisanych w języku sieci semantycznych KL-ONE (Brach-man i Schmolze, 1985) na format systemów klasyfikujących. Czytelnik może się w tej chwili zastanawiać, dlaczego poświęcamy tyle uwagi systemowi nie zawierającemu układu uczącego się. Otóż Forrest przerzuciła most między systemami klasyfikującymi, a zagadnieniami będącymi od długiego czasu przedmiotem zainteresowania bardziej tradycyjnie nastawionych badaczy sztucznej inteligencji. Odwzorowując z powodzeniem model symboliczny na system klasyfikujący, Forrest dostarczyła w pewnym sensie do-
Opis sieci KL-ONE
Parser
i generator
klasyfikatorów
System klasyfikujący
Procesor dyrektyw
Rys. 7.26. Struktura systemu CL-ONE (Forrest, 1985c). Przedruk za zezwoleniem
7.5. Przegląd wybranych zastosowań
313
wodu, że systemy klasyfikujące mogą emulować złożone modele rozważane przez sym-bolistów. W sytuacji, kiedy pierwsze systemy GBML skupiały się (i słusznie) na uczeniu się prostych zachowań, wyznawcom kierunku symbolicznego mogło być trudno dojrzeć możliwości osiągnięcia przez nie wymaganego stopnia złożoności na drodze ewolucji. Praca Forrest wskazała na istnienie takich możliwości.
Aby zrozumieć działanie systemu (któremu Forrest nadała później miano CL-ONE), zapoznajmy się z jego ogólną strukturą, przedstawioną na rys. 7.26. System zawiera cztery główne składowe:
1) analizator składniowy (parser) i generator klasyfikatorów;
2) zarządcatablicysymboli; '�
3) procesordyrektywzewnętrznych; V,,.
4) systemklasyfikujący. '�; ; V v '�'>
Jak pokazano na schemacie, generator klasyfikatorów otrzymuje na wejściu opis sieci KL-ONE i tłumaczy go na zestaw klasyfikatorów. Generuje on przy tym tablicę symboli, która jest potrzebna, aby w przyszłości można było rozszerzyć sieć o nowe pojęcia. Zapytanie użytkownika zostaje przetłumaczone na komunikat przez procesor dyrektyw zewnętrznych. Z kolei komunikat trafia do systemu klasyfikującego w celu przetworzenia. Aby zrozumieć proces kompilacji, musimy zapoznać się bliżej z koncepcją sieci semantycznej KL-ONE.
Schemat sieci KL-ONE jest uwidoczniony na rys. 7.27. W rzeczywistości opis sieci zostaje wprowadzony do systemu przy użyciu notacji zbliżonej do składni języka LISP, jak na wyd. 7.1 (z wyjątkiem węzła Młodzieniec, który traktujemy jako nowe pojęcie, dołączone za pośrednictwem procesora dyrektyw). Na diagramach sieci KL-ONE pojęcia są reprezentowane za pomocą owali, na przykład Rzecz i Mężczyzna; natomiast role - za
(CONCEPTSPEC Person PRIMITIVE
(SPECIALIZES Thing)
(ROLE Limb (VRCONCEPT Legs))
(ROLE Sex (VRCONCEPT Gender)))
(CONCEPTSPEC Legs PRIMITIVE (SPECIALIZES Thing)) (CONCEPTSPEC Gender PRIMITIVE (SPECIALIZES Thing)) (CONCEPTSPEC Male PRIMITIVE (SPECIALIZES Gender)) (CONCEPTSPEC Female PRIMITIVE (SPECIALIZES Gender)) (CONCEPTSPEC Man (SPECIALIZES Person)
(ROLE Sex (VRCONCEPT Male))) (CONCEPTSPEC Woman (SPECIALIZES Person)
(ROLE Sex (VRCONCEPT FemaIe)))
(CONCEPTSPEC Young PRIMITIVE (SPECIALIZES Thing)) (CONCEPTSPEC YoungMan (SPECIALIZES Person)
(ROLE Sex (VRCONCEPT Male))
(ROLE Age (VRCONCEPT Young))) (CONCEPTSPEC HighRiskDriver (SPECIALIZES Person)
(ROLE Sex (VRCONCEPT Male))
(ROLE Age (VRCONCEPT Young))).
Wyd. 7.1. Przykład opisu struktury sieci KL-ONE (Forrest, 1983). Przedruk za zezwoleniem
314
7. Zastosowania genetycznych systemów uczących się
Rys. 7.27. Przykładowyschematsieci KL-ONEukazującypowiązaniamiędzypojęciami (owale) i rolami : (kwadraty w kółkach). Przykład ten, zaczerpnięty z pracy Forrest, miał ilustrować proces <, poszukiwania pojęć najbliższych pojęciu Młodzieńca (Forrest, 1985c). Przedruk za zezwoleniem
pomocą kwadratów w kółkach, na przykład Płeć, Kończyna, Wiek. Obiektami podstawowymi w KL-ONE są pojęcia. Pojęcia mogą być powiązane ze sobą na najrozmaitsze sposoby. Na przykład pojęcie Osobyjest specjalizacją pojęcia Rzeczy, o czym świadczy podwójna strzałka na diagramie sieciowym. W terminologii KL-ONE mówi się, że węzeł Osoba ma dowiązanie typu SUPERC" do węzła Rzecz (w literaturze tego typu dowiązania są częściej oznaczane jako IS-A - JEST). Wyrażając to słowami powiedzielibyśmy, że pojęcie Osoby jest specjalizacją pojęcia Rzeczy albo że Osoba jest rodzajem Rzeczy (mówimy także, że pojęcie Rzeczy obejmuje [subsumes] pojęcie Osoby, ale o tym za chwilę). Z diagramu widać też, w jaki sposób pojęcia są powiązane za pomocą ról (Płeć, Kończyna, Wiek).
Wjęzyku KL-ONE ról używa się do definiowania dalszych pojęć. Można to zrobić określając relację między dwoma pojęciami, tak jak pokazano na rysunku. Na przykład na schemacie zdefiniowano pojęcie Mężczyzny jako Osoby o Płci Męskiej. W sieci KL-ONE potrzeba do tego celu dwóch osobnych dowiązań. W rozważanym przykładzie dowiązanie typu ROLE łączy pojęcie Mężczyzny z rolą Płeć, a dowiązanie typu VR
" Od słowa superconcept (pojęcie nadrzędne) tyrzyp. tłum.).
7.5. Przegląd wybranych zastosowań
315
(value restriction - zakres wartości) łączy rolę Płeć z pojęciem Męski. Przy takim sposobie użycia role przypominają "sloty" wjęzyku reprezentacji ramowej. Zwróćmy uwagę, że niektóre pojęcia nie dają się zdefiniować za pomocą innych. W języku KL-ONE pojęcia takie nazywają się pierwotnymi (PRIMITIVE), a na diagramie zaznacza się je gwiazdką. Na przykład pojęcie Osoby jest pierwotne i nie wymaga zdefiniowania. Odnotujmy, że także inne typy dowiązań w KL-ONE zostały zaimplementowane w systemie Forrest. Zainteresowany Czytelnik może odwołać się do oryginalnej pracy, aby się z nimi zapoznać, dowiedzieć się do czego służą, jak zostały zaimplementowane i dlaczego wybrano ten konkretny podzbiór KL-ONE.
Cały ten aparat notacyjny jest interesujący sam w sobie, ale co możemy za jego pomocą osiągnąć? Możemy na przykład zadawać pytania (i otrzymywać na nie odpowiedzi) w rodzaju: ,,Czy pojęcie Kobiety obejmuje pojęcie Mężczyzny?" (nie) albo "Czy pojęcie Mężczyzny obejmuje pojęcie Młodzieńca?" (tak). Aby odpowiadać na takie pytania, musimy wyjaśnić sobie znaczenie terminu obejmowanie [subsumption\. Mówiąc w uproszczeniu, jedno pojęcie obejmuje drugie, jeżeli pojęcie obejmowane jest powiązane z obejmującym za pomocą ciągu dowiązań typu SUPERC albojeżeli zachodzą pewne związki między definicjami obu pojęć. Bardziej precyzyjnie, pojęcie A obejmuje pojęcie B, jeżeli B ma przynajmniej te same cechy pierwotne co A, jeżeli każda rola A jest rolą B i jeżeli zakresy wartości ról A mieszczą w sobie zakresy wartości odpowiednich ról B (w rzeczywistości definicja tego terminu jest bardziej skomplikowana, ale dla prostoty będziemy się trzymać skróconej wersji). Z tej definicji wynika jasno, dlaczego pojęcie Mężczyzny obejmuje pojęcie Młodzieńca. Obydwa są specjalizacją tego samego pojęcia pierwotnego (Osoba*), rola Mężczyzny (Płeć) jest również rolą Młodzieńca, a zakres wartości tej roli u Mężczyzny (Męski) mieści w sobie analogiczny zakres wartości u Młodzieńca (też Męski). Zdolność do stwierdzania stosunku obejmowania i zachowywania sieci dziedziczenia jest podstawą, na której opierają się liczne symboliczne systemy wnioskowania.
Moglibyśmy też pytać, które pojęcia są najbliższe innemu pojęciu. Taka automatyczna klasyfikacja pojęć jest szczególnie ważna w dynamicznych bazach wiedzy, w których zachodzi potrzeba nieustannego przyswajania nowych pojęć. Przypuśćmy, że pytamy, które pojęcia w sieci z rys. 7.27 są najbliższe pojęciu Młodzieńca. Mówiąc bardziej formalnie: szukamy zbioru najbardziej szczegółowych pojęć obejmujących [most specific subsumers\ dane pojęcie (będącychjego uogólnieniem). W istocie, przykładowa sieć, którą tu omawiamy, posłużyła w rozprawie Forrest (1985) do ilustracji procesu poszukiwania pojęć najbliższych pojęciu Młodzieńca (są nimi Mężczyzna i NiebezpiecznyKierowca).
Tak więc obeszliśmy wszystkie kąty, próbując dowiedzieć się czegoś o systemie KL-ONE, wciąż jednak nie wiemy, jakim sposobem Forrest udało się odwzorować opis sieci KL-ONE na system klasyfikujący. Kluczem do tego są dowiązania. Zilustrujemy to na prostym przykładzie z dowiązaniami typu SUPERC (rys. 7.28). Pojęcie Surfingjest tu dowiązane do obejmującego je pojęcia SportyWodne. Dowiązaniu temu odpowiadają następujące dwa klasyfikatory (w zapisie mnemonicznym): . > t
NORM-SportyWodne-SUPERC-DOWN NORM-Surfing-SUPERC-UP
� NORM-Surfing-SUPERC-DOWN > NORM-SportyWodne-SUPERC-UP
316
7. Zastosowania genetycznych systemów uczących się
Rys. 7.28. Przykładowe dowiązanie typu SUPERC (IS-A) ilustruje odwzorowanie, które Forrest , ,-|,. zastosowała w kompilatorze CL-ONE (Forrest, 1985). Adaptacja za zezwoleniem
W rzeczywistości nazwy mnemoniczne zostałyby tu zastąpione wzorcami z jedynek, zer i symboli uniwersalnych; wartojednak zwrócić uwagę na użycie dwóch klasyfikatorów, co umożliwia poruszanie się po grafie w obydwu kierunkach. Do reprezentacji innych typów dowiązań potrzeba jednego lub więcej klasyfikatorów. Pewne wskazówki natemat sposobu realizacji dowiązań można znaleźć analizując "paskalopodobny" opis zamieszczony na wyd. 7.2. Bardziej szczegółowy opis znajduje się w oryginalnej pracy.
Analizator składniowy i generator klasyfikatorów pospołu konstruują taki opis sieci klasyfikującej i jej realizację. Nast?pnie monitor dyrektyw umieszcza komunikaty na liście komunikatów, aby zapoczątkować proces obejmowania i stawiania pytań na temat najbliższych pojęć. Forrest zaimplementowała też przy użyciu klasyfikatorów wiele przydatnych operacji arytmetycznych (dodawanie, wyznaczanie maksimum i minimum, porównywanie), mnogościowych (iloczyn, suma, dopełnienie i różnica zbiorów), syn-chronizacyjnych (służących do koordynowania różnych działań współbieżnych) i pamięciowych (operacje obsługi stosu push, pop, clear). W sumie, operacje te zapewniają systemowi CL-ONE pokaźną siłę wyrazu, szczególnie, jeśli wziąć pod uwagęjego "prymitywną" podbudowę.
Część omawianego studium była poświęcona oszacowaniu złożoności rozmaitych operacji. Forrest nie tylko dowiodła, że sieć semantyczna może zostać zrealizowana w postaci systemu klasyfikującego; pokazała również, że przydzielając każdemu klasyfikatorowi odrębny procesor (przy zapewnieniu odpowiedniej komunikacji między procesorami), można uzyskać szybkie przetwarzanie zapytań. W pracy rozważa się także problem tzw. dekompilacji\ w jaki sposób wyrazić i przedstawić w zrozumiały dla użytkownika sposób nowe pojęcia, które wyłaniają się w procesie uczenia się systemu klasyfikującego? Forrest wskazuje trzy możliwe metody podejścia do tego trudnego problemu
7.5. Przegląd wybranych zastosowań
317
type
tag = (NORM,ON,HOLD,MEM,NUM,PRE); boolcontrol = NORM .. MEM; compare = (AFIELD,BFIELD,CFIELD); name = string; message = string; numeric = 0 .. 63;
classifier record = record case tag : tagfield
boolcontrol : /* Structural Variant */ (tagfield name);
NUM
PRE end;
: /* Numeric Variant */ (tagfield compare numeric);
: /* PreDefined Message Variant (tagfield message);
tag: 0 - 2, name: 3 31, compare: 21 - 25, numeric: 26 31, message: 3 31.
Wyd. 7.2. Opis struktury danych reprezentującej klasyfikator w systemie CL-ONE wyrażony w składni wzorowanej na języku Pascal (Forrest, 1985c). Przedruk za zezwoleniem
odwracania: śledzenie w czasie rzeczywistym, statyczną analizę reguł oraz analizę dynamiczną zadania. Opracowanie odpowiednich algorytmów nie jest jednak sprawą łatwą, z powodu wielkiej dowolności wewnętrznych sposobów reprezentacji pojęć "zewnętrznych". Niemniej jednak Forrest wykazała w swej doniosłej pracy, że takie reprezentacje mogą istnieć, mogą być efektywnie wyznaczane i, w konsekwencji, mogą powstawać drogą ewolucyjną w uczących się systemach klasyfikujących.
7.5.3. Przetwarzanie genetyczne programów _____________________________________________________________sekwencyjnych: JB i TB
Czytelnik mógł odnieść wrażenie, że algorytmy genetyczne znajdują zastosowanie w programach uczących się wyłącznie wtedy, gdy te ostatnie przybierają postać reguł produkcji. Tak nie jest. Przykład adaptacji programu sekwencyjnego można znaleźć w pracy Cramera (1985). Cramer wyszedł od uniwersalnego języka PL (Brainerd i Land-weber, 1914), usunął instrukcje skoku i doszedł do prostegojęzyka (PL-) służącego do obliczania funkcji pierwotnie rekurencyjnych. Wymyślił on dwie metody kodowania
programów napisanych w języku PL-----JB i TB - oraz użył zmodyfikowanych operacji
genetycznych w procesie automatycznego generowania elementarnego algorytmu mnożenia. Omówimy teraz sam język, oba warianty kodowania, operacje genetyczne oraz wyniki eksperymentów.

318
7. Zastosowania genetycznych systemów uczących się
Język PL- zawiera trzy instrukcje pierwotne i dwie pochodne, zapisane poniżej wskładninaśladującejjęzykLISP:
1 . ( : INC VAR) ; Zwiększ wartość zmiennej VAR o 1 (pierwotna)
2 . ( : ZERO VAR) ; Wyzeruj zmienną VAR (pierwotna)
3 . ( :LOOP VAR STAT) ; Powtórz instrukcję STAT VAR razy (pierwotna)
4. ( :SET VAR1 VAR2) ; Nadaj zmiennej VAR1 wartość VAR2 (pochodna)
5. ( :BLOCK STAT1 STAT2) ; Wykonaj sekwencyjnie instrukcje STAT1 i STAT2 (po-
chodna)
Paskalową operację mnożenia V5: = V4 * V3 można by w języku PL- zaimplementować następująco:
(:ZEROV5) (:LOOPV3 (:LOOPV4 (:INCV5)))
Program ten działa poprawnie, gdyż zmienna V5 zostaje zwiększona o 1 V4 razy, wszystkiego V3 razy - co daje iloczyn V3 i V4.
Chociaż język PL- jest wystarczająco mocny, w zaprezentowanej postaci nie nadaje się szczególnie dobrze do manipulacji genetycznych. Starając się znaleźć format bardziej odpowiedni dla algorytmu genetycznego, Cramer opracował sposób kodowania instrukcji języka PL- za pomocą uporządkowanych trójek liczb całkowitych, który nazwał JB:
gdzie x jest kodem operacji, y - pierwszym argumentem, a z - drugim argumentem. Kody pięciu powyższych operacji są następujące:
: BLOCK = 0
:LOOP = 1
:SET = 2 ,
: ZERO = 3
: INC = 4
W kodzie JB zmienne są reprezentowane przez swoje indeksy, a etykiety instrukcji - przez numery odpowiednich trójek. Ponadto zbędne argumenty i niekompletne trójki liczb są ignorowane. Na przykład ciąg
(0 0 1 3 5 8 1 3 2 1 4 3 4 5 9 9 2)
zostanie zinterpretowany następująco:
(0 0 1) ; instrukcja główna (3 5 8) ; instrukcja 0 (1 3 2) ; instrukcja 1 (1 4 3) ; instrukcja 2 (4 5 9) ; instrukcja 3
( :BLOCK STAT1 STAT2)
( :ZERO V5) ; argument 8 ignorowany
(:LOOP V3 STAT2)
( :LOOP V4 STAT3)
(INC V5) ; argument 9 ignorowany
nadmiarowe liczby 9 i 2 ignorowane
7.5. Przegląd wybranych zastosowań
319
Po uważnym przestudiowaniu powyższego kodu widać, że stanowi on implementację algorytmu mnożenia zapisanego przedtem w notacji PL-. Cramer nie podaje żadnych wyników związanych z zastosowaniem kodu JB w eksperymentach genetycznych; zrezygnował on z dalszych prób po przeprowadzeniu wstępnych eksperymentów (N.L. Cramer, doniesienie prywatne, 1987). Cramer sądził, że operacje zmodyfikowanego krzyżowania Smitha (Smith, 1980, 1983) nie były wystarczające do zapewnienia skutecznego poszukiwania genetycznego z powodu wysokiej epistazy kodu; wniosek taki nie wydaje się jednak usprawiedliwiony bez przeprowadzenia dokładniejszych badań. Cramer kłopotał się także potencjalną możliwością wygenerowania JB-programów, które się nie zatrzymują. Posługiwanie się etykietami instrukcji (zamiast samymi instrukcjami) jest równoważne wprowadzeniu bezwarunkowej instrukcji skoku. Upraszczając PL Cramer miał nadzieję stworzyć język z gwarantowaną własnością zatrzymania. Programy w JB mogły wpadać i wpadały (chociaż rzadko) w nieskończoną pętlę.
Przemyślenia Cramera na temat JB doprowadziły jednak w końcu do implementacji PL- w postaci kodu drzewiastego, który zapewniał żądaną własność zatrzymania. W metodzie tej, nazwanej kodem TB, stosuje się nawiasy w celu zagnieżdżania instrukcji do dowolnej skończonej głębokości. Używa się przy tym tych samych kodów operacji, co w JB, natomiast liczba argumentów musi odpowiadać rodzajowi operacji. Przykładowy algorytm mnożenia można zapisać w TB następująco:
(0(3 5)(1 3)(1 4(4 5))})
Cramer przeprowadził eksperymenty genetyczne z kodem TB, używając zmodyfikowanych operacji genetycznych. Krzyżowanie partnerów polegało na wymianie dwóch losowo wybranych poddrzew. Mutacja sprowadzała się do losowej zmiany liczby całkowitej; trzeba było przy tym zadbać, aby została zachowana zgodność między operacją a liczbą jej argumentów. Wspomniano też o inwersji, ale nie próbowano jej zastosować.
Próbując wygenerować poprawny algorytm mnożenia, Cramer obmyślił mechanizm częściowego nagradzania mający faworyzować "zachowania quasi-multyplikatyw-ne". W tym celu nagradzał on trzy rodzaje programów:
1) programy zmieniające wartości zmiennych wyjściowych; y , :1
2) programy korzystające ze zmiennych wejściowych;
3) programy, które nadawały zmiennej wyjściowej wartość równą wielokrotności zmiennej wejściowej.
Ponadto nakładano kary na programy o zbyt długim kodzie, a każdy program, który przekroczył określony limit czasu wykonania, był przerywany i poddawany ocenie. W eksperymentach z TB obejmujących populacje 50-elementowe i 30 pokoleń znaleziono wiele programów wykonujących mnożenie. Cramer wykonał również symulację kontrolną, w której nie przyznawano żadnych nagród za częściowe rozwiązanie problemu. Eksperyment z częściowym nagradzaniem przyniósł o 72% więcej poprawnych programów mnożących niż eksperyment kontrolny. Mimo że taki "dowód co do zasady" wzbudza mieszane emocje, potrzeba dalszych badań, aby wyciągnąć ostateczne wnioski co do tego typu genetycznych systemów uczących się.
320
7. Zastosowania genetycznych systemów uczących się
7.6. Podsumowanie
W rozdziale tym omówiliśmy kilka przykładów genetycznych systemów uczących się (GBML). Celem systemów GBML jest udoskonalanie programów komputerowych na drodze selekcji, rekombinacji i innych manipulacji genetycznych wykonywanych na populacjach programów lub procedur zakodowanych w postaci ciągów symboli. Odkryliśmy korzenie systemów GBML datujące się z wczesnych lat sześćdziesiątych i prześledziliśmy ich rozwój aż do czasów obecnych, prezentując najbardziej znamienne przykłady.
Poświęciliśmy sporo uwagi procesowi formalnego kształtowania się tego kierunku zainteresowań, począwszy od pierwszych ściśle zakreślonych ram (Holland, 1962c) aż do późniejszych projektów procesorów schematów (Holland, 1971). Widzieliśmy, jak doprowadził on w konsekwencji do sformułowania propozycji ogólnego języka symbolicznego nadającego się do manipulacji genetycznych - języka przekazu (Holland, 1975) oraz do implementacji pierwszego systemu klasyfikującego (Holland i Reitman, 1978) - Systemu Kognitywnego 1 (CS-1). Te pierwsze próby utorowały drogę rosnącej liczbie prac badawczych, które podzieliły się na kilka nurtów.
Jednym z pytań, które stanęły przed badaczami była kwestia, czy jawne przyznawanie ocen jest potrzebne albo choćby użyteczne. Holland wraz z innymi specjalistami od systemów klasyfikujących dali odpowiedź twierdzącą. Dystrybucja wypłat za pomocą algorytmu bucket brigade (czy to w stosunku do pojedynczych reguł, czy to całych łańcuchów) stanowi integralną część tych systemów, umożliwiając im szybkie dostosowanie się do trudnych środowisk. Przeciwną opinię głosił Smith (1980) i inni badacze, którzy wybrali metodę oceny użyteczności całego programu na podstawie długiej serii prób. Te systemy również okazały się zdolne do szybkiego uczenia się w trudnych środowiskach. Oba typy systemów nigdy jednak nie zostały poddane bezpośredniej konfrontacji w tych samych środowiskach i przy zastosowaniu jednakowych mierników ocen. Być może pewnego dnia to nastąpi, powinniśmy jednak uświadomić sobie wcześniej, że ocena wyników takich eksperymentów będzie tendencyjna wskutek przyjęcia takiego lub innego kryterium (czy kryteriów) skuteczności. Zamiast podejmować próby rozstrzygnięcia tego sporu, powinniśmy raczej zachęcać do równoległych eksperymentów z obydwoma typami systemów, ponieważ każdy z nich ma coś do wniesienia w sprawę naszego rozumienia procesów genetycznego uczenia się.
Niezależnie od indywidualnych stanowisk w kwestii przyznawania ocen, prostota syntaktyczna większości systemów GBML opartych na regułach wywołała wątpliwości, czy tego typu systemy będą w stanie radzić sobie z "pojęciami" w rozumieniu tradycyjnego nurtu sztucznej inteligencji. Wyjaśniliśmy ten problem na korzyść systemów GBML, opierając się na pracy Forrest, która zaprojektowała kompilator języka sieci KL-ONE na klasyfikatory (system CL-ONE). System ten otrzymuje na wejściu opis sieci semantycznej wysokiego poziomu i przekształca go na reprezentację w postaci systemu klasyfikującego. W systemie CL-ONE zaimplementowano, na poziomie klasyfikatorów, podstawowe operacje arytmetyczne, mnogościowe i synchronizacyjne. Odnotowaliśmy też, że w CL-ONE nie występuje układ uczący się. Nie rozstrzygnięte pozostaje więc

7.6. Podsumowanie
321
pytanie, czy sieci tego typu są zdolne do uczenia się. Niemniej jednak praca ta dowodzi, że pojęcia, którymi zajmuje się symboliczna gałąź sztucznej inteligencji, dają się wyrazić i przetwarzać w ramach systemu klasyfikującego. "i
Kolejna nie rozstrzygnięta kwestia dotyczy formy reprezentacji programów. W licznych systemach preferowano proste reguły ciągowe. W szczególności w systemach z równoległym odpalaniem proste, niezależne reguły to jakby drobne, dające się kontrolować składniki programu, ponieważ reguły można łączyć i uzgadniać drogą prostej rekombinacji w celu znalezienia nowych reguł (lub zestawów reguł). Mimo całej dogodności tego podejścia nie można twierdzić, że jest ono jedynym możliwym, chociaż istnieje niewiele prac na temat systemów GBML działających na innych zasadach. Omówiona w tym rozdziale praca Cramera na temat języka sekwencyjnego PL- jest przykładem podejścia, które odniosło pewien sukces. Sekwencyjne uporządkowanie instrukcji ma wiele wspólnego z operacjami rekonfiguracji, o których mówiliśmy w rozdziale piątym i być może dalsze przemyślenia idące w tym kierunku mogłyby okazać się owocne.
Te i inne pytania będą nadal zadawane i nadal będą padać na nie odpowiedzi w miarę, jak będziemy się posuwać w kierunku szerszego zastosowania algorytmów genetycznych w problematyce uczących się maszyn. Możemy jednak pocieszyć się świadomością, że nie jesteśmy osamotnieni w naszej wędrówce; wiele dyscyplin dostarczy nam użytecznych wskazówek, analogii, a nawet narzędzi matematycznych (Holland, 1986b, str. 316-317):
Zaproponowane tu ramy matematyczne mają wiele wspólnego z modelami matematycznymi u/ywanymi do badania innych systemów adaptujących się, takich jak systemy ekonomiczne, ekologiczne, układy fizyczne w stanach dalekich od równowagi, układy odpornościowe itd. [...] W każdej z tych dziedzin pojawiają się znajome tematy, opracowane matematycznie, mające swój odpowiednik w pozostałych dziedzinach. Nawet skrócona Iista takich tematów [...] jest imponująca: 1) zajmowanie nisz, ewolucja konwergentna i wymuszona różnorodność [ekologia]; 2) zasada konkurencyjnego wykluczania się [ekologia]; 3) symbioza, pasożytnictwo, mimikra [ekologial; 4) epistaza, zmiany grup sprzężeniowych i re-definicje "cegiełek" [genetyka]; 5) sprzężenia i "genetyczni autostopowicze" [genetyka]; 6) wielotunkcyjność "cegiełek" [genetyka i biologia porównawcza]; 7) polimorfizm [genetyka]; 8) rekombinacja selektywna [genetyka i immunologia]; 9) organizacja hierarchiczna [filogenetyka, biologia rozwoju, ekonomia i sztuczna inteligencja]; 10) "zespoły znakowane" [genetyka molekularna, immunogeneza i teoria systemów adaptacyjnych]; 11) radiacja adaptacyjna i zasada założyciela [ekologia i filogenetyka]; 12) kataliza krzyżowa [biochemia i genetyka molekularna]; 13) "opóźniony dochód" jako funkcja przeszłych sukcesów i bieżących zakupów [ekonomia]; 14) "opodatkowanie" jako narzędzie kontroli wydajności [ekonomia]; 15) "ekploatacja" (produkcja) a "eksploracja" (badania naukowe) [ekonomia i teoria systemów adaptacyjnych]; 16) "śledzenie" a "uśrednianie" [ekonomia i teoria systemów adaptacyjnych]; 17) niejawna ocena "cegiełek" [teoria systemów adaptacyjnych]; 18) obszary przyciągania atraktorów i stany dalekie od równowagi [fizyka]; 19) wzmacnianie małych zaburzeń losowych przy "powolnych" przejściach przez punkty krytyczne [fizyka]. Każdy system złożony, zbudowany z elementów współdziałających ze
322
7. Zastosowania genetycznych systemów uczących się
sobą w sposób nieliniowy bedzie, w tym lub innym reżymie, wykazywał wszystkie wymienione własności. Ogólna teoria matematyczna takich systemów pozwoli wyjaśnić zarówno wszechobecność tych zjawisk, jak i związki między nimi.
Całe szczęście, że lista była skrócona. Nie brak ani użytecznych analogii, ani modeli teoretycznych, które moglibyśmy zapożyczyć w poszukiwaniu lepszych metod GBML. Mamy jeszcze tę przewagę nad naszymi kolegami i koleżankami, którzy mozolą się uprawiając dyscypliny "rzeczywiste" (w przeciwieństwie do "sztucznych"), że możemy dokonywać starannie zaplanowanych symulacji o kontrolowanym rozmiarze i zakresie, nie troszcząc się szczególnie o zgodność między modelem a rzeczywistością. Możemy więc obserwować te nieliniowe zjawiska in silico z pewnym dystansem, mogąc swobodnie wybierać to, co okaże się przydatne do stworzenia sprawniejszych systemów uczących się. Wobec takiej obfitości rozpościerających się przed nami rzeczywistych i sztucznych światów, żyjemy w ekscytującej epoce pod względem rozwoju tej dziedziny badań.
7.7. Zadania
7.1. Skonstruuj skuteczny zestaw reguł dla zadania pokonywania labiryntu z siedmioma węzłami w systemie CS-1 z zastosowaniem i bez zastosowania koncepcji hierarchii domniemań. Porównaj liczbę reguł w każdym zestawie. Czy mamy tu do czynienia z ogólną prawidłowością? Uzasadnij swoją odpowiedź.
7.2. Rozwiąż poprzednie zadanie dla labiryntu z trzynastoma węzłami i porównaj wyniki otrzymane w obydwu przypadkach. Objaśnij wyniki dotyczące przenoszenia wiedzy (rys. 7.5) w kontekście swojej odpowiedzi.
7.3. Porównaj algorytm interwałowy zastosowany w systemie CS-1 z algorytmem buc-ket brigade z późniejszych systemów klasyfikujących. Zwróć uwagę na zalety i wady obu procedur pod względem efektywności obliczeniowej.
7.4. Porównaj podejścia Hollanda (CS-1) i Smitha (LS-1) do architektury systemu klasyfikującego. Przedyskutuj zalety i wady obu metod.
7.5. Porównaj na podstawie literatury mechanizmy uczenia się stosowane w sieciach neuronowych lub systemach konekcyjnych z analogicznymi mechanizmami w systemach klasyfikujących. Przedyskutuj podobieństwa i różnice. Czego konekcjoniści mogą nauczyć się od adeptów algorytmów genetycznych i na odwrót?
7.6. W systemie Wilsona EYE-EYE reguła ma postać macierzy 4 x4 złożonej z sym-, boli alfabetu trójelementowego. Opracuj trzy różne operacje krzyżowania dla takiej reprezentacji i podaj dolne ograniczenie prawdopodobieństwa przeżycia schematu przy każdej z tych operacji.
7.7. W systemie ANIMAT zastosowano operację częściowego przecięcia. Jaki ciąg otrzymamy w wyniku częściowego przecięcia następujących ciągów rodzicielskich (strefa przecięcia została zaznaczona za pomocą znaków ^)?
7.8. Ćwiczenia komputerowe
323
1 1 0 # 1 0 # 1 0 1 1 : 4 0 0 1 1 1 0 0 1 0 # 1 : 4
A A
Podaj dolne ograniczenie prawdopodobieństwa przeżycia schematu przy operacji częściowego przecięcia.
7.8. Oblicz prawdopodobieństwo otrzymania metodą losową "poprawnego" zestawu reguł w systemie BOOLE dla zadania emulacji multipleksera z 6 liniami, przy ośmioelementowej populacji, jeżeli wszystkie trzy allele są jednakowo prawdopodobne. Wykonaj analogiczne obliczenia przy założeniu, że symbol # jest wybierany z prawdopodobieństwem 0,8, a pozostałe dwa z jednakowym prawdopodobieństwem.
7.9. Ile jest różnych JB-programów z 10 zmiennymi i złożonych z co najwyżej 10 instrukcji?
7.10. Zaprojektuj język typu JB o mniejszej epistazie niż oryginalny kod Cramera.
7.11. Skonstruuj jednostki przekazu w języku przekazu Hollanda, które realizują reprodukcję i krzyżowanie.
f
7.8. Ćwiczenia komputerowe
A. Dostosuj program SCS do zadania poszukiwania żywności w lasach Wilsona.
B. Napisz program uczący się mnożenia, posługując się metodą kodowania JB Cramera. Wykonaj taki sam eksperyment, używając dwójkowego odpowiednika kodu JB (zastosuj dwójkowy zapis liczb całkowitych). Porównaj i omów wyniki obu eksperymentów.
C. Dostosuj program SCS do zadania pokonywania labiryntu z siedmioma węzłami (Rys. 7.4a). Wykonaj eksperymenty symulacyjne i porównaj swoje wyniki z wynikami Hollanda i Reitmana (1978).
D. Zaimplementuj jakąś wersję języka przekazu w wybranym przez siebie języku programowania.
E. Zastosuj program SCS do emulacji multipleksera z 6 liniami, zmieniając wartość parametru gaperiod (czas między kolejnymi wywołaniami AG). Użyj wartości mniejszej, równej i większej od pewnej nominalnej długości cyklu nagradzania. Porównaj efektywność on-line dla wszystkich trzech eksperymentów. Porównaj swoje wyniki z wynikami eksperymentów Bookera z parametrem LEARNRATE.