WSTĘP

Wiele praktycznych zastosowań inżynierskich można sformułować jako problem optymalizacji globalnej, w którym funkcja celu ma wiele minimów lokalnych, a pochodne funkcji celu są niedostępne. Ewolucja różniczkowa (DE) to algorytm ewolucyjny kodujący liczby zmiennoprzecinkowe do optymalizacji globalnej w przestrzeniach ciągłych. Obecnie jest on wykorzystywany jako potężna metoda optymalizacji globalnej w szerokim zakresie dziedzin badawczych. Najnowsze badania wskazują, że samoadaptacyjne algorytmy DE są znacznie lepsze niż oryginalny algorytm DE. Konieczność zmiany parametrów sterowania podczas procesu optymalizacji została również potwierdzona eksperymentami. Metoda DE z samoadaptacyjnymi parametrami sterowania została już przedstawiona w pracy (Bresta). W niniejszym rozdziale przedstawiono samoadaptacyjne podejścia, które niedawno zaproponowano dla parametrów sterowania w algorytmie DE.

TŁO

Ewolucja różnicowa

Ewolucja różnicowa tworzy nowe rozwiązania kandydackie poprzez połączenie osobnika macierzystego i kilku innych osobników z tej samej populacji. Kandydat zastępuje osobnika macierzystego tylko wtedy, gdy ma lepszą wartość dopasowania. Populacja oryginalnego algorytmu DE zawiera NP wektorów D-wymiarowych: x_i,G, i = 1, 2, …, NP. G oznacza generację. Populacja początkowa jest zazwyczaj wybierana losowo, jednolicie, pomiędzy dolną i górną granicą. Granice są określane przez użytkownika w zależności od charakteru problemu. Po inicjalizacji DE wykonuje kilka transformacji (operacji) wektorów: mutację, krzyżowanie i selekcję. Wektor mutanta v_i,G można utworzyć, stosując jedną ze strategii mutacji . Najbardziej użyteczną strategią jest "rand/1": v_i,G = x_r1,G + F × (x_r2,G - x_r3,G), gdzie F to współczynnik skali mutacji w zakresie [0, 2], zwykle mniejszy od 1. Indeksy r1, r2, r3 reprezentują losowe i odrębne liczby całkowite generowane w zakresie [1, NP], a także różne od indeksu i. Po mutacji, operacja krzyżowania "binarnego" tworzy wektor próbny u_i,G, zgodnie z i-tym wektorem populacji i odpowiadającym mu wektorem mutanta v_i,G:



gdzie i = 1, 2, …, NP i j = 1, 2, …, D. CR jest parametrem lub czynnikiem krzyżowania w zakresie [0,1] i przedstawia prawdopodobieństwo utworzenia parametrów dla wektora próbnego z wektora mutanta. Jednorodna wartość losowa rand mieści się w zakresie [0, 1]. Indeks j_rand ∈ [1, NP] jest losowo wybranym indeksem i odpowiada za to, że wektor próbny zawiera co najmniej jeden parametr z wektora mutanta. Operacja selekcji wybiera, zgodnie z obiektywną wartością dopasowania wektora populacji x_i,G i odpowiadającego mu wektora próbnego u_i,G, który wektor przetrwa, aby stać się członkiem następnego pokolenia. Oryginalny DE ma więcej strategii, a Feoktistov zaproponował pewne ogólne rozszerzenia strategii DE. Pytanie brzmi, która strategia jest najbardziej odpowiednia do rozwiązania konkretnego problemu. Ostatnio niektórzy badacze stosowali różne kombinacje dwóch, trzech lub nawet więcej strategii w trakcie procesu ewolucyjnego.

Strojenie parametrów i sterowanie parametrami

Globalnie rozróżniamy dwie główne formy ustawiania wartości parametrów: strojenie parametrów i sterowanie parametrami . Pierwsze oznacza powszechnie stosowane podejście, które polega na znalezieniu prawidłowych wartości parametrów przed uruchomieniem algorytmu, a następnie dostrojeniu algorytmu z wykorzystaniem tych wartości, które pozostają niezmienne w trakcie działania. Drugie oznacza, że wartości parametrów są zmieniane w trakcie działania. Według Eibena zmiany można podzielić na trzy klasy:

1. Deterministyczna kontrola parametrów ma miejsce, gdy wartość parametru jest zmieniana przez jakąś regułę deterministyczną.
2. Adaptacyjna kontrola parametrów jest stosowana, gdy istnieje jakaś forma sprzężenia zwrotnego z wyszukiwania, która służy do określenia kierunku i/lub wielkości zmiany parametru.
3. Samoadaptacyjne sterowanie parametrami opiera się na koncepcji, że "ewolucja ewolucji" może być wykorzystana do wdrożenia samoadaptacji parametrów. W tym przypadku parametry, które mają zostać zaadaptowane, są kodowane w chromosomie (osobnikach) i podlegają działaniu operatorów genetycznych. Lepsze wartości tych zakodowanych parametrów prowadzą do lepszych osobników, które z kolei mają większe szanse na przeżycie i wydanie potomstwa, a tym samym na rozmnażanie tych lepszych wartości parametrów.

DW ma trzy parametry kontrolne: współczynnik wzmocnienia wektora różnicowego - F, parametr kontrolny krzyżowania - CR oraz wielkość populacji - NP. Oryginalny algorytm DW utrzymuje wszystkie trzy parametry kontrolne na stałym poziomie podczas procesu optymalizacji. Jednak nadal brakuje wiedzy na temat tego, jak znaleźć w miarę dobre wartości parametrów kontrolnych DW dla danej funkcji . Chociaż wykazano, że algorytm DE jest prostym, a zarazem wydajnym algorytmem ewolucyjnym do optymalizacji funkcji ciągłych, użytkownicy nadal borykają się z problemem wstępnego testowania i ręcznego dostrajania parametrów sterowania przed rozpoczęciem faktycznego procesu optymalizacji . Rozwiązaniem okazała się samoadaptacja, która okazała się niezwykle korzystna w automatycznym i dynamicznym dostosowywaniu parametrów sterowania. Samoadaptacja pozwala strategii ewolucyjnej dostosować się do dowolnej ogólnej klasy problemów poprzez odpowiednią rekonfigurację, i odbywa się to bez interakcji użytkownika.

PRACE POWIĄZANE

Prace związane z ewolucją różnicową

Algorytm DE został zaproponowany przez Storna i Price′a i od tego czasu był wykorzystywany w wielu praktycznych zastosowaniach. Oryginalny DE został zmodyfikowany i zaproponowano wiele nowych wersji. Ali i Törn zaproponowali nowe wersje algorytmu DE, a także zasugerowali pewne modyfikacje klasycznego DE w celu poprawy jego wydajności i odporności. Wprowadzili pomocniczą populację osobników NP obok populacji oryginalnej , zastosowano notację wykorzystującą zbiory). Następnie zaproponowali regułę automatycznego obliczania parametru kontrolnego F. Jiao i inni zaproponowali modyfikację algorytmu DE, stosując metodę teorii liczb do generowania populacji początkowej i wykorzystując uproszczoną aproksymację kwadratową z trzema najlepszymi punktami. Mezura-Montes i inni przeprowadzili badanie porównawcze wariantów DE. Zaproponowali regułę losowej zmiany parametru sterowania F z przedziału [0,4, 1,0] na poziomie generacji. Zastosowali różne wartości parametru sterowania CR dla każdego problemu. Najlepszą wartość CR dla każdego problemu uzyskano poprzez dodatkowe eksperymenty. Tvrdik w (Tvrdik, 2006) zaproponował algorytm DE wykorzystujący konkurencję między różnymi ustawieniami parametrów sterowania. Feoktistov w swojej książce stwierdza, że "koncepcja ewolucji różniczkowej to spontaniczna samoadaptacja do funkcji".

Prace dotyczące adaptacyjnego lub samoadaptacyjnego DE

Liu i Lampinen zaproponowali wersję DE, w której parametr kontroli mutacji i parametr kontroli krzyżowania są adaptacyjne. Samoadaptacyjny DE (SDE) zaproponowali Omran i inni, w którym dostrajanie parametrów nie jest wymagane. Samoadaptację zastosowano dla parametrów kontrolnych F i CR. Teo podjął próbę samoadaptacji parametru wielkości populacji, oprócz samoadaptacyjnego krzyżowania i tempa mutacji. Brest i inni zaproponowali algorytm DE, wykorzystujący mechanizm samoadaptacji dla parametrów kontrolnych F i CR. Wydajność samoadaptacyjnego algorytmu ewolucji różniczkowej została oceniona przy użyciu zestawu funkcji testowych przeznaczonych do optymalizacji parametrów rzeczywistych z ograniczeniami . Qin i Suganthan zaproponowali "Samoadaptacyjny algorytm ewolucji różniczkowej (SaDE), w którym wybór strategii uczenia się i dwóch parametrów sterowania F i CR nie wymaga wstępnego zdefiniowania. Podczas ewolucji odpowiednia strategia uczenia się i ustawienia parametrów są stopniowo samoadaptowane, zgodnie z doświadczeniem uczenia się". Brest i inni przedstawili porównanie wydajności wybranych algorytmów ewolucji różniczkowej, które wykorzystują różne samoadaptacyjne lub adaptacyjne mechanizmy parametrów sterowania. W niniejszym artykule algorytmy DE wykorzystały więcej niż jedną strategię DE. Samoadaptacja była szeroko stosowana w programowaniu ewolucyjnym i strategiach ewolucyjnych (ES) w celu dostosowania rozmiaru kroku wyszukiwania dla każdej zmiennej celu . Abbass zaproponował samoadaptacyjne DE dla problemów optymalizacji wielokryterialnej.

SAMOADAPCYJNE PARAMETRY STEROWANIA W EWOLUCJI RÓŻNICZKOWEJ

W tej sekcji przedstawiono trzy samoadaptacyjne podejścia DE, które zostały zastosowane do parametrów sterowania F i CR.

Parametry sterowania samoadaptacyjnego z wykorzystaniem rozkładu jednostajnego.

Autoadaptacyjny DE odnosi się do mechanizmu samoadaptacji parametrów sterowania, zaproponowanego przez Bresta. Ten mechanizm samoadaptacji wykorzystywał strategię "rand/1/bin". Każdy osobnik w populacji został rozszerzony o wartości dwóch parametrów sterowania: (x_i,G, F_i,G, CR_i,G), i ∈ 1, 2, ...,NP. Oba parametry sterowania zastosowano na poziomie osobnika. Brest i inni zaproponowali samoadaptacyjny DE, w którym nowe parametry sterowania F_i,G+1 i CR_i,G+1 oblicza się w następujący sposób:



i generują parametry sterowania F i CR w nowym wektorze. Wielkości rand_j, j ∈ {1, 2, 3, 4} są jednorodnymi wartościami losowymi ∈ [0, 1]. Wielkości τ₁ i τ₂ reprezentują prawdopodobieństwa dostosowania parametrów sterowania F i CR. Parametry τ₁ ,i τ₂, F_l, F<sub>u,/sub> przyjęto jako wartości stałe, odpowiednio 0,1, 0,1, 0,1, 0,9. Nowy F przyjmuje wartość z zakresu [0,1,1,0] w sposób losowy. Nowy CR przyjmuje wartość z zakresu [0,1]. Nowe Fi,G+1 i CRi,G+1 są uzyskiwane przed wykonaniem mutacji. Wpływają one zatem na operacje mutacji, krzyżowania i selekcji nowego wektora xi,G+1. W (Brest ,2006a) zastosowano samoadaptacyjny mechanizm sterowania do zmiany parametrów sterowania F i CR w trakcie procesu ewolucyjnego. Trzeci parametr kontrolny NP pozostał niezmieniony.

Podejście Abbassa

Abbass (Abbass, 2002) zaproponował samoadaptacyjny algorytm ewolucji różniczkowej Pareto (SPDE). SPDE został wykorzystany w problemach optymalizacji wielokryterialnej. Nowe parametry sterowania Fi,G+1 i CRi,G+1 oblicza się w następujący sposób:



gdzie N(0,1) to rozkład Gaussa. Jeśli wartość Fi,G+1 nie mieści się w [0,1], do jej naprawy stosuje się prostą regułę. Podobnie jest w przypadku wartości CRi,G+1. Następnie oblicza się wektor mutanta vi,G:



i wykonywana jest operacja krzyżowania:



Parametr kontrolny CR jest samoadaptujący się, poprzez kodowanie go w każdym osobniku. Podejście zaproponowane przez Omrana, Salmana i Engelbrechta

Ze względu na sukces osiągnięty w SPDE przez samoadaptujący się CR, Omran i inni zaproponowali samoadaptacyjny DE (SDE), w którym ten sam mechanizm jest stosowany do samoadaptacji parametru kontrolnego F. Parametr kontrolny CR jest generowany dla każdego osobnika na podstawie rozkładu normalnego (CR ~ N(0,5;0,15)) w SDE, a operacja mutacji zmienia się następująco:



gdzie



Indeksy r4, r5, r6 reprezentują losowe i różne liczby całkowite generowane w zakresie [1, NP]. Zatem każdy osobnik i ma swój własny parametr sterujący Fi, który jest obliczany jako stochastyczna liniowa kombinacja parametrów sterujących losowo wybranych osobników. Przedstawione mechanizmy samoadaptacji parametrów sterujących F i CR wykorzystują strategię "rand/1/bin". Oba parametry sterujące są stosowane na poziomie osobniczym. Trzeci parametr sterujący NP pozostaje stały w trakcie procesu ewolucyjnego.

TRENDY NA PRZYSZŁOŚĆ

Zachowanie DE jest uzależnione od wartości jego parametrów (F, CR, NP). W ciągu ostatnich dwóch dekad wiele prac naukowych podejmowało problem znalezienia wglądu w zachowanie algorytmu (Zaharie, 2002). Teoria DE wciąż pozostaje w tyle za badaniami empirycznymi. Teoretyczne badania DE są wysoce pożądane jako przyszłe badania. Nie jest łatwym zadaniem, aby jeden algorytm optymalizacyjny był jednocześnie szybki (np. wymagał niewielkiej liczby ewaluacji funkcji) i odporny (np. nie wpadał w pułapkę lokalnego optimum). Na podstawie naszych doświadczeń (inni autorzy zgłaszali podobne obserwacje) z algorytmem DE, możemy stwierdzić, że DE zapewnia większą odporność, jeśli liczebność populacji jest większa. Z drugiej strony, jeśli liczebność populacji jest zwiększona, potrzebna jest większa moc obliczeniowa (średnio). Liczebność populacji jest ważnym parametrem kontrolnym, dlatego w przyszłości oczekuje się adaptacyjnych i/lub samoadaptacyjnych podejść do tego parametru. W tym rozdziale wykorzystano tylko strategię DE "rand/1/bin", ale algorytm DE oferuje więcej strategii . Którą kombinację (samoadaptacyjnych) strategii DE należy zastosować, aby uzyskać najlepszą wydajność? Można zastosować strategię z tym samym lub innym prawdopodobieństwem, a nawet zastosować samoadaptację, aby wybrać najodpowiedniejszą strategię w procesie optymalizacji. Przyszłe prace mogą być również ukierunkowane na testowanie proponowanych samoadaptacyjnych wersji algorytmu DE, szczególnie w przypadku problemów optymalizacji z ograniczeniami. Optymalizacja wielokryterialna stanowi również wyzwanie dla przyszłych prac.

WNIOSKI

Przedstawiono algorytm ewolucji różniczkowej (DE), koncentrując się na samoadaptacyjnych parametrach sterowania. W rozdziale opisano trzy podejścia samoadaptacyjne, które zostały ostatnio zaproponowane w literaturze. Przedstawione podejścia mają parametry sterowania stosowane na poziomie indywidualnym. Jeśli przyjrzymy się literaturze, samoadaptacyjne wersje algorytmu DE zazwyczaj dawały lepsze wyniki w porównaniu z oryginalnym algorytmem DE. Możemy stwierdzić, że samoadaptacja może poprawić wydajność algorytmu DE, a ten potężny algorytm optymalizacji globalnej mógłby być w przyszłości wykorzystywany w szerokim zakresie obszarów badawczych.</sub>

WSTĘP

Wnioskowanie gramatyczne (znane również jako indukcja gramatyczna) to problem uczenia się gramatyki języka na podstawie zbioru przykładów. W szerokim ujęciu, uczący się otrzymuje dane, które powinny zwrócić gramatykę zdolną do wyjaśnienia w pewnym zakresie danych wejściowych. Gramatyka wywnioskowana z danych może następnie zostać wykorzystana do klasyfikacji niewidzianych danych lub zapewnienia odpowiedniego modelu dla nich. Klasyczna formalizacja wnioskowania gramatycznego (GI) znana jest jako identyfikacja języka w granicy . W tym przypadku istnieje skończony zbiór S₊ ciągów znaków, o których wiadomo, że należą do języka L (przykłady pozytywne) i inny skończony zbiór S- ciągów znaków, które nie należą do języka L (przykłady negatywne). Język L jest uznawany za identyfikowalny w granicy, jeśli istnieje procedura znajdowania gramatyki G takiej, że S₊⊆ L(G), S_- ⊄ L(G) oraz, w granicy, dla wystarczająco dużych S₊ i S>sub>-, L = L(G). Podano rozłączne zbiory S₊ i S>sub>-, aby dostarczyć wskazówek do wnioskowania reguł produkcji P nieznanej gramatyki G użytej do wygenerowania języka L. Wnioskowanie gramatyczne obejmuje tak różnorodne dziedziny, jak przetwarzanie mowy i języka naturalnego, analiza genów, rozpoznawanie wzorców, przetwarzanie obrazów, przewidywanie sekwencji, wyszukiwanie informacji, kryptografia i wiele innych. Doskonałe źródło najnowocześniejszego przeglądu tematu znajduje się w . Tradycyjnie większość prac w dziedzinie GI koncentrowała sięna wnioskowaniu gramatyk regularnych, próbując wygenerować automaty skończenie stanowe, których można efektywnie się nauczyć. W przypadku języków bezkontekstowych niektóre niedawne podejścia wykazały ograniczony sukces , ponieważ przestrzeń poszukiwań możliwych gramatyk jest nieskończona. Zasadniczo języki nawiasowe i palindromowe są typowymi przypadkami testowymi skuteczności metod wnioskowania gramatycznego. Oba języki są bezkontekstowe. Język nawiasowy jest deterministyczny, natomiast język palindromowy jest niedeterministyczny. Zastosowanie metod ewolucyjnych do bezkontekstowego wnioskowania gramatycznego nie jest nowe, ale tylko kilka prób zakończyło się sukcesem. Wyard (1991) z powodzeniem wykorzystał algorytm genetyczny (GA) do wnioskowania gramatyk dla języka prawidłowo zbalansowanych i zagnieżdżonych nawiasów, ale nie udało mu się to w przypadku języka zdań zawierających taką samą liczbę a i b (język aⁿbⁿ). W innej próbie (Wyard, 1994) uzyskał pozytywne wyniki w zakresie wnioskowania dwóch klas gramatyk bezkontekstowych: klasy palindromów n-symbolowych z 2 ≤ n ≤ 4 i klasy małych gramatyk języka naturalnego. Sen i Janakiraman (1992) zastosowali algorytm genetyczny przy użyciu automatu ze stosem do wnioskowania i pomyślnie poznali język aⁿbⁿ oraz problem równoważenia nawiasów. Jednak ich podejście nie jest dobrze skalowalne. Huijsen (1994) zastosował algorytm genetyczny do wnioskowania gramatyk bezkontekstowych dla problemu równoważenia nawiasów, języka równej liczby a i b oraz palindromów 2-symbolowych o parzystej długości. Huijsen używa schematu kodowania "opartego na znacznikach", którego główną zaletą jest dopuszczanie chromosomów o zmiennej długości. Wnioskowanie gramatyk regularnych zakończyło się sukcesem, ale wnioskowanie gramatyk bezkontekstowych zakończyło się niepowodzeniem. Wyniki uzyskane we wcześniejszych próbach wykorzystania algorytmów genetycznych (GA) do bezkontekstowego wnioskowania gramatycznego były ograniczone. Pierwsza próba wykorzystania programowania genetycznego (GP) do wnioskowania gramatycznego wykorzystywała automaty ze stosem i z powodzeniem nauczyła się języka nawiasowego, ale nie powiodła się w przypadku języka aⁿbⁿ. Korkmaz i Ucoluk (2001) również przedstawili podejście GP wykorzystujące teorię prototypów, która umożliwia rozpoznanie podobieństwa między gramatykami w populacji. Dzięki tej reprezentacji możliwe jest rozpoznanie tzw. bloków konstrukcyjnych, ale wyniki są wstępne. Javed i jego współpracownicy (2004) zaproponowali podejście programowania genetycznego (GP) z heurystycznymi operatorami gramatycznymi specyficznymi dla danej gramatyki, z nielosową konstrukcją początkowej populacji gramatycznej. Ich podejście skutecznie doprowadziło do powstania małych gramatyk bezkontekstowych. Rodrigues i Lopes (2006) zaproponowali hybrydowe podejście GP, które wykorzystuje macierz pomyłek do obliczania dopasowania. Zaproponowali również lokalny mechanizm wyszukiwania, który wykorzystuje informacje uzyskane z analizy składniowej zdań do generowania zbioru użytecznych produkcji. System ten został z powodzeniem zastosowany w językach nawiasowych i palindromowych.

TŁO

Język formalny jest zazwyczaj definiowany w następujący sposób. Mając skończony alfabet Σ symboli, definiujemy zbiór wszystkich ciągów znaków (w tym pusty ciąg ε) w Σ jako Σ*. Zatem chcemy nauczyć się języka L ⊂ Σ*. Alfabet Σ może być zbiorem znaków lub zbiorem słów. Najczęstszym sposobem definiowania języka jest oparcie się na gramatykach, które podają reguły łączenia symboli i tworzenia wszystkich zdań języka. Gramatyka jest definiowana przez czwórkę G = (N, Σ, P, S), gdzie N jest alfabetem symboli nieterminalnych, Σ jest alfabetem symboli terminalnych takim, że N ∩ Σ = f, P jest skończonym zbiorem reguł produkcji w postaci α -> β dla α, β ∈ (N ∪ Σ )*, gdzie * reprezentuje zbiór symboli, które można utworzyć, biorąc dowolną ich liczbę, ewentualnie z powtórzeniami. S jest specjalnym symbolem nieterminalnym zwanym symbolem startowym. Język L(G) wygenerowany z gramatyki G to zbiór wszystkich ciągów składających się wyłącznie z symboli terminalnych, które można wyprowadzić z symbolu startowego S poprzez zastosowanie reguł produkcji. Proces wyprowadzania ciągów poprzez zastosowanie produkcji wymaga zdefiniowania nowego symbolu relacji ⇒. Niech αXβ będzie ciągiem terminali i nieterminali, gdzie X jest nieterminalem. Oznacza to, że α i β są ciągami w ( N ∪ Σ)*, a X ∈ N. Jeśli X -> jest produkcją G, możemy powiedzieć, że αXβ ⇒ αφXβ. Ważne jest, aby zaznaczyć, że jeden krok wyprowadzenia może zastąpić dowolny nieterminal w dowolnym miejscu ciągu. Możemy rozszerzyć relację ⇒, aby reprezentowała jeden lub wiele kroków wyprowadzenia. Używamy *, aby oznaczyć więcej kroków. Dlatego formalnie definiujemy język L(G) generowany z gramatyki G jako L(G) = { w | w ∈ Σ*, S ⇒* w }.

Hierarchia Chomsky′ego

Gramatyki są klasyfikowane według formy użytych reguł produkcji. Zazwyczaj grupuje się je w hierarchię czterech klas, znaną jako hierarchia Chomsky′ego .

o Języki rekurencyjnie przeliczalne: gramatyka jest nieograniczona, a jej produkcje mogą zastąpić dowolną liczbę symboli gramatycznych dowolną inną liczbą symboli gramatycznych. Produkcje te mają postać α ->β, gdzie α, β ∈ ( ? ∪ Σ )?.
o Języki kontekstowe: posiadają gramatyki z produkcjami, które zastępują pojedynczy symbol nieterminalny ciągiem symboli, gdy symbol ten występuje w określonym kontekście, tj. ma pewnych sąsiadów z lewej i prawej strony. Produkcje te mają postać αAγ -> αβγ, gdzie A ∈ N i α ,β , γ ∈ ( ? ∪ Σ )?. A jest zastępowane przez β, jeśli występuje między α i γ.
o Języki bezkontekstowe: w tym typie gramatyki produkcje zastępują pojedynczy nieterminal ciągiem symboli, niezależnie od kontekst tego nieterminala. Produkcje te mają postać A ? α dla A ∈ N i α∈ ( N ∪? Σ )*; zatem A nie ma kontekstu. o Języki regularne: posiadają gramatyki, w których produkcja może zastąpić tylko pojedynczy nieterminal innym nieterminalem i terminalem. Produkcje te mają postać A -> Bα lub A -> α? dla A, B ∈ N i α∈ Σ*.

Czasami przydatne jest zapisanie gramatyki w określonej formie. Najczęściej używaną w wnioskowaniu gramatycznym jest postać normalna Chomsky′ego. CFG G jest w postaci normalnej Chomsky′ego (CNF), jeśli wszystkie reguły produkcji mają postać A ? BC lub A ? α dla A, B, C ∈ N i α∈ Σ.

Algorytm Cocke′a-Youngera-Kasamiego

Aby określić, czy ciąg znaków może zostać wygenerowany przez daną gramatykę bezkontekstową w CNF, można użyć algorytmu Cocke′a-Youngera-Kasamiego (CYK). Algorytm ten jest wydajny i ma złożoność O(n³), gdzie n to długość zdania. W algorytmie CYK najpierw konstruowana jest tablica trójkątna, która określa, czy ciąg znaków w należy do L(G). Linia pozioma odpowiada pozycjom ciągu znaków w = a₁ a₂ … a_n. Pozycja tabeli V_rs to zbiór zmiennych A ∈ P takich, że A ⇒^? a_r a_r+1 … a_s. Interesuje nas, czy symbol początkowy S znajduje się w zbiorze V_1n, ponieważ jest to to samo, co powiedzenie S ⇒^? a₁ a₂ … a_n lub S ⇒^? w, tj. w ∈ L(G). Aby wypełnić tabelę, pracujemy wiersz po wierszu w górę. Każdy wiersz odpowiada jednej długości podciągu; dolny wiersz odpowiada ciągom o długości 1, drugi od dołu wiersz odpowiada ciągom o długości 2 i tak dalej, aż górny wiersz odpowiada jednemu podciągowi o długości n, którym jest samo w. Pseudokod przedstawiono na rysunku



Programowanie genetyczne

Programowanie genetyczne (GP) to technika ewolucyjna używana do przeszukiwania ogromnej przestrzeni stanów reprezentacji strukturalnych (programów komputerowych). Każdy program reprezentuje możliwe rozwiązanie zapisane w jakimś języku. Algorytm GP można podsumować na rysunku 2 .



Ocena rozwiązania odbywa się za pomocą zestawu przykładów szkoleniowych, zwanych przypadkami dopasowania, które z kolei składają się z zestawów danych wejściowych i wyjściowych. Dopasowanie jest zazwyczaj miarą odchylenia między oczekiwanym wynikiem dla każdego wejścia a wartością obliczoną przez GP. W GP stosowane są dwie główne metody selekcji: selekcja proporcjonalna do kondycji i selekcja turniejowa. W selekcji proporcjonalnej do kondycji programy są wybierane losowo z prawdopodobieństwem proporcjonalnym do ich kondycji. W selekcji turniejowej ustalona liczba programów jest losowo wybierana z populacji, a następnie wybierany jest program o najlepszej kondycji w tej grupie. W niniejszej pracy wykorzystujemy selekcję turniejową. Reprodukcja to operator genetyczny, który po prostu kopiuje program do następnego pokolenia. Krzyżowanie natomiast łączy części dwóch osobników, aby stworzyć dwa nowe. Mutacja losowo zmienia niewielką część osobnika. Każdy przebieg pętli głównej GP tworzy nową generację programów komputerowych, które zastępują poprzednią. Ewolucja zostaje zatrzymana, gdy zostanie osiągnięte satysfakcjonujące rozwiązanie lub z góry określona maksymalna liczba pokoleń.

GRAMATYCZNE PODEJŚCIE PROGRAMOWANIA GENETYCZNEGO

Prezentujemy, jak podejście GP można zastosować do wnioskowania gramatyk bezkontekstowych. Najpierw omówimy reprezentację gramatyk. Przedstawimy również modyfikacje niezbędne w operatorach genetycznych. W ostatniej sekcji omówiona zostanie ewaluacja gramatyki.

Populacja początkowa

Możliwe jest przedstawienie CFG jako listy drzew strukturalnych. Każde drzewo reprezentuje produkcję, której lewą stronę stanowi korzeń, a derywacje stanowią liście. Rysunek 3 przedstawia gramatykę G = ( N, Σ, P, S ) z Σ = {a, b} , N = {S, A} i P = {S -> AS ; S -> b; A -> SA ; A -> a }.



Populację początkową można utworzyć za pomocą produkcji losowych, pod warunkiem, że wszystkie produkcje są osiągalne bezpośrednio lub pośrednio począwszy od S.

Operatory genetyczne

Operator krzyżowania jest stosowany do pary gramatyk i działa w następujący sposób. Najpierw wybiera się produkcję za pomocą selekcji turniejowej. Jeśli druga gramatyka nie ma produkcji z tą samą lewą stroną co wybrana produkcja, krzyżowanie jest odrzucane. W przeciwnym razie produkcje są zamieniane. Operacja mutacji jest stosowana do pojedynczej wybranej gramatyki. Następnie wybierana jest produkcja, stosując ten sam mechanizm krzyżowania. Nowa produkcja, z tą samą lewą stroną i losowo wybraną prawą stroną, zastępuje wybraną produkcję. Prawdopodobieństwo krzyżowania jest zazwyczaj wysokie (≈90%), a prawdopodobieństwo mutacji jest zazwyczaj niskie (≈10%). Niestety, stosując jedynie wspomniane operatory genetyczne, nie można zagwarantować zbieżności algorytmu. W naszej niedawnej pracy wykazaliśmy, że konieczne jest użycie dwóch operatorów wyszukiwania lokalnego: operatora uczenia przyrostowego oraz operatora rozszerzania . Pierwszy z nich wykorzystuje informacje uzyskane z tabeli CYK, aby odkryć, której produkcji brakuje, aby pokryć zdanie. Drugi może dynamicznie rozszerzać zbiór produkcji, zapewniając różnorodność.

Operator uczenia przyrostowego

Ten operator jest stosowany przed oceną każdej gramatyki w populacji. Wykorzystuje on tablicę CYK uzyskaną z analizy przykładów pozytywnych, aby umożliwić utworzenie nowej, użytecznej produkcji. Pseudokod przedstawiono na rysunku 4.



Po pomyślnym zakończeniu tego procesu, miejmy nadzieję, gramatyka będzie rozpoznawać zbiór przykładów pozytywnych (możliwych wszystkich). Nie ma jednak gwarancji, że niektóre przykłady negatywne nadal będą odrzucane przez gramatykę.

Operator rozszerzenia

Ten operator dodaje nowy nieterminal do gramatyki i generuje nową produkcję z tym nowym nieterminalem jako lewą stroną. To nowe podejście pozwala gramatykom dynamicznie rosnąć. Aby uniknąć nowej, bezużytecznej produkcji, generowana jest produkcja z innym nieterminalem po lewej stronie i nowym nieterminalem po prawej stronie. Należy podkreślić, że nowy operator dodaje dwie produkcje do gramatyki. Operator ten promuje różnorodność w populacji, która jest wymagana na początku procesu ewolucyjnego.

Ocena gramatyki

W wnioskowaniu gramatycznym musimy trenować system zarówno na przykładach pozytywnych, jak i negatywnych, aby uniknąć nadmiernej generalizacji. Zazwyczaj ocena odbywa się poprzez zliczanie przykładów pozytywnych objętych daną gramatyką proporcjonalnie do sumy przykładów pozytywnych. Jeśli gramatyka obejmuje pewne przykłady negatywne, jest w jakiś sposób karana. W naszej niedawnej pracy używamy macierzy pomyłek, która jest zazwyczaj stosowana w uczeniu nadzorowanym. Każda kolumna macierzy reprezentuje liczbę wystąpień przewidzianych pozytywnie lub negatywnie, a każdy wiersz reprezentuje rzeczywistą klasyfikację wystąpień. Wpisy w macierzy pomyłek mają następujące znaczenie w kontekście naszych badań:

o TP to liczba wystąpień pozytywnych rozpoznanych przez gramatykę.
o TN to liczba wystąpień negatywnych odrzuconych przez gramatykę.
o FP to liczba wystąpień negatywnych rozpoznanych przez gramatykę.
o FN to liczba wystąpień pozytywnych odrzuconych przez gramatykę.

Z macierzy pomyłek można uzyskać kilka miar. Najczęściej stosowaną jest całkowita dokładność, która jest obliczana na podstawie sumy poprawnie sklasyfikowanych przykładów podzielonych przez całkowitą liczbę wystąpień. W niniejszym artykule wykorzystaliśmy dwie inne miary: swoistość (równanie 1) i czułość (równanie 2). Miary te oceniają, jak poprawnie klasyfikator rozpoznaje pozytywne i negatywne przykłady.

swoistość = TN/TN + FP (1)
czułość = TP/TP + FN (2)

Dopasowanie oblicza się na podstawie iloczynu tych miar, co prowadzi do zbilansowanej heurystyki. Ta miara dopasowania została zaproponowana przez (Lopes, Coutinho i Lima, 1998) i jest szeroko stosowana w wielu problemach klasyfikacyjnych. Zastosowanie macierzy pomyłek zapewnia lepszą ocenę gramatyk w populacji, ponieważ gramatyki o tym samym wskaźniku dokładności zazwyczaj mają różne wartości specyficzności i czułości.

TRENDY NA PRZYSZŁOŚĆ

Podejście GP do wnioskowania gramatycznego opiera się na algorytmie CYK i macierzy pomyłek. Wstępne wyniki są obiecujące, ale istnieją dwa problemy, które należy rozwiązać. Pierwszym z nich jest to, że znalezione rozwiązanie niekoniecznie jest najmniejsze. W zależności od przebiegu, wywnioskowana gramatyka różni się rozmiarem i czasami może być trudna do zrozumienia oraz może mieć bezużyteczne lub zbędne reguły produkcji. Dalsze prace będą koncentrować się na opracowaniu mechanizmu, który faworyzuje krótsze rozwiązania cząstkowe. Drugim zjawiskiem jest tzw. "rozdęcie" (bloat), czyli niekontrolowany wzrost liczebności osobnika w populacji . Użycie operatora ekspansji może powodować to niepożądane zachowanie. Niemniej jednak, zachowanie to nie zostało wykryte w eksperymentach, ponieważ wszystkie bezużyteczne produkcje są eliminowane podczas przeszukiwania.

WNIOSKI

W niniejszym artykule zaproponowano podejście GP do wnioskowania gramatyki bezkontekstowej. W tym podejściu osobnik jest listą ustrukturyzowanych drzew reprezentujących jego produkcje, z lewą stroną jako korzeniem i derywacjami jako liśćmi. Wykorzystuje ono lokalny operator wyszukiwania o nazwie Incremental Learning, który jest w stanie dostosować każdą gramatykę zgodnie z pozytywnymi przykładami. Wykorzystuje również operator ekspansji, który dodaje nową produkcję do gramatyki, umożliwiając gramatykom wzrost liczebności. Operator ten promuje różnorodność w populacji, która jest wymagana we wcześniejszych generacjach. Zastosowanie lokalnego mechanizmu wyszukiwania, który jest w stanie uczyć się na przykładach, sprzyja szybkiej konwergencji. Wstępne wyniki wykazały, że to podejście jest obiecujące.

WSTĘP

Według Światowej Organizacji Zdrowia nowotwory są główną przyczyną zgonów na świecie. Z łącznej liczby 58 milionów zgonów w 2005 r. nowotwory odpowiadają za 7,6 miliona (czyli 13%) wszystkich zgonów. Główne rodzaje nowotworów prowadzące do ogółu śmiertelność z powodu raka to i) płuca (1,3 miliona zgonów/rok), ii) żołądek (prawie 1 milion zgonów/rok), iii) wątroba (662 000 zgonów/rok), iv) okrężnica (655 000 zgonów/rok) oraz v) pierś (502 000 zgonów/rok). Wśród mężczyzn najczęstszymi typami nowotworów na świecie są (w kolejności liczby zgonów na świecie): płuca, żołądka, wątroby, jelita grubego, przełyku i prostaty, natomiast wśród kobiet (w kolejności liczby zgonów na świecie) są to: piersi, płuc, żołądka, jelita grubego i szyjki macicy. Postęp technologiczny, jaki dokonał się w ostatnich latach, umożliwia gromadzenie dużych ilości danych dotyczących nowotworów. W szczególności w dziedzinie bioinformatyki możliwe są wysokowydajne eksperymenty genowe na mikromacierzach, prowadzące do eksplozji informacji. To wymaga opracowania procedur eksploracji danych, które przyspieszają proces odkryć naukowych i dogłębnego zrozumienia wewnętrznej struktury danych. Ma to kluczowe znaczenie dla nietrywialnego procesu identyfikowania ważnych, nowatorskich, potencjalnie użytecznych i ostatecznie zrozumiałych wzorców w danych . Naukowcy muszą szybko i łatwiej rozumieć swoje dane. Generalnie badane obiekty opisywane są w kategoriach zbiorów heterogenicznych właściwości. Typowe jest, że dane medyczne składają się z właściwości reprezentowanych przez zmienne nominalne, porządkowe lub o wartościach rzeczywistych (skalar), a także inne o bardziej złożonym charakterze, takie jak obrazy, szeregi czasowe itp. Ponadto informacje charakteryzuje się różnym stopniem precyzji, niepewności i kompletności informacji (brakujące dane są dość powszechne). Klasyczne metody eksploracji i analizy danych są czasami trudne w użyciu, wyniki wielu procedur mogą być duże, a ich analiza może być czasochłonna, a często ich interpretacja wymaga specjalnej wiedzy. Co więcej, niektóre metody opierają się na założeniach dotyczących danych, które ograniczają ich zastosowanie, szczególnie do celów eksploracji, porównań, formułowania hipotez itp., typowych dla pierwszych etapów badań naukowych. Dzięki temu prezentacja graficzna jest bezpośrednio atrakcyjna. Ludzie postrzegają większość informacji poprzez wzrok, w dużych ilościach i przy bardzo dużej szybkości wprowadzania danych. Ludzki mózg jest wyjątkowo dobrze wykwalifikowany do szybkiego rozumienia złożonych wzorców wizualnych, a mimo to ma przewagę nad komputerem. Kilka powodów sprawia, że wirtualna rzeczywistość (VR) jest odpowiednim paradygmatem: i) jest elastyczna (pozwala na wybór różnych modeli reprezentacji lepiej dostosowanych do preferencji człowieka), ii) pozwala na immersję (użytkownik może poruszać się po danych i wchodzić w interakcję z obiektami na świecie), iii) tworzy żywe doświadczenie (użytkownik nie jest jedynie biernym obserwatorem, ale aktorem w świecie) oraz iv) VR jest szeroka i głęboka (użytkownik może widzieć świat VR jako całość i/lub koncentrować się na konkretnych szczegółach) świata). Nie mniejsze znaczenie ma fakt, że do interakcji ze światem wirtualnym potrzebne są jedynie minimalne umiejętności. Techniki wizualizacji mogą być bardzo przydatne we wspomaganiu decyzji medycznych w onkologii. W tym artykule nienadzorowane sieci neuronowe są wykorzystywane do konstruowania przestrzeni VR do wizualnej eksploracji danych dotyczących ekspresji genów dotyczących raka. W artykule wykorzystano trzy zbiory danych, reprezentatywne dla trzech najważniejszych typów nowotworów współczesnej medycyny: wątroby, żołądka i płuc. Zestawy danych składają się z próbek z tkanek prawidłowych i nowotworowych, opisanych za pomocą dziesiątek tysięcy zmiennych, które odpowiadają intensywnościom ekspresji genów mierzonymi w eksperymentach z mikromacierzami. Pomimo bardzo dużej wymiarowości badanych wzorców, przy użyciu sieci neuronowych SAMANN uzyskiwane są wysokiej jakości reprezentacje wizualne w postaci zachowujących strukturę przestrzeni VR, co umożliwia różnicowanie tkanek nowotworowych i nienowotworowych. Te same sieci można wykorzystać jako generatory cech nieliniowych na etapie wstępnego przetwarzania w innych procedurach eksploracji danych.

SIECI NEURALOWE DO BUDOWY WIRTUALNEJ PRZESTRZENI ZECZYWISTOŚCI

Przestrzenie VR do wizualnej reprezentacji systemów informatycznych i struktur relacyjnych zostały wprowadzone w (Valdés, 2002) . Przestrzeń VR to krotka



, gdzie jest strukturą relacyjną O jest skończonym zbiorem obiektów, a Γ_v? jest zbiorem relacji); Gto nie-pusty zbiór geometrii reprezentujących różne obiekty i relacje; B jest niepustym zbiorem zachowań obiektów w świecie wirtualnym; m R^m ⊆ ℜ^m to przestrzeń metryczna o wymiarze m (euklidesowym lub nie), która będzie rzeczywistą przestrzenią geometryczną VR. Pozostałe elementy to odwzorowania: g₀ : O -> G, l : O-> R^m, G i b : O->B Typowe postulaty dotyczące wizualnej reprezentacji danych i wiedzy można sformułować w kategoriach minimalizacji utraty informacji, maksymalizacji zachowania struktury, maksymalizacji rozdzielności klas lub ich kombinacji, co prowadzi do jedno- lub wielocelowych problemów optymalizacyjnych. W wielu przypadkach te pojęcia można wyrazić deterministycznie za pomocą funkcji ciągłych z dobrze określonymi pochodnymi cząstkowymi. Jest to dziedzina klasycznej optymalizacji, w której istnieje mnóstwo metod o dobrze znanych właściwościach. W przypadku informacji heterogenicznych sytuacja jest bardziej złożona i wymagane są inne techniki. W przypadku nienadzorowanym funkcję f odwzorowującą pierwotną przestrzeń na przestrzeń VR (geometryczną) R^m można skonstruować tak, aby maksymalizować niektóre kryteria zachowania struktury metrycznej/niemetrycznej, co jest typowe w skalowaniu wielowymiarowym lub minimalizować pewną błędną miarę utraty informacji . Typową miarą błędu jest:



gdzie δ_ij jest miarą odmienności między dwoma obiektami i, j w oryginalnej przestrzeni, a ξ_ij jest kolejną miarą odmienności zdefiniowaną na obiektach i, j w przestrzeni VR (obrazy i, j pod f). Typowymi miarami odmienności dla δ_ij są odległość euklidesowa lub odmienność oparta na współczynniku podobieństwa. Odległość euklidesowa jest zwykłą miarą ξ_ij w przestrzeni VR. Zwykle odwzorowania f uzyskane przy użyciu tego rodzaju podejść są ukryte, ponieważ obrazy obiektów w nowej przestrzeni są obliczane bezpośrednio. Jednakże funkcjonalna reprezentacja f jest wysoce pożądana, szczególnie w przypadkach, gdy a posteriori oczekuje się większej liczby próbek i należy je umieścić w danej przestrzeni. W przypadku reprezentacji ukrytej przestrzeń należy obliczyć za każdym razem, gdy do zbioru dodawana jest nowa próbka, natomiast w przypadku reprezentacji jawnej odwzorowanie można obliczyć bezpośrednio. Dopóki przychodzące obiekty można uznać za należące do tej samej populacji próbek użytych do skonstruowania funkcji odwzorowującej, nie ma potrzeby ponownego obliczania przestrzeni. Sieci neuronowe są naturalnymi kandydatami do konstruowania jawnych reprezentacji ze względu na ich ogólną, uniwersalną właściwość aproksymacji. Jeśli zostaną zastosowane odpowiednie metody uczenia, sieci neuronowe mogą uczyć się z zachowaniem struktury mapowań próbek o dużych wymiarach w przestrzenie o niższych wymiarach, odpowiednie do wizualizacji (2D, 3D). Jeśli wizualizacja nie jest wymagana, spacje o mniejszych wymiarach niż oryginał, można wykorzystać jako nowe funkcje do redukcji szumów lub innych metod eksploracji danych. Takim przykładem jest sieć SAMANN. Jest to sieć ze sprzężeniem zwrotnym, a jej architektura składa się z warstwy wejściowej zawierającej tyle neuronów, ile jest atrybutów deskryptorów, warstwy wyjściowej zawierającej tyle neuronów, ile wynosi wymiar przestrzeni VR oraz jednej lub więcej warstw ukrytych. Klasyczny sposób uczenia sieci SAMANN opisano w (Mao i Jain, 1995). Polega na metodzie gradientowego opadania, w której pochodne błędu Sammona obliczane są w sposób podobny do klasycznego algorytmu propagacji wstecznej. W odróżnieniu od algorytmu propagacji wstecznej, szkolenie odbywa się bez nadzoru, a wagi można aktualizować jedynie po zaprezentowaniu pary przykładów sieci.

OPIS ZESTAWÓW DANYCH RAKOWYCH

Wybrano trzy bazy danych dotyczące ekspresji genów nowotworowych za pomocą mikromacierzy. Są one reprezentatywne dla niektórych z głównych przyczyn zgonów z powodu nowotworów na świecie i mają wspólne cechy typowe dla tego rodzaju danych: niewielką liczbę próbek (rzędu dziesiątek), opisaną za pomocą bardzo dużej liczby atrybutów (rzędu dziesiątek tysięcy).

Dane dotyczące raka wątroby

Wykorzystaliśmy te same dane, co w (Lam, Wu, Vega, Miller, Spitsbergen, Tong, Zhan, Govindarajan, Lee, Mathavan, Murthy, Buhler, Liu i Gong, 2006), gdzie analizowano guzy wątroby danio pręgowanego i porównywano z guzami wątroby u ludzi. Baza danych (http://www.ncbi.nlm.nih.gov/projects/geo/gds/gds_browse.cgi?gds=2220) zawiera 20 próbek (10 normalnych, 10 nowotworowych) z 16 512 atrybutami. Po pierwsze, nowotwory wątroby u danio pręgowanego powstały w wyniku leczenia ich substancjami rakotwórczymi. Następnie porównano profile ekspresji nowotworów wątroby danio pręgowanego z profilami normalnych tkanek wątroby danio pręgowanego przy użyciu Testu sumy rang Wilcoxona. W wyniku tego porównania uzyskano zestaw genów guza wątroby danio pręgowanego o zróżnicowanej ekspresji, składający się z 2315 cech genowych. Ten zestaw danych wykorzystano do porównania z nowotworami ludzkimi. Wyniki sugerują podobieństwa molekularnemiędzy nowotworami danio pręgowanego a nowotworami wątroby ludzkiej są większe niż podobieństwa molekularne między innymi typami nowotworów (żołądka, płuc i prostaty).

Dane dotyczące raka żołądka

Wykorzystaliśmy te same dane, co w (Hippo, Taniguchi, sutsumi, Machida, Chong, Fukayama, Kodama i Aburatani, 2002), gdzie przeprowadzono badanie genów, które ulegają różnej ekspresji w nowotworowych i nienowotworowych tkankach ludzkiego żołądka. Baza danych (http://www.ncbi.nlm.nih.gov/projects/geo/gds/gds_browse.cgi?gds=1210) zawiera 30 próbek (22 guzy, 8 normalnych), które analizowano za pomocą mikromacierzy oligonukleotydowej, uzyskując profile ekspresji dla 6936 genów (7129 atrybutów). Korzystając z 6272 genów, które przeszły procedurę wstępnego filtrowania, udało się rozróżnić tkanki nowotworowe i nienowotworowe za pomocą dwuwymiarowego hierarchicznego grupowania przy użyciu korelacji Pearsona. Jednak w wynikach grupowania wykorzystano większość genów w macierzy. Aby zidentyfikować geny, które ulegały różnej ekspresji w tkankach nowotworowych i nienowotworowych, do danych zastosowano test U Manna-Whitneya. W wyniku tej analizy 162 i 129 genów wykazywało wyższą ekspresję odpowiednio w tkankach nowotworowych i nienowotworowych. Ponadto zidentyfikowano kilka genów związanych z przerzutami do węzłów chłonnych i klasyfikacją histologiczną (jelitowe, rozsiane).

Dane dotyczące raka płuc

Wykorzystaliśmy te same dane, co w badaniu (Spira, Beane, Pinto-Plata, Kadar, Liu, Shah, Celli i Brody, 2004), gdzie porównano ekspresję genów w tkance płuc z ciężką rozedmą płuc (od palaczy poddawanych operacji zmniejszania objętości płuc) i prawidłowej lub lekko rozedmowej tkanki płuc (od palaczy poddawanych resekcji guzków płucnych). Baza danych (http://www.ncbi.nlm.nih.gov/projects/geo/gds/gds_browse.cgi?gds=737) zawiera 30 próbek (18 z ciężką rozedmą płuc, 12 z łagodną rozedmą lub bez niej) z 22 283 atrybutami. Odfiltrowano geny o dużych wartościach P wykrywalności, uzyskując zestaw danych obejmujący 9336 genów, które wykorzystano do późniejszej analizy. Do zidentyfikowania grupy genów, których ekspresja w płucach pozwala odróżnić ciężką rozedmę płuc od łagodnej rozedmy lub jej braku, zastosowano dziewięć algorytmów klasyfikacji. Najpierw przeprowadzono selekcję modelu dla każdego algorytmu poprzez weryfikację krzyżową z pominięciem jednego i zapisano listę genów odpowiadającą najlepszemu modelowi. Do dalszej analizy wybrano geny zgłoszone przez co najmniej cztery algorytmy klasyfikacyjne (102 geny). W przypadku tych genów przeprowadzono dwuwymiarowe hierarchiczne grupowanie przy użyciu korelacji Pearsona, aby rozróżnić ciężką rozedmę płuc od łagodnej rozedmy płuc lub jej braku. Zidentyfikowano także inne geny, które mogą być przyczynowo zaangażowane w patogenezę rozedmy płuc.

USTAWIENIA EKSPERYMENTALNE

Wstępne przetwarzanie danych

W przypadku danych dotyczących żołądka i płuc każdy gen skalowano tak, aby oznaczał zero i odchylenie standardowe jeden (oryginalne dane nie były normalizowane). W przypadku danych dotyczących wątroby nie przeprowadzono transformacji (oryginalne dane to stosunki log2).

Szkolenie modelowe

Dla każdego zestawu danych zbudowano sieci SAMANN w celu odwzorowania oryginalnych danych w przestrzeń 3D VR. Miarą odmienności stosowaną zarówno w przestrzeni oryginalnej, jak i w przestrzeni VR była odległość euklidesowa. Zastosowano funkcje aktywacji sinusoidalne dla pierwszej warstwy ukrytej i tangens hiperboliczny dla pozostałych. Zbiór modeli uzyskano poprzez zmianę niektórych parametrów sterujących siecią: liczba jednostek w pierwszej warstwie ukrytej (dwie różne wartości), zakresy wag w pierwszej warstwie ukrytej (trzy różne wartości), szybkość uczenia się (trzy różne wartości), pęd (trzy różne wartości), liczba par prezentowanych do sieci w każdej iteracji (trzy różne wartości), liczba iteracji (trzy różne wartości) i losowe nasiona (cztery różne wartości), co daje łącznie 1944 sieci SAMANN dla każdej zestaw danych.

Środowisko komputerowe

Wszystkie eksperymenty przeprowadzono na basenie Condor (http://www.cs.wisc.edu/condor) zlokalizowanym w Instytucie Technologii Informacyjnych Kanadyjskiej Krajowej Rady ds. Badań Naukowych.

WYNIKI

Dla każdego zbioru danych skonstruowaliśmy histogramy błędu Sammona dla otrzymanych sieci. Wszystkie rozkłady empiryczne były dodatnio skośne (z modą po dolnej stronie błędu), co jest dobrym zachowaniem. Ponadto zakresy błędów ogólnych były niewielkie. Oczywiste jest, że nie da się przedstawić przestrzeni VR na nośnikach drukowanych (nawigacja, interakcja i zmiany świata zostaną utracone). Dlatego też zastosowano bardzo proste geometrie obiektów i zaprezentowano jedynie migawki wirtualnych światów. Chociaż mapowanie zostało wygenerowane na podstawie niesuper-z szerszej perspektywy (tj. bez użycia etykiet klas) obiekty z różnych klas są w różny sposób reprezentowane w przestrzeni VR dla celów porównawczych. Przezroczyste membrany owijają odpowiednie klasy, dzięki czemu można łatwo zobaczyć stopień nakładania się klas. Dodatkowo pozwala na wyszukiwanie konkretnych próbek o niejednoznacznych decyzjach diagnostycznych. Niskie wartości błędu Sammona wskazują, że przestrzenie zachowały większość struktury odległości danych, dając zatem dobre pojęcie o rozkładzie w oryginalnych przestrzeniach. Trzy wirtualne przestrzenie są wyraźnie spolaryzowane dwoma trybami dystrybucji, każdy odpowiadający innej klasie. Należy jednak zauważyć, że klasy są wyraźniej zróżnicowane w przypadku zbiorów danych dotyczących wątroby i żołądka niż w przypadku zbiorów danych dotyczących płuc, gdzie występuje pewien stopień nakładania się. Przyczyną tego może być fakt, że łagodna i niewymagająca rozedma płuc została uznana za należącą do tej samej klasy (patrz wyżej). Zaletą korzystania z sieci SAMANN jest to, że ponieważ odwzorowanie f między oryginałem a przestrzenią wirtualną jest wyraźne, nową próbkę można łatwo przekształcić i zwizualizować w przestrzeni wirtualnej. Ponieważ odległość między dowolnymi dwoma obiektami wskazuje na ich odmienność, nowy punkt z większym prawdopodobieństwem będzie należeć do tej samej klasy swoich najbliższych sąsiadów. W ten sam sposób można łatwo zidentyfikować wartości odstające, chociaż mogą one wynikać z deformacji przestrzeni nieuchronnie wprowadzonej przez redukcję wymiarowości.

WNIOSEK

Wysokiej jakości przestrzenie rzeczywistości wirtualnej do wizualnej eksploracji danych typowych przykładów danych dotyczących ekspresji genów uzyskano przy użyciu nienadzorowanych sieci neuronowych zachowujących strukturę w rozproszonym środowisku eksploracji danych obliczeniowych (siatce). Te wyniki to pokazują kilka cech nieliniowych może skutecznie uchwycić strukturę podobieństwa danych, a także zapewnić dobre rozróżnienie między klasą nowotworu a klasą normalną. Jednakże w przypadkach, gdy atrybuty deskryptorów nie są bezpośrednio powiązane ze strukturą klasy lub gdy istnieje wiele zaszumionych lub nieistotnych atrybutów, sytuacja może nie być tak jasne. W takich przypadkach wybór podzbioru cech i inne procedury eksploracji danych można rozważyć na etapie wstępnego przetwarzania.

POTWIERDZENIE

Prace te były częściowo wspierane przez Consejo Inministerial de Ciencia y Tecnología (CICYT, Hiszpania) w ramach projektu TIN2006-08114 i prowadzone w ramach ZAKRESU PRAC pomiędzy Kanadyjską Narodową Radą ds. Badań (Instytut ds. Technologii Informacyjnej, Grupa ds. Zintegrowanego Rozumowania) oraz Grupa ds. Miękkiego Obliczenia (Wydział Języków i Systemów Informacyjnych), Politechnika Katalońska, Hiszpania.

WSTĘP

Problemy optymalizacyjne w świecie rzeczywistym są często zbyt złożone, aby można je było rozwiązać metodami analitycznymi. Algorytmy ewolucyjne to klasa algorytmów, które zapożyczają paradygmaty z natury, aby sobie z nimi poradzić. Są to stochastyczne metody optymalizacji, które utrzymują populację poszczególnych rozwiązań, którym odpowiadają punkty w przestrzeni poszukiwań problemu. Algorytmy te cieszą się ogromną popularnością, ponieważ są technikami wolnymi od pochodnych, nie są tak podatne na wpadanie w pułapki w lokalnych minimach i można je dostosować specjalnie do konkretnego problemu. Wydajność algorytmów ewolucyjnych można jeszcze bardziej poprawić, dodając do nich komponent wyszukiwania lokalnego. Algorytm simpleksowy Neldera-Meada (Nelder i Mead, 1965) jest prostym algorytmem wyszukiwania lokalnego, który był rutynowo stosowany w celu usprawnienia procesu wyszukiwania w algorytmach ewolucyjnych i taka strategia spotkała się z wielkim sukcesem. W tym artykule przedstawiamy przegląd różnych strategii przyjętych w celu hybrydyzacji dwóch dobrze znanych algorytmów ewolucyjnych - algorytmów genetycznych (GA) i optymalizacji roju cząstek (PSO).

TŁO

Prawdopodobnie GA są jednym z najpowszechniejszych podejść do optymalizacji opartych na populacji. Populacja potencjalnych rozwiązań, którą te algorytmy utrzymują w każdym pokoleniu, nazywa się chromosomami. GA realizują darwinowskie operatory selekcji, mutacji i rekombinacji na tych chromosomach w celu przeprowadzenia ich wyszukiwania. Każde pokolenie doskonali się poprzez usuwanie z populacji słabszych rozwiązań, przy jednoczesnym zachowaniu lepszych, w oparciu o miarę sprawności. Proces ten nazywa się selekcją. Po selekcji stosuje się metodę rekombinacji rozwiązań zwaną crossover. W tym przypadku dwa (lub więcej) rozwiązania rodzicielskie z bieżącej generacji są wybierane losowo w celu spłodzenia potomstwa w celu zasiedlenia rozwiązań następnej generacji. Chromosomy potomne podlegają następnie probabilistycznie mutacji, która odbywa się poprzez dodanie małych przypadkowych zaburzeń. PSO to nowsze podejście do optymalizacji . Wzorowany na społecznym zachowaniu organizmów, takich jak stado ptaków w locie lub ławica pływających ryb, jest uważany za algorytm ewolucyjny tylko w luźnym sensie. Każde rozwiązanie w populacji nazywane jest cząstką w PSO. Pozycja każdej takiej cząstki w przestrzeni poszukiwań jest stale aktualizowana w każdym pokoleniu, poprzez dodanie do niej prędkości cząstki. Prędkośćcząstki jest następnie dostosowywana w kierunku najlepszej pozycji napotkanej w historii cząstki (najlepsza pozycja indywidualna), a także najlepszej pozycji w bieżącej iteracji (najlepsza globalna). Ponieważ algorytmy ewolucyjne wykorzystują populację osobników i losowe operatory wariacyjne, są one biegłe w przeprowadzaniu przeszukiwań eksploracyjnych w swoich przestrzeniach poszukiwań. Jeśli jednak celem jest uzyskanie wyników w rozsądnych ramach czasowych, ważne jest, aby zrównoważyć tę eksplorację z lepszym wykorzystaniem cech na mniejszą skalę w krajobrazie fitness. W tym drugim kontekście algorytmy wyszukiwania lokalnego umożliwiają ulepszenie pojedynczych rozwiązań przy użyciu informacji lokalnych (np. kierunkowych trendów dopasowania wokół każdego rozwiązania) i doprowadzenie rozwiązania do najbliższego maksymalnego dopasowania. Algorytmy hybrydowe, które łączą zalety eksploracji i eksploatacji, stanowią odrębny obszar ewolucyjnych badań obliczeniowych, nazywany różnie podejściami lamarckowskimi lub memetycznymi, których znaczącą część stanowią hybrydy Neldera-Meada.

NeldeR-meAD HYBRYDYZACJA NA BAZIE SIMPLEX

Algorytm Simplex zjazdowy Nelder-Mead

Algorytm simpleksowy Neldera-Meada jest wolną od pochodnych techniką wyszukiwania lokalnego, która umożliwia przesuwanie grupy rozwiązań w kierunku gradientu i którą, jak wynika z bieżących badań, można bardzo skutecznie łączyć z podejściami GA i PSO. Wykazano, że te hybrydowe algorytmy ewolucyjne są bardzo skuteczne ciągłe problemy optymalizacyjne. Metoda smpleksu Neldera-Meada wykorzystuje konstrukcję zwaną sympleksem (rysunek 1).



Gdy przestrzeń poszukiwań jest n-wymiarowa, sympleks składa się z n+1 rozwiązań, s_i, i = {1, 2, …, n+1}, które są zwykle blisko siebie rozmieszczone. Jak pokazano w lewym górnym rogu rysunku 1, w dwuwymiarowej płaszczyźnie poszukiwań sympleks jest trójkątem. Na każdym etapie metody Neldera-Meada rozważana jest przydatność każdego rozwiązania i identyfikowane jest najgorsze rozwiązanie. Oblicza się środek ciężkości c pozostałych n punktów c =1/nΣ s,sub>i i określa się wzdłuż niego odbicie w. To odbicie daje nowe rozwiązanie r, które w następnym kroku zastępuje w, jak pokazano w prawym górnym rogu rysunku 1. Jeśli rozwiązanie r utworzone w wyniku tego odbicia ma wyższą przydatność niż jakiekolwiek inne rozwiązanie w sympleksie, sympleks jest dalej rozwijany wzdłuż kierunku r, jak pokazano w lewym środkowym rogu rysunku. Z drugiej strony, jeśli r ma niską przydatność w porównaniu z innymi, sympleks jest skurczony. Skurcz może być skierowany na zewnątrz lub do wewnątrz, w zależności od tego, czy r jest lepsze, czy gorsze niż w. Operacje skracania pokazano w prawym środkowym i lewym dolnym rogu rysunku. Jeśli żadne skrócenie nie poprawia najgorszego rozwiązania w sympleksie, obliczany jest najlepszy punkt w sympleksie, a następnie przeprowadzane jest załamanie, a wszystkie punkty sympleksu przesuwają się nieco bliżej w kierunku najlepszego, jak pokazano w prawym dolnym rogu tego samego rysunku. Podejścia przyjęte w celu włączenia procedury wyszukiwania lokalnego opartego na simpleksach w szerokie ramy algorytmu genetycznego można podzielić na cztery różne schematy pokazane na rysunku 2.



Są one następujące:

Hybrydyzacja dwufazowa

Jest to najprostsze ze wszystkich podejść i zostało zastosowane w przypadku GA . W pierwszej fazie tego schematu stosuje się GA do problemu optymalizacji w celu zbadania całej przestrzeni poszukiwań, aż zostanie znalezione jedno lub więcej dobrych rozwiązań, których nie można już ulepszyć poprzez losowe operacje krzyżowania i mutacji. Następnie w drugiej fazie wywoływany jest algorytm simplex Neldera-Meada w celu dalszego udoskonalenia rozwiązań, umożliwiając im wznoszenie się w kierunku ich lokalnych maksimów. W innym podejściu początkowe punkty sympleksu uzyskuje się poprzez przyjęcie rozwiązania o najlepszym przystosowaniu podanym przez GA, a następnie wygenerowanie wokół niego pozostałych n punktów .

Hybrydyzacja szeregowa

W tym schemacie rozwiązania każdej generacji podlegają zwykłym operatorom głównego algorytmu ewolucyjnego, a także jednemu lub większej liczbie etapów metody simpleks Neldera-Meada. Został on z powodzeniem zastosowany do hybrydyzacji GA . Metodę tę stosowano także w połączeniu z PSO przez Dasa. W każdym pokoleniu, po aktualizacji położenia i prędkości, populacja jest grupowana w odrębne skupienia po n+1 rozwiązań każdy, a kilka kroków algorytmu Neldera-Meada stosuje się oddzielnie do każdego skupienia. Krok Neldera-Meada jest stosowany stałą liczbę razy na pokolenie. Schemat hybrydyzacji szeregowej został pomyślnie wdrożony również w ramach optymalizacji wielocelowej . Zamiast sprawności stosuje się metrykę zwaną dominacją rozmytą w celu rozróżnienia rozwiązań n+1 w sympleksie. Rozwiązanie, które nie jest zdominowane przez żadne inne, ma przypisaną dominację rozmytą równą zero. Im gorsze rozwiązanie, tym wyższa jest mu przypisana wartość dominacji rozmytej.

Hybrydyzacja równoległa

Takie podejścia do hybrydyzacji łączą pokolenie potomstwa z pokolenia rodzicielskiego na dwóch równoległych ścieżkach. Do generowania części potomstwa wykorzystywane są standardowe operatory algorytmów ewolucyjnych, inne natomiast generowane są przy użyciu algorytmu simpleksowego. Strategię tę stosuje się do hybrydyzacji GA . W podejściu tym wybierane są najlepsze rozwiązania n+1 (tzw. elity) z każdego pokolenia, które należy dalej udoskonalać, stosując metodę simplex Neldera-Meada. W innej strategii wykorzystuje się probabilistyczny wariant podejścia Neldera-Meada, w którym wielkość skurczu i/lub ekspansji sympleksu wyznaczana jest losowo, ale w określonych granicach . Podejścia przyjęte w (Koduru, Das, Welch i Roe, 2004) oraz (Koduru, Das, Welch, Roe i Lopez-Dee, 2005) to implementacje wielocelowe, które wykorzystują omówioną wcześniej rozmytą metrykę dominacji w celu identyfikacji najlepszych i najgorszych rozwiązań. Aby zachować różnorodność rozwiązań w populacji, nigdy nie stosuje się operacji zwijania i metody Neldera-Meada zamiast tego rutyna zostaje zakończona, gdy pojawia się taka potrzeba, w każdym pokoleniu. Schemat ten zastosowano w przypadku PSO . Tak jak wcześniej, tylko najlepsze punkty populacji n+1 są wybierane do poddania ulepszeniom metodą simpleksową Neldera-Meada. Pozostałe rozwiązania w każdej generacji uzyskiwane są poprzez standardowe aktualizacje położenia i prędkości PSO.

Ukryta hybrydyzacja

Tutaj algorytm simplex Neldera-Meada nie jest stosowany bezpośrednio. Zamiast tego podejście to jest ukryte w obrębie dowolnego operatora generycznego algorytmu ewolucyjnego. Jedną z prostych technik w GA jest wielorodzicowa krzyżówka oparta na simpleksach . W tej metodzie do produkcji stosuje się pojedynczy etap Neldera-Meada nowe potomstwo. Sugeruje się także nowatorskie techniki krzyżowania . W innej metodzie każdy sympleks jest kodowany jako chromosom, a algorytm wykorzystuje specjalnie opracowane krzyżowanie wielu rodziców w GA. Das i inni wykorzystują ukrytą hybrydyzację w PSO, dodając człon do prędkości każdej cząstki pozwala to temu ostatniemu na zmianę orientacji trajektorii w kierunku gradientu wykrywanego przez sympleks Neldera-Meada (od najgorszego w kierunku środka ciężkości).

PRZYSZŁE TENDENCJE

Chociaż tradycyjnie algorytmy ewolucyjne skupiały się na optymalizacji funkcji pojedynczego celu, większość praktycznych problemów inżynieryjnych ma z natury charakter wielocelowy. W związku z tym wieloobiektowa optymalizacja ewolucyjna jest zjawiskiem stosunkowo nowym i pojawiającym siękierunek badań obliczeń ewolucyjnych. Być może jedyne próby włączenia Nelder-Mead simplex jako dodatkowego operatora w ramach GA zostały zgłoszone przez Koduru, Das i Welch . Bez wątpienia potrzebne są dalsze badania w tym kierunku, a w miarę jak algorytmy wielocelowe staną się coraz bardziej powszechne, strategie Neldera-Meada będą badane z większą intensywnością. PSO to nowa technika optymalizacji ewolucyjnej. Badania nad algorytmami hybrydowymi opartymi na PSO rozpoczęły się dopiero niedawno. Das i innizasugerowali kilka ograniczonych podejść do hybrydyzacji PSO z simpleksem Neldera-Meada. oraz Zahara i innych. Metoda zaproponowana w (Koduru, Das, Welch 2007) jest, według najlepszej wiedzy autora, jedyną próbą stworzenia wieloobiektowego algorytmu hybrydowego PSO. Tutaj ponownie konieczne są dalsze badania. Chociaż badania nad tymi ewolucyjnymi algorytmami hybrydowymi trwają ponad dziesięć lat i zaproponowano kilka dobrych podejść, nie ma jasnego konsensusu co do tego, które podejście jest najlepiej dostosowane do danego zastosowania. Uzasadnione są dalsze badania w tym kierunku, aby uzyskać lepszy wgląd w działanie tych algorytmów.

WNIOSEK

W literaturze dotyczącej optymalizacji ewolucyjnej zaproponowano wiele skutecznych podejść do hybrydyzacji GA z simpleksem Neldera-Meada. Niedawno badacze zaczęli wdrażać podobne pomysły również w ramach PSO. Opublikowano kilka artykułów na temat wielocelowych podejść hybrydowych. Jednakże jak dotąd brakowało formalnych ram pozwalających kategoryzować wszystkie te podejścia. W tym rozdziale dokonano przeglądu różnych metod i zaproponowano sposób podzielenia ich na cztery odrębne kategorie.

WSTĘP

System akwizycji jest jednym z najbardziej wrażliwych etapów w odbiorniku z rozproszonym widmem sekwencji bezpośredniej (DS-SS) , ze względu na jego krytyczne położenie w celu demodulacji odbieranych informacji. Istnieje kilka schematów radzenia sobie z tym problemem, takich jak algorytmy wyszukiwania szeregowego i algorytmy równoległe . Algorytmy wyszukiwania szeregowego charakteryzują się długim czasem zbieżności, ale ich obciążenie obliczeniowe jest bardzo niskie; z drugiej strony systemy równoległe zbieżne są bardzo szybkie, ale ich obciążenie obliczeniowe jest bardzo wysokie. W naszym systemie wykorzystano schemat akwizycji o strukturze multirozdzielczej przedstawionej w (Moran, Socoró, Jové, Pijoan i Tarrés, 2001), która łączy szybką zbieżność i niskie obciążenie obliczeniowe. System decyzyjny, który ocenia etap akwizycji, jest kluczowym procesem w ogólnej wydajności systemu, będąc wadą tej struktury. Staje się to szczególnie istotne w przypadku kanałów zmiennych w czasie, gdzie stosunek sygnału do szumu (SNR) nie jest stałym parametrem. Na wydajność systemu akwizycji wpływa kilka czynników (Glisic i Vucetic, 1997): zniekształcenia i zmiany w kanale, szum i interferencje, niepewność co do fazy kodu oraz losowość danych. Istnienie wszystkich tych zmiennych skłoniło nas do rozważenia możliwości wykorzystania logiki rozmytej do rozwiązania tej złożonej estymacji akwizycji (Zadeh, 1973). Estymator akwizycji oparty na logice rozmytej został już przetestowany i wykorzystany w naszej grupie badawczej do sterowania algorytmem wyszukiwania szeregowego z obiecującymi wynikami, a następnie w schemacie wielorozdzielczym, a inne zastosowania w tej dziedzinie można znaleźć w bibliografii (Bas, Pérez i Lagunas, 2001) lub (Jang, Ha, Seo, Lee i Lee, 1998). Kilka wcześniejszych prac koncentrowało się na rozwoju systemów akwizycji dla kanałów nieselektywnych częstotliwościowo z szybkimi zmianami SNR.

TŁO

W 1964 roku dr Lofti Zadeh wprowadził termin logika rozmyta (Zadeh, 1965). Powodem był fakt, że tradycyjna logika nie potrafiła odpowiedzieć na niektóre pytania prostymi odpowiedziami "tak" lub "nie". W związku z tym zajmuje się ona koncepcją prawdy cząstkowej. Logika rozmyta to jedna z możliwości imitacji działania ludzkiego mózgu, a tym samym próby przekształcenia sztucznej inteligencji w inteligencję rzeczywistą. Zadeh opracował tę technikę jako metodę rozwiązywania problemów z zakresu nauk ścisłych, w szczególności tych, które wymagają interakcji międzyludzkich. Logika rozmyta okazała się dobrym rozwiązaniem w przypadku sterowania w bardzo złożonych procesach, gdy nie jest możliwe stworzenie modelu matematycznego. Logika rozmyta jest również zalecana w przypadku procesów wysoce nieliniowych oraz ogólnie, gdy pożądane jest wykorzystanie wiedzy eksperckiej. Nie jest to jednak dobry pomysł, jeśli tradycyjne sterowanie lub estymatory dają zadowalające wyniki lub w przypadku problemów, które można modelować matematycznie. Najnowsze prace z zakresu sterowania i estymacji z wykorzystaniem logiki rozmytej w systemach komunikacji z rozproszonym widmem sekwencyjnym można podzielić na trzy typy. Pierwsza grupa wykorzystuje logikę rozmytą do poprawy stopnia detekcji odbiornika DS-CDMA1 i została przedstawiona przez Basa i Janga . Druga grupa wykorzystuje logikę rozmytą do poprawy tłumienia zakłóceń, a jej prace przedstawili Bas oraz Chia-Chang. Wreszcie techniki logiki rozmytej poprawiają również szacowanie i kontrolę na etapie akwizycji odbiornika DS-CDMA, co zostało opisane w pracach Alsiny i innych.

OSZACOWANIE AKWIZYCJI W ŚRODOWISKACH DS-CDmA

Jednym z najważniejszych problemów do rozwiązania w systemach z rozproszonym widmem sekwencji bezpośredniej jest uzyskanie solidnej i precyzyjnej akwizycji sekwencji pseudoszumu; oznacza to uzyskanie dokładnego oszacowania jej dokładnej fazy lub położenia czasowego (Proaki 1995). W środowiskach zmiennych w czasie fakt ten staje się jeszcze ważniejszy, ponieważ wydajność akwizycji i śledzenia może znacznie obniżyć niezawodność demodulacji komunikacji. W niniejszej pracy zaproponowano nowy wielorozdzielczy system akwizycji z estymatorem logiki rozmytej. Estymacja logiki rozmytej poprawia dokładność etapu akwizycji w porównaniu z wynikami dla kontrolera stabilności, poprzez oszacowanie prawdopodobieństwa akwizycji oraz stosunku sygnału do szumu w kanale, poprawiając wyniki uzyskane dla pierwszego estymatora logiki rozmytej dla struktury wielorozdzielczej

Struktura akwizycji wielorozdzielczej

Celem schematu akwizycji wielorozdzielczej jest znalezienie prawidłowego punktu akwizycji w rozsądnym czasie konwergencji. Zapewnia on dobry kompromis między szybkością konwergencji systemów równoległych a niskim obciążeniem obliczeniowym algorytmów wyszukiwania szeregowego. Najpierw do sygnału wejściowego x[n]² stosuje się decymację M rzędu, ponieważ etap akwizycji może zaakceptować niepewności w okresie chipa, a tym samym zmniejszyć obciążenie obliczeniowe etapu akwizycji. Po decymacji sygnału x[n], sygnał wynikowy r[n] jest przesyłany do filtrów struktury wielorozdzielczej (patrz struktura na rysunku 1).



Należy zauważyć, że istnieje H różnych gałęzi, które pracują z decymowanymi wersjami sygnału wejściowego, rozdzielonymi w H rozłącznych podprzestrzeniach. Każda gałąź ma adaptacyjny filtr FIR LMS o długości



trenowany z wykorzystaniem zdziesiątkowanej wersji sekwencji PN (PN-DEC).W idealnych warunkach, w kanale nieselektywnym częstotliwościowo z białym szumem gaussowskim, tylko jeden z filtrów powinien lokalnie zbiegać impuls, taki jak λb_i[k]δ[n - ?τgdzie b[k] to bit informacyjny, τ reprezentuje opóźnienie między sekwencją PN sygnału wejściowego a sekwencją referencyjną, a λ to współczynnik zaniku zniekształceń kanału. Algorytm jest resetowany po każdym nowym symbolu danych, a do każdego z rozwiązań LMS (wi[n]) stosowany jest algorytm uśredniania wygładzania modulo w celu usunięcia zależności od składowej losowości danych bi[k], uzyskując nieujemne i uśrednione odpowiedzi impulsowe (Wav_i[n]). System decyzyjny wykorzystuje algorytm wykrywania szczytów, aby określić, który z tych filtrów wykrył sygnał (W_con[n]), a położenie maksimum (τ) w tym filtrze da zgrubne oszacowanie fazy akwizycji. Po przywróceniu punktu akwizycji przez system decyzyjny, śledzenie jest rozwiązywane za pomocą kolejnego adaptacyjnego filtru LMS (w_r[n]), który rozszerza okno wyszukiwania wokół punktu akwizycji, wykorzystując sygnał wejściowy o pełnej rozdzielczości czasowej x[n]. W ten sposób oszacowanie punktu akwizycji (obecnie nazywanego ξ) jest udoskonalane przez śledzenie, a sygnał może być poprawnie demodulowany.

Estymacja akwizycji w logice rozmytej

Estymator akwizycji w logice rozmytej został zaprojektowany z wykorzystaniem danych odpowiedzi impulsowej wszystkich filtrów LMS w strukturze. Zmiany ich wartości dają informacje o prawdopodobieństwie poprawnej akwizycji, a także o zmianach współczynnika SNR w kanale. W przeprowadzonych eksperymentach przestrzeń sygnału została podzielona na cztery podprzestrzenie (H=4), więc cztery filtry LMS tworzą etap akwizycji. Długość sekwencji PN wynosi PG=127, więc każdy filtr ma



odczepy do konwergencji. Te zmienne wejściowe i wyjściowe zostały już zdefiniowane w (Alsina, Mateo i Socoró, 2007), ale reguły do oceny zostały zaprojektowane w bardziej precyzyjny sposób.

Zmienne wejściowe

Cztery różne parametry zostały zdefiniowane jako dane wejściowe w estymatorze rozmytym; trzy z nich odnosiły się do wartości czterech filtrów LMS akwizycji uśrednionej dla modułu (Wav_i[n]), w szczególności filtra LMS dostosowanego do zdziesiątkowanej sekwencji PN-DEC (zwanego W_con[n]), a jeden dotyczył filtra śledzącego (w_tr[n]), który precyzuje wyszukiwanie:

o Współczynnik 1: oblicza się go jako iloraz wartości szczytowej filtru LMS W_con[n] podzielonej przez wartość średnią tego filtru, ale nie maksymalną, w następujący sposób:



o Współczynnik 2: oblicza się go jako iloraz wartości szczytowej filtra LMS W_con[τ] podzielonej przez średnią wartość tej samej pozycji w pozostałych trzech filtrach Wav_i[n].



o Współczynnik 3: uzyskuje się go jako iloraz wartości szczytowej filtra LMS W_con[τ] podzielonej przez wartość średnią trzech pozostałych filtrów Wav_i[n].



o Współczynnik śladu Ratio1: oblicza się go jako iloraz wartości szczytowej filtru śledzącego LMS w_tr[ξ], przy czym ξ jest najdokładniejszą oceną prawidłowego punktu pozyskania, podzielonej przez wartość średnią tego samego filtru, ale maksymalną.



Parametry te wybrano ze względu na zawarte w nich informacje o prawdopodobieństwie pozyskania sygnału, a także o poziomie SNR w kanale i jego wahaniach. Wahania wartości dają dobre oszacowania jakości pozyskiwania sygnału i dobrą miarę SNR, z odpowiednią definicją reguł IF-THEN.

Zmienne wyjściowe

Wyniki zostaną uzyskane za pomocą metody defuzyfikacji opartej na centroidzie . Obliczone zostaną dwie zmienne wyjściowe. Zmienna Akwizycja, dająca wartość z zakresu [0,1], równa się zero,gdy jest Niepozyskana, i jedna, gdy jest Pozyskana. Pomiędzy skrajnymi wartościami zdefiniowano trzy dodatkowe zbiory rozmyte: Prawdopodobnie Niepozyskana, Nieokreślona i Prawdopodobnie Pozyskana. Zmienna Akwizycja pokaże wartość niezawodności dla poprawnej demodulacji detektora. Schemat multirozdzielczy daje jedynie oszacowanie punktu akwizycji, a wartość akwizycji ocenia prawdopodobieństwo akwizycji, a tym samym spójność demodulacji bitów wykonywanej przez odbiornik. Drugą zmienną jest estymacja SNR, która podaje wartość (w zakresie [-30,0] dB w naszym eksperymencie) szacowanej wartości SNR w kanale. Estymacja SNR dostarczy nam informacji o warunkach panujących w kanale; pomoże to nie tylko w akwizycji i śledzeniu, ale także w detekcji.

Reguły warunkowe typu "jeśli-to"

W sumie sześćdziesiąt reguł zostało użytych do zdefiniowania dwóch wyjść w funkcji wartości wejściowych, rozwijając zestaw reguł użytych w (Alsina, Mateo i Socoró). Na rysunku 2 przedstawiono powierzchnię akwizycji dla wszystkich zmiennych wejściowych, a na rysunku 3 powierzchnię estymacji SNR dla wszystkich wejść.





Zdefiniowano reguły uwzględniające najlepszą wydajność, w swoim zakresie, każdej wartości parametru wejściowego, aby zaprojektować dwa wyniki estymatora rozmytego. Oznacza to, że zakres wartości jest brany pod uwagę tylko wtedy, gdy ich oszacowania są bardziej wiarygodne dla obu wyników. Najbardziej ulepszoną estymacją dla akwizycji wyjściowej jest zgodność z wartością "Nieustalone"; oznacza to, że parametry wejściowe same w sobie nie mają spójnych wartości "Akwizycja" lub "Nieakwizycja". Aby uzyskać precyzyjną wartość wyjściową, estymator rozmyty ocenia stopień implikacji każdego parametru wejściowego do funkcji przynależności i rzutuje tę implikację na zbiory rozmyte zmiennej wyjściowej "Akwizycja", aby uzyskać jej wartość poprzez defuzyfikację. Parametry Ratio1 i Ratio1 track to najlepsze parametry wejściowe do estymacji akwizycji, gdy warunki w kanale są dobre; te dwa parametry są obsługiwane przez Ratio2 i Ratio3, gdy pogarsza się SNR. Precyzja krytycznych estymacji została poprawiona w projekcie nowych reguł estymatora rozmytego. Z drugiej strony, najbardziej odporne oceny estymacji SNR są dokonywane przez Ratio2 i Ratio3; są one ulepszone przez Ratio1 track, gdy SNR jest wysoki, i przez Ratio1, gdy SNR jest bardzo niski. Jak widać na rysunku 3, zmienne te silnie korelują z wartością estymacji SNR.

Wyniki

W tej sekcji podsumowane zostaną wyniki uzyskane z nową akwizycją i estymatorem logiki rozmytej SNR. Przeprowadzono kilka symulacji z wykorzystaniem kanału z addytywnym białym szumem gaussowskim (AWGN), niektóre z nich z bardzo szybkimi zmianami SNR, aby pokazać wydajność estymatora rozmytego pod względem niezawodności i stabilności.

Niezawodność akwizycji estymatora rozmytego a kontrola stabilności

Wcześniejsze oszacowanie akwizycji uzyskano z wykorzystaniem kontroli stabilności , która uwzględniała zachowanie punktu akwizycji dla celów oceny i porównania. Zakładała ona, że system został akwizycyjny jedynie dzięki ciągłym powtórzeniom punktu akwizycji określonego przez schemat multirozdzielczy. Ta kontrola stabilności dała binarną odpowiedź dotyczącą wydajności systemu. Pomimo dobrej wydajności, widocznej na rysunku 4, nowe podejście rozmyte poprawia wyniki dla szerszego zakresu SNR.



Jakość estymacji rozmytej akwizycji jest znacznie lepsza dla bardzo niskiego SNR w porównaniu z kontrolą stabilności, a jej globalna wydajność dla całego zakresu SNR w naszych testach jest lepsza. Kontrola stabilności nie jest dobrym estymatorem dla krytycznego SNR (rozważanego na poziomie około -15 dB) i zmniejsza swoją niezawodność wraz ze spadkiem SNR. Pomimo podobnej wydajności w okolicach krytycznego SNR, estymacja rozmyta logiki akwizycji poprawia jej wydajność dla gorszych współczynników SNR, osiągając ponad 90% poprawnej estymacji we wszystkich symulacjach.

Estymacja rozmytego SNR w kanałach zmieniających się w czasie

Na rysunku 5a system akwizycji został zasymulowany w kanale AWGN, wymuszając znaczne i bardzo szybkie zmiany SNR w celu oceny szybkości konwergencji estymatora SNR. Średnia wartość estymacji SNR, będąca wartością bardzo zmienną, jest uzyskiwana za pomocą wykładniczego filtru uśredniającego wygładzającego i porównywana z SNR w kanale AWGN. SNR w kanale jest szacowany dość precyzyjnie aż do bardzo niskiego SNR (bliskiego -20 dB) przez blok rozmyty, ponieważ parametry wejściowe nie są wystarczająco stabilne, aby umożliwić dobrą prognozę dla niższych wartości; jest to podobne do tego, co dzieje się w przypadku estymacji akwizycyjnej. Aby zaobserwować odzyskiwanie rozmytego estymatora w przypadku szybkich zmian SNR w kanale, szczegół estymacji SNR pokazano na rysunku 5.b. Informacje te pokazują stan kanału odbiornikowi i umożliwiają dalsze prace nad poprawą niezawodności demodulacji za pomocą różnych podejść .

PRZYSZŁE TRENDY

Przyszłe prace będą koncentrować się na poprawie estymacji SNR w systemie rozmytym. Kolejnym celem jest zwiększenie stabilności w przypadku zmian kanału z wykorzystaniem wcześniej wykrytych symboli, co pozwoli na uzyskanie systemu ze sprzężeniem zwrotnym. Wyjścia estymatora rozmytego zostaną wykorzystane do zaprojektowania kontrolera struktury akwizycji i śledzenia. Jego celem będzie poprawa stabilności estymacji prawidłowego punktu akwizycji (ξ) poprzez skuteczną i niezawodną kontrolę jego zmian w przypadku nagłych zmian kanału, dlatego do estymatora logiki rozmytej zostanie dodana pamięć. W ten sposób estymator jest konwertowany w kontrolerze, co poprawia ogólną wydajność odbiornika. Dalsze badania uwzględnią również warunki kanału wielościeżkowego i możliwe zmiany, w tym detekcję odbiornika opartą na pochyleniu, aby osiągnąć dobrą wydajność akwizycji i śledzenia w kanałach jonosferycznych. Co więcej, wiarygodność wyników zachęca nas do wykorzystania estymacji akwizycji w celu zminimalizowania obciążenia obliczeniowego systemu akwizycji dla odpowiednich warunków kanału, poprzez zmniejszenie liczby iteracji potrzebnych do osiągnięcia zbieżności w adaptacyjnych filtrach LMS. Można zaprojektować bardziej wydajne sterowanie oparte na logice rozmytej, aby uzyskać lepszy kompromis między obciążeniem obliczeniowym (odnoszącym się do adaptacji filtrów LMS) a dokładnością estymacji punktu akwizycji (ξ).

WNIOSKI

Nowy proponowany estymator systemu akwizycji został już zaprezentowany, a niektóre wyniki porównano ze strategią kontroli stabilności w wielorozdzielczym systemie akwizycji w środowisku o zmiennym współczynniku SNR. Główną zaletą wielorozdzielczego estymatora rozmytego jest jego wiarygodność przy ocenie prawdopodobieństwa akwizycji, a także jego stabilność oraz szybka zbieżność w przypadku szybkich zmian współczynnika SNR w kanale. Obciążenie obliczeniowe estymatora rozmytego jest wyższe niż koszt takiego samego sterowania stabilnością. Średnia liczba FLOPS-ów w procesorze DSP potrzebna do wykonania całego procesu jest większa w porównaniu z konwencjonalną kontrolą stabilności. Należy to uwzględnić, ponieważ struktura wielorozdzielcza powinna minimalizować koszty obliczeniowe, aby móc pracować on-line z odebranymi danymi. Dalsze prace zostaną przeprowadzone w celu porównania obciążenia obliczeniowego dodanego do struktury z globalnymi ulepszeniami odbiornika wielorozdzielczego, aby ocenić, czy ten wzrost kosztów jest akceptowalny dla systemu akwizycji, czy też nie.

WSTĘP

Jednym z najskuteczniejszych narzędzi w świecie sztucznej inteligencji (AI) są sztuczne sieci neuronowe (ANN). Technika ta jest potężnym narzędziem wykorzystywanym w wielu różnych środowiskach i do różnych celów, takich jak klasyfikacja, klasteryzacja, modelowanie sygnałów czy regresja . Chociaż są one bardzo łatwe w użyciu, ich tworzenie nie jest prostym zadaniem, ponieważ ekspert musi włożyć w to dużo wysiłku i poświęcić dużo czasu. Rozwój ANN można podzielić na dwa etapy: rozwój architektury oraz trenowanie i walidację. Rozwój architektury określa nie tylko liczbę neuronów ANN, ale także rodzaj połączeń między nimi. Trenowanie określa wagi połączeń dla danej architektury. Projektowanie architektury jest zazwyczaj wykonywane ręcznie, co oznacza, że ekspert musi przetestować różne architektury, aby znaleźć tę, która zapewni najlepsze rezultaty. Każda próba architektury oznacza jej trenowanie i walidację, co może być procesem wymagającym wielu zasobów obliczeniowych, w zależności od złożoności problemu. Dlatego ekspert ma duży udział w całym rozwoju sieci neuronowej, chociaż ostatnio opracowano techniki stosunkowo automatycznego tworzenia sieci neuronowych.

TŁO

Rozwój sieci neuronowych (ANN) to temat badawczy, który przyciągnął wielu badaczy ze świata algorytmów ewolucyjnych . Techniki te opierają się na ogólnej strategii algorytmu ewolucyjnego: początkowa populacja z różnymi typami genotypów kodujących również różne parametry - zazwyczaj wagi połączeń i/lub architekturę sieci i/lub reguły uczenia - jest tworzona losowo i wielokrotnie indukowana do ewolucji. Najbardziej bezpośrednim zastosowaniem narzędzi EC w świecie ANN jest ewolucja wag połączeń. Proces ten rozpoczyna się od sieci neuronowej o już określonej topologii. W tym przypadku problemem do rozwiązania jest trenowanie wag połączeń, dążąc do zminimalizowania awarii sieci. Większość algorytmów trenujących, takich jak algorytm propagacji wstecznej (BP) , opiera się na minimalizacji gradientu, co wiąże się z szeregiem niedogodności. Główną z tych wad jest to, że algorytm dość często utyka w lokalnym minimum funkcji dopasowania i nie jest w stanie osiągnąć minimum globalnego. Jedną z możliwości zaradzenia tej sytuacji jest zastosowanie algorytmu ewolucyjnego, w którym proces uczenia odbywa się poprzez ewolucję wag połączeń w środowisku zdefiniowanym zarówno przez architekturę sieci, jak i rozwiązywane zadanie. W takich przypadkach wagi można przedstawić jako konkatenację wartości binarnych lub liczb rzeczywistych w algorytmie genetycznym (GA) . Ewolucja architektur polega na generowaniu struktury topologicznej, tj. ustaleniu łączności i funkcji przejścia każdego neuronu. Aby osiągnąć ten cel za pomocą algorytmu ewolucyjnego, konieczne jest wybranie sposobu kodowania genotypu danej sieci, aby mógł on zostać wykorzystany przez operatorów genetycznych. Najbardziej typowym podejściem jest kodowanie bezpośrednie. W tej technice istnieje jednoznaczna korespondencja między każdym z genów a określoną częścią sieci. Macierz binarna reprezentuje architekturę, w której każdy element ujawnia obecność lub brak połączenia między dwoma węzłami. W porównaniu z kodowaniem bezpośrednim istnieją pewne metody kodowania pośredniego. W tych metodach tylko niektóre cechy architektury są kodowane w chromosomie. Metody te mają kilka typów reprezentacji. Po pierwsze, reprezentacje parametryczne reprezentują sieć jako grupę parametrów, takich jak liczba warstw ukrytych, liczba węzłów dla każdej warstwy, liczba połączeń między dwiema warstwami itp. Inny typ reprezentacji pośredniej opiera się na systemie reprezentacji wykorzystującym reguły gramatyczne , ukształtowane jako reguły produkcji, które tworzą macierz reprezentującą sieć. Innym typem kodowania są metody wzrostu. W tym przypadku genotyp zawiera grupę instrukcji do budowy sieci . Wszystkie te metody rozwijają architektury, samodzielnie (najczęściej) lub razem z wagami. Zakłada się, że funkcja przejścia dla każdego węzła architektury została wcześniej ustalona przez eksperta i jest taka sama dla wszystkich węzłów sieci lub przynajmniej wszystkich węzłów tej samej warstwy. Opracowano tylko kilka metod, które również indukują ewolucję funkcji przejścia .

ROZWÓJ SIECI NOŚNYCH Z UŻYCIEM PROGRAMOWANIA GENETYCZNEGO

W tej sekcji bardzo krótko przedstawiono przykład tworzenia sieci neuronowych z wykorzystaniem narzędzia sztucznej inteligencji - programowania genetycznego (GP), które wykonuje algorytm ewolucyjny, oraz jak można je zastosować w zadaniach eksploracji danych.

Programowanie genetyczne

GP opiera się na ewolucji danej populacji. Jego działanie jest podobne do algorytmu genetycznego. W tej populacji każdy osobnik reprezentuje rozwiązanie problemu, który ma zostać rozwiązany. Ewolucja odbywa się poprzez selekcję najlepszych osobników - choć te najgorsze również mają niewielką szansę na wybór - i ich wzajemne połączenie w celu tworzenia nowych rozwiązań. Po kilku pokoleniach populacja powinna zawierać kilka dobrych rozwiązań problemu. Kodowanie GP dla rozwiązań ma kształt drzewa, więc użytkownik musi określić, które terminale (liście drzewa) i funkcje (węzły mogące mieć potomków) będą wykorzystywane przez algorytm ewolucyjny w celu zbudowania złożonych wyrażeń.Szerokie zastosowanie GP w różnych środowiskach i wynikający z tego sukces wynikają z możliwości adaptacji do wielu zróżnicowanych problemów. Chociaż głównym i bardziej bezpośrednim zastosowaniem jest generowanie wyrażeń matematycznych , GP znalazło również zastosowanie w innych dziedzinach, takich jak projektowanie filtrów , ekstrakcja wiedzy, przetwarzanie obrazu itp.

Przegląd modelu

W niniejszej pracy wykorzystano kodyfikację opartą na grafach do reprezentacji sieci neuronowych w genotypie. Grafy te nie będą zawierały żadnych cykli. Ze względu na ten typ kodyfikacji operatory genetyczne musiały zostać zmienione, aby można było użyć algorytmu GP. Operatory zostały zmienione w następujący sposób:

o Algorytm tworzenia musi umożliwiać tworzenie grafów. Oznacza to, że w momencie tworzenia potomka węzła, algorytm ten musi umożliwiać nie tylko utworzenie tego węzła, ale także powiązanie z istniejącym w tym samym grafie, bez tworzenia cykli wewnątrz grafu.
o Algorytm krzyżowania musi umożliwiać krzyżowanie grafów. Algorytm ten działa bardzo podobnie do istniejącego algorytmu dla drzew, tj. na każdym osobniku wybierany jest węzeł, aby zmienić cały podgraf, który reprezentuje, na inny osobnik. Należy zachować szczególną ostrożność w przypadku grafów, ponieważ przed krzyżowaniem mogą istnieć powiązania spoza tego podgrafu do dowolnych węzłów na nim. W tym przypadku, po krzyżowaniu, połączenia te są aktualizowane i zmieniane tak, aby wskazywały na losowe węzły w nowym podgrafie.
o Algorytm mutacji również został zmieniony i działa bardzo podobnie do algorytmu mutacji opartego na drzewie GP. Węzeł jest wybierany z jednostki, a jego podgraf jest usuwany i zastępowany nowym. Zanim nastąpi mutacja, węzły w jednostce mogą wskazywać na inne węzły w podgrafie. Połączenia te są aktualizowane i zmieniane tak, aby wskazywały na losowe węzły w nowym podgrafie.

Algorytmy te muszą również spełniać dwa ograniczenia w GP: typowanie i maksymalną wysokość. Właściwość typowania GP (Montana, 1995) oznacza, że każdy węzeł będzie miał typ, a także określi, jaki typ będzie miał każdy z jego potomków. Ta właściwość umożliwia tworzenie struktur zgodnych z określoną gramatyką. Aby móc użyć GP do opracowania dowolnego rodzaju systemu, konieczne jest określenie zestawu operatorów, które znajdą się w drzewie. Dzięki nim system ewolucyjny musi być w stanie budować poprawne drzewa reprezentujące sieci neuronowe. Przegląd używanych operatorów można znaleźć w tabeli



Tabela ta zawiera podsumowanie operatorów, których można użyć w drzewie. Ten zestaw terminali i funkcji służy do zbudowania drzewa reprezentującego sieć neuronową (SN).Chociaż zestawy te nie są wyjaśnione w tekście, na rysunku można zobaczyć przykład ich wykorzystania do reprezentacji sieci neuronowej (SSN).



Operatory te służą do budowania drzew GP. Drzewa te muszą zostać ocenione, a po ocenie genotyp przekształca się w fenotyp. Innymi słowy, jest ono konwertowane na sieć neuronową (SSN) z już ustalonymi wagami (a zatem nie wymaga trenowania) i może zostać ocenione. Proces ewolucyjny wymaga przypisania każdemu genotypowi wartości dopasowania. Wartość ta jest wynikiem oceny sieci z zestawem wzorców reprezentującym problem. Wynik ten to średni błąd kwadratowy (MSE) różnicy między wynikami sieci a wynikami pożądanymi. Niemniej jednak wartość ta została zmodyfikowana, aby skłonić system do generowania prostych sieci. Modyfikacja została dokonana poprzez dodanie wartości penalizacji pomnożonej przez liczbę neuronów w sieci. W ten sposób, biorąc pod uwagę, że system ewolucyjny został zaprojektowany w celu minimalizacji wartości błędu, po dodaniu wartości dopasowania, większa sieć miałaby gorszą wartość dopasowania. Dlatego istnienie prostych sieci byłoby preferowane, ponieważ dodawana wartość kary jest proporcjonalna do liczby neuronów w sieci neuronowej (ANN). Rachunek końcowego dopasowania będzie następujący: dopasowanie = MSE + N * P gdzie N to liczba neuronów sieci, a P to wartość kary dla tej liczby. Przykłady zastosowań .Technika ta została wykorzystana do rozwiązywania problemów o różnej złożoności zaczerpniętych z UCI . Wszystkie te problemy to problemy ekstrakcji wiedzy z baz danych, w których, biorąc za podstawę pewne cechy, ma się na celu przeprowadzenie predykcji dotyczącej innego atrybutu bazy danych. Krótki opis problemów do rozwiązania można znaleźć w Tabeli 2, wraz z innymi parametrami ANN używanymi w dalszej części pracy.



Wszystkie te bazy danych zostały znormalizowane między 0 a 1 i podzielone na dwie części, przy czym 70% bazy danych przeznaczono na szkolenie, a pozostałe 30% na testy.

Wyniki i porównanie z innymi metodami

W celu oceny wydajności systemu przeprowadzono kilka eksperymentów. Wartości parametrów przyjęte w tych eksperymentach były następujące:

o Wielkość populacji: 1000 osobników.
o Współczynnik krzyżowania: 95%.
o Prawdopodobieństwo mutacji: 4%.
o Algorytm selekcji: turniej 2-osobniczy.
o Maksymalna wysokość grafu: 5.
o Maksymalna liczba wejść dla każdego neuronu: 9.
o Wartość kary: 0,00001.

Aby osiągnąć te wartości, konieczne było przeprowadzenie kilku eksperymentów w celu uzyskania wartości parametrów, które dałyby dobre wyniki dla wszystkich problemów. Problemy te różnią się znacznie pod względem złożoności, dlatego oczekuje się, że parametry te dadzą dobre wyniki dla wielu różnych problemów. Aby ocenić wydajność, przedstawiony tutaj system został porównany z innymi metodami generowania i trenowania sieci neuronowych (SSN). Metoda 5x2cv została wykorzystana przez Cantú-Paza i Kamatha (1995) do porównania różnych technik generowania i trenowania sieci neuronowych (ANN) opartych na narzędziach EC. Niniejsza praca przedstawia jako wyniki średnie precyzje uzyskane w 10 wynikach testów wygenerowanych tą metodą. Wartości te stanowią podstawę porównania opisanej tutaj techniki z innymi dobrze znanymi, szczegółowo opisanymi przez Cantú-Paza i Kamatha (1995). Niniejsza praca pokazuje średni czas potrzebny do osiągnięcia wyników. Ponieważ nie użyto tego samego procesora, co w przypadku poprzedniego, można oszacować nakład obliczeniowy potrzebny do uzyskania wyników. Nakład ten reprezentuje liczbę ocen pliku wzorca. Nakład obliczeniowy dla każdej techniki można zmierzyć za pomocą wielkości populacji, liczby pokoleń, liczby zastosowań algorytmu BP itp. Obliczenia te różnią się dla każdego użytego algorytmu. Wszystkie techniki porównywane z pracą są związane z wykorzystaniem algorytmów ewolucyjnych do projektowania ANN. W celu oceny dokładności sieci przeprowadzono pięć iteracji 5-krotnego krzyżowego testu walidacyjnego we wszystkich tych technikach. Techniki te obejmują macierz łączności, przycinanie, wyszukiwanie parametrów i gramatykę przepisywania grafów. Tabela 2 przedstawia podsumowanie liczby neuronów użytych przez Cantú-Paza i Kamatha (1995) do rozwiązania problemów z macierzą łączności i technikami przycinania. Podano tu również numer epoki algorytmu BP, jeśli został użyty. Tabela 3 przedstawia konfigurację parametrów wykorzystaną przez te techniki.



Wykonywanie zostało zatrzymane po 5 generacjach bez poprawy lub po 50 generacjach łącznie. Wyniki uzyskane tymi 4 metodami przedstawiono w Tabeli 4.



Każde pole tabeli wskazuje 3 różne wartości: wartość precyzji uzyskaną przez Cantú-Paza i Kamatha (1995) (po lewej), nakład obliczeniowy potrzebny do uzyskania takiej wartości za pomocą tej techniki (poniżej) oraz wartość precyzji uzyskaną za pomocą techniki opisanej tutaj i powiązanej z wcześniej wspomnianą wartością nakładu obliczeniowego (po prawej). Patrząc na tę tabelę, widać wyraźnie, że wyniki uzyskane za pomocą proponowanej tutaj metody są nie tylko podobne do tych przedstawionych przez Cantú-Paz i Kamath (1995), ale w większości przypadków nawet lepsze. Wynika to z faktu, że metody te wymagają dużego obciążenia obliczeniowego, ponieważ uczenie jest niezbędne dla każdego przypadku oceny sieci (indywidualnej), co z kolei okazuje się czasochłonne. W opisanych tutaj pracach procedury projektowania i uczenia są wykonywane jednocześnie, a zatem czas potrzebny na projektowanie i ocenę sieci jest łączony.

TRENDY NA PRZYSZŁOŚĆ

Przyszłym kierunkiem prac w tym obszarze będzie badanie parametrów systemu w celu oceny ich wpływu na wyniki różnych problemów. Innym interesującym kierunkiem jest połączenie tego algorytmu ewolucji grafu z algorytmem genetycznym, który przeprowadza proces optymalizacji wartości wag. Dzięki tej modyfikacji cały system będzie miał dwa poziomy:

1. Algorytm ewolucji grafu wyjaśniony w tej pracy przeprowadza ewolucję architektur.
2. GA bierze te architektury i optymalizuje wagi połączeń. Dzięki tej architekturze ewolucję sieci neuronowych można postrzegać jako strategię lamarkowską.

WNIOSKI

Niniejsza praca opisuje technikę, w której algorytm ewolucyjny jest używany do automatycznego tworzenia sieci neuronowych. Ten algorytm ewolucyjny przeprowadza ewolucję grafów i jest oparty na algorytmie GP, chociaż musiał zostać zmodyfikowany, aby działał z grafami zamiast z drzewami. Wyniki pokazują, że sieci zwrócone przez ten algorytm dają w większości przypadków błąd niższy niż błąd generowany przez pozostałe systemy tworzenia sieci neuronowych użyte do porównania. Tylko jedna technika (przycinanie) działa lepiej niż opisana tutaj. Jednak technika ta nadal wymaga pewnego nakładu pracy ze strony eksperta, aby zaprojektować początkową sieć. Większość technik stosowanych do tworzenia sieci neuronowych jest dość kosztowna, w niektórych przypadkach ze względu na połączenie uczenia z ewolucją architektury. Opisana tutaj technika pozwala na osiągnięcie dobrychwyników przy niskim koszcie obliczeniowym, a ponadto dodatkową zaletą jest to, że nie tylko architektura i łączność sieci ulegają ewolucji, ale także sama sieć przechodzi proces optymalizacji.

WSTĘP

Tradycyjnie systemy fizyczne były projektowane przez inżynierów z wykorzystaniem złożonych zbiorów reguł i zasad. Proces projektowania ma charakter odgórny i rozpoczyna się od precyzyjnej specyfikacji. Kontrastuje to bardzo silnie z mechanizmami, które doprowadziły do niezwykłej różnorodności i wyrafinowania istot żywych. W tym przypadku "projekty" ewoluują w procesie doboru naturalnego. Projekt zaczyna się od zestawu instrukcji zakodowanych w DNA, którego regiony kodujące są najpierw transkrybowane na RNA w jądrze komórkowym, a następnie tłumaczone na białka w cytoplazmie komórki. DNA zawiera instrukcje budowy cząsteczek za pomocą sekwencji aminokwasów. Ostatecznie, po szeregu niezwykle złożonych i subtelnych reakcji biochemicznych, powstaje cały żywy organizm. Przeżywalność organizmu można postrzegać jako proces składania większego systemu z wielu części składowych, a następnie testowania organizmu w środowisku, w którym się znajduje (Miller, 2000). Głównym celem ewolucyjnego sprzętu jest zbudowanie obwodu cyfrowego z wykorzystaniem metod inspirowanych biologicznie, takich jak algorytmy genetyczne. Potencjalne rozwiązania są tutaj kodowane jako wektory konfiguracji, które zarządzają połączeniami między komórkami logicznymi wewnątrz obwodu rekonfigurowalnego. Wszystkie wektory konfiguracji reprezentują genotyp, a jeden wektor konfiguracji to osobnik z jego własnymi cechami (takimi jak chromosom). Osobniki są generowane za pomocą operatorów genetycznych, takich jak krzyżowanie lub mutacja. Jeden osobnik daje jeden obwód rozwiązania, który jest testowany w module ewaluacyjnym. Obwód uzyskany od osobnika składa się z fenotypu. Zachowanie obwodu jest porównywane z funkcjami docelowymi, które chcemy zaimplementować. Rezultatem jest dopasowanie: jeśli obwód aproksymuje zachowanie funkcji docelowej, mamy dobre dopasowanie osobnika, który go generuje. Następnie każdy osobnik o odpowiednim dopasowaniu trafia do modułu selekcji, gdzie wybierani są przyszli rodzice w krzyżowaniu i mutacji. Ostatecznie otrzymujemy rozwiązanie obwodu, które implementuje funkcję docelową. Mamy ewolucyjną syntezę obwodu cyfrowego - metodę taką jak montaż i testowanie.Ta metoda może być użyteczna, ponieważ pozwala eksplorować przestrzeń projektową poza ograniczeniami narzucanymi przez tradycyjne metody projektowania. W ewolucyjnym sprzęcie rozwijane są dwa kierunki badań. W ewolucyjnym sprzęcie zewnętrznym jednostki są uzyskiwane z implementacji programowejna komputerze, a fenotyp składa się z abstrakcyjnych obwodów wysokiego poziomu, takich jak pliki obiektowe SPICE lub pliki konfiguracyjne FPGA (.bit). Z drugiej strony, ewolucja wewnętrzna zakłada, że cały proces ewolucji odbywa się w jednym lub kilku układach scalonych (FPGA): implementacji sprzętowejewolucyjnego sprzętu. Wyzwaniem jest zaprojektowanie ewolucji wewnętrznej, ponieważ może być ona wykorzystywana w aplikacjach takich jak systemy sterowania robotami. Wymaga to jednak implementacji algorytmów opartych na oprogramowaniu w modułach sprzętowych.

TŁO

Dynamiczny, rekonfigurowalny i ewolucyjny sprzęt w ostatnich latach dynamicznie ewoluował. Dziesięć lat temu implementacja układów cyfrowych, charakteryzująca się wysokim stopniem złożoności, wiązała się z wieloma problemami, spowodowanymi zwłaszcza ograniczeniami technologicznymi. Największy popyt na rynku generowały złożone, programowalne macierze bramek lub niskoziarniste, programowalne macierze bramek, gdzie głównymi problemami były liczba komórek Boole′a dostępnych w układzie oraz czas opóźnienia. Szybki rozwój technologii zwiększa obecnie wydajność układów programowalnych. Dzięki temu możliwe jest zaimplementowanie rdzenia jednostki centralnej o wysokiej szybkości przetwarzania (CPU), porównywalnego z implementacją układów scalonych dedykowanych konkretnym zastosowaniom. Niskie koszty produktu sprawiają, że nowoczesne programowalne układy cyfrowe mogą być nabywane przez użytkowników końcowych, takich jak studenci i naukowcy. W związku z tym konieczna jest ewolucja w zakresie projektowania, syntezy i implementacji układów logicznych programowalnych. Jednym z bardzo atrakcyjnych kierunków badań jest implementacja sprzętowych systemów inspirowanych biologią w programowalnych układach logicznych, takich jak sieci neuronowe lub algorytmy ewolucyjne (np. algorytmy genetyczne). Pierwszym kierunkiem badań w tej dziedzinie jest znalezienie rozwiązań poprawiających wydajność algorytmu genetycznego poprzez implementację sprzętową. Implementacje programowe charakteryzują się elastycznością i łatwością konfiguracji. Jednak szybkość konwergencji jest niska ze względu na szeregowe wykonywanie kroków podczas działania algorytmu. Aby zwiększyć szybkość, wymagana jest równoległa implementacja modułów . Odbywa się to poprzez implementację sprzętową na programowalnych układach logicznych. W tej dziedzinie prowadzone są dalsze badania. Drugim kierunkiem badań jest połączenie koncepcji montażu i testowania z algorytmem ewolucyjnym w celu stopniowej poprawy jakości projektu. Zostało to w dużej mierze przyjęte w rozwijającej się dziedzinie ewolucyjnego sprzętu, gdzie zadaniem jest zbudowanie układu elektronicznego. Thompson przeprowadził pierwsze badania, wykorzystując platformę rekonfigurowalną i wykazał, że możliwe jest stworzenie układu, który mógłby rozróżniać dwa sygnały prostokątne. Udowodnił, że możliwe jest zaprojektowanie układu cyfrowego z wykorzystaniem ewolucyjnego algorytmu. Proces ewolucyjny wykorzystał właściwości fizyczne podłoża krzemowego do stworzenia wydajnego układu. Twierdził, że sztuczna ewolucja może wytworzyć projekt obwodu elektronicznego, który wykracza poza zakres konwencjonalnych metod. Koza (Koza, 1997) był pionierem zewnętrznej ewolucji obwodów analogowych przy użyciu SPICE i automatycznie generował obwody, które są konkurencyjne w stosunku do ludzkich projektantów. Większość pracowników zadowala się zewnętrzną ewolucją, ponieważ algorytm ewolucyjny jest oparty na oprogramowaniu. Jednak Scott i inni osiągają różne rozwiązania dla sprzętowej implementacji algorytmów ewolucyjnych. W (Scott, 1997) jest projekt sprzętowego algorytmu genetycznego zaimplementowanego jako struktura sprzętowa potoku w FPGA. Jego praca jest demonstracją, że można zaimplementować w pełni zintegrowane rozwinięte rozwiązanie sprzętowe (wewnętrzne). Do projektowania modułów sprzętowych dla krzyżowania, selekcji i mutacji wykorzystuje się sieci kombinacyjne, takie jak tablice systolicowe przedstawione przez (Bland2001). Miller i inni podają odniesienie do jego pracy dotyczącej ewolucji kombinacyjnego układu cyfrowego do implementacji funkcji arytmetycznych. Najpierw wykorzystuje sieci bramek, które ewoluują w obwodach arytmetycznych, ale pokazuje, że możliwe jest wykorzystanie ewolucji niektórych podukładów do uzyskania bardziej złożonych układów. Inny przykład zewnętrznej syntezy ewolucyjnej podaje praca Martina. Tutaj fenotyp jest określony przez sekwencje języka opisu sprzętu (HandleC). Jednak wykorzystanie algorytmu genetycznego w projektowaniu sprzętu nie ogranicza się do innych dziedzin. W (Shaaban 2001) jest on wykorzystywany w projektowaniu układów scalonych w detektorach półprzewodnikowych. Yasunaga wykorzystuje sprzętową syntezę układu cyfrowego w rekonfigurowalnej, programowalnej strukturze logicznej do implementacji systemu rozpoznawania mowy. Ostatnio synteza ewolucyjna jest wykorzystywana do projektowania układów sekwencyjnych lub w projektowaniu filtrów cyfrowych . Rozwinięta synteza kombinacyjna i sekwencyjna układów cyfrowych została uwzględniona jako moduł sterujący autonomicznym systemem mobilnym, umożliwiający wykonywanie większej liczby zadań, takich jak omijanie przeszkód i trafianie w cel . W rzeczywistości rozwiązywanie problemów wielocelowych (wielozadaniowych) w systemach sprzętowych metodą ewolucyjną jest omawiane przez Coello i wykorzystywane w nowszych pracach . Pytanie brzmi: czy możliwe jest projektowanie układów cyfrowych za pomocą algorytmu ewolucyjnego, takiego jak algorytm genetyczny (GA)? Aby odpowiedzieć na to pytanie, najpierw konieczne jest zaprojektowanie układu rekonfigurowalnego, który można programować za pomocą algorytmu ewolucyjnego. Rozwiązaniem może być rekonfigurowalna sieć bramek wielowarstwowych. Każda bramka w warstwie x może być połączona lub nie z bramką w warstwie x+1.

SIEĆ BRAMEK REKONFIGUROWALNYCH I SPRZĘTOWY ALGORYTM GENETYCZNY

Wykorzystane modele

Ta sekcja poświęcona jest omówieniu modeli dwóch komponentów ewolucyjnych mikrostruktur sprzętowych: sprzętowego algorytmu genetycznego i dynamicznie rekonfigurowalnego układu. W tej sekcji najpierw przedstawiono koncepcję generycznych struktur dynamicznie rekonfigurowalnych. Każda komórka sieci jest podzielona na jednostki obliczeniowe i konfigurowalną jednostkę sieciową. Aby uruchomić algorytm, wykonywane jest lokalne obliczenie - operacje arytmetyczne i logiczne przez każdą komórkę, oraz obliczenie sieciowe - każda komórka może skonfigurować połączenie z pozostałymi komórkami w sieci. Koncepcję tę można rozszerzyć na sieć bramek wielowarstwowych poprzez zastąpienie lokalnej komórki obliczeniowej bramkami elementarnymi, a połączeń sieciowych poleceniami przełączania za pomocą algorytmu genetycznego . W tym konkretnym przypadku dynamicznie rekonfigurowalna struktura stała się strukturą rekonfigurowalną sprzętowo. Na rysunku 1 przedstawiono komórkę rekonfigurowalnego sprzętu: generyczną bramkę cyfrową.



Każda bramka generyczna może być skonfigurowana z lokalną elementarną funkcją Boole′a i większą liczbą połączeń przełączających z innymi bramkami. W ten sposób powstaje pierwszy schemat kodowania algorytmu genetycznego: jednostka to ciąg kodów statusu połączeń i funkcji Boole′a, jak na rysunkub. Każdy algorytm zawiera funkcje, które mogą być wykonywane przez jednostkę centralną. W systemach obliczeniowych z pojedynczym procesorem można wykonywać tylko jedną funkcję w danym momencie. W strukturze sprzętowej każda funkcja może być zaimplementowana w sieci kombinacyjnej. Istnieją dwa główne rodzaje sieci kombinacyjnych: sieć sortująca składa się z obwodów elementarnych min/max oraz sieć permutacyjna składa się z obwodów elementarnych permutacji. Na rysunku 2 przedstawiono rekurencyjny obwód sortujący i rekurencyjny obwód permutacyjny.



Projektowanie sprzętowego algorytmu genetycznego, dynamiczny obwód rekonfigurowalny i opis zastosowaniaW tej sekcji omówiono techniki wykorzystywane do projektowania ewolucyjnych mikrostruktur sprzętowych. Najpierw przedstawiono projektowanie sprzętowego algorytmu genetycznego z wykorzystaniem modeli z poprzedniej sekcji. Każdy moduł jest projektowany indywidualnie i opisany za pomocą sieci kombinacyjnych. Sprzętowy algorytm genetyczny to układ, który łączy wszystkie moduły w rozwiązanie w pełni sprzętowe. Schemat blokowy HGA (sprzętowego algorytmu genetycznego) przedstawiono na poniższym rysunku



Głównym problemem tego rozwiązania jest to, że moduły można wykorzystać w innym algorytmie i połączyć w inny sposób bez konieczności przeprojektowywania. Każdy moduł może działać niezależnie, dzięki czemu struktura może przetwarzać więcej generacji w tym samym czasie. Z drugiej strony, każdy moduł został zaprojektowany jako sieć funkcji elementarnych, takich jak min/maks lub permutacja. W związku z tym wszelkie nowe zmiany, takie jak zwiększenie rozmiaru lub liczby osobników, można bardzo łatwo wprowadzić, dodając bloki funkcji elementarnych. W module selekcji jednostka (ciąg bitów) z obliczoną sprawnością wchodzi do lewej strony tablicy. Każda komórka zestawia wartości sprawności z dwóch wejść x_in i y_in. Wyjście x_out otrzymuje jednostkę o najmniejszej wartości sprawności z wejść, a wyjście y_out jednostkę o największej. Zatem jednostki o słabej (małej) sprawności będą przemierzać tablicę poziomo, od lewej do prawej, a jednostki o dobrej sprawności będą przemierzać tablicę z góry do dołu w pionie. Wreszcie po lewej stronie mamy wyjścia o najlepszej sprawności. Tę samą koncepcję stosuje się do obwodu krzyżowania. Niektóre jednostki posortowane według modułu selekcji wchodzą do modułu krzyżowania. Operator jest stosowany do określonej liczby par jednostek. Zazwyczaj jednostki o najlepszej sprawności są "rodzicami" dla pierwszego pokolenia potomstwa, które powstaje z tego modułu. W module mutacji używamy również pojedynczej kolumny struktur logicznych (komórek mutacji). Tablica została zaprojektowana z następującym ograniczeniem: mutacja musi dotyczyć tylko jednego bitu od osobnika i jednego osobnika z generacji (wszystkich osobników z jednego kroku iteracji). Strukturę można łatwo zmienić, jeśli zależy nam na innym zachowaniu. Ocena odbywa się poprzez porównanie odpowiedzi rozwiązań cząstkowych dostarczonych przez każdego osobnika z odpowiedzią pożądaną. W tym przypadku definiowana jest docelowa funkcja boolowska, która musi być zaimplementowana sprzętowo. Kolejnym kryterium oceny jest minimalizacja zasobów cyfrowych użytych do implementacji funkcji docelowej. Wartość dopasowania jest obliczana na podstawie obu kryteriów oceny.



Zaprojektowano i przetestowano trzy dynamiczne układy rekonfigurowalne. Wszystkie oparte są na sprzętowej strukturze rekonfigurowalnej . Pierwszy schemat, układ rekonfigurowalny z terminami min-max, wykorzystuje te same zasady, co programowalna tablica logiczna. Schemat składa się z trzech warstw: warstwy INV, warstwy AND i warstwy OR. Połączenia między warstwą INV a warstwą AND są oparte na poleceniach algorytmu genetycznego. Ten układ rekonfigurowalny charakteryzuje się dużą szybkością zbieżności, a jednostki o najmniejszym rozmiarze eksplorują tylko tradycyjne rozwiązania przestrzenne, a jego rozmiar rośnie wykładniczo wraz z liczbą wejść i liniowo wraz z liczbą wyjść. Drugi układ to układ rekonfigurowalny INV-AND-OR. Podobnie jak pierwszy, ma on trzy warstwy: warstwę INV, warstwę AND i warstwę OR. Algorytm genetyczny konfiguruje w tym przypadku połączenia między warstwą INV - AND a warstwą AND - OR. Ten schemat zmniejsza wzrost rozmiaru wraz z liczbą wyjść, ale zachowuje wykładniczy wzrost wraz z liczbą wejść, a rozmiar jednostek jest większy niż w pierwszym układzie. Ostatni układ rekonfigurowalny to układ rekonfigurowalny funkcji elementarnych (e - rekonfigurowalny). Zawiera on więcej warstw. Każda warstwa zawiera szereg bramek generycznych. Bramka generyczna może implementować elementarne funkcje Boola (AND, OR, XOR) i bardziej złożone układy, takie jak multipleksery. To rozwiązanie zwiększa rozmiar jednostek i złożoność układu rekonfigurowalnego, ale jest prawie niezmienne w zależności od liczby wejść i wyjść. Ostatni układ rekonfigurowalny eksploruje największą przestrzeń rozwiązań, wykraczającą poza ograniczenia tradycyjnych metod projektowania. Ewolucyjny układ sprzętowy jest wykorzystywany w trzech zastosowaniach. Po pierwsze, funkcja docelowa jest statyczna, a algorytm musi znaleźć rozwiązanie sprzętowe, aby ją zaimplementować. Każdy układ reprezentuje tutaj potencjalne rozwiązanie dla sprzętowej implementacji funkcji docelowej. Pętla ewolucyjna jest powtarzana aż do znalezienia optymalnego rozwiązania. Znajdowanie rozwiązania sprzętowego nazywa się tutaj sprzętem ewolucyjnym. W tym momencie pętla ewolucyjna zostaje zatrzymana. W drugim zastosowaniu funkcja docelowa jest również statyczna. Jednak tutaj układ koduje tylko podukład - jedną bramkę generyczną lub jedną warstwę bramek. Osobniki ewoluują, a potomstwo zastępuje rodziców na różnych pozycjach, a ewaluacja jest przeprowadzana na całym obwodzie, aż nowe rozwiązanie będzie lepsze od starego. Pętla ewolucji jest powtarzana aż do znalezienia optymalnego rozwiązania. To rozwiązanie jest wykorzystywane do projektowania obwodów z dużą liczbą wejść, wyjść i podobwodów. Ostatnie zastosowania wykorzystują dynamiczne funkcje docelowe. Tutaj każdy osobnik reprezentuje kompletne rozwiązanie układu. Pętla ewolucji składa się z dwóch kroków. Pierwszy krok jest taki sam jak w pierwszym zastosowaniu: pętla działa aż do znalezienia rozwiązania. Po znalezieniu rozwiązania w osobniku, zwanym osobnikiem głównym, ewolucja jest kontynuowana dla pozostałych osobników. Celem drugiego kroku pętli ewolucji jest uzyskanie różnych osobników w stosunku do osobnika głównego. Po zmianie funkcji docelowej pętla ewolucji przechodzi do pierwszego kroku, a osobniki o wysokim stopniu rozproszenia ewoluują do nowego rozwiązania.

WNIOSKI


W niniejszym artykule przedstawiono koncepcję ewolucyjnego sprzętu i przedstawiono praktyczną implementację sprzętowego algorytmu genetycznego oraz rekonfigurowalnej struktury sprzętowej. Sprzętowy algorytm genetyczny zwiększa szybkość zbieżności do rozwiązań, które reprezentują konfigurację układu rekonfigurowalnego. Może być on wykorzystany do ewolucyjnej syntezy obwodów cyfrowych w wewnętrznie ewoluującym sprzęcie. Rozwiązania ciągów bitów, które są generowane przez algorytm genetyczny, mogą byćkonfiguracją połączeń dla dynamicznego rekonfigurowalnego układu sprzętowego. Przedstawiamy tutaj trzy architektury układów rekonfigurowalnych, które mogą być dynamicznie programowane przez ten sam sprzętowy moduł algorytmu genetycznego. Struktura została zaimplementowana na układzie FPGA Spartan 3 firmy Xilinx.

PRZYSZŁE TRENDY

Niniejszy artykuł wskazuje na więcej kierunków badań. Pierwszym z nich jest projektowanie układów rekonfigurowalnych z wykorzystaniem prymitywów FPGA. Nowa generacja układów FPGA (Virtex5) umożliwia dynamiczną rekonfigurację za pomocą prymitywów. W tym przypadku bramka generyczna jest zastępowana przez fizyczne komórki z układu FPGA. Kolejnym kierunkiem jest implementacja hybrydowej struktury neurogenetycznej. Sprzętowa implementacja sieci neuronowej może być wykorzystana do przechowywania najlepszych rozwiązań algorytmu genetycznego. Ta konfiguracja może być wykorzystana do poprawy zbieżności algorytmu genetycznego. Udoskonalony sprzęt może być wykorzystany do projektowania układów analogowych. W tym przypadku układ rekonfigurowalny Boole′a może zostać zastąpiony analogowym układem rekonfigurowalnym (takim jak Field Programmable Transistors Area).

WSTĘP

Bezprzewodowe sieci ad-hoc to sieci bezinfrastrukturalne, w których heterogeniczne, sprawne węzły łączą się ze sobą i rozpoczynają komunikację bez wsparcia szkieletu. Sieci te mogą być prawdziwie dynamiczne, a węzły w tych sieciach mogą swobodnie się przemieszczać, łącząc się i rozłączając z innymi węzłami w sieci. Ta właściwość sieci ad-hoc, polegająca na samoorganizacji i komunikacji bez wsparcia zewnętrznego, zapewnia im ogromną elastyczność i czyni je idealnymi do zastosowań takich jak sytuacje kryzysowe, zarządzanie kryzysowe, wojsko i opieka zdrowotna. Na przykład, w przypadku sytuacji kryzysowych, takich jak trzęsienia ziemi, często większość istniejącej infrastruktury sieci przewodowej ulega zniszczeniu. Ponadto, ponieważ większość sieci bezprzewodowych, takich jak GSM i IEEE 802.11, wykorzystuje infrastrukturę przewodową jako szkielet, często stają się one bezużyteczne. W takich sytuacjach sieci ad-hoc można szybko wdrożyć i wykorzystać do koordynacji działań pomocowych i ratunkowych. Sieci ad-hoc mogą być wykorzystywane do komunikacji między różnymi stacjami na polu bitwy, gdzie konfiguracja sieci przewodowej lub opartej na infrastrukturze jest często uważana za niepraktyczną. Chociaż przeprowadzono wiele badań nad sieciami ad-hoc, wiele problemów, takich jak bezpieczeństwo, jakość usług (QoS) i multicasting, musi zostać w zadowalający sposób rozwiązanych, zanim sieci ad-hoc będą mogły wyjść z laboratoriów i zapewnić elastyczne i tanie rozwiązanie sieciowe. Algorytmy obliczeń ewolucyjnych to klasa algorytmów obliczeniowych inspirowanych biologią. Obliczenia inspirowane biologią odnoszą się do zbioru algorytmów, które wykorzystują techniki zaczerpnięte z naturalnych zjawisk biologicznych i implementują je do rozwiązania problemu matematycznego (Olario i Zomaya, 2006). Zjawiska naturalne, takie jak ewolucja, genetyka, zachowania zbiorowe organizmów społecznych i funkcjonowanie mózgu ssaków, uczą nas różnorodnych technik, które można skutecznie wykorzystać do rozwiązywania problemów informatycznych, które z natury są trudne. W tym rozdziale oraz w rozdziale zatytułowanym "Podejście oparte na inteligencji roju w bezprzewodowych sieciach ad hoc" tej książki przedstawiamy niektóre z obecnie dostępnych, ważnych implementacji obliczeń inspirowanych biologią w dziedzinie sieci ad hoc. W rozdziale tym omówiono problem optymalnego klastrowania w sieciach ad hoc i jego rozwiązanie z wykorzystaniem metody programowania genetycznego (GP). Rozdział zatytułowany "Podejścia oparte na inteligencji roju w bezprzewodowych sieciach ad hoc" tej książki kontynuuje ten sam duch i wyjaśnia zastosowanie zasad leżących u podstaw optymalizacji kolonii mrówek (ACO) do routingu w sieciach ad hoc.

TŁO

Pierwsza sieć bezinfrastrukturalna została wdrożona jako radio pakietowe . Została ona zainicjowana przez Agencję Zaawansowanych Projektów Badawczych w Obszarze Obronności (DARPA) w latach 70. XX wieku. W tym czasie projekt ALOHA (McQuillan i Walden, 1977) na Uniwersytecie Hawajskim wykazał wykonalność wykorzystania transmisji rozgłoszeniowej do wysyłania/odbierania pakietów danych w sieciach radiowych jednoskokowych. ALOHA doprowadziła później do rozwoju Sieci Radia Pakietowego (PRNET),która była wieloskokową siecią wielodostępową, sponsorowaną przez Agencję Zaawansowanych Projektów Badawczych (ARPA). Cele projektowe PRNET były podobne do obecnych sieci ad-hoc, takie jak kontrola przepływu i błędów na wieloskokowej trasie komunikacyjnej, wytwarzanie i utrzymywanie informacji o topologii sieci i mechanizmów obsługi mobilności routerów oraz wymagań dotyczących mocy i rozmiaru, między innymi. Jednak ze względu na ogromne rozmiary urządzeń elektronicznych, radia pakietowe nie były łatwe w transporcie, co prowadziło do ograniczonej mobilności. Ponadto zasięg sieci był powolny, a ponieważ do routingu wykorzystano algorytm najkrótszej ścieżki Bellmana-Forda, występowały pętle przejściowe. Od tego czasu przeprowadzono wiele badań nad sieciami ad-hoc i opracowano szereg algorytmów routingu, które zapewniają znacznie większą wydajność i są wolne od pętli. Szybki rozwój technologii krzemowej doprowadził również do ciągłego zmniejszania urządzeń o rosnącej mocy obliczeniowej. Sieci ad-hoc są rozpatrywane pod kątem zastosowania w medycynie, ratownictwie, środowiskach biurowych, sieciach osobistych i wielu innych zastosowaniach codziennego życia. Algorytmy inspirowane biologią, do których należą ewolucyjne podejścia obliczeniowe, takie jak algorytmy genetyczne, istnieją od ponad 50 lat. W rzeczywistości istnieją dowody sugerujące, że sztuczne sieci neuronowe mają swoje korzenie w niepublikowanych pracach A. Turinga (związanych z popularną maszyną Turinga) (Paun, 2004). Teoria automatów skończonych została opracowana około dekady później, w oparciu o modelowanie neuronowe. Doprowadziło to ostatecznie do powstania dziedziny, która obecnie znana jest jako neural computing. Można to w zasadzie nazwać początkiem obliczeń inspirowanych biologią. Od tego czasu badano i rozwijano techniki takie jak GP, inteligencja roju, optymalizacja kolonii mrówek oraz obliczenia DNA, ponieważ natura wciąż nas inspiruje i wskazuje nam drogę do rozwiązania najbardziej złożonych problemów znanych człowiekowi.

GŁÓWNY CEL Niniejszy tekst przedstawia przede wszystkim podejście GP do sieci ad hoc. Najpierw przedstawiamy ogólne wprowadzenie do GP i wyjaśniamy koncepcje genów i chromosomów. Wyjaśniamy również stochastyczną naturę GP oraz proces mutacji i krzyżowania, aby zapewnić optymalne rozwiązanie problemu za pomocą podejścia GP. Następnie przedstawiamy algorytm klasteryzacji ważonej (WAG) podany przez Chatterjee, Das i Turgut, 2002, który jest używany do klasteryzacji węzłów w mobilnych sieciach ad-hoc, jako przykład tego podejścia. GP GP to popularna, inspirowana biologią metoda obliczeniowa. Koncepcje w algorytmach genetycznych są inspirowane samym zjawiskiem życia i ewolucji. Życie to problem, którego rozwiązanie obejmuje zachowanie tych, które posiadają wystarczająco silne cechy, aby przetrwać w środowisku, i odrzucenie pozostałych. Ten znakomity proces może dostarczyć rozwiązań złożonych problemów analitycznych oczekujących na najbardziej "dopasowany" wynik. Podstawy obejmują rolę chromosomów igenów. Chromosomy niosą geny, które zawierają parametry/cechy wymagające optymalizacji. Dlatego GP rozpoczyna się od deklaracji struktur danych, które tworzą cyfrowe chromosomy. Te cyfrowe chromosomy zawierają informacje genetyczne, gdzie każdy gen reprezentuje parametr do optymalizacji. Gen może być reprezentowany jako pojedynczy bit, który może być "1" (WŁ.) lub "0" (WYŁ.). Zatem chromosom jest sekwencją jedynek i zer, a parametr jest albo całkowicie obecny, albo całkowicie nieobecny. Inne abstrakcje mogłyby reprezentować obecność parametru na poziomach względnych. Na przykład gen można przedstawić za pomocą 5 bitów, gdzie wielkość liczby binarnej mówi o wielkości obecności parametru w zakresie od "0" (00000) do "31" (11111). Najpierw te cyfrowe chromosomy są tworzone za pomocą metod stochastycznych. Następnie ich dopasowanie jest testowane albo poprzez statyczne obliczanie dopasowania za pomocą jakiejś metody, albo dynamicznie poprzez modelowanie walk między chromosomami. Chromosomy o ustalonym poziomie dopasowania są zachowywane i mogą wytworzyć nowe pokolenie chromosomów. Można to osiągnąć poprzez rekombinację genetyczną, czyli produkcję nowych chromosomów z połączenia obecnych chromosomów, lub poprzez mutację, czyli produkcję nowych chromosomów poprzez losowe wprowadzanie zmian w obecnych chromosomach. Ten proces testowania dopasowania i tworzenia nowych pokoleń powtarza się, aż najlepiej dopasowane chromosomy zostaną uznane za wystarczająco zoptymalizowane do zadania, dla którego stworzono algorytm genetyczny. Proces ten opisano na rysunku



Algorytmy genetyczne zaczynają od procesu stochastycznego i prowadzą do zoptymalizowanego rozwiązania, co jest czasochłonne. Dlatego są one zazwyczaj wykorzystywane do rozwiązywania złożonych problemów. Jak wspomniał Ashby (1962), samoorganizacja jest jednym z takich złożonych problemów. Samoorganizacja to problem, w którym komponenty systemu wielokomponentowego osiągają (lub próbują osiągnąć) wspólny cel bez scentralizowanej lub rozproszonej kontroli. Organizacja odbywa się zazwyczaj poprzez zmianę bezpośredniego środowiska, które może być dostosowywane przez różne komponenty systemu, a tym samym wpływać na zachowanie tych komponentów. Jak wspomniano, "Samoorganizacja jest szczególnie ważna w sieciach ad-hoc ze względu na spontaniczną interakcję wielu heterogenicznych komponentów za pośrednictwem bezprzewodowych połączeń radiowych bez interakcji z człowiekiem" . Dressler (2006) podaje następującą listę możliwości samoorganizacji:

o Samonaprawianie: System powinien być w stanie wykrywać i naprawiać awarie spowodowane przeciążeniem, nieprawidłowym działaniem komponentów lub awarią systemu.
o Samokonfiguracja: System powinien być w stanie generować odpowiednie konfiguracje, w tym łączność, jakość usług itp., zgodnie z wymaganiami istniejącego scenariusza.
o Samozarządzanie: System powinien być w stanie utrzymywać urządzenia, a tym samym sieć, w zależności od ustawionych parametrów konfiguracyjnych.
o Samooptymalizacja: System powinien dokonywać optymalnego wyboru metod w zależności od zachowania systemu.
o Adaptacja: System powinien dynamicznie dostosowywać się do zmieniających się warunków otoczenia, np. zmiany położenia węzłów, zmiany liczby węzłów w sieci itd.

Algorytmy genetyczne są szeroko stosowane w robotyce, projektowaniu układów elektronicznych, przetwarzaniu języka naturalnego, teorii gier, wyszukiwaniu wielomodelowym, projektowaniu topologii sieci komputerowych i wielu innych zastosowaniach. W kontekście bezprzewodowych sieci ad-hoc, algorytmy genetyczne były wykorzystywane między innymi do rozwiązywania problemów z trasowaniem najkrótszej ścieżki , odkrywania ścieżek QoS , opracowywania strategii rozgłoszeniowych , routingu QoS . Dla zwięzłości przedstawiamy poniżej tylko jedno reprezentatywne zastosowanie algorytmów genetycznych do rozwiązywania problemów w sieciach ad-hoc.

Klastrowanie ważone z wykorzystaniem algorytmu genetycznego

Węzły w sieciach ad-hoc są czasami grupowane w różne klastry, z których każdy ma swoją głowicę. Klastrowanie ma na celu wprowadzenie pewnego rodzaju organizacji w sieciach ad-hoc. Prowadzi to do lepszej skalowalności sieci, a co za tym idzie, lepszego wykorzystania zasobów w większych sieciach. Za tworzenie i utrzymanie klastrów w sieciach ad-hoc odpowiada osoba zarządzająca klastrem. Zaproponowano kilka mechanizmów klastrowania dla sieci ad-hoc, takich jak Lowest-ID , Highest Connectivity , Distributed Mobility-Adaptive Clustering (DMAC) , Distributed Dynamic Clustering Algorithm oraz Weight-Based Adaptive Clustering Algorithm (WBACA) . Algorytm klastrowania ważonego (WCA) to popularny algorytm klastrowania, który wybiera węzeł-czołowy klastra na podstawie mobilności węzła, mocy baterii, łączności, odległości od sąsiada i stopnia łączności. Każdemu parametrowi przypisuje się wagę, a następnie oblicza się łączną ważoną metrykę Wv, jak pokazano w równaniu (1) ). Z pewnymi ograniczeniami, węzły o minimalnej wartości Wv są wybierane jako węzeł-czołowy klastra.



W równaniu (1),

Δ_v oznacza różnicę między optymalną a rzeczywistą łącznością węzła.
D_voznacza sumę odległości od wszystkich sąsiednich węzłów.
M_v to średnia krocząca prędkości węzła.
P_vv oznacza czas, w którym węzeł pełnił funkcję głowicy klastra.
w₁, w₂, w₃ i w₄ to względne wagi przypisane różnym parametrom. Należy zauważyć, że :

w₁ + w₂ + w₃ + w₄ = 1

Projektanci WCA przedstawili podejście oparte na algorytmie genetycznym. Rozwiązania suboptymalne są mapowane na chromosomy i podawane jako dane wejściowe w celu uzyskania najlepszych rozwiązań za pomocą technik genetycznych. Prowadzi to do lepszej wydajności i bardziej równomiernego podziału obciążenia. Podstawowe elementy składowe algorytmu przedstawiono poniżej:

Populacja początkowa: Rozwiązanie kandydujące, które działa jak chromosom, można przedstawić w sposób pokazany na rysunku 6. Ten początkowy zbiór populacji jest generowany losowo poprzez rozmieszczenie węzłów w ciągach, a następnie przechodzenie przez ten ciąg. Węzeł, który nie jest głowicą klastra i nie jest sąsiadem głowicy klastra (a zatem częścią istniejącego klastra), jest wybierany jako głowica klastra, jeśli ma mniej niż ? (z góry zdefiniowaną stałą) sąsiadów. δ jest dobierane tak, aby zapobiec przeciążeniu głowic klastra przez głowicę klastra z większą liczbą sąsiadów niż optymalny.

Cel funkcji dopasowania: Wartość dopasowania chromosomu można obliczyć jako sumę wartości Wv zawartych genów. Analizowane są wszystkie węzły obecne w genie [1]. Jeśli węzeł nie jest głową klastra ani członkiem głowy klastra i ma stopień węzła mniejszy niż MAX_DEGREE, jest dodawany do listy głowic klastra, a jego wartość Wv jest dodawana do sumy całkowitej. W przypadku pozostałych węzłów w sieci, jeśli węzeł nie jest głową klastra ani członkiem innej głowy klastra, jego wartość Wv jest dodawana do sumy, a węzeł jest dodawany do listy głowic klastra. Im mniejsza suma wartości Wv genów, tym wyższa wartość dopasowania chromosomu.
Krzyżowanie: Współczynnik krzyżowania wynosi 80%. Autorzy zastosowali technikę o nazwie X_Over1 jako technikę krzyżowania do implementacji genetycznej.
Mutacja: Mutacja wprowadza losowość do przestrzeni rozwiązań. Jeśli tempo mutacji jest niskie, istnieje ryzyko, że rozwiązanie zbiegnie się do nieoptymalnej przestrzeni rozwiązań. Dlatego mutacja jest bardzo ważnym etapem w obliczeniach genetycznych. W przedstawionym algorytmie twórcy zastosowali zamianę w procesie mutacji. Dwa geny chromosomuzostały losowo wybrane i zamienione. Zastosowana częstość mutacji wynosi 10%.
Kryteria selekcji: Jak wspomniano wcześniej, chromosomy o niższych wartościach Wv są uważane za lepiej dopasowane. Do selekcji, zgodnie z wartościami dopasowania tych chromosomów, stosuje się metodę koła ruletki.
Elityzm: Jeśli nowe pokolenie ma wartość dopasowania lepszą niż najlepsza wartość dopasowania poprzedniego pokolenia, wówczas najlepsze rozwiązanie jest zastępowane przez nowe pokolenie. Ponieważ najlepsze rozwiązania danego pokolenia są zastępowane, ten krok pomaga uniknąć lokalnych maksimów przestrzeni rozwiązań i zmierzać w kierunku maksimów globalnych.
Zastępowanie: Ta metoda polega na tym, że podczas zastępowania najlepsze rozwiązanie danego pokolenia jest dołączane do zbioru rozwiązań następnego pokolenia. Ten krok pomaga zachować najlepsze rozwiązanie podczas operacji genetycznych.
Wykorzystując te funkcje budowania, przedstawiono algorytm genetyczny dla algorytmu klastrowania ważonego. Algorytm ten przedstawiono na rysunku



WNIOSKI

Niniejszy artykuł przedstawia przegląd ewolucyjnego podejścia obliczeniowego wykorzystującego algorytmy GP oraz ich zastosowanie w bezprzewodowych sieciach ad-hoc, które są obecnie "gorącymi" tematami w społeczności badawczej informatyki i sieci. Celem napisania tego artykułu było pokazanie, jak można "połączyć" koncepcje algorytmów GP z sieciami ad-hoc, aby uzyskać interesujące wyniki. W szczególności przeanalizowano algorytm WCA , który wykorzystuje algorytmy GP do klastrowania węzłów w sieciach ad-hoc.

WSTĘP

Znaczenie napojów sokowych w codziennych nawykach żywieniowych sprawia, że uwierzytelnianie soków staje się istotną kwestią, na przykład w celu uniknięcia oszustw. Skuteczny model klasyfikacji powinien uwzględniać dwa ważne filary kontroli jakości napojów na bazie soków: monitorowanie ilości soku oraz monitorowanie ilości (i charakteru) innych substancji dodawanych do napojów. W szczególności dodawanie cukru jest powszechnym i prostym zafałszowaniem, choć trudnym do scharakteryzowania. Inne metody fałszowania, stosowane samodzielnie lub w połączeniu, obejmują dodawanie wody, płukania miąższu, tańszych soków, barwników i innych niezadeklarowanych dodatków (mających naśladować profile składu czystych soków).

SELEKCJA ZMIENNYCH ZA POMOCĄ TECHNIK EWOLUCYJNYCH

W niniejszejsekcji przedstawiono kilka podejść do problemu selekcji zmiennych. Wszystkie z nich oparte są na technikach ewolucyjnych. Można je podzielić na dwie grupy. Pierwsza grupa technik opiera się na odmiennych kodyfikacjach populacji tradycyjnego algorytmu genetycznego (GA) i odmiennych specyfikacjach funkcji ewaluacyjnej. Druga grupa przedstawia modyfikację tradycyjnego algorytmu genetycznego w celu poprawy zdolności generalizacji poprzez dodanie nowej populacji i podejścia opartego na ewolucji podgatunków w populację genetyczną.

TŁO

Do rozwiązywania problemów z uwierzytelnianiem wykorzystano szereg technik analitycznych. Należą do nich wysokosprawna chromatografia cieczowa , chromatografia gazowa oraz metody izotopowe . Niestety, są one drogie i powolne. Spektrometria w podczerwieni (IR) to szybka i wygodna technika przeprowadzania badań przesiewowych w celu oceny zawartości czystego soku w napojach komercyjnych. Zainteresowanie budzi opracowanie, na podstawie danych spektroskopowych, metod klasyfikacji, które umożliwiłyby określenie ilości naturalnego soku zawartego w próbce. Jednak informacje zebrane z analiz IR mają pewne niejasne cechy (szum losowy, niejasne przypisanie chemiczne itp.), dlatego chemicy analityczni zazwyczaj stosują techniki takie jak sztuczne sieci neuronowe (ANN) lub opracowują doraźne modele klasyfikacji. Poprzednie badania wykazały, że ANN klasyfikuje napoje z sokiem jabłkowym według stężenia zawartego w nich naturalnego soku i że ANN ma przewagę nad klasycznymi metodami statystycznymi, takimi jak solidne modele i łatwość zastosowania tej metodologii w laboratoriach badawczo-rozwojowych. Niestety, duża liczba zmiennych uzyskanych ze spektrometrii IR sprawia, że ANN są czasochłonne w trakcie uczenia i, co najważniejsze, bardzo utrudnia ustalenie relacji między tymi zmiennymi a wiedzą analityczną. Zastosowano kilka podejść w celu zmniejszenia liczby zmiennych do małego podzbioru, który powinien zachować możliwości klasyfikacyjne całego zbioru danych. Dzięki temu proces szkolenia sieci neuronowej i interpretacja wyników uległyby znacznej poprawie. Ponadto, wcześniejszy wybór zmiennych przyniósłby inne korzyści: redukcję kosztów (jeśli model klasyfikacji wymaga zmniejszonego zestawu danych, czas potrzebny na ich uzyskanie będzie krótszy); zwiększoną wydajność (jeśli system przetwarza mniej informacji, czas potrzebny na ich przetworzenie będzie krótszy); poprawę zrozumienia (jeśli dwa modele rozwiązują to samo zadanie, ale jeden z nich wykorzystuje mniej informacji, zostanie to dokładniej zinterpretowane. Zatem im prostszy model, tym łatwiejsza ekstrakcja wiedzy, a im łatwiejsze zrozumienie, tym łatwiejsza walidacja). Ponadto udowodniono, że analiza danych IR wiązała się z problemem wysoce multimodalnym, ponieważ wiele kombinacji zmiennych (uzyskanych przy użyciu innejmetody) prowadziło do podobnych wyników po sklasyfikowaniu próbek. ALGORYTMY GENETYCZNE

ALGORYTMY GENETYCZNE to rekurencyjny i stochastyczny proces, który działa z grupą potencjalnych rozwiązań problemu, znanego jako populacja genetyczna, w oparciu o jedną z zasad Darwina: przetrwanie najlepszych osobników (Darwin, 1859). W skrócie, algorytm genetyczny działa w następujący sposób. Początkowo populacja rozwiązań jest generowana losowo, a rozwiązania ewoluują w sposób ciągły po kolejnych etapach krzyżowania i mutacji. Każdy osobnik w populacji ma przypisaną wartość, która kwantyfikuje jego użyteczność (dopasowanie lub dopasowanie), zgodnie z jego adekwatnością do rozwiązania problemu. Wartość ta musi zostać uzyskana dla każdego potencjalnego rozwiązania i stanowi informację ilościową, której algorytm ewolucyjny użyje do kierowania poszukiwaniami. Proces będzie kontynuowany do momentu osiągnięcia z góry określonego kryterium zatrzymania. Może to być określony błąd progowy rozwiązania lub określona liczba pokoleń (populacji). Dlatego wdrożenie algorytmu genetycznego będzie wymagało różnych podstawowych kroków: kodyfikacji problemu, która skutkuje strukturą populacji, inicjalizacji pierwszej populacji, zdefiniowania funkcji dopasowania w celu oceny, jak dobrze każdy osobnik nadaje się do rozwiązania problemu, a wreszcie cyklicznej procedury reprodukcji i zastępowań .

OPIS DANYCH

W niniejszym praktycznym zastosowaniu zakres widmowy mierzony spektrometrią IR (liczby falowe od 1250 cm-1 do 900 cm-1) dostarczył 176 absorbancji (mierzących absorpcję światła) . Głównym celem zastosowania było przewidywanie ilości czystego soku w próbce na podstawie wartości absorbancji uzyskanych z pomiarów IR. Jednak ilość danych uzyskanych dla próbki za pomocą spektrometrii IR jest ogromna, dlatego bezpośrednie zastosowanie metod matematycznych i/lub obliczeniowych (choć możliwe) wymaga dużo czasu. W związku z tym ważne jest ustalenie, czy wszystkie surowe dane dostarczają istotnych informacji do rozróżnienia próbek. W związku z tym problem stanowił odpowiedni przypadek zastosowania technik selekcji zmiennych. Przed przystąpieniem do selekcji zmiennych wymagane było skonstruowanie zestawów danych zarówno do opracowania modelu, jak i jego walidacji. W związku z tym w laboratorium przygotowano próbki o różnych ilościach czystego soku jabłkowego. Ponadto przeanalizowano 23 napoje na bazie soku jabłkowego sprzedawane w Hiszpanii (jako dane wejściowe wykorzystano deklarowaną ilość soku wydrukowaną na etykietach). Próbki podzielono na 2 zakresy: próbki zawierające mniej niż 20% czystego soku oraz próbki zawierające ponad 20% czystego soku jabłkowego .



Dla wszystkich próbek uzyskano widma IR. Dane te podzielono na dwa zestawy danych w celu wyodrębnienia reguł (uczenie sieci neuronowej) i ich walidacji. Próbki komercyjne wykorzystano do dalszego sprawdzenia wydajności modelu. Warto zauważyć, że jeśli przewidywana wartość nie zgadza się z wartością podaną na etykietach produktów komercyjnych, może to być spowodowane albo błędnym działaniem modelu (błędem klasyfikacji), albo nieprawidłowym oznakowaniem napoju komercyjnego.

Test klasyfikacyjny z uwzględnieniem wszystkich zmiennych pierwotnych

Pierwszy test obejmował wszystkie zmienne podane za pomocą spektroskopii IR. Dedykowana sieć neuronowa wykorzystała wszystkie absorbancje danych treningowych do uzyskania modelu klasyfikacyjnego. Później wyniki klasyfikacji uzyskane za pomocą tego modelu zostaną wykorzystane jako punkt odniesienia do porównania skuteczności propozycji dla tych samych danych. Zastosowano również różne parametryczne techniki klasyfikacji (PLS, SIMCA, krzywe potencjału itp.) , dając bardzo podobne wyniki. Najlepsze wyniki uzyskano jednak przy użyciu ANN, co będzie bardzo przydatne w rozwiązaniu problemu wyboru zmiennych z wykorzystaniem GA z funkcjami dopasowania opartymi na ANN. Dokładność metody referencyjnej przedstawiono w tabeli 2.



Wyczerpujące badanie wyników różnych modeli klasyfikacji pozwoliło nam stwierdzić, że zbiór próbek o niskim (2-20%) udziale soku był znacznie bardziej złożony i trudniejszy do sklasyfikowania niż próbki o wyższym udziale (25-100%). Rzeczywiście, liczba błędów była zazwyczaj wyższa w zakresie 2-20%, zarówno w kalibracji, jak i walidacji. Klasyfikacja próbek handlowych była dość zgodna z zawartością procentową soku podaną na etykietach, ale w przypadku konkretnej próbki, po jej szczegółowym zbadaniu, zaobserwowano, że jej widmo różniło się nieznacznie od typowego. Sugerowało to, że sok zawierał nietypowo dużą ilość dodanego cukru (cukrów).

PODEJŚCIA DO SELEKCJI ZMIENNYCH

W celu optymalizacji klasyfikacji sieci neuronowych (ANN) przeprowadzono procesy selekcji zmiennych. Najpierw krótko opisano dwa proste podejścia: wyszukiwanie przycięte i wyszukiwanie stałe. Oba podejścia opierają się na tradycyjnym algorytmie genetycznym i oba wykorzystują ANN do oceny dopasowania. Jak pokażą wyniki, obie techniki oferują dobre rozwiązania, ale wiążą się z wspólnym problemem: wykonanie każdej z metod dostarcza jedynie rozwiązanie (odrzucając wszelkie inne możliwe rozwiązanie optymalne). Problem ten rozwiązano za pomocą dwóch bardziej zaawansowanych podejść opisanych w kolejnych sekcjach. Niezależnie od podejścia do selekcji zmiennych, algorytm genetyczny (AN) będzie kierował wyszukiwaniem, oceniając możliwości predykcyjne każdego modelu ANN opracowanego z wykorzystaniem różnych zestawów zmiennych IR. Problem, który należy rozwiązać, polega na znalezieniu niewielkiego zestawu zmiennych IR, który w połączeniu z modelem ANN prawidłowo klasyfikuje napoje na bazie soku jabłkowego (zgodnie z ilością zawartego w nich czystego soku jabłkowego). Za każdym razem, gdy proponowany jest podzbiór zmiennych IR, powiązane wartości absorbancji są wykorzystywane jako wzorce wejściowe dla ANN. Zatem sieć neuronowa będzie uwzględniać tyle samo elementów przetwarzania wejściowego (PE), co zmiennych. Warstwa wyjściowa ma jeden PE na kategorię (6 dla dolnego zakresu i 5 dla górnego). Po kilku wcześniejszych próbach z uwzględnieniem kilku warstw ukrytych (od 1 do 4), każda z różnymi PE (od 1 do 50), ustalono kompromis między końcowym poziomem sprawności osiągniętym przez sieć neuronową a czasem potrzebnym na jej trenowanie. Kompromis ten był niezbędny, ponieważ chociaż lepsze wyniki uzyskano z większą liczbą warstw ukrytych, czas potrzebny na trenowanie był również znacznie dłuższy. Następnie postanowiono nie trenować sieci w sposób ekstensywny, lecz uzyskać dobre przybliżenie jej rzeczywistej wydajności i wyjaśnić, czy zmienne wejściowe rzeczywiście nadają się do dokładnej klasyfikacji próbek. Celem jest określenie, które rozwiązania spośród rozwiązań dostarczonych przez algorytm genetyczny stanowią dobre punkty wyjścia do przeprowadzenia bardziej wyczerpującego treningu. Dlatego wystarczyłoby wydłużyć uczenie sieci neuronowej do punktu, w którym zaczyna się ona zbieżność. W tym konkretnym przypadku zbieżność rozpoczęła się po 800 cyklach; Aby to uzasadnić, wykonano 1000 iteracji. Następnie każde z najbardziej obiecujących rozwiązań jest wykorzystywane jako dane wejściowe do zewnętrznej sieci neuronowej (SSN), która ma dostarczyć ostatecznych wyników klasyfikacji.

Wyszukiwanie z przyciętymi fragmentami

To podejście rozpoczyna się od rozważenia wszystkich zmiennych, z których grupy zmiennych są stopniowo odrzucane. Algorytm genetyczny będzie stopniowo zmniejszał liczbę zmiennych charakteryzujących obiekty, aż do uzyskania optymalnego podzbioru, który pozwoli na ogólnie satysfakcjonującą klasyfikację. Służy to do klasyfikowania próbek, a wyniki służą do określenia, jak istotne były odrzucone liczby falowe dla klasyfikacji. Proces ten można kontynuować, dopóki wyniki klasyfikacji są równe lub przynajmniej podobne do wyników uzyskanych przy użyciu całego zestawu zmiennych. Dlatego algorytm genetyczny określa, ile i jakie liczby falowe zostaną wybrane do klasyfikacji. W tym podejściu każdy osobnik w populacji genetycznej jest opisany przez n genów, z których każdy reprezentuje jedną zmienną. W kodowaniu binarnym każdy gen może mieć wartość 0 lub 1, wskazując, czy gen jest aktywny, czy nie, a zatem, czy zmienna powinna zostać uwzględniona w klasyfikacji. Funkcja ewaluacyjna musi kierować procesem przycinania, aby uzyskać osobniki o małej liczbie zmiennych. Aby to osiągnąć, funkcja powinna pomagać osobnikom, które oprócz dokładnej klasyfikacji, wykorzystują mniejszą liczbę zmiennych. W tym konkretnym przypadku zdefiniowano współczynnik proporcjonalny do odsetka aktywnych genów, aby pomnożyć MSE uzyskany przez ANN, tak aby osobniki z mniej aktywnymi genami - i o podobnej skuteczności klasyfikacji - miały wyższe dopasowanie, a w konsekwencji większe prawdopodobieństwo przeżycia. Tabela 3 przedstawia wyniki kilku przebiegów metody "Przyciętego wyszukiwania".



Warto zauważyć, że każde rozwiązanie zostało wyodrębnione z innego wykonania i że w ramach tego samego wykonania tylko jedno rozwiązanie zapewniło prawidłowe wskaźniki klasyfikacji. Jak można zauważyć, wyniki klasyfikacji były bardzo podobne, chociaż zmienne użyte do przeprowadzenia klasyfikacji były różne. Uzyskane modele ANN są nieco gorsze niż te uzyskane przy użyciu 176 liczb falowych, chociaż możliwości generalizacji najlepszego modelu ANN były całkiem zadowalające, ponieważ wystąpił tylko jeden błąd podczas klasyfikacji napojów komercyjnych.

Stałe wyszukiwanie

To podejście wykorzystuje rzeczywistą kodyfikację w chromosomie osobników genetycznych. Populacja genetyczna składa się z osobników z n genami, gdzie n to liczba liczb falowych uznawanych za wystarczające do klasyfikacji według pewnego zewnętrznego kryterium. Każdy gen reprezentuje jedną ze 176 liczb falowych uwzględnionych w widmach IR. Algorytm genetyczny znajdzie podzbiory n zmiennych, dające najlepsze modele klasyfikacyjne. Liczba zmiennych jest z góry zdefiniowana w genotypie. Ponieważ ostateczna liczba zmiennych musi zostać ustalona z góry, potrzebne jest zewnętrzne kryterium. Aby uprościć porównywanie wyników, ostateczną liczbę zmiennych zdefiniowano na podstawie minimalnej liczby głównych składowych, które mogą opisać nasz zbiór danych - były to dwie. Ponieważ liczba liczb falowych pozostaje stała w trakcie procesu selekcji, to podejście definiuje dopasowanie genetyczne każdego osobnika jako średni kwadratowy błąd osiągnięty przez ANN na końcu procesu uczenia.Tabela 4 przedstawia wyniki kilku przebiegów metody "Purned Search".



Należy ponownie zauważyć, że każdy przebieg dostarcza tylko rozwiązanie. Problem polegał na tym, że osobniki genetyczne zawierają tylko dwa geny. W związku z tym, każdy operator krzyżowania wykorzysta unikalny dostępny punkt krzyżowania (między genami), a tylko połowa informacji od każdego rodzica zostanie przekazana jego potomstwu. To przekształca metodę "Fixed Search" w "losowe przeszukiwanie", gdy chromosom składa się tylko z dwóch genów.

Hybrydowy algorytm genetyczny dla dwóch populacji

Główną wadą podejść niemultimodalnych jest to, że odrzucają one lokalne rozwiązania optymalne, ponieważ preferowane jest rozwiązanie ostateczne lub globalne. Istnieją jednak sytuacje, w których ostateczny model musi zostać wyodrębniony po przeanalizowaniu różnych podobnych rozwiązań tego samego problemu. Na przykład, po przeanalizowaniu różnych rozwiązań uzyskanych w wyniku jednego wykonania zadania klasyfikacyjnego z wykorzystaniem hybrydowego algorytmu genetycznego dla dwóch populacji , uzyskano trzy trafne (i podobne) modele



Co więcej, wyniki były wyraźnie lepsze od tych uzyskanych przy użyciu poprzednich alternatyw. Co jednak najważniejsze, zaobserwowano, że rozwiązania koncentrowały się wzdłuż określonych obszarów widmowych (wokół liczby falowej 88). Nie byłoby to możliwe przy użyciu poprzednich podejść. To podejście zostanie szczegółowo omówione w dedykowanym rozdziale (Znajdowanie wielu rozwiązań za pomocą algorytmu genetycznego w problemach multimodalnych) i nie będzie tu przedstawiane więcej szczegółów.

PRZYSZŁE TRENDY

Kolejnym naturalnym etapem powinno być rozważenie podejść multimodalnych. Obliczenia ewolucyjne dostarczają użytecznych narzędzi, takich jak współdzielenie sprawności, analiza zatłoczenia… które należy porównać z hybrydowym podejściem dwóch populacji. Konieczne są badania w celu wdrożenia kryteriów umożliwiających zatrzymanie algorytmu genetycznego po znalezieniu zadowalająco małej liczby zmiennych. Inną odpowiednią opcją powinno być uwzględnienie w systemie większej ilości informacji naukowych, które pokierują wyszukiwaniem. Na przykład, użytkownik końcowy mógłby dostarczyć opis idealnego rozwiązania pod względem wydajności, kosztów akwizycji danych, prostoty itp. Wszystkie te parametry mogą być wykorzystane jako cele w wielokryterialnym algorytmie genetycznym, którego celem jest zapewnienie najlepszego podzbioru zmiennych spełniającego wszystkie wymagania.

WNIOSKI

Można wyciągnąć kilka wniosków dotyczących zadań selekcji zmiennych: Po pierwsze, zadowalające wyniki klasyfikacji można uzyskać ze zredukowanych zestawów zmiennych wyodrębnionych za pomocą zupełnie różnych technik, opartych na połączeniu algorytmów genetycznych i sieci neuronowych (SSN). Najlepsze rezultaty uzyskano stosując multimodalną GA (hybrydowe podejście dwupopulacyjne), zgodnie z oczekiwaniami, ze względu na jej zdolność do utrzymania jednorodnego rozmieszczenia osobników genetycznych w przestrzeni poszukiwań. Taka różnorodność nie tylko sprzyja pojawianiu się optymalnych rozwiązań, ale także zapobiega zatrzymaniu się poszukiwań na minimum lokalnym. Ta opcja nie dostarcza jedynie rozwiązania, ale grupę rozwiązań o podobnej sprawności. Pozwala to naukowcom wybrać rozwiązanie o solidnym tle chemicznym i uzyskać dodatkowe informacje.

WSTĘP

Sztuczne sieci neuronowe (ANN) to modele obliczeniowe, luźno inspirowane biologicznymi sieciami neuronowymi, składające się z połączonych grup sztucznych neuronów, które przetwarzają informacje z wykorzystaniem podejścia koneksjonistycznego. Sieci neuronowe są szeroko stosowane w takich zagadnieniach, jak rozpoznawanie wzorców, klasyfikacja i analiza szeregów czasowych. Sukces zastosowania ANN zazwyczaj wymaga dużej liczby eksperymentów. Ponadto, kilka parametrów ANN może wpływać na dokładność rozwiązań. Pewien rodzaj ewoluujących systemów, a mianowicie systemy neurogenetyczne, stał się bardzo ważnym tematem badawczym w projektowaniu ANN. Tworzą one tzw. Ewolucyjne Sztuczne Sieci Neuronowe (EANN), czyli inspirowane biologicznie modele obliczeniowe, które wykorzystują algorytmy ewolucyjne (EA) w połączeniu z ANN. Algorytmy ewolucyjne i najnowocześniejsze rozwiązania projektowe sieci neuronowych (EANN) zostały po raz pierwszy przedstawione w przeglądzie kamieni milowych przez Xin Yao (1999), a ostatnio przez Abrahama (2004), Cantu-Paza i Kamatha (2005), a następnie przez Castellaniego (2006). Celem niniejszego artykułu jest przedstawienie głównych technik ewolucyjnych wykorzystywanych do optymalizacji projektu sieci neuronowych (ANN), omówienie zagadnień związanych z projektowaniem sieci neuronowych i powiązanych z nimi problemów, a następnie omówienie najnowszych osiągnięć w dziedzinie sieci neuronowych, opisanych w literaturze. Na koniec przedstawiono krótkie podsumowanie wraz z kilkoma uwagami końcowymi.

PROJEKTOWANIE SZTUCZNYCH SIECI NEURONOWYCH

W projektowaniu sieci neuronowych (SSN), ich skuteczne zastosowanie zazwyczaj wymaga wielu eksperymentów. Należy ustawić wiele parametrów. Niektóre z nich obejmują typ SSN, inne liczbę warstw i węzłów definiujących architekturę oraz wagi połączeń. Również dane treningowe są ważnym czynnikiem i należy poświęcić wiele uwagi danym testowym, aby upewnić się, że sieć będzie poprawnie generalizować dane, na których nie była trenowana. Selekcja cech, projektowanie struktury i trening wagowy można traktować jako trzy problemy wyszukiwania odpowiednio w przestrzeni dyskretnej podzbiorów atrybutów danych, przestrzeni dyskretnej możliwych konfiguracji SSN oraz przestrzeni ciągłej parametrów SSN. Projektowanie architektury ma kluczowe znaczenie dla skutecznego zastosowania SSN, ponieważ ma znaczący wpływ na ich możliwości przetwarzania informacji. Rzeczywiście, biorąc pod uwagę zadanie uczenia się, sieć neuronowa z niewielką liczbą połączeń i węzłów liniowych może w ogóle nie być w stanie go wykonać, podczas gdy sieć neuronowa z dużą liczbą połączeń i węzłów nieliniowych może nadmiernie dopasowywać szum w danych treningowych i nie mieć możliwości generalizacji. Głównym problemem jest brak systematycznego sposobu automatycznego zaprojektowania optymalnej architektury dla danego zadania. Zaproponowano kilka metod przezwyciężenia tych niedociągnięć. Niniejszy rozdział koncentruje się na jednej z nich, a mianowicie sieciach neuronowych (EANN). Jedną z charakterystycznych cech sieci neuronowych (EANN) jest ich zdolność adaptacji do dynamicznego środowiska. Sieci neuronowe można traktować jako ogólne ramy dla systemów adaptacyjnych, tj. systemów, które mogą odpowiednio zmieniać swoją architekturę i reguły uczenia się bez ingerencji człowieka. W celu poprawy wydajności algorytmów ewolucyjnych (EA), w literaturze zaproponowano różne schematy selekcji i operatory genetyczne. Ten rodzaj ewolucyjnego uczenia się sieci neuronowych został również wprowadzony w celu ograniczenia, a jeśli to możliwe, uniknięcia problemów tradycyjnych technik spadku gradientu, takich jak propagacja wsteczna (BP), które polegają na wychwytywaniu lokalnych minimów. Wiadomo, że algorytmy ewolucyjne (EA) są mało wrażliwe na początkowe warunki uczenia, ponieważ są metodami optymalizacji globalnej, podczas gdy algorytm gradientu prostego może znaleźć jedynie lokalne optimum w otoczeniu początkowego rozwiązania. Sieci neuronowe (EANN) stanowią rozwiązanie tych problemów i alternatywę dla kontroli złożoności sieci. Projektowanie sieci neuronowych (ANN) można traktować jako problem optymalizacji. Tettamanzi i Tomassini (2001) przedstawili dyskusję na temat systemów ewolucyjnych i ich interakcji z systemami neuronowymi i rozmytymi, a Cantu-Paz i Kamath (2005) opisali również empiryczne porównanie algorytmów ewolucyjnych i sieci neuronowych w problemach klasyfikacji.

EWOLUCYJNE SZTUCZNE SIECI NEURONOWE

Istnieje kilka podejść do ewolucji sieci neuronowych (EA), które zazwyczaj dzielą się na dwie szerokie kategorie: reprezentację ANN niezależną od problemu i reprezentację ANN zależną od problemu. Pierwsze opierają się na ogólnej reprezentacji, niezależnej od typu i struktury poszukiwanej ANN, i wymagają zdefiniowania schematu kodowania odpowiedniego dla algorytmów genetycznych (GA). Mogą one obejmować mapowanie między ANN a reprezentacją binarną, dbanie o dekodery lub algorytmy naprawcze, ale zadanie to zazwyczaj nie jest łatwe. Drugie to ANN, w których reprezentacja chromosomów jest określoną strukturą danych, która naturalnie mapuje się na ANN, do której stosuje się odpowiednie operatory genetyczne. ANN są wykorzystywane do wykonywania różnych zadań, takich jak trenowanie wag połączeń, projektowanie architektury, adaptacja reguł uczenia się, wybór cech wejściowych, inicjalizacja wag połączeń, ekstrakcja reguł z ANN itp. Trzy z nich są uważane za najpopularniejsze na następujących poziomach:

o Wagi połączeń koncentrują się wyłącznie na optymalizacji wag, zakładając, że architektura sieci jest dana. Ewolucja wag wprowadza adaptacyjne i globalne podejście do uczenia, szczególnie w paradygmacie uczenia się przez wzmacnianie i rekurencyjnego uczenia sieci, gdzie algorytmy uczenia oparte na gradiencie często napotykają duże trudności.

o Reguły uczenia się można postrzegać jako proces "uczenia się, jak się uczyć" w sieciach neuronowych (SN), w którym adaptacja reguł uczenia się jest osiągana poprzez ewolucję. Można je również postrzegać jako adaptacyjny proces automatycznego odkrywania nowych reguł uczenia się.

o Architektura umożliwia sieciom neuronowym dostosowywanie swoich topologii do różnych zadań bez ingerencji człowieka. Zapewnia również podejście do automatycznego projektowania sieci neuronowych, ponieważ zarówno wagi, jak i struktury mogą podlegać ewolucji. W tym przypadku można dokonać dalszego podziału, definiując "czystą" ewolucję architektury i jednoczesną ewolucję zarówno architektury, jak i wag.

Inne podejścia uwzględniają ewolucję funkcji przejścia sieci neuronowej (SN) i selekcję cech wejściowych, ale zazwyczaj stosuje się je w połączeniu z jedną z trzech powyższych metod w celu uzyskania lepszych wyników. Wykorzystanie uczenia ewolucyjnego w projektowaniu sieci neuronowych ma zaledwie dwie dekady. W tych latach wykonano jednak znaczną pracę, której główne wyniki przedstawiono poniżej.

Optymalizacja wag

Ewolucję wag można uznać za alternatywny algorytm uczenia. Główną motywacją do stosowania technik ewolucyjnych zamiast tradycyjnych technik spadku gradientowego, takich jak BP, jak donoszą Rumelhart i inni (1986), jest unikanie pułapek w minimach lokalnych i wymóg różniczkowalności funkcji aktywacji. Z tego powodu, zamiast dostosowywać wagi wyłącznie na podstawie lokalnej poprawy, algorytmy ewolucyjne ewoluują wagi w oparciu o dopasowanie całej sieci. Niektóre podejścia wykorzystują algorytmy genetyczne z rzeczywistymi kodowaniami dla odchyleń i wag, jak w pracy przedstawionej przez Montanę i Davisa (1989); inne początkowo wykorzystywały binarne kodowanie wag, a następnie zaimplementowały zmodyfikowaną wersję z rzeczywistymi kodowaniami, jak Whitley i inni (1990). Mordaunt i Zalzala (2002) zaimplementowali reprezentację liczb rzeczywistych do ewolucyjnych wag, analizując ewolucję z mutacjami i krzyżowaniem wielopunktowym, natomiast Seiffert (2001) opisał podejście polegające na całkowitym zastąpieniu tradycyjnego algorytmu spadku gradientu algorytmem genetycznym w fazie uczenia. Często podczas stosowania algorytmów genetycznych mogą wystąpić pewne problemy, na przykład przedwczesna konwergencja i stagnacja rozwiązania, jak donosił Goldberg (1992). Aby rozwiązać ten problem, Yang i in. (2002) zaproponowali ulepszony algorytm, w którym zaimplementowano algorytm genetyczny oparty na strategii stabilności ewolucyjnej, aby utrzymać równowagę między różnorodnością populacji a szybkością konwergencji podczas ewolucji. Niedawno Pai (2004) zaproponował nową GA, w której zaimplementowano operator dziedziczenia genetycznego w celu określenia wag sieci EANN, bez uwzględniania operatorów mutacji, a jedynie dwupunktowego krzyżowania dla reprodukcji, stosując go do chromosomów dziesiętnych.

Optymalizacja reguł uczenia

W algorytmach uczenia nadzorowanego standardowa metoda BP jest najpopularniejszą metodą uczenia sieci wielowarstwowych. Projektowanie algorytmów uczenia, w szczególności reguł uczenia używanych do dostosowywania wag połączeń, zależy od rodzaju rozpatrywanej architektury sieci neuronowej. Zaproponowano kilka standardowych reguł uczenia, ale zaprojektowanie optymalnej reguły uczenia staje się bardzo trudne, gdy istnieje niewielka wcześniejsza wiedza na temat topologii sieci, co prowadzi do bardzo złożonej relacji między ewolucją a uczeniem. Podejście ewolucyjne staje się ważne w modelowaniu procesu twórczego, ponieważ nowo wyewoluowane reguły uczenia mogą radzić sobie ze złożonym i dynamicznym środowiskiem. Pierwszy rodzaj optymalizacji uwzględnia dostosowanie parametrów uczenia i można go postrzegać jako pierwszą próbę ewolucji reguł uczenia. Obejmują one parametry BP, takie jak tempo uczenia się i pęd, oraz parametry genetyczne, takie jak prawdopodobieństwo mutacji i krzyżowania. Merelo i inni (2002) przeprowadzili kilka prac, w których przedstawili kilka rozwiązań dla optymalnych parametrów uczenia się wielowarstwowych konkurencyjnych sieci neuronowych uczących się. Jednym z pierwszych badań dotyczących optymalizacji reguł uczenia się było badanie przeprowadzone przez Chalmersa (1990). Zauważył on również, że odkrywanie złożonych reguł uczenia się za pomocą algorytmów genetycznych nie jest łatwe ze względu na bardzo złożone kodowanie genetyczne, które sprawia, że przestrzeń poszukiwań jest duża i trudna do eksploracji, podczas gdy algorytmy genetyczne wykorzystują prostsze kodowanie, które dopuszcza znane reguły uczenia się, co powoduje, że wyszukiwanie jest bardzo stronnicze. Aby pokonać te ograniczenia, Chalmers zasugerował zastosowanie algorytmów genetycznych (GP), szczególnego rodzaju algorytmów genetycznych. Przeprowadzono wiele badań w tym kierunku, a niektóre z nich zostały opisane, wraz z nowym podejściem przedstawionym przez Poli i Radi (2002).

Optymalizacja architektury

Projektowanie optymalnej architektury można sformułować jako problem wyszukiwania w przestrzeni architektury, gdzie każdy punkt reprezentuje topologię sieci neuronowej (ANN). Jak zauważył Yao (1999), biorąc pod uwagę pewne kryteria wydajności (optymalności), np. minimalny błąd, szybkość uczenia się, niższą złożoność itp., dotyczące architektur, poziom wydajności wszystkich tych kryteriów tworzy powierzchnię w przestrzeni projektowania. W tym kierunku przeprowadzono kilka podejść. Podejście neuroewolucyjne zostało zaprezentowane przez Miikkulainena i Stanleya (2002) z wykorzystaniem topologii rozszerzających. Zostało ono zaprojektowane specjalnie po to, aby przewyższyć rozwiązania wykorzystujące zasadniczą metodę krzyżowania różnych topologii, chronić innowacje strukturalne za pomocą specjacji oraz stopniowo rozwijać się od minimalnej struktury . Inna praca przeprowadzona przez Wanga rozważała definicję optymalnej sieci opartej na połączeniu konstruowania i przycinania przez algorytmy genetyczne, podczas gdy ostatnio Bevilacqua przedstawił wielokryterialne podejście algorytmów genetycznych (GA) do optymalizacji poszukiwania optymalnej topologii, oparte na teorii schematów. Jedną z najważniejszych form oszustwa w optymalizacji struktury sieci neuronowych (SN) jest mapowanie typu wiele-do-jednego i jeden-do-wielu genotypów w przestrzeni reprezentacji na fenotypy w przestrzeni ewaluacji. Istnienie sieci funkcjonalnie równoważnych i o różnym kodowaniu sprawia, że ewolucja jest nieefektywna. Problem ten określa się mianem problemu konkurencyjnej konwencji. Inne ważne kwestie dotyczą reprezentacji i definicji algorytmu adaptacyjnego (EA). W fazie kodowania ważnym aspektem jest decyzja, ile informacji o architekturze powinno zostać zakodowanych w genotypie. Wydajność sieci neuronowych (SN) silnie zależy od ich topologii, uwzględniającej rozmiar i strukturę, a w konsekwencji jej definicja charakteryzuje cechy sieci, takie jak szybkość procesu uczenia się, precyzja uczenia, tolerancja na szum i zdolność generalizacji. Optymalizacja funkcji przejścia.Zaburzenia funkcji przejścia mogą zaczynać się od funkcji stałej, takiej jak liniowa, sigmoidalna lub gaussowska, i pozwalać algorytmowi genetycznemu na dostosowanie się do użytecznej kombinacji w zależności od sytuacji. Yao i Liu (1996) przeprowadzili pewne prace w celu zastosowania adaptacji funkcji przejścia w kolejnych pokoleniach, a Figueira i Poli (1999) z algorytmem GP ewoluującym funkcje. Aby ulepszyć rozwiązania, często ten rodzaj ewolucji przeprowadza się łącznie z innymi rodzajami optymalizacji sieci neuronowych, opisanymi w niniejszym dokumencie.

Selekcja danych wejściowych

Jednym z najważniejszych czynników wpływających na uczenie sieci neuronowych jest dostępność i integralność danych. Powinny one reprezentować wszystkie możliwe stany rozpatrywanego problemu i zawierać wystarczającą liczbę wzorców do zbudowania zbioru testowego i walidacyjnego.Spójność wszystkich danych musi być zagwarantowana, a dane treningowe muszą być reprezentatywne dla problemu, aby uniknąć nadmiernego dopasowania. Selekcję danych wejściowych można traktować jako problem wyszukiwania w przestrzeni dyskretnej podzbiorów atrybutów danych. Rozwiązanie wymaga usunięcia zbędnych, sprzecznych, nakładających się i redundantnych cech w celu maksymalizacji dokładności klasyfikatora, zwartości i możliwości uczenia się. Redukcję danych wejściowych zajęli się Reeves i Taylor (1998), którzy zastosowali algorytmy genetyczne do wyboru zbiorów treningowych dla pewnego rodzaju sieci neuronowych, oraz Castellani (2006), osadzając poszukiwanie optymalnego zestawu cech w fazie uczenia. Wspólna ewolucja architektury i wag Wady związane z indywidualną architekturą i wagami technik ewolucyjnych można przezwyciężyć dzięki podejściom uwzględniającym ich koniunkcję. Zaletą połączenia tych dwóch podstawowych elementów sieci neuronowej jest to, że w pełni funkcjonująca sieć może być ewoluowana bez ingerencji eksperta. W literaturze zaproponowano kilka metod, które ewoluują zarówno strukturę sieci, jak i wagi połączeń. Castillo i inni (1999) przedstawili metodę poszukiwania optymalnego zestawu wag, optymalnej topologii i parametrów uczenia z wykorzystaniem algorytmu genetycznego do ewolucji sieci oraz algorytmu uczenia maszynowego (BP) do trenowania sieci, podczas gdy Yao i inni zaimplementowali odpowiednio ewolucyjny system do ewoluowania sieci neuronowych z wyprzedzeniem oparty na programowaniu ewolucyjnym, a ostatnio nowatorski konstruktywny algorytm do trenowania kooperacyjnych zespołów sieci neuronowych. Azzini i Tettamanzi (2006) przedstawili neurogenetyczne podejście do wspólnej optymalizacji struktur i wag sieci, wykorzystujące algorytm uczenia maszynowego (BP) jako wyspecjalizowany dekoder, a Pedrajas zaproponował kooperatywną metodę koewolucyjną do projektowania sieci neuronowych (ANN).

Zagadnienia otwarte

W badaniach nad sieciami neuronowymi (EANN) wciąż istnieje kilka otwartych kwestii. W odniesieniu do wag połączeń, kluczowym aspektem jest to, że struktura musi być z góry określona, co stwarza pewne problemy, gdy taka topologia jest trudna do zdefiniowania. Również w ewolucji reguł uczenia się, projektowanie algorytmów szkoleniowych, w szczególności reguł uczenia się, zależy od rodzaju architektury sieci. Dlatego projektowanie takich reguł może stać się bardzo trudne, gdy istnieje niewielka wiedza wstępna na temat topologii sieci, co powoduje złożoną relację między ewolucją a uczeniem się. Ewolucja architektury ma istotny wpływ na ewolucję sieci neuronowych, a ewolucja czystej architektury stwarza trudności w dokładnej ocenie dopasowania. Jednoczesna ewolucja architektury i wag jest jedną z najciekawszych technik ewolucyjnych sieci neuronowych i obecnie stanowi użyteczne rozwiązania w projektowaniu sieci neuronowych. Prowadzone są różne prace w tych kierunkach, które nadal stanowią otwarte kwestie. Niektóre z nich dotyczą zastosowania kooperatywnych lub konkurencyjnych podejść koewolucyjnych, inne zaś projektowania zespołów sieci neuronowych.

WNIOSKI

Niniejsza praca przedstawia przegląd stanu wiedzy w dziedzinie systemów ewolucyjnych badanych w ostatnich dekadach i prezentowanych w literaturze. W szczególności praca koncentruje się na zastosowaniu algorytmów ewolucyjnych do optymalizacji projektowania sieci neuronowych. Zaprezentowano kilka podejść do ewolucji sieci neuronowych wraz z kilkoma powiązanymi pracami, a dla każdej metody przedstawiono najważniejsze cechy wraz z ich głównymi zaletami i wadami.

WSTĘP

E-learning i wpływ nowych technologii na współczesne życie to niezwykle istotny obszar edukacji. Nie można ignorować wyzwania, jakie technologia stawia konwencjonalnym wzorcom uczenia się, co samo w sobie rodzi szereg pytań: czy nauka online może ułatwić głębokie uczenie się? W jakim stopniu wideokonferencje łagodzą wyzwanie związane z odległością? W jaki sposób można rozwijać i utrzymywać społeczności oparte na uczeniu się przy użyciu obecnych i nowych technologii? Jednocześnie nowe technologie komunikacyjne wpływają na sposób, w jaki rozumiemy siebie i świat, w którym żyjemy. W związku z tym celem dzisiejszej edukacji nie jest nauka określonych treści, ale raczej nauka uczenia się przez całe życie. Badanie procesu uczenia się może pomóc nam znaleźć istotne punkty, aby określić interesujące cechy naprawdę funkcjonalnego systemu e-learningowego.

PROCES UCZENIA SIĘ

Proces uczenia się polega na modyfikacji naszego zachowania, która poprzez wyciąganie wiedzy z nabytego doświadczenia pozwala nam rozwiązywać problemy (Pedreira, 2004a). Definicja ta podkreśla dwa podstawowe aspekty wszystkich procesów uczenia się: nabywanie wiedzy oraz doświadczenie, które do niej prowadzi. Większość badań nad naturą wiedzy zgadza się co do faktu, że wiedza znajduje się na szczycie hierarchicznej struktury zwanej informacją. Zgodnie z tą wizją, dane reprezentują fakty lub koncepcje w sposób sformalizowany, który umożliwia ich komunikację, interpretację lub opracowanie przez ludzi lub automatycznie (poziom syntaktyczny informacji). Tak zwane "wiadomości" to znaczenie, jakie inteligentna istota nadaje danym w oparciu o konwencjonalne reguły stosowane do ich reprezentacji (poziom semantyczny). Wiedza implikuje osąd faktów i sytuacji i składa się z wywnioskowanych danych i wiadomości, ukrytych relacji między obiektami, pojęciami, zdarzeniami i sytuacjami oraz niezbędnych działań kontrolnych, aby skutecznie zarządzać wszystkimi tymi elementami. W związku z tym wiedza dotyczy pragmatycznego aspektu informacji, ponieważ łączy otrzymane wiadomości z wiedzą, którą obserwator już posiada.

EDUKACJA W SPOŁECZEŃSTWIE WIEDZY

W ostatnich latach edukacja zaszła w tak wielu obszarach, że sama edukacja wymaga unowocześnienia. Ilość wiedzy, z którą mamy do czynienia, jest znacznie większa niż wcześniej, wzajemne powiązania między różnymi formami informacji są znacznie bardziej złożone, a źródła rozproszone. W związku z tym model liniowy, w którym każde pytanie ma swoje miejsce i swój moment, nie jest już adekwatny do dzisiejszej informacji. Logiczne hierarchie są zastępowane przez liczne i jednoczesne media, które odpowiadają na potrzeby procesu poznawczego. Nieunikniony wzrost złożoności i ilości dostępnych i niezbędnych informacji doprowadził do potrzeby ciągłego uczenia się. Co więcej, we współczesnym społeczeństwie wiedza nie jest związana wyłącznie z edukacją. Żyjemy w tzw. "społeczeństwie informacyjnym lub wiedzy", w którym posiadanie wiedzy jest czynnikiem decydującym. Posługiwanie się wiedzą wymaga głębokiej transformacji metod uczenia się i nauczania: od modelu, w którym nauczyciel jest monopolistą i pełnomocnym przedstawicielem wiedzy, musimy przejść do modelu, który oferuje uczniowi przestrzeń do indywidualnej eksploracji i samokształcenia. Uczeń musi budować relacje, odkrywać proces od wewnątrz i czuć się stymulowany do nakreślenia własnej mapy drogowej . Tego rodzaju uczenie się można osiągnąć jedynie poprzez strategie działania, które nie są postrzegane jako ograniczające zobowiązania, ale raczej jako interesujące możliwości uczenia się. Na przykład treści powinny być przedstawiane nie jako przedmiot nauki, ale raczej jako niezbędne elementy do osiągnięcia szeregu celów, które zostaną odkryte w trakcie różnych testów. Gry komputerowe stosują tę samą strategię, zmuszając użytkowników do uczenia się przechodzenia z jednej fazy do drugiej w oparciu o zdobyte doświadczenie i zwiększoną zręczność. W ten sposób zapewniają użytkownikom rozrywkę na wiele godzin metodą prób i błędów. Poza tym uczniowie pochodzą z różnych środowisk, mają różny wiek i wykształcenie, co utrudnia ich integrację w jednej grupie. Prawdziwie spersonalizowane podejście wymagałoby znacznie większej liczby nauczycieli i znacznie więcej czasu. Dodając do tego rosnące zapotrzebowanie na kształcenie ustawiczne, z elastycznymi planami zajęć i przedmiotami, staje się jasne, że obecne programy są zbyt sztywne. Do zalet e-learningu należą wygoda i przenośność (elastyczność fizyczna i czasowa), koszty i wybór (szeroki zakres kursów i cen, różne poziomy), indywidualizacja i wyższy poziom zaangażowania studentów . Jednakże, jeśli zawartość platform edukacyjnych pozostaje taka sama jak w systemach tradycyjnych, nawet jeśli format prezentacji jest dostosowany, nie przyczynia się to znacząco do poprawy procesu uczenia się (Martínez, 2002). To samo dzieje się z wykorzystaniem systemów obliczeniowych, które wspierają nauczanie ex cathedra i usprawniają nabywanie określonych umiejętności, takich jak symulatory i gry. Symulatory mogą być używane tylko wtedy, gdy pewne koncepcje są już dobrze zrozumiane, a w większości przypadków ich interfejs jest dość skomplikowany. Gry komputerowe są wykorzystywane głównie do konkretnych aspektów i na kursach podstawowych. Projektowanie instrukcji e-learningowych było udoskonalane i udoskonalane przez wiele lat, przy wykorzystaniu uznanych zasad nauczania, co przyniosło wiele korzyści uczniom. Należy jednak kontynuować badania w tym obszarze, ponieważ wyniki wciąż nie są tak dobre, jak oczekiwano.

PROPOZYCJA NOWYCH TECHNOLOGII

Mimo to obecne technologie komunikacyjne, w tym sztuczna inteligencja, umożliwiają wdrażanie strategii uczenia się opartych na działaniu (np. gry wideo), wdrażanie systemów usprawniających zarządzanie wiedzą , odzyskiwanie modelu uczenia się jeden do jednego (mistrz-uczeń staje się nauczycielem-uczniem) oraz wdrażanie nowego modelu uczenia się ("wielu nauczycieli dla jednego ucznia"). Model komputerowy obejmujący wszystkie te cechy może stanowić solidną podstawę do usprawnienia procesu uczenia się i istniejących systemów e-learningowych. Mógłby on nauczyć uczniów czegoś więcej niż tylko określonych treści: mógłby nauczyć ich, jak się uczyć, poprzez dobór i udostępnianie odpowiednich informacji w każdym momencie. W tym punkcie zwrócimy uwagę na niektóre pedagogiczne cechy komputerowych modeli e-learningowych, o których wiadomo, że usprawniają proces uczenia się. Dla każdej z tych cech proponujemy funkcję, którą można wdrożyć za pomocą nowych technologii.

Cecha pedagogiczna 1

Korzystanie z informacji pochodzących z różnych źródeł pozwoli uczniom spojrzeć na te same zagadnienia z różnych punktów widzenia, ułatwiając ich zrozumienie i ochronę.

Cecha nowych technologii 1
W pamięci instytucjonalnej systemu zarządzania wiedzą znajdziemy wszystkie informacje dotyczące każdej jednostki tematycznej, różnych poziomów i powiązanych z nimi zadań. Możliwość rozwiązywania różnych zadań i dostęp do informacji z różnych źródeł pozwala uczniowi na zdobywanie informacji na różne sposoby, dzięki czemu jego wiedza będzie pełniejsza i trwalsza.

Cecha pedagogiczna 2

Model e-learningowy powinien zapewniać indywidualne podejście, uwzględniając preferencje ucznia dotyczące strategii uczenia się, różnych rodzajów materiałów, jego wcześniejszej wiedzy itp.

Nowe Technologie Cecha 2

Aby to osiągnąć, inteligentni agenci mogą przejąć kontrolę nad wyborem i wyświetlaniem, w każdym przypadku, odpowiednich informacji (z repozytorium informacji) zgodnie z preferencjami i poziomem każdego ucznia. Agenci ci mogą wykonywać różne zadania i rozdzielać je między komputery użytkowników a serwer, na którym przechowywana jest Pamięć Instytucjonalna.

Cecha pedagogiczna 3

Model e-learningu musi udostępniać uczniom wszystkie dostępne informacje, w różnych formatach i z różnych źródeł, aby mogli oni nauczyć się wybierać elementy najbardziej istotne dla swojej nauki.

Nowe Technologie Cecha 3

Aby to osiągnąć, można wykorzystać globalną ontologię, ustanawiającą klasyfikację poziomów i relacje między dostępnymi informacjami, zarządzaną za pośrednictwem Systemu Zarządzania Wiedzą.

Cecha pedagogiczna 4

Komputerowe modele e-learningu powinny proponować tę praktykę poprzez zadania i problemy do rozwiązania, tak aby wiedza uczniów rozwijała się w miarę postępów w rozwiązywaniu zadań.

Nowe Technologie Cecha 4

Konieczne jest opracowanie wielu różnych rodzajów prac, na różnych poziomach, dla każdej jednostki, którą musi przygotować student. Zadania, a także dostępne informacje, będą oparte na Pamięci Instytucjonalnej zorganizowanej w ramach ontologii, co ułatwi dostęp do istotnych informacji w dowolnym momencie. Wykonując zadania, uczeń będzie budował własną wiedzę.

Cecha pedagogiczna 5

Model e-learningu powinien łączyć strategie mające na celu wzbudzenie i podniesienie motywacji studenta oraz pobudzenie jego ciekawości, łącząc dostępne informacje z jego zainteresowaniami, proponując możliwość głębszego zgłębiania tych samych lub pokrewnych tematów i wykorzystując strategie gier komputerowych, które zachęcają do badań.

Nowe Technologie Cecha 5

Gdy treści kursu są częścią Pamięci Instytucjonalnej, istnienie globalnej ontologii może ułatwić prezentację elementów, wskazując powiązania między nimi. Ponadto, jak wspomniano wcześniej, użycie inteligentnych agentów pozwala nam pokazać te powiązania zgodnie z indywidualnymi preferencjami. Strategie wykorzystywane w grach komputerowych, w tym praktyka poprzez akcję, pomogą przyciągnąć i utrzymać zainteresowanie uczniów.

PRACA W PRZYSZŁOŚCI

W naszym laboratorium badawczym opracowano kilka prototypów aspektów wymienionych w poprzednim punkcie w celu przetestowania proponowanych funkcji. Każdy z nich osiągnął całkiem dobre wyniki. Te przybliżenia pokazują, że wykorzystanie nowych technologii w edukacji pozwala uczniom na rozszerzenie lub udoskonalenie metod rozwiązywania problemów oraz umiejętności przekazywania wiedzy . Po tych pierwszych podejściach pracujemy nad połączeniem prototypów i ich rozszerzeniem o pewne cechy, które nie zostały jeszcze przetestowane.

WNIOSKI

W niniejszym artykule proponujemy kilka cech, które powinny posiadać systemy e-learningowe, aby usprawnić naukę online, co można osiągnąć dzięki wykorzystaniu nowych technologii. Krótko mówiąc, proponujemy model komputerowy oparty na Systemie Zarządzania Wiedzą, który, wykorzystując globalną ontologię, utrzymuje największą liczbę relacji między dostępnymi informacjami a ich klasyfikacją na różnych poziomach. Dzięki temu wsparciu wiedzy, praktyka może być realizowana poprzez proponowanie zadań, w oparciu o strategie gier komputerowych. Wykorzystując filozofię inteligentnych agentów, systemy te mogą wchodzić w interakcje ze studentami, prezentując im informacje zgodnie z ich preferencjami, aby ich zmotywować i pobudzić ich zdolność do zadawania pytań.

WSTĘP

Eksploracja danych to dziedzina obejmująca badanie narzędzi i technik wspomagających ludzi w inteligentnej analizie (eksploracji) gór danych. Eksploracja danych znalazła skuteczne zastosowania w wielu dziedzinach, w tym w sprzedaży i marketingu, identyfikacji przestępstw finansowych, zarządzaniu portfelem, diagnostyce medycznej, zarządzaniu procesami produkcyjnymi i poprawie opieki zdrowotnej itp. Techniki eksploracji danych można sklasyfikować jako techniki opisowe lub predykcyjne. Techniki opisowe podsumowują/charakteryzują ogólne właściwości danych, podczas gdy techniki predykcyjne konstruują model na podstawie danych historycznych i wykorzystują go do przewidywania niektórych cech przyszłych danych. Eksploracja reguł asocjacyjnych, analiza sekwencji i klasteryzacja to kluczowe opisowe techniki eksploracji danych, podczas gdy klasyfikacja i regresja to techniki predykcyjne. Celem tego artykułu jest wprowadzenie do problemu eksploracji reguł asocjacyjnych i opisanie niektórych podejść do rozwiązania tego problemu.

TŁO

Eksploracja reguł asocjacyjnych, jedna z podstawowych technik eksploracji danych, ma na celu wyodrębnienie interesujących korelacji, częstych wzorców lub struktur przyczynowych pomiędzy zestawami elementów w danych. Reguła asocjacyjna ma postać X → Y i wskazuje, że obecność elementów w poprzedniku reguły (X) implikuje obecność elementów w następniku reguły (Y). Na przykład reguła {PC, drukarka kolorowa} → {komputer stołowy} implikuje, że osoby, które kupują komputer PC (komputer osobisty) i drukarkę kolorową, mają również tendencję do kupowania komputera stołowego. Te skojarzenia nie są jednak oparte na inherentnych cechach domeny (jak w zależności funkcjonalnej), ale na współwystępowaniu elementów danych w zestawie danych. Tak więc eksploracja reguł asocjacyjnych jest techniką całkowicie sterowaną danymi. Reguły asocjacyjne zostały pomyślnie zastosowane w licznych aplikacjach, z których niektóre są wymienione poniżej:

1. Analiza rynku detalicznego: Odkrywanie reguł asocjacyjnych w danych detalicznych zostało zastosowane w domach towarowych do planowania powierzchni, planowania zapasów, ukierunkowanych kampanii marketingowych w celu zwiększenia świadomości produktu, promocji produktu i utrzymania klientów.
2. Analiza asocjacji sieciowych: Reguły asocjacyjne w eksploracji wykorzystania sieci były używane do rekomendowania powiązanych stron, odkrywania stron internetowych ze wspólnymi odniesieniami, stron internetowych z większością tych samych linków (lustrzanych) i predykcyjnego buforowania. Wiedza ta jest stosowana w celu ulepszenia projektu witryny internetowej i przyspieszenia wyszukiwania.
3. Odkrywanie powiązanych pojęć: Słowa lub zdania, które często pojawiają się razem w dokumentach, nazywane są powiązanymi pojęciami. Reguły asocjacyjne mogą być używane do odkrywania powiązanych pojęć, co dalej prowadzi do odkrycia splagiatowanego tekstu i rozwoju ontologii itp.

Problem eksploracji reguł asocjacyjnych (ARM) został wprowadzony przez Agrawala i inych. Duże bazy danych transakcji detalicznych zwane bazami danych koszyków rynkowych, które gromadzą się w domach towarowych, stanowiły motywację dla ARM. Koszyk odpowiada fizycznej transakcji detalicznej w domu towarowym i składa się z zestawu artykułów kupowanych przez klienta. Transakcje te są rejestrowane w bazie danych zwanej bazą danych transakcji. Celem jest analiza nawyków zakupowych klientów poprzez znalezienie powiązań między różnymi artykułami, które klienci umieszczają w swoich "koszykach zakupowych". Odkryte reguły asocjacyjne mogą być również wykorzystywane przez kierownictwo w celu zwiększenia skuteczności reklamy, marketingu, zarządzania zapasami i zmniejszenia powiązanych kosztów. Autorzy pracowali nad bazą danych transakcji boolowskich. Każdy rekord odpowiada koszykowi klienta i zawiera identyfikator transakcji (TID), szczegóły transakcji i listę artykułów zakupionych w ramach transakcji. Lista artykułów jest reprezentowana przez wektor boolowski, w którym jedynka oznacza obecność odpowiedniego artykułu w transakcji, a zero oznacza brak. Problemem znalezienia reguł asocjacyjnych jest znalezienie kolumn z często występującymi regułami w bazie danych boolowskich. Jednak większość algorytmów dla ARM używa formy bazy danych transakcyjnych pokazanej po prawej stronie. Poniżej podajemy matematyczną formułę problemu.

MATEMATYCZNA FORMUŁA PROBLEMU ARM

Niech I = {i₁, i₂, …,i_n} oznacza zbiór elementów, a D oznacza bazę danych N transakcji. Transakcja T ∈ D jest podzbiorem I, tj. T ⊆ I i jest powiązana z unikalnym identyfikatorem TID. Zbiór elementów to kolekcja jednego lub większej liczby elementów. X jest zbiorem elementów, jeśli X ⊆ I. Mówi się, że transakcja zawiera zbiór elementów X, jeśli X ⊆ T. Zbiór k-elementów to zbiór elementów, który zawiera k elementów. Reguła asocjacji ma postać X → Y [wsparcie, pewność], gdzie X ⊂ I, Y ⊂ I, X ∩ Y = ∅, a wsparcie i pewność to metryki oceny reguł. Wsparcie zbioru elementów X to ułamek transakcji, które zawierają X. Oznacza ono prawdopodobieństwo, że transakcja zawiera X.

Wsparcie (X) = P(X) = Liczba transakcji zawierających X / Całkowita liczba transakcji w D Wsparcie reguły X → Y w D wynosi "s", jeśli s% transakcji w D zawiera X ∪ Y i jest obliczane jako: Wsparcie (X → Y) = P(X ∪ Y) = Liczba transakcji zawierających X ∪ Y / Całkowita liczba transakcji w D Wsparcie wskazuje na stopień rozpowszechnienia reguły. Reguła o niskiej wartości wsparcia reprezentuje rzadkie zdarzenie. Pewność reguły mierzy jej siłę i dostarcza wskazówki co do niezawodności przewidywań dokonanych przez regułę. Reguła X → Y ma pewność "c" w D, jeśli c% transakcji w D, które zawierają X, zawiera również Y. Jest ona obliczana jako prawdopodobieństwo warunkowe, że Y występuje w transakcji, zakładając, że X jest obecne w tej samej transakcji, tj. Pewność (X → Y) = P(Y/X) = P(X ∪ Y) / P(X)



Przykład 1: Rozważ przykładową bazę danych przedstawioną na (a). Tutaj I = {A, B, C, D, E}. Rysunki (b) i (c) pokazują obliczenia wsparcia i pewności dla reguły. Przy n elementach w I, całkowita liczba możliwych reguł asocjacyjnych jest bardzo duża (O(3ⁿ)). Jednak większość tych reguł (skojarzeń) istniejących w D nie jest interesująca dla użytkownika. Miary ciekawości są stosowane w celu zmniejszenia liczby reguł odkrytych przez algorytmy. Najważniejszym kryterium ciekawości jest wysoka powszechność zarówno zestawów elementów, jak i reguł, która jest określana przez użytkownika jako minimalna wartość wsparcia. Zestaw elementów (reguła), którego wsparcie jest większe lub równe określonemu przez użytkownika minimalnemu progowi wsparcia (minsup), nazywa się Częstym zestawem elementów (regułą). Drugim kryterium ciekawości jest siła reguły. Reguła, której pewność jest większa niż określony przez użytkownika minimalny próg ufności (minconf), jest interesująca dla użytkownika. Pewność może jednak czasami być myląca. Na przykład, pewność reguły może być wysoka, nawet jeśli poprzednik i następnik reguły są niezależne. Podniesienie (nazywane również Zainteresowaniem) i Przekonanie reguły to inne powszechnie stosowane miary zainteresowania regułą. Należy zidentyfikować odpowiednią miarę siły reguły dla zastosowania.

GÓRNICTWO REGUŁ ASOCJONOWANIA

Ponieważ reguła asocjacji jest implikacją między zestawami elementów, podejście siłowe do generowania reguł asocjacji wymaga zbadania relacji między wszystkimi możliwymi zestawami elementów. Taki proces zazwyczaj obejmowałby zliczanie współwystępowania wszystkich zestawów elementów w D i późniejsze generowanie z nich reguł. Dla n elementów istnieje 2ⁿ możliwych zestawów elementów, które należy zliczyć. Może to wymagać nie tylko zaporowej ilości pamięci, ale także złożonego indeksowania liczników. Ponieważ użytkownik jest zainteresowany tylko częstymi regułami, należy zliczyć tylko częste zestawy elementów przed wygenerowaniem reguł asocjacji. Tak więc problem eksploracji reguł asocjacji rozkłada się na dwie fazy:

Faza I: Odkrywanie częstych zestawów elementów
Faza II: Generowanie reguł z częstych zestawów elementów odkrytych w fazie I.

Różne algorytmy dla ARM różnią się pod względem podejścia do optymalizacji czasu i wymagań dotyczących pamięci masowej dla zliczania w pierwszej fazie. Pomimo zmniejszenia przestrzeni wyszukiwania poprzez narzucenie ograniczenia minsup, generowanie częstych zestawów elementów jest nadal procesem kosztownym obliczeniowo. Antymonotoniczna własność wsparcia jest ważnym narzędziem do dalszego zmniejszania przestrzeni wyszukiwania i jest używana w większości algorytmów reguł asocjacyjnych. Zgodnie z tą własnością, wsparcie zbioru elementów nigdy nie przekracza wsparcia żadnego z jego podzbiorów, tj. jeśli X jest zbiorem elementów, to dla każdego z jego podzbiorów Y, sup(X) ⇐ sup(Y). Ta własność sprawia, że zbiór częstych zbiorów elementów jest domknięty w dół. Zadanie generowania reguł jest trywialne, gdy zbiór częstych zbiorów elementów zostanie odkryty. Algorytm Apriori wykorzystuje podejście poziomowe do odkrywania częstych zbiorów elementów. Ten algorytm wykonuje wielokrotne skanowanie danych. Podczas każdego skanowania algorytm generuje i zlicza potencjalne częste zbiory elementów (kandydatów). Kandydujące zbiory elementów o rozmiarze k+1 są generowane przez łączenie częstych zbiorów elementów o rozmiarze k i są przycinane, wykorzystując antymonotoniczną własność. Pod koniec skanowania zestaw częstych zbiorów elementów jest potwierdzany. Strategia ta wiąże się z ogromnymi kosztami wejścia/wyjścia i zmotywowała szereg wariantów, które zmniejszają liczbę liczników (kandydatów) i skanów. Algorytm wzrostu FP wykorzystuje metodę wzrostu wzorca, aby uniknąć kosztownego procesu generowania i testowania kandydatów, dlatego jest uważany za ważny kamień milowy. Algorytm wykorzystuje opartą na drzewie strukturę danych w pamięci, zwaną FP-Tree, aby przechowywać bazę danych w formie skompresowanej. Dwa przebiegi są wykonywane po bazie danych w celu skonstruowania drzewa prefiksów, które jest następnie używane do generowania częstych wzorców. Zaproponowano również podejścia oparte na kratce w celu wydajnego odkrywania częstych zestawów elementów. Zadanie generowania reguł (faza II) z danych częstych zestawów elementów jest dość proste . Sprowadza się to do wyliczenia wszystkich podzbiorów częstego zestawu elementów i znalezienia stosunku wsparcia każdego zestawu elementów do wsparcia każdego z jego podzbiorów. Podzbiory, których stosunek jest większy niż minconf, kwalifikują się jako silne reguły i są zgłaszane użytkownikowi.

RODZAJE REGUŁ ASOCJONOWANIA

Popularność ARM doprowadziła do jego zastosowania w wielu typach danych i domenach aplikacji. W literaturze poświęconej eksploracji danych opisano kilka wyspecjalizowanych rodzajów reguł asocjacyjnych. Opisujemy tutaj niektóre z ważnych typów:

1. Reguły asocjacji ilościowej: Reguły asocjacji ilościowej wprowadziły pojęcie eksploracji asocjacji między atrybutami numerycznymi oprócz atrybutów kategorycznych. Reguły asocjacji ilościowej można wyprowadzić, mapując wartości atrybutów na zestaw kolejnych liczb całkowitych lub dzieląc je na przedziały. Przykład reguły asocjacji ilościowej:

Wiek (x, "30….39") ^ pensja (x, "42…48K.") → kupuje(x, "samochód") [1%, 75%]

2. Reguły asocjacji wielopoziomowej: Wiele aplikacji ma wrodzoną taksonomię (hierarchię pojęć) między elementami. W takich scenariuszach reguły asocjacji mogą być generowane na różnych poziomach taksonomii, aby uchwycić wiedzę na różnych poziomach abstrakcji. W miarę przesuwania się w dół hierarchii (od wartości uogólnionych do wyspecjalizowanych), wsparcie reguł maleje, a niektóre reguły mogą stać się nieciekawe. Jednak podczas wspinania się w górę hierarchii niektóre nowe reguły mogą stać się interesujące. Daje to początek regułom asocjacji wielopoziomowej , które uchwycą powiązania między elementami lub atrybutami na różnych poziomach abstrakcji, tj. na różnych poziomach hierarchii pojęć. Na przykład reguła {Brown Bread} → {Coke} uchwyca powiązania między elementami na różnych poziomach hierarchii pojęć. Reguły wielopoziomowe można eksplorować przy użyciu tych samych progów wsparcia lub różnych progów na różnych poziomach. Wybór odpowiedniego poziomu abstrakcji może mieć znaczący wpływ na użyteczność generowanej wiedzy. Kopanie na bardzo wysokim poziomie abstrakcji prawdopodobnie wygeneruje zbyt uogólnione reguły, które mogą nie być interesujące, podczas gdy kopanie na zbyt niskim poziomie abstrakcji może prowadzić do generowania wysoce specyficznych reguł.

3. Wielowymiarowe reguły asocjacyjne: Reguły asocjacyjne zasadniczo ujawniają powiązania wewnątrz rekordu. Jeśli powiązania istnieją między różnymi wartościami tego samego atrybutu (wymiaru), powiązanie nazywa się jednowymiarową regułą asocjacyjną, podczas gdy jeśli powiązania obejmują wiele wymiarów, powiązania nazywa się wielowymiarowymi regułami asocjacyjnymi. Na przykład następująca jednowymiarowa reguła zawiera koniunkcje zarówno w antecedencie, jak i w konsekwencji pojedynczego atrybutu "kupuje".

Kupuje (X, "mleko") i Kupuje (X, "masło") → Kupuje (X, "chleb")

Wielowymiarowe asocjacje zawierają dwa lub więcej predykatów, na przykład

Wiek (X, "19-25") i Zawód (X, "student") → Kupuje (X, "cola")

4. Reguły asocjacyjne w strumieniowaniu danych: Wspomniane typy reguł dotyczą statycznych repozytoriów danych. Jednak wydobywanie reguł ze strumieni danych jest znacznie bardziej złożone . Dziedzina ta jest stosunkowo nowa i stwarza dodatkowe wyzwania, takie jak charakterystyki danych jednokrotnego spojrzenia, ograniczona pamięć główna, ciągła aktualizacja danych i przetwarzanie online, aby móc podejmować decyzje w locie.

5. Eksploracja reguł asocjacyjnych z wieloma minimalnymi wsparciami: W dużych domach towarowych, w których liczba przedmiotów jest bardzo duża, użycie pojedynczego progu wsparcia czasami nie daje interesujących reguł. Ponieważ trendy zakupowe dla różnych przedmiotów często znacznie się różnią, zaleca się stosowanie różnych progów wsparcia dla różnych przedmiotów .

6. Negatywne reguły asocjacyjne: Typowe reguły asocjacyjne odkrywają korelacje między przedmiotami, które są kupowane podczas transakcji i są nazywane pozytywnymi regułami asocjacyjnymi. Negatywne reguły asocjacyjne odkrywają implikacje we wszystkich przedmiotach, niezależnie od tego, czy zostały kupione, czy nie. Negatywne reguły asocjacyjne są przydatne w analizie koszyka rynkowego w celu identyfikacji produktów, które są ze sobą sprzeczne lub się uzupełniają. Znaczenie negatywnych reguł asocjacyjnych zostało podkreślone u Brina, Wu i innych.

PRZYSZŁE TRENDY

Chociaż analiza asocjacji będzie nadal oddziaływać na różne sfery naukowe i biznesowe za pośrednictwem baz danych opieki zdrowotnej, baz danych finansowych, baz danych przestrzennych, baz danych multimedialnych i baz danych szeregów czasowych itp., badamy rolę górnictwa reguł asocjacyjnych w niektórych obiecujących zastosowaniach.

Business Intelligence (BI): BI przekształca surowe dane w spersonalizowaną inteligencję w celu zwiększenia zadowolenia klientów, lojalności i rentowności produktów. Integruje dane z wielu źródeł w całej firmie, analizuje je i działa szybko na podstawie wyników, co prowadzi do przewagi konkurencyjnej i terminowego wdrażania rozwiązań. Analiza asocjacji jest jednym z podstawowych narzędzi wspierających BI. W sektorze detalicznym analiza asocjacji stanowi podstawę analizy danych punktu sprzedaży, analizy koszyka rynkowego, optymalizacji zarządzania zasobami i przestrzenią. W sektorze bankowym BI wykorzystuje badanie asocjacji do przeprowadzania analizy ryzyka kredytowego, wykrywania oszustw i zatrzymywania klientów. Firmy kredytowe korzystają z wykrywania oszustw, monitorowania wzorców zakupów, oceniania wiarygodności klientów i analizowania sprzedaży krzyżowej.

Eksploracja danych strumieniowych: W przeciwieństwie do danych w tradycyjnych statycznych bazach danych, strumień danych jest uporządkowaną sekwencją elementów, która jest ciągła, nieograniczona, zwykle występuje z dużą prędkością i ma rozkład danych, który zmienia się w czasie. Wraz ze wzrostem liczby aplikacji w strumieniach danych eksploracyjnych, rośnie potrzeba przeprowadzania eksploracji reguł asocjacyjnych w danych strumieniowych. Reguły asocjacyjne są wykorzystywane do szacowania brakujących danych w strumieniach danych generowanych przez czujniki i szacowania częstotliwości strumieni pakietów internetowych. Eksploracja reguł asocjacyjnych jest również przydatna do monitorowania przepływów produkcyjnych w celu przewidywania awarii lub generowania raportów na podstawie strumieni dzienników internetowych. Bioinformatyka: Asocjacje są wykorzystywane w bazach danych bioinformatycznych do identyfikacji współwystępujących sekwencji genów. Są również wykorzystywane do wykrywania mutacji genów. Gen to segment cząsteczki DNA, który zawiera wszystkie informacje wymagane do syntezy produktu. Każda zmiana w sekwencji DNA genu (na przykład: insercja, usunięcie, insercja/usunięcie, złożona i wielokrotna substytucja) jest określana jako mutacja genu. Odkrycie interesujących relacji asocjacyjnych wśród ogromnej liczby mutacji genów jest ważne, ponieważ może pomóc w ustaleniu przyczyny mutacji w nowotworach i chorobach.

WNIOSEK

Eksploracja reguł asocjacyjnych jest ważną techniką eksploracji danych, która została wprowadzona w celu opisania powiązań wewnątrz rekordów w bazach danych transakcyjnych. Jednak zarówno środowisko akademickie, jak i przemysł uznały tę technologię za rentowną i odnoszącą sukcesy ze względu na jej prostotę, łatwość zrozumienia i szerokie zastosowanie. Ponad dekadę później technologia ta nadal obiecuje być siłą napędową dla niektórych nowych, wymagających zastosowań. Nie ma wątpliwości, że eksploracja reguł asocjacyjnych została uznana za jeden z najważniejszych wkładów społeczności baz danych w KDD. W tym artykule wprowadziliśmy pojęcie reguł asocjacyjnych, ich zastosowania i przedstawiliśmy ich matematyczną formułę. Przedstawiliśmy również główne kamienie milowe w historii rozwoju reguł asocjacyjnych. Omówiono również ogólną strategię eksploracji, powiązane problemy, takie jak ogrom przestrzeni wyszukiwania i miary ciekawości. Na koniec opisano różne typy reguł asocjacyjnych.