Sztuczne sieci neuronowe i algorytmy genetyczne

brodzinski

SPIS TREŚCI



1.0 ARCHITEKTURY, ALGORYTMY UCZENIA I PROJEKTOWANIE SIECI NEURONOWYCH


1.1. HISTORIA ROZWOJU SZTUCZNYCH SIECI NEURONOWYCH


1.2. INSPIRACJE BIOLOGICZNE


1.3. MATEMATYCZNY MODEL SZTUCZNEGO NEURONU I SIECI NEURONOWEJ


1.4. KLASYFIKACJA SIECI NEURONOWYCH


1.5. WSTĘPNE PRZETWARZANIE DANYCH


1.5.1. Skalowanie i normalizacja


1.6. UCZENIE SIECI


1.6.1. Algorytm wstecznej propagacji błędów


1.6.2. Algorytm wstecznej propagacji błędu ze współczynnikiem momentum


1.7. DOBÓR STRUKTURY SIECI NEURONOWEJ


1.7.1. Metody wzrostu


1.7.2. Metody redukcji


1.7.3. Metody optymalizacji dyskretnej


1.7.4. Algorytm genetyczny jako optymalizator struktury sieci


2.0 PREZENTACJA I ANALIZA WYNIKÓW PREDYKCJI NOTOWAŃ GIEŁDOWYCH INDEKSU WIG20



1. Architektury, algorytmy uczenia i projektowanie sieci neuronowych

Sieci neuronowe są sztucznymi strukturami, których budowa i działanie zostały zaprojektowane w sposób modelujący działanie naturalnego układu nerwowego, w szczególności mózgu. Cieszą się bardzo dużym zainteresowaniem. Jednym z głównych czynników mających na to wpływ jest możliwość stosowania ich w bardzo wielu dziedzinach życia do rozwiązywania problemów, gdzie użycie innych metod jest trudne lub niemożliwe. Znakomicie sprawdzają się w problemach klasyfikacji, predykcji, związanych ze sterowaniem, analizą danych. Są często wykorzystywane w geologii, fizyce, ekonomii, dla celów wojskowych oraz medycznych. Na tak wielką popularność wpływają podstawowe cechy oferowane przez sieci neuronowe. Pozwalają one rozwiązywać problemy dla opisów których nie ma modeli matematycznych. Przygotowanie sieci do pracy jest dwuetapowe. Pierwszym jest proces uczenia, w którym sieć uczy się na podstawie danych empirycznych jak reagować na zadany bodziec. Gdy sieć zostanie wytrenowana można przejść do etapu pracy właściwej (drugi etap), podając na jej wejścia dowolne sygnały. Jest więc to metoda łatwa w użyciu. Poza tym sieć neuronowa umożliwia generalizację zdobytej "wiedzy". Sieć nauczona na pewnym wektorze danych będzie dawać wyniki dla danych nie biorących udziału w procesie uczenia. Cechy te zostały uzyskane dzięki wzorowaniu się na sposobie pracy mózgu. Dzięki badaniom nad budową i funkcjonowaniem naturalnego systemu nerwowego oraz próbom przeniesienia zaobserwowanych mechanizmów do modeli matematycznych, powstało bardzo użyteczne narzędzie, chętnie wykorzystywane w wielu zadaniach praktycznych.

1.1. Historia rozwoju sztucznych sieci neuronowych

Prace nad poznaniem procesów zachodzących w mózgu, które mają wpływ na inteligentny sposób jego działania, były prowadzone od bardzo dawna przez wielu badaczy z całego świata. Początkiem dziedziny sztucznych sieci neuronowych było przedstawienie matematycznego modelu neuronu przez McCulloch'a i Pitts'a w 1943 roku. Ich praca stała się inspiracją dla wielu późniejszych badaczy. W 1949 roku Donald Hebb odkrył, że informacja może być przechowywana jako wartość wag pomiędzy połączeniami poszczególnych neuronów i zaproponował pierwszy algorytm uczenia takiej sieci. Polegał on na zmianach wag połączeń - nazwany on został regułą Hebba. Pierwszą znaną i opisaną, działającą siecią neuronową był perceptron. Została ona opracowana przez Rossenblatt'a w 1957 roku w Cornell Aeronautical Laboratory. W 1960 roku powstała struktura Adaline, na którą składał się pojedynczy element liniowy. Jej twórcą był Bernard Widrow ze Standford University. Element Adaline po rozbudowaniu o kolejne elementy połączone ze sobą tworzyła sieć Madaline. Początkowy gwałtowny wzrost zainteresowania i postęp w tej dziedzinie został ostudzony w latach 70-tych przez publikację pracy Minsky-ego i Paperta (1969 r.) która dowodziła, że sieć składająca się z jednej warstwy liniowej ma bardzo ograniczone zastosowanie. Pomimo tego powstawało wiele nowych pomysłów i modeli sieci. Można tu wymienić sieć Cerebellatron Davida Mara (sterowanie robotem), Brain in the Box Jamesa Andersona (1977 r.) działająca jak pamięć asocjacyjna. Zastój w badaniach nad siecią został przełamany po publikacji algorytmu uczenia wielowarstwowej nieliniowej sieci neuronowej. Metoda wstecznej propagacji błędów została po raz pierwszy opisana przez Werbosa w 1974 roku, jednak jej popularyzacja nastąpiła dopiero w 1986 roku za sprawą Rumelharta. To umożliwiło konstruowanie wielowarstwowych nieliniowych sieci neuronowych i ich skuteczne uczenie. Spowodowało to powrót zainteresowania sieciami neuronowymi i dalszy szybki ich rozwój.

1.2. Inspiracje biologiczne

Jak już wspomniano wyżej, badacze rozwijający model sieci neuronowej wzorowali się na naturalnym systemie nerwowym, szczególnie mózgu. Mózg składa się z około 10 miliardów elementarnych komórek nerwowych nazywanych neuronami. Tworzą ona bardzo skomplikowane sieci powiązań między sobą. Neurony w mózgu pracują równolegle. Poszczególne neurony składaja się z następujących części: dendrytów, perikarionu, aksonu. Dendryty są wejściami neuronu. Prowadzą sygnał od innych neuronów. Perikarion stanowi część scalającą dla sygnałów z dendrytów. Akson pełni funkcje wyjścia sygnału od neuronu do innych neuronów. Odbywa się to poprzez telodendron - rozgałęzioną strukturę transportującą sygnały wyjściowe. Nośnikiem pamięci w naturalnej sieci neuronów jest synapsa - biochemiczne złącze, modyfikujące sygnały. Na podstawie budowy biologicznej powstał model sztucznego neuronu oraz sieci neuronowej. Jest on znacznie uproszczony w stosunku do systemu biologicznego.

1.3. Matematyczny model sztucznego neuronu i sieci neuronowej

Na podstawie obserwacji mechanizmów zachodzących w naturalnej sieci neuronów, opracowano matematyczne koncepcje sztucznych sieci neuronowych. Podobnie jak w naturalnych sieciach, składają się one z elementarnych komórek - neuronów. Zdając sobie sprawę z braku możliwości dokładnego odwzorowania naturalnych układów i budowy, badacze opracowali model sztucznego neuronu. Jego działanie można przestawić następująco: - do neuronu docierają sygnały (na wejścia neuronu), - każdy sygnał ma swoja wagę (efektywność synapsy), - w neuronie obliczana jest ważona suma wejść i odejmowana wartość progowa, - wynik sumy ważonej wprowadzany jest jako argument funkcji aktywacji, wynik funkcji jest wprowadzany na wyjście neuronu.

![Schemat budowy sztucznego neuronu.](https://4programmers.net/Download/4020/903) Schemat budowy sztucznego neuronu.

Na tej podstawie, działanie pojedynczego neuronu można opisać następującymi wzorami:


wzor1.JPG


![wzor2.JPG](https://4programmers.net/Download/4020/892)
więc:
![wzor3.JPG](https://4programmers.net/Download/4020/891)

Funkcja aktywacji może mieć różne postaci. Każda funkcja, aby mogła pełnić tę rolę musi być ciągła i łatwo różniczkowalna. Wyjątkiem jest perceptron, w przypadku którego funkcja aktywacji nie jest poddana tym ograniczeniom. W praktyce stosuje się najczęściej następujące funkcje: liniową, logistyczną, tangens hiperboliczny, sinus oraz signum.


a) Funkcja liniowa


Neurony z liniową funkcją aktywacji tworzą liniowe sieci neuronowe. Wartość ważonej sumy wejść są przepisywane na wyjście neuronu. Budowanie wielowarstwowych sieci liniowych nie jest uzasadnione, gdyż zawsze można zastąpić ją odpowiednią siecią jednowarstwową.


b) Funkcja logistyczna
Funkcja logistyczna jest bardzo często stosowaną funkcją aktywacji neuronu. Określona jest ona następującym wzorem:
![wzor4.JPG](https://4programmers.net/Download/4020/890)

Funkcja przyjmuje wartości z przedziału (0,1).

Na rys. zamieszczonym niżej widoczny jest wpływ współczynnika beta na postać funkcji aktywacji.


Przebieg wartości funkcji logistycznej przy różnych wartościach współczynnika beta.
Przebieg wartości funkcji logistycznej przy różnych wartościach współczynnika beta.
c) funkcja tangens hiperboliczny


Równie często stosowaną funkcją przejścia jest tangens hiperboliczny. Wzór funkcji jest następujący:


wzor5.JPG

Funkcja tangens hiperboliczny przyjmuje wartości z przedziału (-1,1);


funkc_tanh.JPG


Przebieg wartości funkcji tanh dla różnych parametrów beta.
d) Funkcja sinus
Dla zastosowań w sieciach neuronowych, stosuje się następującą postać:
![wzor6.JPG](https://4programmers.net/Download/4020/888)
e) Funkcja signum </br> ![wzor7.JPG](https://4programmers.net/Download/4020/887)
Jednokierunkowa, wielowarstwowa sztuczna sieć neuronowa powstaje przez połączenie opisanych wyżej sztucznych neuronów. Stosowana jest przy tym zasada łączenia każdego neuronu warstwy poprzedniej z każdym neuronem warstwy następnej. Powstające w ten sposób warstwy można podzielić na:
a) warstwę wejściową,
b) warstwy ukryte,
c) warstwę wyjściową.

![schemat_budowy.JPG](https://4programmers.net/Download/4020/899)
Działanie sieci neuronowej możne przedstawić w następujących krokach:
- dane wejściowe są wprowadzane na wejścia warstwy wejściowej,
- dane są propagowane na wejścia następnych warstw, aż do warstwy wyjściowej,
- wartości otrzymane w ostatniej, wyjściowej warstwie sieci neuronowej traktuje się jako wyjścia sieci.

1.4. Klasyfikacja sieci neuronowych

W rozdziale 1.3 przedstawiona została budowa i sposób działania jednokierunkowej wielowarstwowej, nieliniowej sieci neuronowej. Jest to najczęściej wykorzystywany model w neurokomputingu. Trzeba jednak zauważyć, że istnieje wiele innych modeli sieci, często wyspecjalizowanych w szczegółowych typach zadań, różniących się koncepcjach nauki, innym przepływem sygnałów. Poniżej przedstawiono opisane w literaturze najważniejsze typy sieci neuronowych i ich krótką charakterystykę. Klasyfikacji sieci neuronowych dokonuje się według czterech podstawowych kryteriów: metod trenowania, kierunków propagacji sygnałów w sieci, typów funkcji przejścia, rodzajów danych wprowadzanych na wejścia. Klasyfikacja sieci według tych kryteriów wygląda następująco:

![Klasyfikacja sieci neuronowych.](https://4programmers.net/Download/4020/900) Klasyfikacja sieci neuronowych.
Sieci nadzorowane są często spotykanymi sieciami w wielu zastosowaniach. Ich trening polega na prezentowaniu sieci wartości wejściowych wraz z odpowiednimi, pożądanymi wartościami na wyjściach. Na tej podstawie sieć tak ustawia wartości wag, by odpowiedź mieściła się w granicy błędu określonym przez użytkownika. Sieci liniowe są stosowane raczej rzadko, ze względu na małe możliwości. Sieci jednokierunkowe nieliniowe są obecnie najczęściej stosowanymi strukturami neuronowymi. Cechują się dobrą efektywnością działania oraz prostą i intuicyjną budową. Są one również bardzo uniwersalne. Sieci rekurencyjne działają w nieco inny sposób niż sieci jednokierunkowe. Wyjścia niektórych neuronów, lub całych warstw mogą być wprowadzane ponownie na wejścia tych samych neuronów lub warstw. Sieci nie nadzorowane różnią się od sieci nadzorowanych sposobem treningu. Nie wymagają one podawania pożądanych wartości wyjściowych dla prezentowanych wejść lecz tylko wektorów wejściowych. </p>

1.5. Wstępne przetwarzanie danych

Sieć neuronowa do odpowiedniego działania potrzebuje poprawnie zdefiniowanych danych wejściowych. Istnieje wiele metod zapewnienia poprawności danych zależnie od ich charakteru oraz rodzaju sieci. Niezależnie od rodzaju sieci i problemu, który ma być rozwiązany, dane powinny spełniać podstawowe warunki, takie jak reprezentatywność, pełne oddanie problemu, odpowiednie przeskalowanie i normalizacja, eliminacja niedokładności pomiarów. Przeprowadzenie tych czynności jest niezbędne do poprawnego działania sieci.

1.5.1. Skalowanie i normalizacja

Dane przetwarzane przez sieć pochodzą najczęściej z obserwacji pewnych wartości w badanym modelu. Ich skala wartości zazwyczaj nie na bezpośrednie wprowadzenie na wejścia sieci. Istnieje kilka popularnych metod skalowania. Poniżej wymieniono najczęściej stosowane.

  • skalowanie względem wartości maksymalnej:

    wzor8.JPG

- skalowanie względem wartości średniej:
![wzor91.JPG](https://4programmers.net/Download/4020/904)
- skalowanie względem odchylenia od wartości średniej:
![wzor10.JPG](https://4programmers.net/Download/4020/885)
przeskalowanie do zakresu (-1,1),
- skalowanie względem odchylenia od wartości minimalnej:
![wzor11.JPG](https://4programmers.net/Download/4020/884) ,
transformacja do wartości (0,1),
- skalowanie względem standardowego odchylenia średniokwadratowego:
![wzor12.JPG](https://4programmers.net/Download/4020/883) .

Wybór odpowiedniej metody skalowania jest uzależniony od rodzaju rozwiązywanego problemu.

1.6. Uczenie sieci

Jedną z głównych zalet sieci neuronowej w stosunku do innych metod przetwarzania danych jest umiejętność generalizacji wiedzy, co umożliwia poprawną reakcję na sygnały nie przewidziane przez projektanta. W odróżnieniu od metod matematycznych lub algorytmicznych sieć może być wykorzystywana dla wielu różnych modeli, bez znaczących modyfikacji. Powyższe cechy mogą zostać uzyskane tylko przez zastosowanie odpowiedniego algorytmu uczenia. Istnieje wiele algorytmów uczenia sieci. Do najczęściej stosowanych zalicza się metodę wstecznej propagacji błędów i jej modyfikacje.

</p>

1.6.1. Algorytm wstecznej propagacji błędów

Algorytm wstecznej propagacji błędów jest podstawowym algorytmem uczenia nadzorowanego wielowarstwowych jednokierunkowych sieci neuronowych. Polega na takiej zmianie wag sygnałów wejściowych każdego neuronu w każdej warstwie, by wartość błędu dla kolejnych par uczących zawartych w zbiorze uczącym była jak najmniejsza. Wykorzystuje on w tym celu metodę gradientową - najszybszego spadku.
Ogólny przebieg uczenia nadzorowanego sieci neuronowej przebiega według algorytmu przedstawionego na rys:

![Schemat przebiegu algorytmu wstecznej propagacji błędu.](https://4programmers.net/Download/4020/898) Schemat przebiegu algorytmu wstecznej propagacji błędu.
Przebieg algorytmu dla wszystkich elementów ciągu uczącego nazywa się epoką. Jak już wspomniano wyżej, sieć jest uczona poprzez odpowiednie zmiany wartości wag na wejściach poszczególnych neuronów. Aby można tego dokonać potrzebne jest określenie wartości błędów na wyjściach poszczególnych neuronów. Oblicza się je według następujących wzorów:
dla warstwy k=N, ostatniej:
![wzor13.JPG](https://4programmers.net/Download/4020/882) ,
gdzie
![wzor14.JPG](https://4programmers.net/Download/4020/881) , jest błędem sygnału wyjściowego poszczególnego neuronu
![wzor15.JPG](https://4programmers.net/Download/4020/880) , jest sygnałem wyjściowym części liniowej neuronu
![wzor16.JPG](https://4programmers.net/Download/4020/879) - sygnał wzorcowy i-tego neuronu

Dla każdej innej warstwy k, błąd wylicza się według następującego wzoru:


wzor17.JPG


oznaczenia:
wzor18.JPG - wyjście neuronu,

wij(k) - waga wejścia j w i-tym neuronie w warstwie k,

n - numer okresu przebiegu algorytmu.



Wyznaczanie wartości błędów odbywa się w kierunku od warstwy wyjściowej wstecz do warstwy wejściowej.
Gdy błędy są wyliczone, przystępuje się do modyfikacji wartości wag, według wzoru:


wzor20.JPG


Algorytm można więc przedstawić następująco:


wzor21.JPG


Działanie algorytmu kończy się, gdy osiągnięty zostanie poziom błędu wyznaczony przez użytkownika lub po przebiegu określonej liczby epok.

1.6.2. Algorytm wstecznej propagacji błędu ze współczynnikiem momentum

Algorytm wstecznej propagacji błędów ma niestety kilka wad. Do najczęściej wymienianych zalicza się duża liczba iteracji potrzebna do osiągnięcia oczekiwanego wyniku oraz wrażliwość na minima lokalne funkcji błędu. Jego działanie zależy również od odpowiednio dobranego współczynnika szybkości uczenia. Zbyt mały powoduje długą pracę algorytmu a zbyt duży może powodować oscylacje. Istnieje jednak metoda zwiększania tempa uczenia bez pogorszenia jakości uczenia oraz przy mniejszej wrażliwości na minima lokalne. Jest to momentowa metoda wstecznej propagacji błędu. Modyfikacja podstawowego algorytmu polega tu na dodaniu członu, który pełni rolę współczynnika bezwładności przy modyfikacji wagi. Powoduje to większą płynność zmian oraz "przeskakiwanie" nad minimami lokalnymi.
Postać po modyfikacji wygląda następująco:

![wzor22.JPG](https://4programmers.net/Download/4020/874)
gdzie:
![wzor23.JPG](https://4programmers.net/Download/4020/873) jest wzorem algorytmu wstecznej propagacji błędów (BP),
Alfa - współczynnik momentum.

Z powyższego wzoru widać, że podstawowy człon algorytmu nie uległ zmianie. Widoczny jest człon bezwładności, o współczynniku . Powstaje on poprzez wyliczenie różnicy wagi i odpowiadającej jej wagi z poprzedniej epoki. W ten sposób każda kolejna zmiana jest uzależniona z wagą alfa od poprzedniej wartości wagi.

1.7. Dobór struktury sieci neuronowej

Jednym z bardziej znaczących czynników, mających wpływ na parametry działania sieci, takie jak szybkość uczenia, wielkość popełnianego błędu, zdolność generalizacji, ma odpowiednio dobrana struktura sieci. Niestety nie istnieją jednoznaczne metody jej definiowania. Często nawet pozornie podobny problemy trzeba rozwiązywać za pomocą różnej pod względem struktury sieci. O ile ilość neuronów w warstwach wejściowej i wyjściowej jest determinowana przez założenia użytkownika, to ilości warstw ukrytych i neuronów, które się w nich znajdują nie są wielkościami oczywistymi.
Metody optymalizacji wielowarstwowej sieci neuronowej są przedmiotem badań od wielu lat. Problem ten nie jest jednak zamknięty. Opracowano dotychczas grupę algorytmów, których działanie ma pomóc w utworzeniu sieci optymalnej. Można podzielić je na trzy grupy:
- metody wzrostu,
- metody redukcji,
- metody optymalizacji dyskretnej.
Żadna z wymienionych wyżej metod nie jest idealna. Często wybór którejś z nich zależy od rodzaju rozwiązywanego problemu.

1.7.1. Metody wzrostu

Algorytmy, należące do metody wzrostu zakładają, że na początku procesu optymalizacji struktura sieci powinna być możliwie mała. W kolejnych iteracjach zostają dodawane kolejne neurony ukryte, co powinno powodować zwiększenie sprawności działania sieci. Czynność ta jest powtarzana aż do osiągnięcia punktu optymalnego. Przykładowe algorytmy działające według metody wzrostu to:
- algorytm kafelkowy,
- dynamiczna kreacja neuronów.
Algorytm kafelkowy jest stosowany do konstruowania nieliniowej, wielowarstwowej sieci neuronowej. Algorytm polega na dodawaniu kolejnych neuronów do struktury sieci. Każdy pierwszy neuron w warstwie pełni specjalną funkcję. Nazywa się go elementem głównym. Na podstawie wyniku elementu głównego warstwy ostatnio dodanej ocenia się jakość sieci. Jeżeli jakość nie jest wystarczająca, wprowadzane są kolejne neurony do warstwy. Czynność ta jest wykonywana do momentu gdy sieć nie osiągnie optymalnych parametrów struktury. Algorytm dynamicznej kreacji neuronów został zaprojektowany do optymalizacji sieci nieliniowej o jednej warstwie ukrytej. Zasada działania jest bardzo zbliżona do algorytmu kafelkowego. Przebieg działania algorytmu wygląda następująco:
- utworzenie sieci początkowej o małej liczbie neuronów w warstwie ukrytej (najczęściej 2 neurony),
- trenowanie sieci za pomocą algorytmu wstecznej propagacji,
- dodanie neuronu do warstwy ukrytej.
Czynności te są powtarzane, aż sieć osiągnie odpowiednią strukturę do rozwiązania określonego zadania.

1.7.2. Metody redukcji

Algorytmy metody redukcji są równie często stosowane jak metody wzrostu. Opierają się one na założeniu, że kolejne iteracje mają zmniejszać ilość neuronów ukrytych. Wyróżnia się tu następujące metody:
- metody wrażliwości,
- metody analizy kowariancji.
W początkowym stadium sieć neuronowa charakteryzuje się dużą złożonością strukturalną. Zostaje ona redukowana aż do osiągnięcia optymalnej struktury. W metodzie wrażliwości usuwa się połączenia synaptyczne, których wagi mają najmniejszy wpływ na wynik sieci. Metoda analizy kowariancji jest zbliżona do wcześniej wymienionej metody. Analizie poddawana jest macierz kowariancji sygnałów generowanych przez neurony warstwy ukrytej. Liczba znacząco dużych wartości własnych macierzy określa liczbę neuronów, które powinny znajdować się w warstwie ukrytej.

1.7.3. Metody optymalizacji dyskretnej

Algorytmy optymalizacji dyskretnej opierają się na założeniu, że proces nauki sieci i wyboru architektury zachodzą równocześnie. Czynnikiem, który zostaje poddany ocenie jest określona funkcja, reprezentująca jakość danej sieci. W kolejnych krokach sieci dobierane są tak, by dążyć do maksymalizacji funkcji jakości. Jednym z najciekawszych algorytmów optymalizacji jest algorytm genetyczny.

1.7.4. Algorytm genetyczny jako optymalizator struktury sieci

Algorytmy genetyczne są szczególnie interesującą formą rozwiązywania problemów optymalizacyjnych. Podobnie jak sieci neuronowe, metodyka ta powstała na podstawie obserwacji procesów zachodzących w świecie organizmów żywych.</br> Implementacje algorytmów genetycznych pozwoliły stwierdzić, że jest to metoda skuteczna i łatwa do zastosowania w wielu problemach optymalizacji. Podobnie jak sieć neuronowa, algorytm genetyczny nie wymaga od użytkownika znajomości szczegółów procesu optymalizacji danego zadania. Wymagane jest jedynie określenie pewnej funkcji, zwanej funkcją przystosowania, której wartość będzie maksymalizowana w kolejnych przebiegach algorytmu. Poniżej przedstawię ogólne wiadomości dotyczące modeli ewolucyjnych. Skupiono się na klasycznym algorytmie genetycznym oraz przedstawię przykładowe założenia algorytmu optymalizującego hipotetyczną siec neuronową.


Zasada działania klasycznego algorytmu genetycznego

Algorytm genetyczny operuje na chromosomach. Rolę tę pełni wektor o stałej długości, najczęściej składający się z wartości binarnych. Każdy z bitów wektora pełni rolę genu. Zbiór chromosomów o określonej liczności tworzy populację. Algorytm genetyczny potrzebuje zdefiniowania następujących operacji:
- generacji populacji początkowej,
- określenia jakości poszczególnych osobników,
- reprodukcji,
- mutacji,
- krzyżowania.
Schemat algorytmu genetycznego przedstawiono na rys:

![schematGen.JPG](https://4programmers.net/Download/4020/897)
Schemat klasycznego algorytmu genetycznego.

Generacja populacji początkowej zaczyna proces ewolucji. Po jej wykonaniu otrzymujemy populację, składającą się z osobników o chromosomach z losowymi wartościami genów. Bardzo ważnym elementem jest określenie liczności populacji. Zbyt mała liczba osobników może prowadzić do małego przeszukania przestrzeni rozwiązań, a zbyt duża do długiego działania algorytmu. Przykładowy chromosom, o 10 genach może wyglądać następująco:



Ch=(1,0,0,1,0,0,0,1,1,0).


Sposób budowania określonego osobnika na podstawie chromosomu binarnego jest określany przez projektanta algorytmu.

Kolejnym etapem algorytmu jest obliczenie wartości funkcji przystosowania. Określa ona jakość osobnika, opartego na wzorcu znajdującym się w chromosomie. Istnieją pewne założenia dotyczące funkcji dopasowania:

  • przyjmuje ona wartości większe od 0,
  • proces optymalizacji dąży do uzyskania maksimum funkcji przystosowania.

    Jeżeli wyznaczona funkcja nie spełnia powyższych warunków, powinna zostać poddana transformacji.

    Po obliczeniu wartości funkcji przystosowania każdego osobnika, następuje selekcja chromosomów do reprodukcji. Najprostszą i najczęściej stosowaną jest metoda ruletki. Jej sposób działania przebiega w następującej kolejności:
  • obliczenie sumy przystosowań wszystkich osobników,
  • obliczona suma stanowi całe "koło ruletki",
  • każdemu osobnikowi przydzielany jest wycinek koła według wzoru:

    wzor24.JPG

- losowana jest liczba z przedziału <0,100>,
- osobnik, na który wskazuje wylosowany punkt zostaje wytypowany do reprodukcji,
- liczba losowań jest równa liczności populacji.
W wyniku działania tej metody, wyznaczone zostają chromosomy do reprodukcji. Choć wybór jest losowy, chromosomy o wyższej wartości funkcji przystosowania mają większe prawdopodobieństwo wylosowania. Jest to bezpośrednia analogia z procesu ewolucji naturalnej.
Operator krzyżowania umożliwia wymianę materiału genetycznego pomiędzy rodzicami. Z grupy wyznaczonych np. metodą ruletki chromosomów generuje się losowo pary rodziców. Jeden rodzic może powtórzyć się wiele razy (to również analogia do procesów naturalnych). Kolejnym etapem jest losowanie punktu podziału kodu genetycznego rodziców (crossing-over). Pierwszy potomek otrzymuje pierwsze n genów rodzica A i m genów rodzica B (n+m=wielkość chromosomu). Drugi potomek dziedziczy pierwsze n genów rodzica B i m genów rodzica A. Iteracja ta jest powtarzana dla każdej pary rodziców. W wyniku jej działania otrzymujemy populację potomków, która zastępuje populację rodziców.
Ważnym operatorem jest operator mutacji. Trzeba zaznaczyć, że mutacja nie ma za zadanie polepszyć jakość osobników, lecz zwiększyć różnorodność genetyczną. Metoda działania operatora mutacji jest bardzo prosta - losowana jest liczba z przedziału <1,n> gdzie n jest liczbą genów w chromosomie. Po wylosowaniu liczby gen, o numerze jej odpowiadającym jest przekłamywany - jeśli miał wartość 1 to jest ona zmieniana na 0 i odwrotnie. Operacja mutacji nie powinna przebiegać zbyt często. Zakłada się, analogicznie do procesów naturalnych, bardzo małe prawdopodobieństwo jej wystąpienia. Powinna być ona przeprowadzona na populacji potomków.
Wszystkie opisane wyżej czynności wykonujemy do chwili osiągnięcia warunku stopu. Najczęściej określa się go jako określoną liczbę powtórzeń (pokoleń). Gdy algorytm zatrzyma się, najlepszy osobnik ostatniego pokolenia przyjmowany jest jako rozwiązanie problemu optymalizacyjnego. Nie istnieje gwarancja, że jest to rozwiązanie optymalne. Praktyka pokazuje jednak, że przy odpowiednio dobranej liczności populacji, ilości pokoleń i odpowiednio dobranym prawdopodobieństwem mutacji uzyskuje się bardzo dobre wyniki.
Założenia dotyczące algorytmu genetycznego, wykorzystanego do optymalizacji hipotetycznej sieci neuronowej .
Jak wspomniałem wcześniej, algorytm genetyczny dokonuje operacji na osobnikach pewnej populacji, dokładniej mówiąc na chromosomach poszczególnych osobników poprzez standardowe operatory genetyczne. Podstawowymi elementami, które trzeba zaprojektować implementując algorytm genetyczny, są:
- określenie postaci funkcji celu,
- sposób kodowania poszczególnych sieci neuronowych w chromosomy,
- określenie liczności populacji,
- określenie prawdopodobieństwa wystąpienia mutacji i inwersji.
W zadaniu optymalizacji struktury sieci, jako cel wybrałem liczbę epok potrzebną do trenowania danej sieci przy wzięciu pod uwagę złożoności jej struktury. Ewolucja dąży więc do maksymalizacji następującej funkcji:

![wzor25.JPG](https://4programmers.net/Download/4020/871)
gdzie:
le - liczba epok,
ln - liczba neuronów.

Model taki przyjąłem na podstawie własnych symulacji. Testy wykazały, że żaden z tych elementów oddzielnie nie pozwala na otrzymanie optymalnej sieci. Często sieć o bardziej złożonej strukturze wykazuje nieco lepsze właściwości treningu niż sieć mniejsza, lecz nie są one proporcjonalne do złożoności obliczeniowej. Sensownym więc wydaje się poddać minimalizacji oba czynniki, co powinno przy dostatecznie długim, w sensie pokoleniowym czasie, pozwolić na otrzymanie sieci o optymalnych parametrach. Postać odwrotną funkcji zastosowano w celu zgodności z klasycznym algorytmem genetycznym, w którym optymalizacja polega na maksymalizacji funkcji celu. Kolejnym elementem algorytmu genetycznego, który należy dobrać podczas implementacji jest liczność populacji. Zbyt duża powoduje wydłużenie czasu działania algorytmu a zbyt mała nie zapewnia dostatecznej różnorodności genetycznej. Ja stosuję liczność populacji równą 20. Kolejnym ważnym elementem jest sposób kodowania chromosomów, opisujących strukturę sieci. Zgodnie z założeniami klasycznego algortymu genetycznego przyjmuję kodowanie binarne. Można przyjąć następujące rozwiązanie : każdy chromosom składa się z 21 bitów, po 7 bitów na każdą warstwę ukrytą sieci (przy założeniu struktury 3 warstw ukrytych sieci - a jak wynika z doświadczeń ludzi zajmujących się tymi tematami, taka złożoność wystarcza w większości problemów, max po 128 neuronów na warstwę). Warstwa wejściowa i wyjściowa nie są kodowane, gdyż ich rozmiar jest determinowany przez dane uczące oraz charakter problemu. Liczba neuronów w danej warstwie jest obliczana poprzez konwersje liczby z reprezentacji bitowej na dziesiętną.
Ostatnim parametrem, który musi zostać określony na etapie implementacji to wielkość prawdopodobieństwa wystąpienia operacji genetycznych. Mogą być to następujące wielkości prawdopodobieństw :
- operacja krzyżowania - 1,
- operacja mutacji - 0,01,
- operacja inwersji - 0,001.
Pozostałe elementy algorytmu, wykorzystanego do optymalizacji sieci są zgodne z założeniami klasycznego algorytmu genetycznego.

2. Prezentacja i analiza wyników predykcji notowań giełdowych indeksu WIG20

Przejdę teraz do pokazania efektywności zastosowania wielowarstwowej, nieliniowej sieci neuronowej do predykcji ciągów niedeterministycznych. Badanie zostało wykonane przy wykorzystaniu opracowanej specjalnie do tego celu aplikacji (prawdopodobnie niebawem zamieszczę w sieci - muszę tylko zlokalizować płytkę ze źródłami, więc proszę o cierpliwość). Trzeba na tym etapie podkreślić, że wielowarstwowa sieć nieliniowa jest siecią "ogólnego przeznaczenia" - można zastosować specjalizowane architektury i sprawić, że predykcja da jeszcze lepsze wyniki.
Do predykcji notowań WIG20 wykorzystana została sieć o architekturze 50-25-10-1, czyli 50 wejść, 25 neuronów w warstwie pierwszej, 10 w drugiej oraz jedno wyjście. Sieć została poddana treningowi o następujących parametrach:
- współczynnik uczenia = 0,3,
- współczynnik momentu= 0,9,
- dopuszczalny błąd epoki=0,01.
Zbiór uczący składał się z 200 par uczących. Każda para zawierała 50 kolejnych notowań historycznych indeksu WIG20. Dane zostały przeskalowane metodą odchylenia od średniej. Trenowanie trwało 2934 epok.
Po treningu wykonano predykcję o horyzoncie 38 okresów. Wynik predykcji przedstawiono na rys.

![Wynik predykcji notowań WIG20 i wartości rzeczywistych.](https://4programmers.net/Download/4020/894)

W celu dokonania analizy jakości predykcji wykonane zostały testy, porównujące wyniki uzyskane za pomocą sieci neuronowej z metodami funkcji trendu oraz przeprowadzono pomiary błędów oraz wyników testów. Jako pierwsze przeprowadzono porównanie wyników z metodami analizy funkcji trendu. Wykorzystano model liniowy i wielomianowy. Wynik przedstawiono na rys a szczegółowe wyniki w tabeli pod ilustracją:

![wynikroznemetody.JPG](https://4programmers.net/Download/4020/895)
Porównanie wyników predykcji metodami sztucznej sieci neuronowej oraz trendem liniowym i wielomianowym z danymi rzeczywistymi.

Wartości indeksu WIG20 w kolejnych okresach otrzymane przy zastosowaniu różnych metod predykcji.
![tabelawyniki1.JPG](https://4programmers.net/Download/4020/905)
Wykres ukazuje zupełną nieprzydatność do tego zadania liniowego modelu funkcji trendu. Wartości, uzyskane metodą trendu wielomianowego się o wiele lepsze. Aby wskazać, która z wybranych metod daje najlepszą skuteczność w badanym okresie przeprowadzono wyliczenia.
Jako pierwsze wyliczono podstawowe parametry. Wyniki przedstawiono w tabeli

tabelatestytrendy.JPG


Wyniki testów dla różnych metod predykcji.
Z wyników zamieszczonych w tabeli widać znaczną przewagę sieci neuronowej nad pozostałymi metodami oceny trendu. Każdy parametr jest korzystniejszy w przypadku sieci neuronowej. Wyniki uzyskane dzięki sieci oscylują cały czas wokół wartości rzeczywistych. Kolejnym badaniem jest analiza współczynnika zgodności kierunków zmian, który określa odsetek przypadków, w których kierunek rzeczywisty zmian jest zgodny z kierunkiem zmian zmiennych prognozowanych. Współczynnik ten mówi, w jakim stopniu dana metoda może być wykorzystana w celu wspomagania podejmowania decyzji. Aby uznać daną metodę za przydatną do tego celu, miernik musi mieć wartość większą niż 50%.
Wartość miernika wylicza się z następującego wzoru:
![wzor26.JPG](https://4programmers.net/Download/4020/870)
gdzie:
![wzor27.JPG](https://4programmers.net/Download/4020/869)
Uzyskane wyniki są nastepujące:
![zgodnosczmian.JPG](https://4programmers.net/Download/4020/868)
Wyniki testu zgodności kierunków zmian.
Widać więc, że sieć umożliwia lepszą skuteczność również w tym teście. Z powyższych testów widać, że sieć neuronowa daje lepsze efekty od przedstawionych metod opartych na krzywych trendu. Wyniki, uzyskane przy wykorzystaniu wielowarstwowej, jednokierunkowej sieci neuronowej mogą być jeszcze lepsze, gdy szereg wejściowy podda się operacjom wstępnej obróbki. Trzeba jednak pamiętać, że metodyka oparta na sieciach neuronowych, implementowana w systemach komputerowych, charakteryzuje się znaczną złożonością obliczeniową.




Bibliografia

  1. Duch W., Korbicz J., Rutkowski L., Tadeusiewicz R.: Biocybernetyka i inżynieria biomedyczna 2000. Sieci neuronowe, Exit, Warszawa 2000.
  2. Gwiazda T.: Algorytmy genetyczne, WSPiZ, Warszawa 1998.
  3. Grad L.: Materiały do wykładów z przedmiotu „Metody sztucznej inteligencji w zarządzaniu”, WSISiZ (chyba dostepne są jeszcze na stronach studentów wsisiz)
  4. Goldberg D. E., Algorytmy genetyczne i ich zastosowanie, tłum. K. Grygiel, wyd. 2, Wydawnictwo Nauowo-Techniczne, Warszawa 1998.
  5. Tadeusiewicz R., Sieci neuronowe, Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie, 1993.
  6. Rutkowska D., Rutkowski L., Piliński M., Sieci neuronowe, algorytmy genetyczne i systemy rozmyte, Wydawnictwo Naukowe PWN, Warszawa 1999.

5 komentarzy

Co z obrazkami ?? Nic nie widać :(

Artykuł bardzo cenny. Jeszcze są dwa tak cenne artykuły w sieci. Niestety u siebie nie widzę obrazków (ani jednego) (sprawdzałem w dwóch przeglądarkach Opera oraz IE i nic - widocznie nie ma ich na serwerze).
Dzięki!

Racja, bibliografia umknęła...Późno było więc może to jest przyczyną... Już dodałem.

Artykuł wygląda na zrobiony poprawnie i nie zawierający błędów (chociaż nie czytałem całego :> ). Przydałoby się podać jeszcze jeden sposób na zabezpieczenie sieci przed minimum lokalnym. Współczynnik momentu zazwyczaj sobie radzi, ale można również uczyć sieć wyrywkowo - przygotowanymi, konkretnymi wzorcami – a nie epokowo.
Funkcja akywacji "logistyczna" to inaczej funkcja sigmoidalna unipolarna, a tangens hiperboliczny to inaczej funkcja sigmoidalna bipolarna (to tak, gdyby ktoś szukał czegoś więcej o nich). Przy implementacji tej drugiej, wygodniejsza wydaje się postać: f(x)=2/(1+e^(Bx))-1, no ale kto co woli... Dobór odpowiedniej funkcji aktywacji to bardzo ważny element przy projektowaniu sieci w zależności od jej zastosowania. Warto też dodać, że przy B dążącym do nieskończoności, obie funkcje automatycznie przechodzą w progowe unipolarną/bipolarną (o których autor chyba nie wspomina) - ale to jasna sprawa.
Co do pozycji lektur, jeśli chodzi o Sztuczne Sieci Neuronowe – to jeśli mi wolno – mogę polecić:
„Sieci Neuronowe” – Stanisław Osowski
„Sieci Neuronowe w ujęciu algorytmicznym” – Stanisław Osowski
„Sieci Neuronowe” – Ryszard Tadeusiewicz
Powinny być na sieci skany w różnych formach plikowych – ja oczywiście byłem w posiadaniu ich tradycyjnych form bibliotecznych :>

Nie widzę źródeł. Czyżbyś był taki mądry, że sam to wszystko wymyśliłeś?
Jeśli zapomniałeś ich dodać - jest to jak najbardziej na miejscu, żeby się tu znalazły :)