Algorytmy Genetyczne

[ Pobierz całość w formacie PDF ]
Zastosowanie algorytmów genetycznych w
sieciach neuronowych
Tomasz Kowal, Marcin Wojtkiewicz
5 stycznia 2000 roku
Streszczenie
Czy poł aczenie dwóch rewolucyjnych ideii wytworzy now a jakosc ? Czy tez
spowoduje tylko powstanie nowego „modnego” terminu ?
Algorytmy genetyczne
uzywaj a nowych technik optymalizacji, pozwalaj acych
na ewolucje prostych programów; w podobny sposób drog a ewolucji i stopniowe-
go ulepszania pisz a programy ludzie. Programy „szkieletowe” s a przez algorytmy
genetyczne stale ulepszane w poszukiwaniu lepszego rozwi azania. Własnie na tej
koncepcji opieraj a sie
Algorytmy genetyczne.
Algorytmy genetyczne
oparte na pionierskich pracach Johna H. Hollanda, Da-
vida E. Goldberga i innych s a ewolucyjnymi technikami przeszukiwania przestrze-
ni rozwi azan, inspirowanymi selekcj a naturaln a (znaczy to ni mniej ni wiecej, ze
przezywa lepiej przystosowany).
Sieci Neuronowe
natomiast s a sposobem budowania pewnych struktur maj a-
cych symulowac działanie ludzkiego mózgu. Ich działanie oparte jest na budowie
komórki neuronowej.
Poł aczenie nowych idei bedzie 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 tresci
I Wprowadzenie do algorytmów genetycznych
1
1 Wstep 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 a algorytmów genetycz-
nych
7
2.1 Wybór reprezentacji . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2 Populacja pocz atkowa . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3 Funkcja oceny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4 Operatory genetyczne . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.5 Parametry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1
2.6 Wyniki oblicze n . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3 Teoretyczne podstawy algorytmów genetycznych - dlaczego one działaj a
9
II Wstep 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 Wstep
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 uzyciem 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 Wydajnosc sieci . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
14 Eksperyment
34
Czesc I
Wprowadzenie do algorytmów
genetycznych
1 Wstep
Algortmy genetyczne s a prawdopodobnie najblizszym naturalnej ewolucji modelem
obliczeniowym. S a silnym narzedziem w przeszukiwaniu przestrzeni rozwi aza n pro-
blemu. Dzieki swojej sile znalazły one szerokie zastosowanie w rozwi azywaniu pro-
blemów szeregowania zada n, modelowania finansowego, optymalizacji funkcji, har-
monogramowania.
1.1 Konkretne zastosowania
rozwi azanie problemu komiwojazera,
podział obiektów i grafów,
planowanie drogi w srodowisku ruchomego robota,
uczenie maszynowe (automatyczne programowanie),
wyznaczenie ekstremum funkcji na danym przedziale,
tworzenie sieci neuronowych.
Wynalazca algorytmów genetycznych John Holland swoj a inspiracje czerpał z natu-
ry. Algorytmy genetyczne składaj a sie z populacji jednostek, z których kazda posia-
da DNA reprezentowany w pamieci w postaci wektora. Na DNA jednostki okreslona
jest funkcja zwracaj aca wartosc wektora, zwana stopniem przystosowania. Działanie
alogorytmu genetycznego polega na tworzeniu kolejnych pokole n poprzez wymiane
fragmentów DNA osobników z danego pokolenia. Mozliwe s a takze mutacje. Kazde
nastepnie pokolenie tworz a jednostki o wiekszym stopniu przystosowania.
Przy rozwi azywaniu konkretnych problemów kazda jednostka reprezentuje punkt
w przestrzeni rozwi aza n. Funkcja przystosowania zwraca dla tego punktu pewn a war-
tosc. Jesli wartosc ta jest wystarczaj aco dobra, proces jest wstrzymywany, a punkt ten
jest rozwi azaniem. S a dwie metody podejscia do wyznaczenia rozwi azania:
zakładamy, ze musimy otrzymac rozwi azanie w okreslonym czasie lub po okre-
slonej liczbie iteracji (ewolucji pokole n);
3
Rysunek 1: Rozmnazanie przez krzyzowanie
Rysunek 2: Rozmnazanie przez mutacje
zakładamy nieskonczony czas (liczbe pokole n) i patrzymy, kiedy rozwi azanie
sie ustabilizuje.
Sposób ewolucji nowego pokolenia jest takze wziety z natury. Nowe wektory (DNA) s a
brane z wektorów jednostek najlepiej przystosowanych, a rozmnazanie moze odbywac
sie na dwa sposoby:
przez mutacje (
ang. mutation
) - wektor rodzica z przypadkowymi mutacjami
tworzy wektor dziecka (Rys. 1.2)
przez krzyzowanie (
ang. crossingover
) - wektor dziecka jest tworzony poprzez
kombinacje odcinków DNA rodziców
Krzyzowanie polega na losowym okreslaniu miejsc podziału w DNA rodziców oraz
na odpowiednim ich poł aczeniu, a w rezultacie stworzeniu potomka (lub potomków).
Jedne z najczesciej stosowanych rodzajów krzyzowania to:
podział wektora rodziców na dwie czesci, z których składa sie wektor dziecka
(Rys. 1.1),
wybór z DNA rodziców wiecej czesci z których tworzony potomek (np. dwa bity
z pocz atku i dwa z ko nca DNA rodzica1 i cztery srodkowe z DNA rodzica2.).
Tak własnie z grubsza wygl ada idea algorytmów genetycznych. Nalezy jednak zdac
sobie sprawe, ze w przypadku kazdego szczególnego problemu podejscie musi byc
nieco bardziej złozone.
Tak
wiec algorytm genetyczny w szczególnym wypadku powinien zawierac piec ele-
mentów:
podstawow a reprezentacje potencjalnych rozwi aza n zadania, czyli odpowiedni
rodzaj DNA dla danego przypadku (niekonieczne wektor),
sposób tworzenia pocz atkowej populacji potencjalnych rozwi aza n,
4
Rysunek 3: Krzyzowanie dwupunktowe
funkcje przystosowania (oceniaj ac a), która gra role srodowiska i ocenia rozwi a-
zania według ich „dopasowania”,
podstawowe operatory, które wpływaj a na skład populacji dzieci,
wartosci róznych parametrów uzywanych w algorytmie genetycznym (rozmiar
populacji, prawdopodobie nstwa uzycia operatorów genetycznych itp.).
1.2 Modyfikacje algorytmów genetycznych
Okazuje sie, ze powyzsza forma algorytmów genetycznych zwana
SGA
(ang. Simple
Genetic Algorithm) nie zapewnia rozwi azania dla pewnej klasy problemów, co wi aze
sie miedzy innymi ze stał a długosci a ła ncucha DNA. Dlatego wprowadzono rozszerze-
nia do algorytmów genetycznych, zwane odt ad
ESGA
(ang. Extended Simple Genetic
Algorithm).
1.2.1 Rozszerzone algorytmy genetyczne (ESGA)
Algorytmy te takze bazuj a na populacji ła ncuchów bitów, jednak w przeciwie nstwie do
SGA, długosc ła ncucha DNA moze sie zmieniac. Pocz atkowa populacja jest tworzona
losowo i wszystkie osobniki s a tej samej długosci. Jednak po krzyzowaniu dwupunk-
towym (rys 1.2.1) długosc osobników moze rosn ac lub malec.
1.2.2 Semantycznie zmienne algorytmy genetyczne (SCGA)
S a one bezposrednim rozszerzenie prostych algorytmów genetycznych. Kodowanie ge-
notypu zostało podzielone na dwa poziomy: wyzszy i nizszy. Na nizszy poziomie od-
bywa sie rozwi azywanie problemu, na wyzszym natomiast determinuje sie odpowied-
nie kodowanie elementów otrzymanych z nizszej warstwy, znajdowanie istotnych pod
wzgledem wiedzy modułów i szybk a ich dystrybucje, kontrolowanie wzrostu osob-
ników oraz integracje wiedzy. Nizszy poziom stanowi a ła ncuchy bitów SGA. Wyz-
szy poziom stanowi samoadaptuj aca tablica symboli, w której ła ncuchy bitów ulegaj a
5
[ Pobierz całość w formacie PDF ]