Zastosowanie algorytmów genetycznych w
sieciach neuronowych
Tomasz Kowal, Marcin Wojtkiewicz
5 stycznia 2000 roku
Streszczenie
Czy połączenie dwóch rewolucyjnych ideii wytworzy nową jakość ? Czy też
spowoduje tylko powstanie nowego  modnego terminu ?
Algorytmy genetyczne używają nowych technik optymalizacji, pozwalających
na ewolucję prostych programów; w podobny sposób drogą ewolucji i stopniowe-
go ulepszania piszą programy ludzie. Programy  szkieletowe są przez algorytmy
genetyczne stale ulepszane w poszukiwaniu lepszego rozwiązania. Właśnie na tej
koncepcji opierają się Algorytmy genetyczne.
Algorytmy genetyczne oparte na pionierskich pracach Johna H. Hollanda, Da-
vida E. Goldberga i innych są ewolucyjnymi technikami przeszukiwania przestrze-
ni rozwiązań, inspirowanymi selekcją naturalną (znaczy to ni mniej ni więcej, że
przeżywa lepiej przystosowany).
Sieci Neuronowe natomiast są sposobem budowania pewnych struktur mają-
cych symulować działanie ludzkiego mózgu. Ich działanie oparte jest na budowie
komórki neuronowej.
Połączenie nowych idei będzie pokazane na przykładach optymalizacji topolo-
gii sieci neuronowej z wykorzystaniem algorytmów genetycznych, oraz rekuren-
cyjnych sieci neuronowych tworzonych przy pomocy algorytmów genetycznych.
Spis treści
I Wprowadzenie do algorytmów genetycznych 1
1 Wstęp 1
1.1 Konkretne zastosowania . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Modyfikacje algorytmów genetycznych . . . . . . . . . . . . . . . . 3
1.2.1 Rozszerzone algorytmy genetyczne (ESGA) . . . . . . . . . . 3
1.2.2 Semantycznie zmienne algorytmy genetyczne (SCGA) . . . . 4
1.2.3 Rozszerzone semantycznie zmienne algorytmy genetyczne (SCGA) 7
2 Przykład optymalizacji prostej funkcji za pomocą algorytmów genetycz-
nych 7
2.1 Wybór reprezentacji . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Populacja początkowa . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Funkcja oceny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Operatory genetyczne . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 Parametry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1
2.6 Wyniki obliczeń . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Teoretyczne podstawy algorytmów genetycznych - dlaczego one działają 9
II Wstęp do sieci neuronowych 12
4 Wprowadzenie 12
5 Zastosowanie sieci neuronowych 12
6 Rodzaje sieci neuronowych 13
6.1 Realizacja sieci neuronowych . . . . . . . . . . . . . . . . . . . . . . 13
6.2 Liniowe i nieliniowe sieci neuronowe . . . . . . . . . . . . . . . . . 14
6.3 Struktura neuronu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.4 Uczenie neuronu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.5 Sieci CP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.6 Sieci rezonansowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
III Optymalizacji topologii sieci neuronowej z wykorzystaniem
algorytmów genetycznych 17
7 Wstęp 17
8 Kodowanie genetyczne 17
8.1 Model jednostka-klaster . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.1.1 Przykład procesu translacji . . . . . . . . . . . . . . . . . . . 19
8.2 Rozszerzony model jednostka-klaster . . . . . . . . . . . . . . . . . 21
8.2.1 Przykład procesu translacji w rozszerzonym modelu jednostka-
klaster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
8.3 Restrykcyjny model jednostka-klaster . . . . . . . . . . . . . . . . . 22
9 Funkcja oceny 23
10 Przykład zastosowania 24
10.1 Test dodawania liczb 6-bitowych. . . . . . . . . . . . . . . . . . . . . 24
10.1.1 Train error. . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
10.1.2 Test error. . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
10.2 Wnioski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
IV Zastosowanie algorytmów ewolucyjnych w konstrukcji re-
kurencyjnych sieci neuronowych 28
11 Wprowadzenie 28
12 Programy ewolucyjne i algorytmy genetyczne 28
12.1 Tworzenie sieci z użyciem algorytmów genetycznych . . . . . . . . . 29
12.2 Sieci i programowanie ewolucyjne . . . . . . . . . . . . . . . . . . . 31
2
13 Algorytmy programu GNARL 31
13.1 Selekcja, replikacja i mutacje sieci . . . . . . . . . . . . . . . . . . . 32
13.1.1 Ograniczenia mutacji . . . . . . . . . . . . . . . . . . . . . 33
13.1.2 Mutacje parametryczne sieci . . . . . . . . . . . . . . . . . . 33
13.1.3 Strukturalne mutacje sieci . . . . . . . . . . . . . . . . . . . 33
13.2 Wydajność sieci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
14 Eksperyment 34
Część I
Wprowadzenie do algorytmów
genetycznych
1 Wstęp
Algortmy genetyczne są prawdopodobnie najbliższym naturalnej ewolucji modelem
obliczeniowym. Są silnym narzędziem w przeszukiwaniu przestrzeni rozwiązań pro-
blemu. Dzięki swojej sile znalazły one szerokie zastosowanie w rozwiązywaniu pro-
blemów szeregowania zadań, modelowania finansowego, optymalizacji funkcji, har-
monogramowania.
1.1 Konkretne zastosowania
" rozwiązanie problemu komiwojażera,
" podział obiektów i grafów,
" planowanie drogi w środowisku ruchomego robota,
" uczenie maszynowe (automatyczne programowanie),
" wyznaczenie ekstremum funkcji na danym przedziale,
" tworzenie sieci neuronowych.
Wynalazca algorytmów genetycznych John Holland swoją inspirację czerpał z natu-
ry. Algorytmy genetyczne składają się z populacji jednostek, z których każda posia-
da DNA reprezentowany w pamięci w postaci wektora. Na DNA jednostki określona
jest funkcja zwracająca wartość wektora, zwana stopniem przystosowania. Działanie
alogorytmu genetycznego polega na tworzeniu kolejnych pokoleń poprzez wymianę
fragmentów DNA osobników z danego pokolenia. Możliwe są także mutacje. Każde
następnie pokolenie tworzą jednostki o większym stopniu przystosowania.
Przy rozwiązywaniu konkretnych problemów każda jednostka reprezentuje punkt
w przestrzeni rozwiązań. Funkcja przystosowania zwraca dla tego punktu pewną war-
tość. Jeśli wartość ta jest wystarczająco dobra, proces jest wstrzymywany, a punkt ten
jest rozwiązaniem. Są dwie metody podejścia do wyznaczenia rozwiązania:
" zakładamy, że musimy otrzymać rozwiązanie w określonym czasie lub po okre-
ślonej liczbie iteracji (ewolucji pokoleń);
3
Rysunek 1: Rozmnażanie przez krzyżowanie
Rysunek 2: Rozmnażanie przez mutacje
" zakładamy nieskończony czas (liczbę pokoleń) i patrzymy, kiedy rozwiązanie
się ustabilizuje.
Sposób ewolucji nowego pokolenia jest także wzięty z natury. Nowe wektory (DNA) są
brane z wektorów jednostek najlepiej przystosowanych, a rozmnażanie może odbywać
się na dwa sposoby:
" przez mutację (ang. mutation) - wektor rodzica z przypadkowymi mutacjami
tworzy wektor dziecka (Rys. 1.2)
" przez krzyżowanie (ang. crossingover) - wektor dziecka jest tworzony poprzez
kombinację odcinków DNA rodziców
Krzyżowanie polega na losowym określaniu miejsc podziału w DNA rodziców oraz
na odpowiednim ich połączeniu, a w rezultacie stworzeniu potomka (lub potomków).
Jedne z najczęściej stosowanych rodzajów krzyżowania to:
" podział wektora rodziców na dwie części, z których składa się wektor dziecka
(Rys. 1.1),
" wybór z DNA rodziców więcej części z których tworzony potomek (np. dwa bity
z początku i dwa z końca DNA rodzica1 i cztery środkowe z DNA rodzica2.).
Tak właśnie z grubsza wygląda idea algorytmów genetycznych. Należy jednak zdać
sobie sprawę, że w przypadku każdego szczególnego problemu podejście musi być
nieco bardziej złożone.
Tak więc algorytm genetyczny w szczególnym wypadku powinien zawierać pięć ele-
mentów:
" podstawową reprezentację potencjalnych rozwiązań zadania, czyli odpowiedni
rodzaj DNA dla danego przypadku (niekonieczne wektor),
" sposób tworzenia początkowej populacji potencjalnych rozwiązań,
4
Rysunek 3: Krzyżowanie dwupunktowe
" funkcję przystosowania (oceniającą), która gra rolę środowiska i ocenia rozwią-
zania według ich  dopasowania ,
" podstawowe operatory, które wpływają na skład populacji dzieci,
" wartości różnych parametrów używanych w algorytmie genetycznym (rozmiar
populacji, prawdopodobieństwa użycia operatorów genetycznych itp.).
1.2 Modyfikacje algorytmów genetycznych
Okazuje się, że powyższa forma algorytmów genetycznych zwana SGA (ang. Simple
Genetic Algorithm) nie zapewnia rozwiązania dla pewnej klasy problemów, co wiąże
się między innymi ze stałą długością łańcucha DNA. Dlatego wprowadzono rozszerze-
nia do algorytmów genetycznych, zwane odtąd ESGA (ang. Extended Simple Genetic
Algorithm).
1.2.1 Rozszerzone algorytmy genetyczne (ESGA)
Algorytmy te także bazują na populacji łańcuchów bitów, jednak w przeciwieństwie do
SGA, długość łańcucha DNA może się zmieniać. Początkowa populacja jest tworzona
losowo i wszystkie osobniki są tej samej długości. Jednak po krzyżowaniu dwupunk-
towym (rys 1.2.1) długość osobników może rosnąć lub maleć.
1.2.2 Semantycznie zmienne algorytmy genetyczne (SCGA)
Są one bezpośrednim rozszerzenie prostych algorytmów genetycznych. Kodowanie ge-
notypu zostało podzielone na dwa poziomy: wyższy i niższy. Na niższy poziomie od-
bywa się rozwiązywanie problemu, na wyższym natomiast determinuje się odpowied-
nie kodowanie elementów otrzymanych z niższej warstwy, znajdowanie istotnych pod
względem wiedzy modułów i szybką ich dystrybucję, kontrolowanie wzrostu osob-
ników oraz integrację wiedzy. Niższy poziom stanowią łańcuchy bitów SGA. Wyż-
szy poziom stanowi samoadaptująca tablica symboli, w której łańcuchy bitów ulegają
5
litera zawartość string bitowy odpowiadający symbol
4 10% 0...00000 7
67 20% 0...00001 4
. . 0...00010 67
. .
7 30% 1...11111 77
Tabela 1: Początkowy alfabet oraz początkowa tablica translacji
translacji na stringi symboli. Stringi symboli służą do bezpośredniej budowy osobni-
ków definujących np. sieć neuronową.
Aby rozpocząć proces optymalizację podstawowe kroki (przed samą inicjalizacją)
muszą zostać podjęte:
1. Musi zostać zdefiniowany alfabet symboli i ich procentowa zawartość w począt-
kowej tablicy symboli. Alfabet powinien zawierać elementarne parametry, części
oraz funkcje potrzebne do zakodowania pożądanego rozwiązania. Procentowa
zawartość definuje częstość pojawiania się symboli w początkowo zainicjalizo-
wanej tablicy. Jeśli informacja o częstości występowania nie jest znana, to sym-
bole są dystrybułowane równomiernie.
2. Musi zostać określony rozmiar tablicy symboli. Minimalny rozmiar tablicy to
rozmiar alfabetu. Jeśli zostanie wybrany większy rozmiar, litery alfabetu będą
się pojawiały więcej niż raz w zainicjalizowanej tablicy translacji.
3. Wreszcie musi zostać ustalona wyjściowa liczba bitów genotypu dla pierwszych
osobników1. Definuje ona ziarnistość tablicy symboli. Czym większa liczba bi-
tów, tym więcej symboli będzie miała tablica symboli.
Pierwszą fazą optymalizacji genetycznej jest faza inicjująca. Podczas tej fazy dwie
podstawowe struktury są definiowane:
1. Początkowa populacja bitowych stringów. Rozmiar populacji, jak także długość
stringów jest definiowana przez użytkownika2. Same stringi są generowane lo-
sowo.
2. Początkowa tablica translacji. Początkowa tablica translacji jest tworzona z wy-
korzystaniem alfabetu, jego procentowych zawartości oraz ustalonej długości ta-
blicy. Litery alfabetu są rozmieszczane losowo w tablicy translacji. Po inicjali-
zacji rozpoczyna się właściwy proces ewolucji genetycznej.
Główna pętla genetyczna Pętla startuje mając populacje stringów bitowych i wyko-
nywane są następujące działania:
1. Translacja stringów bitowych na symbole. Podczas tego etapu następuje przej-
ście z niższego poziomu reprezentacji na wyższy. Rezultatem jest populacja
stringów bitowych wraz z odpowiadającymi im symbolami.
1
Liczba bitów dla osobnika w populacji może się zmieniać w trakcie ewulucji w przypadku rozszerzonych
semantycznie zmiennych algorytmów genetycznych (ESGA), ale nie w przypadku SCGA.
2
Jednak wszystkie stringi muszą mieć tę samą długość.
6
2. Wyliczenie dopasowania jednostek. Każdy symbol jest tłumaczony na postać bę-
dącą jednostką, reprezentowaną przez genotyp, wyliczane jest jego dopasowanie
i przyporządkowane genotypowi.
3. Modyfikacja tablicy translacji. Ten etap jest bardzo istotny, to właśnie tutaj od-
bywa się zmiana semantyki. Zostanie on omówiony dokładniej w dalszej części.
4. Powtórna translacja stringów bitowych na symbole.
5. Selekcja. Podobnie jak w zwykłach algorytmach genetycznych następuje selek-
cja osobników i utworzenie nowej populacji o tej samej liczebności co poprzed-
nia.
6. Krzyżowania. Następuje dwupunktowe krzyżowanie.
7. Mutacja. Następuje mutacja z określonym prawdopodobieństwem pojedyńczych
bitów.
8. Redukcja. Ostatni krok pętli genetycznej. Zgodnie ze strategią elitarności pra-
wie wszystkie oprócz najlepszych jednostek-rodziców są zastępowane przez ich
dzieci.
Modyfikacja tablicy translacji Aby zmodyfikować tablicę translacji w porządany
sposób, potrzebne jest ustawienie kilku parametrów. W pierwszym rzędzie musimy
mieć oczywiście populację stringów bitowych wraz z towarzyszącymi im symbolami
oraz wartości ich dopasowania. Następnie istotnym jest zdefiniowanie przez użytkow-
nika czterech parametrów:
1. Procent elementów w tablicy translacji, które będą zmienione.
2. Preferowana długość podłańcuchów. Ponieważ stosujemy krzyżowanie dwupunk-
towe, stringi bitowe będą zmieniać długość. Dlatego też istotnym jest podanie
pożądanej długości podłańcuchów, które mają wchodzić do tablicy translacji.
3. Utrzymanie preferowanej długości. Za pomocą tego parametru możemy wpły-
wać, jak długo będzie utrzymana stała długość podłancuchów.
4. Współczynnik mutacji dla podłańcuchów symboli. Mutacja jest wymagana, po-
nieważ zapobiega bezpowrotnej utracie informacji przez tablicę symboli.
Po tym etapie inicjalizacji można przystąpić do właściwej modyfikacji tablicy transla-
cji.
Wybór elementów z tablicy translacji Wybieramy elementy, które będą zastą-
pione nowymi podłańcuchami. Przy wyborze kierujemy się następującymi ideami:
" Zostawiamy w tabeli niezmienione te podłańcuchy, które są wykorzystywane
przez najlepsze osobniki w populacji. Prawdopodobnie zawierają one ważną in-
formacje, która nie powinna być zmieniana.
" Zastępujemy podłańcuchy, które są używane przez osobniki o niskiej jakości.
By skorzystać powyższych pomysłów dla każdego symbolu w tabeli liczony jest współ-
czynnik zwany ważnością - liczony na podstawie tego, jak często i przez jakie osobniki
jest on używany.
7
Wybór podłańcuchów Wybieramy podłańcuchy, które mają zastąpić te wcze-
śniej wybrane z tablicy translacji. Wybór przede wszystkim opiera się na wyborze z
tablicy symboli podłańcuchów o wysokiej jakości (dopasowaniu). Najpierw wybiera-
my grupę osobników będących dawcami podłańcuchów za pomocą randomizowanej
selekcji. Każdy osobnik-dawca dostarczy tylko jeden podłańcuch, którego długości i
początek musi być znany. Długość może się wahać od zera do długości całego osob-
nika - na podstawie rozkładu Gaussa długości podłańcuchów wybiera się pożądaną
długość3. Po określeniu grupy podłańcuchów są one poddane mutacji z zadanym praw-
dopodobieństwem. Po tym są one włączane do tablicy translacji.
Analiza SCGA Wprowadziły nowe, ciekawe właściwości do algorytmów genetycz-
nych, jak:
" możliwość kontrolowania wzrostu kodu genetycznego
" automatyczne definiowanie tablicy translacji zawierającej moduły (podłańcu-
chy) z wyselekcjonowaną wiedzą
" rozszorzone metody dystrybucji modułów
" izolacja modułów
" integracja wiedzy
1.2.3 Rozszerzone semantycznie zmienne algorytmy genetyczne (SCGA)
Powstały one z pomysłu połączenia rozszerzonych algorytmów genetycznych ESGA
oraz semantycznie zmiennych algorytmów genetycznych SCGA. Modyfikacje ESCGA
w porównaniu do SCGA sprowadzają się do:
" ESCGA używają podobnie jak ESGA ciągów bitowych o zmiennej długości
" parametr, który definuje preferowaną długość podłańcuchów (modułów), musi
być uaktualniany, by długość genotypu nie rosła lub malała eksponencjalnie.
Wnioski Algorytmy te wydają się być kompromisem pomiędzy ESGA a SCGA. Z
jednej strony nie osiągają one wydajności ESGA, z drugie zaś nie nadają się do klasy
problemów takich jak SCGA.
2 Przykład optymalizacji prostej funkcji za pomocą al-
gorytmów genetycznych
Funkcja ta ma postać:
f (x) = xsin(10Ąx) +1,0
Zadanie polega na znalezieniu x z przedziału [-1,2] maksymalizującego funkcje f , to
znaczy znalezieniu x0 takiego, że:
3
Wybierając różne punkty na rozkładzie Gaussa możemy sterować wzrostem lub kurczeniem się osobni-
ków.
8
f (x0) e" f (x) dla wszystkich x " [-1,2]
Funkcję f można łatwo zbadać. Należy znalez
ć zera pierwszej pochodnej f
f (x) = sin(10Ąx) + 10Ąxcos(10Ąx) = 0
co można przekształcić do
tg(10Ąx) = -10Ąx
Powyższe równanie ma oczywiście nieskończenie wiele rozwiązań
2i-1
xi = + �i i = 1, 2, ...
20
x0 = 0
2i+1
xi = - �i i = -1, -2, ...
20
przy czym �i jest ciągiem malejących liczb rzeczywistych, dążących do zera.
Metodologia konstrukcji algorytmu genetycznego dla powyższego zadania jest zgod-
na z ogólnymi pięcioma punktami opisanymi powyżej. Zauważmy także, że funkcja
f osiąga w xi lokalne maksima, gdy i jest nieparzyste, a lokalne minima, gdy i jest
parzyste. Ponieważ dziedziną funkcji jest przedział [-1,2], zatem funkcja osiąga mak-
37
simum dla x19 = + �19 = 1,85 + �19, przy czym f (x19) jest nieznacznie większe niż
20
Ą
f (1,85) = 1,85sin(18Ą + ) + 1,0 = 2,85
2
2.1 Wybór reprezentacji
Do reprezentacji rzeczywistych wartości zmiennej x użyjemy DNA w postaci wektora
binarnego. Długość tego wektora zależy od żądanej dokładności obliczenia rozwiąza-
nia, którą przykładowo przyjmiemy jako 6 cyfr po przecinku. Dziedzina zmienności x
ma długość 3. Żądana dokładność wymaga, aby przedział [-1,2] był podzielony na co
najmniej 3 * 1 000 000 równych podprzedziałów. Oznacza to, że wektor binarny musi
mieć 22 bity, gdyż
2097152 = 221 < 3000000 d" 222 = 4194304
odwzorowanie łańcucha binarnego b21b20...b0 w liczbę rzeczywistą z zakresu [-1,2]
jest proste i można je wykonać w dwóch krokach:
" przekształcenie łańcucha binarnego b21b20...b0 z systemu dwójkowego na sys-
21
tem dziesiętny: ( b21b20...b0 )2 = bi2i 10 = x ,
"
i=0
3x
" obliczenia odpowiedniej liczby rzeczywistej x : x = -1,0+ , gdzie -1.0 jest
222-1
lewą granicą dziedziny, a 3 jest długością przedziału.
Na przykład DNA (1000101110110101000111) przedstawia liczbę 0,637197, gdyż
x =(1000101110110101000111)2 = 2288976
i
3
x = -1,0 + 2288967 " = 0,637197
4194303
Oczywiście DNA
(0000000000000000000000) i (1111111111111111111111)
reprezentują odpowiednio granice dziedziny, -1,0 i 2,0.
9
2.2 Populacja początkowa
Tworzymy populację osobników, którego każde DNA jest wektorem binarnym o 22
bitach. Wszystkie bity w każdym chromosomie są wyznaczane losowo.
2.3 Funkcja oceny
Funkcja oceny eval z binarnym wektorem v jako argumentem jest równa funkcji f:
eval(v)=f(x)
przy czym wektor v reprezentuje wartość rzeczywistą x. Funkcja oceny gra rolę śro-
dowiska, oceniając potencjalne rozwiązania według ich dopasowania. Na przykład 3
wektory:
v1 = (1000101110110101000111)
v2 = (0000001110000000010000)
v3 = (1110000000111111000101)
odpowiadają wartością x1 = 0,637197, x2 = -0,958973 i x3 = 1,627888. Wobec tego
funkcja oceny przyporządkowuje im następujące oceny:
eval(v1)=f(x1)=1,586345
eval(v2)=f(x2)=0,078878
eval(v3)=f(x3)=2,250650
Oczywiście wektor DNA v3 jest z najlepszy, gdyż jego ocena jest najwyższa.
2.4 Operatory genetyczne
W fazie zmian w algorytmie genetycznym użyjemy dwóch klasycznych operatorów
genetycznych: mutacji i krzyżowania.
2.5 Parametry
W tym zadaniu użyliśmy następujących parametrów: rozmiar populacji pop_size=50,
prawdopodobieństwo krzyżowania pc = 0.25, prawdopodobieństwo mutacji pm = 0,01.
2.6 Wyniki obliczeń
W tablicy 1.1 przedstawiono numery pokoleń, w których zanotowano poprawę funkcji
oceny, oraz wartość tej funkcji. Najlepszy osobnik w 150 pokoleniu miał postać
vmax = (1111001101000100000101)
co odpowiada wartości xmax = 1,850773.
10
Numer pokolenia Funkcja oceny
1 1,441962
6 2,250003
8 2,250283
9 2,250284
10 2,250363
12 2,328077
39 2,344251
40 2,344251
51 2,738930
99 2,849246
137 2,850217
145 2,850227
Tabela 2: Wyniki po 150 pokoleniach
3 Teoretyczne podstawy algorytmów genetycznych - dla-
czego one działają
Teoretyczne podstawy algorytmów genetycznych opierają się na reprezentacji rozwią-
zań za pomocą łańcuchów binarnych i na pojęciu schematów - szablonie pozwalającym
badać prawdopodobieństwa między chromosomami. Schemat buduje się wprowadza-
jąc symbol nieistotne (*) do struktury DNA. Schemat reprezentuje wszystkie łańcuchy
(hiperpłaszczyznę lub podzbiór przestrzeni przeszukiwań), które zgadzają się z nim na
wszystkich pozycjach innych niż  * .
Wez
my pod uwagę łańcuch i schemat o długości 10. Do schematu (*111100100)
pasują dwa łańcuchy
{(0111100100), (1111100100)}
a do schematu (*1*1100100) cztery łańcuchy
{(0101100100), (0111100100), (1101100100), (1111100100)}
Należy oczywiście zauważyć, że schemat (1001110001) reprezentuje tylko jeden łań-
cuch, a schemat (**********) reprezentuje wszystkie łańcuchy o długości 10. Do każ-
dego łańcucha o długości m pasuje 2m schematów, a wszystkich możliwych schematów
istnieje 3m. Różne schematy mają różne właściwości. Dlatego też wprowadza się dwie
istotne właściwości schematu: rząd i długość definiującą.
Rzędem schematu S (oznaczanym przez o(S)) nazywamy liczbę pozycji 0 lub 1,
to znaczy pozycji ustalonych (pozycji nie nieistotnych) w schemacie. Jest to po pro-
stu długość szablonu minus liczba symboli nieistotne (*). Rząd określa specyficzność
schematu. Pojęcie rzędu schematu jest użyteczne przy obliczaniu prawdopodobieństwa
przeżycia schematu po mutacji.
Długość definiująca schematu S (oznaczana przez �(S)) jest odległością między
pierwszą a ostatnią ustaloną pozycją schematu. Określa ona zwartość informacji zawar-
tej w schemacie. Pojęcie długości definiującej schematu jest użyteczne przy obliczaniu
prawdopodobieństwa przeżycia po krzyżowaniu. Jak już było to powiedziane symulo-
wany proces ewolucyjny algorytmu genetycznego składa się z czterech powtarzających
się po sobie kroków:
11
" t �! t + 1
" wyselekcjonuj P(t) z P(t-1)
" zastosuj operatory mieszania do P(t)
" oceń P(t)
Pierwszy krok przesuwa zegar ewolucji o jednostkę dalej. W czasie ostatniego kroku
oceniamy bieżącą populację. Główne przemiany zachodzą w pozostałych krokach cy-
klu ewolucji: selekcji i mieszania. Mając daną populację i pewien wybrany ze względu
na wysoką ocenę szablon, możemy obliczyć dopasowanie każdego łańcucha DNA do
tego schematu. Możemy także obliczyć średnie dopasowanie całej populacji do sche-
matu. W następnym kroku tworzy się pośrednią populację, do której łańcuchy są kopio-
wane zależnie od stopnia dopasowania. Im lepszy schemat, tym więcej łańcuchów jest
kopiowanych - wzrost liczby łańcuchów jest wykładniczy. Jednak sama selekcja nie
wprowadza żadnego nowego punktu z przeszukiwanej przestrzeni. W trakcie selekcji
po prostu kopiuje się pewne łańcuchy, tworząc populację pośrednią. Tak więc dopie-
ro drugi krok cyklu ewolucyjnego, rekombinacji, odpowiada za wprowadzenie nowych
osobników do populacji. Dokonuję się to za pomocą operatorów genetycznych krzyżo-
wania i mutacji, omawianych już wcześniej. Jednak mogą one doprowadzić do znisz-
czenia pożądanego schematu. I tutaj z pomocą przychodzi nam rząd schematu o(S)
oraz długość definiująca schematu �(S). Im są one mniejsze, tym większe prawdopo-
dobieństwo przetrwania schematu. Jest to logiczne - bardziej zwarty schemat trudniej
przeciąć przez wybór punkt podziału w operatorze krzyżowania, a krótszy trudniej
zmienić przez operator mutacji.Wynikiem rozważań jest zdefiniowanie Twierdzenia o
schematach:
TWIERDZENIE 1
Krótkie, niskiego rzędu i oceniane powyżej średniej schematy uzyskują
wykładniczo
rosnącą liczbę łańcuchów w kolejnych pokoleniach.
Z twierdzenia tego wynika wprost, że algorytmy genetyczne badają przeszukiwaną
przestrzeń przez krótkie, niskiego rzędu schematy, które z kolei są używane do wymia-
ny informacji genetycznej podczas krzyżowania. Definiowana jest także w literaturze
Hipoteza p blokach budujących:
HIPOTEZA 1
Algorytm genetyczny poszukuje działania zbliżonego do optymalnego
przez zestawianie krótkich , niskiego rzędu schematów o dużej wydajności
działania, zwanych blokami budującymi.
Chociaż prowadzone są badania w celu udowodnienia powyższej hipotezy, to w więk-
szości zastosowań polega się głównie na wynikach empirycznych. Jednak jest ona jak
na razie tylko aktem wiary, który dla niektórych zadań może być łatwo naruszony.
Przypuśćmy, że mamy dwa krótkie schematy o niskim rzędzie
S1=(111********) i
S2=(*********11)
są oba oceniane powyżej średniej, ale ich kombinacja
12
S3=(111******11)
ma dopasowanie gorsze niż
S4=(000******00).
Załóżmy dalej, że optymalny łańcuchem jest s0=(11111111111) (pasuje on do S3). Al-
gorytm genetyczny może mieć trudności w zbiegnięciu się do s0, gdyż może się zbie-
gać do punktów w rodzaju (00011111100). Jest to nazywane zawodem. Pewne bloki
budujące (krótkie schematy o niskim rzędzie) mogą z
le ukierunkować algorytm i spo-
wodować jego zbieżność do punktów suboptymalnych. Zjawisko to jest silnie połączo-
ne z pojęciem epistazy4, które dla algorytmu genetycznego oznacza silne uzależnienie
miedzy genami w chromosomie. Innymi słowy, epistaza podaje, na ile wpływ jednego
genu na dopasowanie łańcucha zależy od wartości innych genów. Dla danego zada-
nia wysoka epistaza oznacza, że bloki budujące nie mogą się formować i w rezultacie
zadanie jest zawodne.
Istnieją trzy sposoby walki z zawodem. W pierwszy zakłada się początkową umie-
jętność zakodowania funkcji celu w odpowiedni sposób, aby uzyskać  ścisłe bloki
budujące. W drugim sposobie używa się trzeciego operatora genetycznego, inwersji.
Pojedyńcza inwersja jest podobnie jak mutacja operatorem jednoargumentowym. Wy-
biera ona dwa punkty w łańcuchu i odwraca kolejność bitów między tymi łańcuchami,
pamiętając jednak  znaczenie bitów. oznacza to, że musimy rozpoznawać bity w łań-
cuchu. Robimy to przez utrzymanie bitów razem z zapisem ich początkowej pozycji.
Na przykład łańcuch
s=((1,0)(2,0)(3,0)| (4,1)(5,1)(6,0)(7,1)|(8,0)(9,0)(10,0)(11,1))
z dwoma zaznaczonymi punktami po inwersji staje się łańcuchem
s =((1,0)(2,0)(3,0)| (7,1)(6,0)(5,1)(4,1)|(8,0)(9,0)(10,0)(11,1))
Algorytm genetyczny z inwersją, jako jednym z operatorów, poszukuje najlepszego
ustawienia bitów do formowania bloków budujących. Trzeci sposób walki z zawodem
zaproponowano ostatnio - jest to nieporządny algorytm genetyczny5.
Część II
Wstęp do sieci neuronowych
4 Wprowadzenie
W tej część projektu przedstawimy ogólną charakterystykę sieci neuronowych, rodzaje,
zasadę działania i zastosowania.
Sieci neuronowe są elektronicznym (informatycznym) modelem ludzkiego mózgu.
Model ten składa się z modeli ludzkich komórek nerwowych. Rozważamy różne ro-
dzaje modeli realizowanych software owo lub hardware owo (procesory neuronowe).
4
Genetycy używają terminu epistaza do opisu efektu maskowania lub przełączania. Gen jest epistatyczny,
jeżeli jego obecność tłumi efekt innego genu znajdującego się w innym miejscu.
5
Jednak nie będzie on w tej pracy omawiany
13
Komórki te są tak, jak w mózgu połączone ze sobą, a pomiędzy nimi zachodzą pewne
relacje determinowane sygnałami (wartościami zmiennych). Sieci neuronowe mogą za-
wierać od kilkuset do kilku milionów neuronów w zależności od rodzaju zastosowań.
Ilość połączeń pomiędzy neuronami od 4*105 do 1.5*106. Szybkość impulsu prze-
chodzącego pomiędzy neuronami (przełączeń) od 3*105 do 6*106. Ogólny schemat
zastosowania sieci neuronowej:
" uczenie sieci - wyróżniamy kilka metod uczenia sieci
" zastosowanie sieci wykorzystując zgromadzoną uprzednio wiedzę
5 Zastosowanie sieci neuronowych
Najprostszym zastosowaniem sieci neuronowej może być prosty program w C/C++
zawierający matrycę kilku tysięcy neuronów rozpoznający uprzednio zadane kształ-
ty figur geometrycznych na podstawie podanego fragmentu. Inne, bardziej poważne
zastosowania sieci neuronowych:
" badania psychiatryczne
" prognozy giełdowe, cen, sprzedaży
" sterowanie procesów przemysłowych
" rozpoznawanie tekstu
" dobór pracowników
Ponadto
" analiza danych
" kojarzenie danych
" filtracja sygnałów
" optymalizacja (poszukiwanie optymalnego rozwiązania)
6 Rodzaje sieci neuronowych
Do określonych zadań stosujemy określony rodzaj sieci neuronowych. Obok najpopu-
larniejszych typów sieci istnieją także różne ich modyfikacje. Modyfikacje opracowuje
np. firma, która prowadzi badania nad określonym zastosowaniem sieci. W tym celu
firma tworzy własną sieć, która realizuje dany cel najbardziej efektywnie. Podstawowe
rodzaje sieci neuronowych:
" liniowe
" nieliniowe
" CP
" rezonansowe
" modyfikacje
W dokumencie tym dokładniej opiszemy działanie sieci liniowych i nieliniowych, po-
zostałe omówimy pobieżnie.
14
Rysunek 4: Naturalna komórka nerwowa
6.1 Realizacja sieci neuronowych
Sieci neuronowe są realizowane jako modele matematyczne lub symulacyjne. Możemy
zrealizować sieć neuronową software owo, lub hardware owo. Współcześnie istnieją
neuroprocesory np. DELTA, bądz
systemy komputerowe bazujące na dedykowanym
oprogramowaniu. Istnieją też symulatory sieci bądz
programy pozwalające je zastoso-
wać. Niektóre aplikacje:
" ANSkit - zestaw programów pod MS-DOSem do projektowania i modelowania
sieci
" AXON - język do opisu i projektowania sieci neuronowych dla komputerów
ANZA
" Cognitron - system do projektowania, modelowania i uruchamiania sieci neuro-
nowych
Neurokomputery:
" ANZA - kooprocesor do neurokomputingu, tworzący z komputera IBM specja-
lizowaną stację roboczą
" NeuroComputer II - stacja robocza zbudowana w oparciu o procesor 68030 (33
MHz)
" Delta II - procesor stosowany do obliczeń sieci neuronowych.
6.2 Liniowe i nieliniowe sieci neuronowe
Liniowe sieci neuronowe charakteryzują się tym, że neuron przetważa informację w
sposób liniowy. Przykładami sieci liniowych mogą być ADALINE i MADALINE.
6.3 Struktura neuronu
Od tej chwili perceptronem nazywać będziemy model sztucznej komórki nerwowej.
Podstawowe jego elementy to:
" sygnały wejściowe X1...Xn
" wagi W1...Wn
15
Rysunek 5: Sztuczna komórka nerwowa
16
" sygnał wyjściowy y
" komparator
" funkcja progowa
Sygnały wejściowe i wagi prezentujemy jako wektory w n-wymiarowych przestrze-
niach sygnałów i wag. X=T , W=T . Równaniem neuronu
będziemy nazywać iloczyn skalarny y=W*X, bądz
iloczyn wektorowy y=WT X. Sy-
gnał wyjściowy neuronu będzie tym większy, im bardziej położenie wektora X będzie
przypominać położenie wektora W.
6.4 Uczenie neuronu
W procesie uczenia neuronu biorą udział dwa dodatkowe elementy - procesor zmia-
ny wag i detektor błędu (komparator). Taki neuron nazywamy ADALINE (ADAptive
LINear Element). Zadanie stawiane neuronowi polega na tym, by sygnał wyjściowy y
był związany z sygnałami wejściowymi X pewną zależnością funkcyjną y=f(X). Pod-
stawowym algorytmem uczenia jest tzw. reguła DELTA. Zakłada ona, że z każdym
wektorem sygnałów X do neuronu podawany jest sygnał z, stanowiący wymaganą od-
powiedz
neuronu na sygnał X. Neuron odpowiada na sygnał X sygnałem y=W*X,
przy czym jeśli neuron nie jest nauczony, sygnał ten jest inny, niż wymagany (y =z).

Wewnątrz ADALINE istnieje komparator oceniający wielkość błędu �=z-y. Składa się
on z inwertora (dla uzyskania sygnału -y) oraz sumatora. Na podstawie sygnału błę-
du � oraz wektorawejściowego X możliwe jest takie skorygowanie wektora wag W,
by neuron lepiej realizował zadaną funkcję y=f(X). Nowy wektor wag W obliczany
jest ze wzoru W =W+��X, gdzie � jest współczynnikiem liczbowym decydującym o
szybkości uczenia.
Rozważmy wielkość zwaną wypadkowym pobudzeniem neuronu e= wixi. Ważną
"
rolę w funkcjonowaniu neuronu odgrywa funkcja � określająca związek pomiędzy sy-
gnałem wypadkowego pobudzenia neuronu e a odpowiedzią y zwaną activation func-
tion (funkcja progowa). W klasycznym perceptronie funkcja ta ma postać progową:
�(e)={1 gdy ee"0, 0 gdy ed"0
Zależnie od postaci przyjętej funkcji �(e) sygnał y można rozpatrywać jako binar-
ny (model liniowy) y"{0,1} lub bipolarny (model nieliniowy) y"{-1,1}. Jako że funk-
cja e jest funkcją w Rn, to różnice pomiędzy tymi dwoma podejściami rozpatrujemy
jako zjawiska matematyczne w przestrzeni Rn . Z tego wynika, że w modelu linio-
wym funkcja y przyjmuje wartości true lub false, a w nieliniowym są to dwa obszary.
Przykłady nieliniowych funkcji progowych:
1
�(e)=
1+exp(-�e)
�(e)=tgh(�e)
Istnieją inne funkcje progowe. Są one stosowane w zależności od rozwiązywanego
problemu.
W procesie uczenia pojawia się też problem doboru parametrów oraz metody ucze-
nia. Zagadnienia te szerzej opisane są w [1].
W dalszej części omówimy pobieżnie inne rodzaje sieci neuronowych.
6.5 Sieci CP
Opisane uprzednio sieci zalicza się do sieci z wsteczną propagacją błędu. Uczenie ich
jest pracochłonne, więc pojawiły się propozycje sieci o podobnym przeznaczeniu i
17
Rysunek 6: Przykład nieliniowej funkcji progowej
sprawniejszym działaniu. Jedną z najbardziej znanych jest propozycja Roberta Hecht-
Nielsena, określana jako sieć Counter-Propagation. Sieć ta stanowi kompilację sieci
Grossberga i Kohonena. Sieć ta stosunkowo szybko się uczy i ma nieograniczony za-
kres możliwych odwzorowań pomiędzy wektorem X i sygnałem y. Sieć CP składa się z
warstwy wejściowej (Kohonena) i wyjściowej (Grossberga). Sieć CP może być stoso-
wana w zadaniach praktycznych takich jak ustalanie harmonogramu dnia na podstawie
ilości pilnej pracy do wykonania oraz stopnia uczuć rodzinnych.
6.6 Sieci rezonansowe
Do tego rodzaju sieci należą ART1 i ART2, (Adaptive Resonance Theory). ART1 służy
do analizy obrazów binarnych, ART2 do analogowych.
Część III
Optymalizacji topologii sieci
neuronowej z wykorzystaniem
algorytmów genetycznych
7 Wstęp
Sieci neuronowe feedforward, szczególnie sieci modularne6 dostarczają rozwiązania
dla wielu klas problemów. Jednak wybór odpowiednich parametrów dla algorytmów
uczących jak także wybór danych do treningu oraz topologii7 sieci nie jest sprawą pro-
stą. Wybór odpowiedniej topologii jest szczególnie ważny, ponieważ nieodpowiednia
topologia nie pozwoli sieci na rozwiązania problemu. Sieć albo nie będzie w stanie
nauczyć się danych wejściwych, albo nie będzie w stanie uogólniać wprowadzanych
danych. Sieć o najmniejszej kompleksowości8, potrafiąca uczyć sie szybko i dobrze
uogólniająca to optimum, jednak trudno znalez
ć odpowiednią dla danego rozwiązania
topologię ręcznie. I tutaj z pomocą mogą nam przyjść algorytmy genetyczne.
6
Sieci modularne mają kilka zalet w porównaniu z sieciami niemodularnymi jak mniejsza komplekso-
wość, przestrzeń rozwiązań ma mniej lokalnych minimów, są mniej podatne na efekt  przeuczenia (ang.
overlearning).
7
Przez topologie sieci rozumiemy liczbę neuronów w sieci oraz sposób ich połączenia.
8
Kompleksowość sieci to liczba neuronów oraz połączeń w sieci.
18
8 Kodowanie genetyczne
Genetyczne kodowanie sieci może być klasyfikowane na dwie kategorie - bezpośrednie
kodowanie oraz pośrednie kodowanie.
Bezpośrednie kodowanie (ang. Direct Encoding Scheme DES) opiera się na ideii,
że sieć neuronowa jest całkowicie definiowana przez genotyp. Oznacza to, że każdy
neuron w sieci oraz każde połączenie wraz z odpowiadającą mu wagą jest bezpośred-
nio zakodowane w genotypie o postaci np. matrycy. Zaletą tego podejścia jest łatwość
określenia jakości sieci - obliczenia mogą być dokonane bezpośrednio. I na tym zalety
tego kodowania się kończą. Rozrost sieci powoduje eksponencjalny wzrost genotypu,
ponieważ każdy dodatkowy neuron oraz wszystkie jego połączenia muszą być w nim
reprezentowane.To powoduje ograniczenie uzywania DES do małych sieci. Drugim
problemem jest problem bloków funkcjonalnych9.
Kodowanie pośrednie (ang. Indirect Encoding Scheme IES) jest bardziej zwarte
niż DES i bliższe biologicznemu modelowi. Pomysłem na którym oparto to kodowanie
jest zakodowanie tylko najbardziej istotnych elementów sieci neuronowej w genotypie
i budowanie sieci neuronowej z tych elementów za pomocą predefiniowanych zasad.
IES zostały podzialone na trzy podklasy:
" Kodowanie w postaci  planu (ang. blueprint), w którym zakodowane są istot-
ne dane do zbudowania połączeń sieci neuronowej oraz parametry istotne dla
algorytmu genetycznego.
" Kodowanie zasad tworzenia sieci neuronowej wewnątrz genotypu (rekursywnie).
" Fraktalne kodowanie połączeń.
Ogólnie rzecz biorąc kodowanie pośrednie IES jest bardziej zaawansowaną strategią
kodowania, jednak w pracy z której korzystaliśmy [3] zastosowano inne podejście.
Oparte było ono na zakodowaniu struktury sieci w strukturze przypominającej pro-
gram, definującej proces wzrostu struktury sieci od poziomu pustego. Zostały wyróż-
nione dwa poziomy kodowania struktury sieci neuronowej:
1. liczba neuronów w warstwie wejściowej, ukrytej oraz wyjściowej
2. połączenia pomiędzy neuronami10.
Neurony oraz ich pozycja jest kodowana w genotypie, natomiast strukturę połą-
czeń, czyli rzeczywistą strukturę sieci koduje się na wyższym poziomie. Prowadzi nas
to do modelu jednostka-klaster11 (ang. Unit-Cluster Model).
8.1 Model jednostka-klaster
Model ten zapewnia równorzędne traktowanie jednostki w obrębie klastra. Jednostki
będące w jednym klastrze są kodowane jedna obok drugiej w genotypie. Połączenia
pomiędzy klastrami są generowane w trakcie dekodowanie osobnika z genotypu. Pro-
wadzi nas to do systemu opartego o rejest poziomu oraz trzyliterowy alfabet. Rejestr
9
Polega on na trudności w znalezieniu bloków funkcjonalnych w genotypie i zwarty ich zakodowaniu.
10
Mowa oczywiście o sieci neuronowych feedforward, bo taki rodzaj sieci będzie tu stosowany.
11
Gdzie jako jednostkę traktujemy neuron w sieci neuronowej.
19
poziomu (dodatnia liczba całkowita) określa poziom, an którym klaster będzie utwo-
rzony. Początkowo jest on inicjowany liczbą 0, wskazującą że jesteśmy w warstwie
wejściowej12. Alfabet jest następujący: {U, >, < }
Te trzy litery są interpretowane w sposób następujący:
" U
tworzy jednostkę (ang. unit)
" >
inkrementuje rejestr poziomu o jeden ; przed inkrementacją automatycz-
nie tworzy wszystkie jednostki U, których ciąg nie był przedzielony inną
literą niż U, tworząc klaster, łączy ten klaster z poprzednim; jeśli nie ma
takiego klastra (rejestr poziomu =0), to klaster bieżący będzie przypisany
do warstwy wejściowej.
" <
dekrementuje rejestr poziomu o jeden; jeśli wartość rejestr jest większa
od zera to powtarza się podobna procedura jak poprzednio; jeśli wartość
rejestru jest równa 0, to klaster bieżący będzie przypisany do warstwy wej-
ściowej.
8.1.1 Przykład procesu translacji
Poddano translacji genotyp postaci (UU>UUUU>UU). Proces translacji obrazuje ry-
sunek 7. Poniżej znajdują się objaśnienia procesu translacji:
1. rejestr poziomu jest ustawiany na 0; UU tworzy dwie jednostki
2. > inkrementuje rejestr poziomu o jeden i definuje dwie poprzednio utworzone
jednostki jako klaster. Ponieważ jest to pierwszy stworzony klaster, to wszystkie
neurony zostaną w końcowym etapie zadeklarowane jako warstwa wejściowa.
3. rejestr poziomu ustawiany jest na 0; UUUU tworzy cztery jednostki
4. > inkrementuje rejestr poziomu o jeden i definuje cztery poprzednio utworzo-
ne jednostki jako klaster. Dokonuje pełnego połączenia tego klastra do klastra
stworzonego na niższym poziomie
5. rejestr poziomu ustawiany jest na 2; UU tworzy dwie jednostki
6. osiągnięcie końca stringu;
" definuje się ostatnio stworzone jednostki jako klaster i dokonuje pełnego połą-
czenia tego klastra do klastra stworzonego na niższym poziomie
" definuje się wszystkie jednostki, które nie mają połączenia z jednostkami wej-
ściowymi i wyjściowymi
" przypisuje się każdy klaster do odpowiedniej warstwy
12
Choć nic nie przeszkadza, aby zdefiniować warstwę wyjściową jako poziom 0.
20
Rysunek 7: Proces translacji genotypu (UU>UUUU>UU)
21
Rysunek 8: Przykład topologii, która nie może być zakodowana w modelu jednostka-
klaster.
Wnioski Zalety modelu jednostka-klaster:
" pozwala na utrzymanie małego alfabetu i prowadzi bezpośrednio do topologii
sieci neuronowej
" wzrost gonotypu jest liniowy
" używana jest względna pozycja jednostki w genotypie, przez co mozna budować
sieci modularne13.
Wadą jest możliwość budowania tylko topoligii, w których klastry są połączone
tylko z jednym innym klastrem.
Dlatego też potrzebne było rozszerzenie modelu jednostka-klaster.
8.2 Rozszerzony model jednostka-klaster
Rozszerzony model jednostka-klaster (ang. Extended Unit-Claster Model) postał po-
przez dodanie do poprzedniego modelu rejestru łączącego oraz dwóch nowych liter al-
fabetu. Rejest łączący służy do pamiętania klastra, do którego ma zostać zrealizowane
połączenie. Połączenia wykonywane są zawsze od właśnie utworzonego klastra. Rejest
łączący jest zawsze reinicjalizowany w chwili utworzenia nowego klastra i wskazuje na
ostatnio utworzony klaster, będący przynajmniej jeden poziom niżej niż klaster tworzo-
ny aktualnie. Natomiast litery dodane do alfabetu używają omawianego powyżej rejestr
łączącego. Mają one następujące znaczenie:
" c
wymusza utworzenie połączenia do klastra, na który wskazuje rejestr łą-
czący
" -
13
Jednak nie wszystkie klasy sieci modularnych
22
dekrementuje wartość rejestru łączącego. Po dekrementacji rejestr wska-
zuje na klaster utworzony wcześniej, położony na poziomie niższym niż
klaster bieżący. Jeśli taki klaster nie istniej, to nie jest podejmowana żada-
na akcja i rejestr nie rejest już więcej dekrementowany. Jeśli nie ma klastra
spełniającego wymaganie14 to rejest łączący ustawiany jest na  połączenie
niemożliwe .
8.2.1 Przykład procesu translacji w rozszerzonym modelu jednostka-klaster
Poddano translacji genotypu postaci (UU>UU>Uc<UU>Uc-c-c). Poniżej znaj-
duje się przykład jak używane są dodatkowe litery w procesie translacji:
1. inicjalizacja rejestrów ; rejestr poziomu=0, rejestr łączący= połączenie nie-
możliwe
2. UU ; rejestr poziomu=0, rejestr łączący= połączenie niemożliwe , klaster 1
utworzony
3. > ; rejestr poziomu=0, rejestr łączący= połączenie niemożliwe
4. UU ; rejestr poziomu=1, rejestr łączący= połączenie niemożliwe , klaster 2
utworzony
5. > ; rejestr poziomu=2, rejestr łączący= połączenie niemożliwe
6. U ; rejestr poziomu=2, rejestr łączący=115, klaster 3 utworzony
7. c ; rejestr poziomu=2, rejestr łączący=1, połączenie klastrów 1 i 3
8. << ; rejestr poziomu=0, rejestr łączący=1
9. UU ; rejestr poziomu=0, rejestr łączący= połączenie niemożliwe , klaster 4
utworzony
10. > ; rejestr poziomu=1, rejestr łączący= połączenie niemożliwe
11. UU ; rejestr poziomu=1, rejestr łączący=1, klaster 5 utworzony
12. > ; rejestr poziomu=2, rejestr łączący=1
13. U ; rejestr poziomu=2, rejestr łączący=4, klaster 6 utworzony
14. c ; rejestr poziomu=2, rejestr łączący=4, połączenie klastrów 4 i 6
15. - ; rejestr poziomu=2, rejestr łączący=2
16. c ; rejestr poziomu=2, rejestr łączący=2, połączenie klastrów 2 i 6
17. - ; rejestr poziomu=2, rejestr łączący=1
18. c ; rejestr poziomu=2, rejestr łączący=1, połączenie klastrów 1 i 6
14
To znaczy jeśli licznik poziomu jest na 0 i to nie ma klastra na niższym poziomie, bo nie ma niższego
poziomu.
15
Numer oznacza klaster, do którego może być ustanowione połączenia
23
Rysunek 9: Proces translacji genotypu (UU>UU>Uc<UU>Uc-c-c).
8.3 Restrykcyjny model jednostka-klaster
Rozszerzony model jednostka-klaster wraz z SCGA dobrze spełnia zadanie kodowania
sieci neuronowych feedforward. Jednak w praktyce można ten model uprościć, gdyż
liczba jednostek wejściowych i wyjściowych jest znana. I tę informacje trzeba udostęp-
nić algorytmowi genetycznemu. Są dwa podejścia:
1. Zakodowanie wiedzy w funkcji oceny .
2. Definicja liczby jednostek wejściowych i wyjściowych i genetyczne poszukiwanie
topologii sieci warstw ukrytych.
Wybrano drugie podejście, ponieważ można ręcznie ustalić liczbę jednostek wejścio-
wych i wyjściowych. Nie trzeba wtedy w czasie pracy algorytmu genetycznego elimi-
nować osobników o nieodpowiedniej liczbie wejść i wyjść, co oszczędza czas.
9 Funkcja oceny
Wybór odpowiedniej funkcji jest bardzo istotny w mechaniz
mie genetycznego budo-
wania sieci neuronowych. Wybór odpowiedniej funkcji zależy od problemu, którego
rozwiązania poszukujemy. Dobrze jest oprzeć funkcje oceny na pomiarze parametrów
błędu uczenia sieci (wybrano algorytm wstecznej propagacji), niż na ocenie samej to-
pologii sieci. Parametry takie jak liczba jednostek w sieci, liczba połączeń w sieci,
train error, test error pojedyńczo nie są najlepszymi funkcjami oceny. Funkcjonując
oddzielnie tworzą, funkcje oceny sterujące różnymi parametrami sieci:
24
" liczba jednostek w sieci
Jako oddzielna funkcja oceny mało przydatna. Sprawdza się przy rozsze-
rzonym modelu jednostka-klaster, przy odrzucaniu sieci o nieodpowied-
niej liczbie neuronów wejściowych i wyjściowych. Może też służyć do
sterowania liczbą jednostek w warstwie ukrytej w celu znalezienia sieci
o najmniejszej wielkości. Jest porządane znalez
ć sieć rozwiązującej pro-
blem o minimalnej topologii, gdyż taka sieć lepiej uogólnia dane wejścio-
we.
" liczba połączeń w sieci
Jako oddzielna funkcja oceny także mało przydatna. Jedynym chyba zasto-
sowaniem jest użycie do preferowania osobników o odpowiedniej (mniej-
szej/większej) liczbie połączeń. Jednak trzeba skądś posiadać wiedzę o
porządanej liczbie połączeń.
" train error
Train error w metodzie nauczania ze wsteczną propagacją błędu mierzy
możliwość nauczenia się przez sieć podawanych danych. Może być sama
w sobie funkcją oceny. Dla różnych sieci można porównywać: train error
po określonej liczbie pokoleń lub po określonym czasie.
" test error
Test error służy do oceny możliwości uogólniania sieci neuronowej. Może
być używany jako pojedyńcza funkcja oceny. Zaletą jest fakt bezpośred-
niego testowania generalizacji sieci , a do tego właśnie przeznaczona jest
sieć neuronowa.
Próbowano zbudować funkcję oceny jako sumę tych parametrów. Jednym z pomysłów
było zastosowanie wielomianu postaci:
f = a0 " (neurony)n0 + a1 " (połączenia)n1 + a2 " (train_error)n2 + a3 "
(test_error)n3
Jednak problemem jest dobranie wartości ai oraz ni, zależnych od danego problemu
oraz poszukiwanego rozwiązania. Stosuje się także inne kombinacje, jak:
" kombinacja train error, liczby jednostek ukrytych oraz liczby połączeń
Taka funkcja oceny łatwo wykrywa, gdy sieć jest zbyt duża i nie genera-
lizuje. Przydatna, gdy nie chcemy, by sieć tylko pamiętała wprowadzone
dane.
" kombinacja train error i test error
Wybieramy wtedy, gdy chcemy wykrywać problemy z  przeuczeniem
(ang. overlearning) sieci.
Możliwa jest także zmiana funkcji oceny w czasie procesu ewolucji, np. na początku
będzie nią train error, a potem test error.
25
Rysunek 10: Wykres ewolucji dopasowanie najlepszych osobników w procesie uczenia
6 bitowego dodawania, dla funkcji oceny train error.
10 Przykład zastosowania
10.1 Test dodawania liczb 6-bitowych.
Zadaniem było znalezienie sieci, która będzie w stanie dodać dwie liczby zakodowane
w naturalnym kodzie binarnym. Rezultatem dodawania jest 7-bitowa liczba w natural-
nym kodzie binarnym.
Użyto dwóch funkcji oceny: kwadratu train error oraz kwadratu test error. Używa-
jąc pierwszej z nich kierujemy ewolucją procesu w kierunku stworzenia sieci neurono-
wej, która nauczy się problemu. Natomiast w drugim przypadku zmusimy SCGA do
stworzenia sieci, która będzie dobrze generalizować. Każda z nich zostanie przetesto-
wana oddzielnie. Każda sieć była uczona przez 40 tur w trybie wstecznej propagacji
błędu, na losowo wybranych 500 wzorcach wejściowych/wyjściowych.
10.1.1 Train error.
Jak zostało już wspomniane, wybierając train error jako funkcję oceny, sterujemy two-
rzeniem sieci neuronowej w kierunku topologii, która może szubko nauczyć się danych
treningowych. Punkt konwergencji16 w tym teście został znaleziony w dwóch niezależ-
nych przebiegach w generacji 27 i 32. Wykres 10 pokazuje jakość najlepszych osob-
ników w procesie ewolucji. Wykres pokazuje, że algorytm genetyczny jest w stanie
przeprowadzić szybką ewolucję sieci neuronowej w krótkim czasie. Natomiast rysu-
nek 11 obrazuje ewolucję struktury sieci neuronowe pierwszego przebiegu, pokazując
kilka kolejnych struktur o najlepszym dopasowaniu. Wyrażenie wyższego stopnia ko-
dowania genetycznego opisujące najlepszego osobnika (32 generacja) miało postać:
cUU-16
Punkt w procesie ewolucji, po którym nie ma dużych różnić w przystosowaniu najlepszych osobników
znalezionych póz
niej.
26
Rysunek 11: Ewolucja topologii osobników dla funkcji oceny train error.
-UcU>UUcUUcU-UUUcUUU<>U<--Należy zauwżyć, iż podobna struktura została uzyskana także w drugim przebiegu.
Algorytm SCGA najpierw rozbudowuje pojedynczą warstwę przez co znacząco
może poprawić dopasowanie osobnika, jednak rozwiązania obu przebiegów są wielo-
warstwowe. Prowadzi to do konkluzji, że po przekroczeniu p[ewnego stopnia ewolucji
wielowarstwowe struktóry są jednak niezbędne, by poprawić możliwości nauczania
sieci. Oba rozwiązania wyglądają podobnie, składają się z trzech podsieci: jadna duża
jednowarstwowa podsieć i dwie małe wielowarstwowe podsieci z dwiema lub trzema
warstwami.
10.1.2 Test error.
Funkcja oceny oparta na powyższym wskaz
niku wspiera budowanie sieci, które do-
brze generalizują dane. W tym teście punkt konwergencji został osiągnięty w 38 i 43
generacji dla pierwszego i drugiego przebiegu. Rysunek 12 pokazuje ewolucję dopa-
sowania osobników obu przebiegów. Ten test obrazuje zdolność algorytmu SCGA do
tworzenia sieci neuronowych mających zdolność generalizacji w przypadku nauczania
dodawania 6-bitowych liczb. Kilka najlepszych osobników uzyskiwanych w trakcie
działania algorytmu genetycznego zostało pokazanych na rysunku 13. Najlepszy osob-
nik uzyskany w pierwszym przebiegu, a ujęty na rysunku 13 ma następujące kodowanie
genetyczne:
U-UUcUUU-UUU-UU-cUUUUcUU UUUUcU-
UUUUUUUUUUcW porównaniu do testu, gdzie funkcją oceny był train error, widać że obecnie algorytm
genetyczny faworyzuje raczej strukturę wielowarstwową sieci neuronowej. Jednak i tak
podstawowa struktura oparta jest na dużej jednowarstwowej podsieci i dodatkowych
wielowarstwowych podsieciach.
27
Rysunek 12: Wykres ewolucji dopasowanie najlepszych osobników w procesie uczenia
6 bitowego dodawania, dla funkcji oceny test error.
Rysunek 13: Ewolucja topologii osobników dla funkcji oceny test error.
28
10.2 Wnioski
W obu przykładach 6-bitowego dodawania znalezione rozwiązanie nie było perfekcyj-
ne. Wartość test error, jakkolwiek znacząco mniejsza niż na początku ewolucji, jest
ciągle większa od 1000 i przez to jest możliewe, że pewne wzorce nie zostaną prawi-
dłowo rozpoznane.
Część IV
Zastosowanie algorytmów
ewolucyjnych w konstrukcji
rekurencyjnych sieci neuronowych
11 Wprowadzenie
Przy konstrukcji sieci neuronowych przeznaczonych do rozwiązania określonych za-
dań pojawia się problem stworzenia sieci o określonej architekturze wagowo - struktu-
ralnej. Istniejące algorytmy generują pewne klasy architektur sieci. Problemem jest to,
że nie możemy dobrze określić zależności pomiędzy strukturą sieci a funkcją przezeń
wykonywaną. Przy rozwiązaniu tego problemu wykorzystywane są algorytmy gene-
tyczne i programy ewolucyjne tworzące metody przeszukiwania bazujące na zacho-
waniach populacji. W tej części przedstawimy opis i zastosowanie programu GNARL
(GeNeralized Acquisition of Recurrent Links), który równocześnie tworzy strukturę i
wagi sieci rekurencyjnych.
Rozważamy dwa sposoby tworzenia sieci neuronowych:
" Addytywny (Constructive algorithms) - startujemy od prostej sieci złożonej z
kilku węzłów i połączeń (sieć rozpatrujemy jako graf), po czym dodajemy ko-
lejne węzły i połączenia.
" Subtraktywny (Destructive algorithms) - rozważamy dużą sieć, a następnie okra-
jamy ją z nadmiarowych węzłów.
Wadą tych metod jest to, że tworzą one tylko określone struktury neuronowe, w których
najczęstszym sposobem modyfikacji jest dodanie neuronu  ukrytego . Jest to jedna z
metod poszukiwania minimum strukturalnego, która może utknąć w przypadku napo-
tkania minimum lokalnego. Ponadto algorytmy strukturalne nierzadko dotyczą tylko
jednego typu sieci np. sieci typu feedforward. Okazuje się więc, że zmuszeni jesteśmy
dobrać zadanie do architektury, a nie odwrotnie.
12 Programy ewolucyjne i algorytmy genetyczne
Obliczenia ewolucyjne dostarczają obiecujących algorytmów dla uczenia parametrycz-
nego i strukturalnego sieci rekurencyjnych. Algorytmy te są rozpoznawane po tym,
że by zlokalizować ekstrema funkcji zdefiniowane w przestrzeni poszukiwań polegają
bardziej na populacji, niż na jednej pozycji. Podczas jednego cyklu przeszukiwania,
lub pokolenia, członkowie populacji są oceniani w odniesieniu do funkcji wydajności
29
Rysunek 14: Schemat dualnej reprezentacji użytej w algorytmach genetycznych. Funk-
cja interpretacji pośredniczy pomiędzy elementami w przestrzeni rekombinacji w któ-
rej następuje proces szukania i znajduje się podzbiór struktur, który może być rozwija-
ny jako potencjalne rozwiązanie zadania
(współczynnika przystosowania). Osobniki z większą wartością funkcji są losowo wy-
bierane jako rodzice następnego pokolenia. Członkowie nowej populacji zwani potom-
stwem są tworzoni przy użyciu specjalnej heurystyki reprodukcji. Używając pokolenia,
heurystyki i funkcji wydajności algorytm ewolucyjny wchodzi w tryb przeszukiwania
niemonotonicznego, które daje dobre wyniki w złożonych środowiskach. Każda klasa
obliczeń ewolucyjnych charakteryzuje się inną heurystyką.
Powinniśmy więc rozpatrywać sieć na podstawie szczegółów dotyczących zadania,
a nie odwrotnie. GNARL jest programem, który równomiernie rozwija topologię sie-
ci, strukturę wag, tworzy minimalne ograniczenia dotyczące architektury zapobiegając
jednocześnie tworzeniu się pułapek wynikających z minimum.
Badania wykazały, że różne formy algorytmów genetycznych (Genetic Algorithms
- GAs) pozwalają na dobór parametrów do zmiennej architektury sieci. Istnieje możli-
wość stworzenia pewnego układu wartości, ale procesy tworzące strukturę nie są sko-
relowane z procesami tworzenia wag sieci. Dzieje się tak, ponieważ w tej metodzie
zostały użyte GAs współpracujące z tradycyjnymi algorytmami uczącymi. Niektóre
teorie dopuszczają równoczesne tworzenie struktur topologicznych i wagowych bez
zastosowania GA.
12.1 Tworzenie sieci z użyciem algorytmów genetycznych
Algorytmy genetyczne tworzą nowe pokolenia poprzez rekombinacje fragmentów chro-
mosomów dwóch członków populacji. W GA rozważamy dwie przestrzenie :
" Przestrzeń rekombinacji (Recombination space) - przestrzeń ta jest zdefiniowana
na zbiorze ciągów binarnych zmiennej długości. Zbiór ten zawiera struktury do
których odnoszą się operatory genetyczne.
" Przestrzeń ewaluacyjna (Evaluation space) zawierająca dane dotyczące proble-
mu, a konkretnie zbiór struktur które mają ustalone pewne reguły dotyczące wy-
konania zadania.
W przypadku użycia GA do tworzenia sieci, przestrzeń ewaluacyjna jest zbiorem sie-
ci neuronowych. Relacje pomiędzy tymi przestrzeniami tworzy funkcja interpretacji
(Interpretation function). Żaden zbiór łańcuchów binarnych nie może reprezentować
30
Rysunek 15: Przestrzenie rekombinacji i ewaluacji. Zależności pomiędzy nimi okre-
śla funkcja interpretacji. Krzyżowanie w przestrzeni rekombinacji ma odpowiednik w
przestrzeni ewaluacji. Powstały potomek nie zawsze wyraża lepszą zdolność oblicze-
niową niż rodzic. Dzieje się tak, ponieważ potomstwo może posiadać wiele kopii tego
samego węzła ukrytego.
wszystkich możliwych sieci, co powoduje że przestrzeń ewaluacyjna zawiera ustalo-
ny zbiór sieci. Dualna natura tego układu pozwala GA na krzyżowanie chromosomów
bez jakiej kolwiek znajomości ich neuronowych odpowiedników. Pełni ona ważną ro-
lę przy przeszukiwaniu przestrzeni. Dualno - przestrzenna reprezentacja jest idealna,
gdy nie jest jasne jak w prosty sposób przeszukać przestrzeń ewaluacyjną i gdy istnie-
je taka funkcja interpretacji, że przeszukiwanie przestrzeni ciągów bitowych poprzez
krzyżówki prowadzi do dobrych rezultatów w przestrzeni ewaluacyjnej.
Nie jest jednak pewne, że istnieje funkcja interpretacji, która powoduje, że dual-
na reprezentacja sprawdza się wystarczająco w problemie rozwoju sieci neuronowych.
Pewne jest, że wybór funkcji interpretacji wprowadza silne zaburzenia w przeszuki-
waniu. Typowym zaburzeniem jest wykluczenie wielu interesujących i użytecznych
elementarnych sieci neuronowych (jest to kolejny przykład dostosowania zadania do
architektury) . Ponadto korzyści z zastosowania dualnej reprezentacji opartej na krzy-
żowaniach zależne są od operatora krzyżowania, który jest dostosowywany do danego
zadania. Z drugiej strony potrzeba translacji pomiędzy dualną reprezentacją jest niepo-
trzebną komplikacją.
Określenie jaki operator krzyżowania jest najodpowiedniejszy dla danego zadania
jest sprawą otwartą. Obecne badania sugerują, że krzyżowanie sprawdza się przy re-
kombinacji krótkich łańcuchów bitowych, które odnoszą się do rozwiązań dotyczących
zadań. A
ańcuchy te są zwane blokami (building blocks). Istnieje zasada, że jednostki
z większym współczynnikiem dostosowania są zbudowane ze struktur o mniejszym.
Krzyżowanie zdaje się być bardziej efektywne w środowiskach, gdzie współczynnik
dostosowania członków pokolenia jest skorelowany z oczekiwaną wydajnością kompo-
nentów, które ją prezentują. W środowiskach, w których relacja ta nie zachodzi istnieją
trzy rodzaje błędów (środowiska te znane są jako deceptive enviroments) . Rozważymy
teraz wszystkie trzy przypadki:
" Pierwszy błąd obejmuje sieci, których topologia i układ wag są identyczne. W
tym przypadku dwie funkcje interpretacyjne odnoszą się do jednej sieci. Takie
sieci nie powinny mieć reprezentacji w postaci tego samego ciągu bitów. Proces
31
krzyżowania zdaje się dążyć do generowania potomstwa, które gubi zdolność ob-
liczeniową ukrytych jednostek swoich rodziców. Sieci powstałe w wyniku takich
krzyżówek będą gorzej spełniać swoje zadania, ponieważ nie zawierają kluczo-
wych komponentów obliczeniowych tworzących zadanie.
" Drugi błąd dotyczy sieci z identycznymi topologiami ale innym układem wag.
Powszechnie znanym jest fakt, że dla każdego zadania topologia jednego łączni-
ka pozwala na zastosowanie wielorakich rozwiązań, z których każde jest przed-
stawione w postaci unikalnej reprezentacji dzielonej (distributed reprezentation).
Usunięcie małej liczby węzłów pokazało, by wprowadzić tylko małe zmiany w
jakości sieci, zadanie obliczeniowe które dotyczy każdego węzła jest zależne
całkowicie od istoty i mocy ich połączeń. Ponadto nie ma potrzeby zaistnienia
korelacji pomiędzy wyraz
nie rozdzielonymi reprezentacjami dotyczącymi archi-
tektur sieci dla danego zadania. To poważnie redukuje ryzyko, że operacja krzy-
żowania pomiędzy dwiema wyraz
nie rozdzielonymi reprezentacjami zbuduje re-
alne potomstwo niezależnie od użytej funkcji interpretacji.
" Trzeci błąd może wystąpić, kiedy rodzice różnią się topologicznie. Typy dzie-
lonych reprezentacji, które mogą wytworzyć sieć są bardzo różne jeśli chodzi o
liczbę jednostek ukrytych i połączeń sieciowych. Istnieje więc duża szansa na to,
że rozdzielone reprezentacje sieci będą rodzicami nie zachowującymi kompaty-
bilności. To zjawisko redukuje prawdopodobieństwo, że krzyżowanie w rezulta-
cie wytworzy dobre potomstwo.
12.2 Sieci i programowanie ewolucyjne
W odróżnieniu od algorytmów genetycznych programowanie ewolucyjne określa za-
leżne od reprezentacji operatory mutacji, które tworzą potomstwo bez specjalnego
ulokowania rodziców. Zastosowanie EP jako podstawowego operatora mutacji przy
przeszukiwaniu przestrzeni jest zalecane, gdy nie ma wystarczającej ilości obliczeń do
przeprowadzenia krzyżowania, lub gdy uniezależnienie procesów przeszukania prze-
strzeni ewaluacyjnych nie daje dodatkowych korzyści.
13 Algorytmy programu GNARL
GNARL jest programem bazującym na algorytmie ewolucyjnym, który monotonicz-
nie tworzy sieci potrzebne do rozwiązania danego zadania. GNARL dotyczy typów
sieci, które powstają na podstawie algorytmu indukcyjnego. Algorytm ten wprowadza
strukturalny i parametryczny typ uczenia. Powstałe sieci nie mają jednolitych, bądz
sy-
metrycznych topologii a ich połączenia pomiędzy węzłami ukrytymi tworzy GNARL.
Połączenia te bardziej wydajnie spełniają wymagania dotyczące zadania.
Architektura GNARL a jest prosta. Węzły wejściowe i wyjściowe są zdetermino-
wane przez zadanie i niemodyfikowalne przez algorytm. Tym sposobem każda sieć ma
zawsze min węzłów wejściowych i mout węzłów wyjściowych dla każdego zadania.
Liczba węzłów ukrytych waha się od 0 do hmax. Zakłócenia są opcjonalne i zaimple-
mentowane jako dodatkowy węzeł wejściowy ze stałą jednostkową wartością. Wszyst-
kie węzły nie należące do warstwy wejściowej mają zaimplementowaną standardową
funkcję sigmoidalną. Połączenia korzystają z wag których wartości zawierają się w
zbiorze liczb rzeczywistych i muszą spełniać trzy warunki:
W1: Połączenia dochodzące do węzła wejściowego nie mogą istnieć.
32
Rysunek 16: Przykładowa sieć inicjująca. Liczba węzłów wejściowych (min) i wyj-
ściowych (mout) jest stała dla danego zadania. Obecność węzła dotyczącego zakłóceń
(b=0 lub 1) jak również liczby węzłów ukrytych (hmax) są określane przez użytkow-
nika. Początkowa struktura połączeń jest określana losowo. Nie połączone węzły sieci
nie przeszkadzają w szczegółowych obliczeniach.
W2: Połączenia odchodzące z węzła wyściowego nie mogą istnieć.
W3: Pomiędzy dowolnymi węzłami x i y może istnieć tylko jedno połączenie.
Przestrzeń przeszukiwań GNARL definiujemy jako:
S = {�: � jest siecią z wagami wi"R , gdzie:
� spełnia warunki W1 - W3
� ma min+b węzłów wejściowych, gdzie b=1, gdy włączony jest tryb zakłóceń, 0
w przypadku przeciwnym.
� ma mout węzłów wyjściowych
� ma i węzłów ukrytych, gdzie 0d"id"hmax}
13.1 Selekcja, replikacja i mutacje sieci
GNARL inicjalizuje populację zawierającą losowo wygenerowane sieci (rys. 16). Licz-
ba ukrytych węzłów dla każdej sieci jest wyselekcjonowana na podstawie podziału ba-
zującego na rozkładzie jednostajnym. Zakres podziału i liczbę połączeń inicjujących
podaje użytkownik.Węzły przyległe dla każdego połączenia są wybierane w odniesie-
niu do mutacji strukturalnych opisanych poniżej. Gdy tylko topologia zostanie wybra-
na następuje inicjalizacja wag na linkach, których wartości należą do zbioru [-1,1]. W
procesie inicjalizacji węzły nie muszą mieć połączeń przyległych nie mówiąc już o
ich istnieniu pomiędzy węzłami wejściowymi i wyjściowymi. W eksperymencie opi-
sanym poniżej liczba węzłów ukrytych dla sieci w populacji startowej była wybrana
jednostajnie z przedziału [1,5] a liczba zainicjowanych linków waha się pomiędzy 1 a
10.
W każdym pokoleniu poszukiwania sieci są najpierw rozwijane z udziałem funkcji
wydajności wprowadzanej przez użytkownika f : SR , gdzie R reprezentuje liczby
rzeczywiste. Sieci, które osiągają współczynnik ok. 50% są klasyfikowane jako rodzice
następnego pokolenia. Pozostałe sieci zostają odrzucone. Tego typu metoda selekcji
jest używana w wielu algorytmach EP.
Generowanie potomstwa przebiega w trzech etapach:
" kopiowanie rodzica
" określenie zakresu mutacji jednostek uczestniczących w procesie mutacji
" określenie ich kopii
Mutacje sieci są podzielone na dwie klasy. Mutacje parametryczne zawierają warto-
ści parametrów (wagi połączeń) bezpośrednio w sieci. Mutacje strukturalne zmieniają
33
liczbę ukrytych węzłów i połączenia sieci zmieniając w ten sposób przestrzeń parame-
trów.
13.1.1 Ograniczenia mutacji
Ograniczenia mutacji dla danego rodzica sieci � jest określona przez wielkość zwaną
temperaturą sieci.
f (�)
T(�) = 1-
fmax
gdzie fmaxjest maksymalnym współczynnikiem dostosowania dla danego zadania.
W ten sposób temperatura sieci jest określona przez bliskość sieci na tle rozwiązania
zadania. Ta miara wydajności sieci jest użyta do uwidocznienia strukturalnej i parame-
trycznej tożsamości pomiędzy rodzicami i potomstwem. Sieci z wysoką temperaturą
są o wiele bardziej zmutowane niż te z niską. To pozwala na zastosowanie przeszuki-
wania gruboziarnistego przy inicjacji a następnie na bardziej wyszukane, gdy sieć jest
blisko rozwiązania problemu zadania.
13.1.2 Mutacje parametryczne sieci
Mutacje parametryczne są wzbogacone poprzez wprowadzenie do każdej wagi sieci �
szumu gaussowskiego. Wagi są zmodyfikowane według wzoru :
w=w+N(0,ąT(�)), "w " �
gdzie ą jest współczynnikiem proporcjonalności podawanym przez użytkownika.
N(�, �2) jest gaussowską zmienną losową. Gdy duże mutacje parametryczne są spo-
radycznie potrzebne, by zapobiec powstawaniu minimów lokalnych podczas przeszu-
kiwania. Jest bardzo prawdopodobne, że będą one wpływać niekorzystnie na zdolność
potomstwa do osiągania lepszej wydajności niż ich rodzice. By skompensować to zja-
wisko GNARL uzupełnia wagi używając wariantu 3 równania
T (�)=U(0,1)T(�)
Gdzie U(0,1) jest jednostajną zmienną losową na przedziale [0,1]. Nowa tempera-
tura zmienia się od 0 do T (�) i zastępuje T(�) w poprzednim wzorze:
w=w+N(0,ąT (�)), "w " �
W gruncie rzeczy modyfikacja ta zmniejsza częstotliwość dużych mutacji parame-
trycznych bez kompletnego ich odrzucenia. W eksperymencie przedstawionym poniżej
ą=1.
13.1.3 Strukturalne mutacje sieci
Mutacje strukturalne zastosowane w programie GNARL zawierają liczbę ukrytych wę-
złów i strukturę połączeń pomiędzy wszystkimi węzłami uwzględniając warunki W1-
W3. By uniknąć radykalnych skoków wydajnościowych pomiędzy rodzicami a potom-
stwem, mutacje strukturalne próbują utrzymać zachowanie sieci. Na przykład nowe
połączenia są zainicjowane z wagami o wartościach równych zero pozostawiają nie-
zmienny stan zmodyfikowanej sieci. Ukryte węzły są również dodawane do sieci bez
żadnych przyległych połączeń. Połączenia muszą byc dodane na podstawie przyszłych
mutacji strukturalnych, by określić jak zawrzeć nową jednostkę obliczeniową. Niestety,
osiągnięcie ciągłości zachowań pomiędzy rodzicami i dzieckiem nie jest takie proste
podczas usuwania ukrytego węzła lub połączenia. W konsekwencji usunięcie węzła
prowadzi do kompletnego usunięcia węzła i wszystkich przyległych połączeń z bra-
kiem szansy modyfikacji by skompensować zmianę zachowań. Usunięcie połączenia
usuwa ten parametr z sieci.
34
Selekcja węzłów, które mają być usunięte opiera się na rozkładzie jednostajnym.
Dodawanie, lub usuwanie połączenia jest trochę bardziej skomplikowane w tym, że
parametr identyfikuje prawdopodobieństwo z którym połączenie będzie pochodzić z
węzła wejściowego, lub kończyć się na wyjściowym. Gdy klasa węzła przyległego jest
określona , bieżący węzeł jest losowany z klasy wg. rozkładu jednostajnego. Zakłó-
cając w ten sposób proces wyboru połączeń powinniśmy zwrócić uwagę na to, gdzie
jest największa różnica pomiędzy liczbą ukrytych węzłów i liczbą wejściowych lub
wyjściowych węzłów. W poniższym eksperymencie ten parametr został ustawiony na
wartość 0.2.
By zwiększyć efektywność przeszukiwania architektury sieci GNARL używa ogra-
niczeń dotyczących mutacji dla każdej odseparowanej mutacji strukturalnej. Unikalny
przedział zdefiniowany przez użytkownika określający zakres modyfikacji jest stowa-
rzyszony z każdą z czterech mutacji strtukturalnych. Biorąc przedział ["min, "max] dla
mutacji strukturalnej liczba modyfikacji tego typu dla potomstwa jest określona przez
"min+[U(0,1)T (�)("max - "min)]
Tym sposobem liczba modyfikacji zmienia się wg. rozkładu jednostajnego na zwę-
żającym się przedziale zależnym od wydajności sieci-rodzica.
13.2 Wydajność sieci
W rozwijających się sieciach w celu wprowadzenia zadania GNARL nie potrzebuje
jasno wyznaczonego wektora celu - wszystko, co jest potrzebne to sprzężenie zwrotne
określone przez funkcję wydajności f. Gdy jednak taki wektor istnieje jak w przypad-
ku uczenia z nadzorem rozpatrujemy wiele dróg jego transformacji na współczynnik
dostosowania. Rozważmy zbiór uczący {(x1,y1), (x2,y2)...}, trzy możliwe miary wydaj-
ności dla sieci � są sumą błędów średniokwadratowych, sumą błędów bezwzględnych
i sumą bezwzględnych błędów eksponencjalnych:
i
"(y - Out(�,xi))2
| yi - Out(�,xi) |
"
i
"e|y -Out(�,xi)|
Ponieważ GNARL zgłębia przestrzeń sieci poprzez mutację i podział wybór funkcji
wydajności nie zmienia struktur algorytmu.
14 Eksperyment
W tym rozdziale opiszemy jeden z eksperymentów, w którym wykażemy zalety pro-
gramu GNARL.
Eksperyment z mrówką
GNARL był przetestowany na złożonych zadaniach dotyczących przeszukiwania i ko-
lekcjonowania. W tym zadaniu umieszczono model mrówki na 2-wymiarowej siatce w
35
Rysunek 17: Struktura semantyczna jednostek we/wy dla sieci mrówki. Pierwszy węzeł
wejściowy określa istnienie żywności w kwadracie w przedniej części mrówki. Drugi
określa nieobecność tej żywności. Ta sieć znalazła 42 kawałki jedzenia zanim zapadła
w nieskończoną pętlę w punkcie P, ukazując bardzo głębokie minimum lokalne.
Rysunek 18: Sieć FSA. Duża strzałka wskazuje stan startowy. Ten prosty system speł-
nia strategię: idz
do przodu jeśli żywność jest przed tobą, gdy nie - obróć się w prawo
cztery razy szukając jedzenia. Jeśli pożywienie zostało znalezione podczas obrotu -
zdobądz
je, w przeciwnym przypadku idz
do przodu jeden krok i powtórz proces. Ta
sieć czyści całą ścieżkę w 314 krokach i osiąga wynik 81 punktów w 200 krokach.
kształcie torusa, zawierającej ślady pokarmu. Mrówka przemierza siatkę zbierając por-
cje jedzenia, które napotka na swej drodze. Celem zadania jest opracowanie mrówki,
która zbierze maksymalną liczbę kawałków jedzenia w danym czasie.
Każda mrówka stanowi sieć z dwoma węzłami wejściowymi i czterema wyjścio-
wymi. Pierwszy węzeł wejściowy oznacza istnienie jedzenia w kwadracie naprzeciwko
mrówki, drugi oznacza brak jedzenia w tymże kwadracie. Podawane impulsy dotyczą-
ce istnienia żywności należą do przedziału (0,1) lub (1,0). Każdy z czterech węzłów
wyjściowych odnosi się do innej czynności - krok do przodu, obrót o 90ć%w prawo i
obrót o 90ć%w lewo oraz nic nie rób. W każdym kroku jest uwzględniana czynność, któ-
ra odnosi się do węzła wyjściowego mającego stan maksymalnego pobudzenia. Brak
wykonania czynności powoduje, że mrówka zostaje na stałej pozycji podczas, gdy po-
budzenie przepływa przez połączenia. Współczynnik przystosowania jest zdefiniowany
jako liczba pozycji siatki wyczyszczona w 200 krokach. Sieć na rysunku 19 skolekcjo-
nowała 42 kawałki jedzenia przed tym, jak zaczęła krążyć w nieskończoność w punk-
cie A. Punkt A jest bardzo dużym maksimum lokalnym w przestrzeni poszukiwań. W
eksperymencie uczestniczy populacja 100 sieci, każda ograniczona do dziewięciu jed-
nostek ukrytych i nie zawierająca trybu zakłóceń. W pierwszym kroku (2090 pokoleń)
GNARL znalazł sieć, która czyści 81 pozycji w 200 krokach. Gdy ta mrówka przejdzie
następne 119 kroków zjada wszystkie porcje. By zrozumieć jak działa sieć rozważmy
prostą sieć FSA na rys. 18. Ten prosty twór osiąga wynik 81 punktów w 200 krokach i
czyści całą wstążkę jedzenia tylko o pięć kroków szybciej niż sieć na rysunku 20b.
Porównywanie krok po kroku wykazuje, że istnieje minimalna różnica pomiędzy
tymi dwoma sieciami. Sieć stworzoną przez GNARL spełnia założenia ogólnej strategii
36
Rysunek 19: Eksperyment z mrówką. Przy inicjacji szlak jest połączony, ale staje się
coraz bardziej trudny do pojęcia. Siatka 2-wymiarowa jest w kształcie torusa. Punkt
 A jest pierwszą luką na szlaku.
zawartej w FSA. W punktach B i C na rysunku 19 sieć wykonuje kilka dodatkowych
ruchów zabierając trochę więcej czasu na ukończenie procesu. Rysunek 18 przedstawia
strategię sieci w celu zaimplementowania FSA poprzez ukazanie stanów na węzłach
wyjściowych na trzech różnych zbiorach.
Każdy punkt ma trzy współrzędne move, right, left przestrzeni R3. Rysunek 21a
ukazuje wynik podania do sieci 500 sygnałów  jest pokarm - stałych punktów, które
wykonują  move . rysunek 8b pokazuje sekwencję stanów osiąganych gdy 500 sygna-
łów  brak pokarmu dostanie się do sieci - zbiór punktów opisujących ograniczony
cykl długości 5 stanowiący sekwencję  right, right, right, right, move . Te dwa atrak-
tory określają odpowiedz
sieci na zadanie.
Dodatkowe punkty na rysunku 8c są chwilowe. Pojawiają się, gdy sieć balansuje
pomiędzy atraktorami. Sieć GNARL powstaje z powodu stanów ukrytych jednostek
podczas transferu z atraktora  pokarmu do atraktora  braku pokarmu . Jednakże nie
wszystkie sieci w tak prosty sposób przybliżają FSA. Podczas drugiego uruchomienia
(1595 pokoleń) GNARL wprowadza sieć, która oczyszcza 82 siatki w 200 krokach.
Rysunek22 przedstawia zachowanie tej sieci.
Atraktor  istnienia pokarmu pokazany na rysunku 22 jest pojedyńczym punktem
w przestrzeni, która zawsze wykonuje ruch  move . Zachowanie typu  brak jedze-
nia nie jest charakterystyczne dla FSA ale jest kwaziokresową trajektorią punktów w
kształcie litery  D w przestrzeni wyjściowej.  D znajduje się w rogu  move / right
przestrzeni i koduje złożone zmiany pomiędzy tymi dwiema operacjami (rys. 22d).
Bibliografia
[1] Zbigniew Michalewicz, Algorytmy genetyczne + struktury danych = programy
ewolucyjne, Wydawnictwo Naukowo-Techniczne, Warszawa 1996, 1999
[2] William B. Langdom, Adil Qureshi, Computers using  Natural Selection to ge-
nerate programs, Dept of Computer Science, University College London
[3] Rafał Sałustowicz, A genetic algorithm for topological optimization of neural ne-
tworks, Politechnika Berlińska
[4] Peter J.Angeline, Gregory M.Saunders and Jordan B.Pollack, An Evolutionary Al-
gorithm that Constructs Recurrent Neutral Networks, Laboratory for Artyficial In-
37
Rysunek 20: (a) Najlepsza sieć w pokoleniu startowym. Węzły 0 i 1 są wejściowymi,
5-8 wyjściowymi, 2-4 ukrytymi. (b) Sieć wytworzona przez GNARL po 2090 poko-
leniach. Połączenia typu  forward są oznaczone linią przerywaną. Połączenia dwu-
stronne i pętle są oznaczone linią ciągłą. Jasne szare połączenie pomiędzy węzłami 8 i
13 jest podstawowym połączeniem zwrotnym. Ta sieć oczyszcza szlak w 319 posunię-
ciach.
Rysunek 21: Zachowanie sieci, która czyści szlak w 319 krokach. Rysunki pokazują
stany węzłów wyjściowych Move, Right, Left; (a) Atraktor punktu stałego, który jest
rezultatem sekwencji 500 sygnałów  jest pożywienie ; (b) Atraktor będący rezultatem
sekwencji 500 sygnałów  brak żywności podanych do sieci; (c) Wszystkie stany, które
przyjęła sieć podczas przechodzenia szlaku; (d) Trajektoria mrówki po pustej siatce.
Oś Z oznacza czas. Współrzędna x jest stała a y wzrasta monotonicznie z taką samą
prędkością . Duże skoki współrzędnej y są artefaktami ? siatki toroidalnej.
38
Rysunek 22: Zachowanie sieci w drugim przebiegu. Rysunki pokazują stany węzłów
wyjściowych Move, Right, Left; (a) Atraktor punktu stałego, który jest rezultatem se-
kwencji 3500 sygnałów  jest pożywienie ; (b) Atraktor będący rezultatem sekwencji
3500 sygnałów  brak żywności podanych do sieci; (c) Wszystkie stany, które przy-
jęła sieć podczas przechodzenia szlaku; (d) Trajektoria mrówki po pustej siatce. Oś Z
oznacza czas. Trajektoria mrówki jest zawarta w zbiorze  torów kolejowych . Wzdłuż
każdej linii kreski przedstawiają ruch do tyłu i do przodu. Na połączeniach pomiędzy
liniami występują bardziej skomplikowane ruchy. Tutaj nie ma (artifacts) siatki toro-
idalnej, wszystkie są bieżącymi ruchami.
39
telligence Research, Computer and Information Science Department, The Ohio
State University
40