Algorytmy Genetyczne.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 Wstep 1

1.1 Konkretne zastosowania . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Modyﬁkacje 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

2.1 Wybór reprezentacji . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Populacja pocz atkowa . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 Funkcja oceny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Operatory genetyczne . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Parametry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6 Wyniki oblicze n . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Teoretyczne podstawy algorytmów genetycznych - dlaczego one działaj a

II Wstep do sieci neuronowych

4 Wprowadzenie

5 Zastosowanie sieci neuronowych

6 Rodzaje sieci neuronowych

6.1 Realizacja sieci neuronowych . . . . . . . . . . . . . . . . . . . . . .

6.2 Liniowe i nieliniowe sieci neuronowe . . . . . . . . . . . . . . . . .

6.3 Struktura neuronu . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4 Uczenie neuronu . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.5 Sieci CP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.6 Sieci rezonansowe . . . . . . . . . . . . . . . . . . . . . . . . . . . .

III Optymalizacji topologii sieci neuronowej z wykorzystaniem

algorytmów genetycznych

7 Wstep

8 Kodowanie genetyczne

8.1 Model jednostka-klaster . . . . . . . . . . . . . . . . . . . . . . . . .

8.1.1 Przykład procesu translacji . . . . . . . . . . . . . . . . . . .

8.2 Rozszerzony model jednostka-klaster . . . . . . . . . . . . . . . . .

8.2.1 Przykład procesu translacji w rozszerzonym modelu jednostka-

klaster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.3 Restrykcyjny model jednostka-klaster . . . . . . . . . . . . . . . . .

9 Funkcja oceny

10 Przykład zastosowania

10.1 Test dodawania liczb 6-bitowych. . . . . . . . . . . . . . . . . . . . .

10.1.1 Train error. . . . . . . . . . . . . . . . . . . . . . . . . . . .

10.1.2 Test error. . . . . . . . . . . . . . . . . . . . . . . . . . . .

10.2 Wnioski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

IV Zastosowanie algorytmów ewolucyjnych w konstrukcji re-

kurencyjnych sieci neuronowych

11 Wprowadzenie

12 Programy ewolucyjne i algorytmy genetyczne

12.1 Tworzenie sieci z uzyciem algorytmów genetycznych . . . . . . . . .

12.2 Sieci i programowanie ewolucyjne . . . . . . . . . . . . . . . . . . .

13 Algorytmy programu GNARL

13.1 Selekcja, replikacja i mutacje sieci . . . . . . . . . . . . . . . . . . .

13.1.1 Ograniczenia mutacji . . . . . . . . . . . . . . . . . . . . .

13.1.2 Mutacje parametryczne sieci . . . . . . . . . . . . . . . . . .

13.1.3 Strukturalne mutacje sieci . . . . . . . . . . . . . . . . . . .

13.2 Wydajnosc sieci . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14 Eksperyment

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 ﬁnansowego, 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);

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,

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 Modyﬁkacje 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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: