Omówimy, jak logika rozmyta rozszerza zakres głównych zadań eksploracji danych: klasteryzacji, klasyfikacji, regresji i reguł asocjacyjnych. Rozpoczniemy od przedstawienia formuły eksploracji danych z wykorzystaniem atrybutów logiki rozmytej. Następnie, dla każdego zadania, przedstawimyprzegląd głównych algorytmów i szczegółowy opis (tj. pseudokod) najpopularniejszych algorytmów.

WSTĘP

Istnieją dwa główne rodzaje niepewności w uczeniu nadzorowanym: statystyczna i poznawcza. Niepewność statystyczna dotyczy losowego zachowania natury, a wszystkie istniejące techniki eksploracji danych potrafią poradzić sobie z niepewnością, która pojawia się (lub zakłada się, że pojawia się) w świecie naturalnym w wyniku zmienności statystycznej lub losowości. Niepewność poznawcza natomiast dotyczy poznania ludzkiego. Teoria zbiorów rozmytych, po raz pierwszy wprowadzona przez Zadeha w 1965 roku, zajmuje się niepewnością poznawczą i dąży do przezwyciężenia wielu problemów występujących w klasycznej teorii mnogości. Na przykład, głównym problemem, z jakim borykają się badacze teorii sterowania, jest to, że niewielka zmiana danych wejściowych powoduje znaczną zmianę danych wyjściowych. To wprowadza cały system sterowania w stan niestabilności. Ponadto istnieje również problem sztucznej i niedokładnej reprezentacji wiedzy subiektywnej. Teoria zbiorów rozmytych jest próbą stawienia czoła tym trudnościom i w tym rozdziale pokazujemy, jak można ją wykorzystać w zadaniach eksploracji danych.

TŁO

Data mining to termin ukuty w celu opisania procesu przeszukiwania dużych i złożonych baz danych w celu identyfikacji prawidłowych, nowych, użytecznych i zrozumiałych wzorców i zależności. Data mining obejmuje wnioskowanie algorytmów, które eksplorują dane, opracowują model i odkrywają nieznane wcześniej wzorce. Model służy do zrozumienia zjawisk na podstawie danych, ich analizy i prognozowania. Dostępność i obfitość danych sprawia, że odkrywanie wiedzy i data mining są dziś niezwykle ważne i konieczne. Rozpoczynamy od przedstawienia kilku podstawowych pojęć logiki rozmytej. Główny nacisk położony jest jednak na pojęcia wykorzystywane w procesie indukcyjnym w przypadku data miningu. Ponieważ teoria zbiorów rozmytych i logika rozmyta są znacznie szersze niż wąska perspektywa przedstawiona tutaj, zainteresowanego czytelnika zachęcamy do lektury Zimmermanna . W klasycznej teorii mnogości dany element albo należy, albo nie należy do zbioru. Teoria zbiorów rozmytych natomiast pozwala na stopniową ocenę przynależności elementów w odniesieniu do zbioru. Niech U będzie wszechświatem dyskursu, reprezentującym zbiór obiektów oznaczonych generycznie przez u. Zbiór rozmyty A we wszechświecie dyskursu U jest scharakteryzowany przez funkcję przynależności μ_A, która przyjmuje wartości z przedziału [0, 1]. Gdzie μ_A(u) = 0 oznacza, że u zdecydowanie nie należy do zbioru A, a μ_A(u) = 1 oznacza, że u zdecydowanie należy do zbioru A. Powyższą definicję można zilustrować na przykładzie zbioru nieostrego Younga. W tym przypadku zbiór U jest zbiorem osób. Dla każdej osoby w U definiujemy stopień przynależności do zbioru rozmytego Younga. Funkcja przynależności odpowiada na pytanie "w jakim stopniu osoba U jest młoda?". Najłatwiejszym sposobem na to jest funkcja przynależności oparta na wieku osoby. Na przykład, rysunek przedstawia następującą funkcję przynależności.





Biorąc pod uwagę tę definicję, John, który ma 18 lat, ma stopień młodości 0,875. Philip, 20 lat, ma stopień młodości 0,75. W przeciwieństwie do teorii prawdopodobieństwa, stopnie przynależności nie muszą sumować się do 1 dla wszystkich obiektów, a zatem wiele lub niewiele obiektów w zbiorze może mieć wysoki stopień przynależności. Jednakże przynależność obiektu do zbioru (takiego jak "młody") i dopełnienie zbioru ("niemłody") muszą nadal sumować się do 1. Główną różnicą między klasyczną teorią mnogości a teorią mnogości rozmytych jest to, że ta druga dopuszcza częściowe przynależność do zbioru. Zbiór klasyczny lub ostry jest zatem zbiorem rozmytym, który ogranicza swoje wartości przynależności do {0,1}, punktów końcowych przedziału jednostkowego. Funkcje przynależności mogą być używane do reprezentowania zbioru ostrego. Na przykład, rysunek 2 przedstawia ostrą funkcję przynależności zdefiniowaną jako:





W standardowych problemach klasyfikacyjnych zakładamy, że każdy przypadek przyjmuje jedną wartość dla każdego atrybutu i że każdy przypadek jest klasyfikowany tylko do jednej z wzajemnie wykluczających się klas. Aby zilustrować, jak logika rozmyta może pomóc w zadaniach eksploracji danych, wprowadzamy problem modelowania preferencji widzów telewizyjnych. W tym problemie występują 3 atrybuty wejściowe: A = {Pora dnia, Grupa wiekowa, Nastrój}. Klasyfikacja może być gatunkiem filmu, który widz chciałby obejrzeć, na przykład C = {Akcja, Komedia, Dramat}. Wszystkie atrybuty są z definicji niejasne. Na przykład, ludzkie uczucia szczęścia, obojętności, smutku, kwaśności i zrzędliwości są niejasne i nie ma między nimi wyraźnych granic. Chociaż niejasności "Grupy wiekowej" lub "Pory dnia" można uniknąć, wskazując dokładny wiek lub dokładną godzinę, reguła indukowana za pomocą precyzyjnego drzewa decyzyjnego może mieć sztuczną, wyraźną granicę, na przykład "JEŻELI wiek < 16, TO film akcji". Ale co z osobą, która ma 17 lat? Czy ten widz zdecydowanie nie powinien obejrzeć filmu akcji? Preferowany gatunek widza może być nadal niejasny. Na przykład, widz może mieć ochotę zarówno na komedie, jak i dramaty. Co więcej, powiązanie filmów z gatunkami również może być niejasne. Na przykład film "Zabójcza broń" (z Melem Gibsonem i Dannym Gloverem w rolach głównych) jest uważany zarówno za komedię, jak i film akcji. Koncepcję rozmytą można wprowadzić do klasycznego zadania eksploracji danych, jeśli przynajmniej jeden z atrybutów jest rozmyty. W opisanym powyżej przykładzie zarówno atrybuty wejściowe, jak i docelowe są rozmyte. Formalnie problem jest zdefiniowany następująco: Każda klasa c_j jest zdefiniowana jako zbiór rozmyty w uniwersum obiektów U. Funkcja przynależności μ_cj(u) wskazuje stopień, w jakim obiekt u należy do klasy c_j. Każdy atrybut a_i jest zdefiniowany jako atrybut lingwistyczny, który przyjmuje wartości lingwistyczne z dom(a_i) = {v_i,1, v_i,2,… v_i,|dom(ai)|}. Każda wartość lingwistyczna v_i,k jest również zbiorem rozmytym zdefiniowanym na U. Przynależność μ_vi,k(u) określa stopień, w jakim atrybut a_i obiektu u jest v_i,k. Przypomnijmy, że przynależność wartości lingwistycznej może być subiektywnie przypisana lub przeniesiona z wartości liczbowych za pomocą funkcji przynależności zdefiniowanej w zakresie wartości liczbowej. Zazwyczaj, zanim będzie można włączyć koncepcje rozmyte do aplikacji eksploracji danych, ekspert musi dostarczyć zbiory rozmyte dla atrybutów ilościowych wraz z odpowiadającymi im funkcjami przynależności . Alternatywnie, odpowiednie zbiory rozmyte są określane za pomocą klasteryzacji rozmytej.


GŁÓWNY CEL ROZDZIAŁU

Rozmyte uczenie nadzorowane

W tej sekcji omówimy metody nadzorowane, które wykorzystują zbiory rozmyte. Metody nadzorowane to metody, które próbują odkryć związek między atrybutami wejściowymi a atrybutem docelowym (czasami nazywanym zmienną zależną). Odkryta relacja jest reprezentowana w strukturze zwanej modelem. Zazwyczaj modele opisują i wyjaśniają zjawiska ukryte w zbiorze danych i mogą być używane do przewidywania wartości atrybutu docelowego, znając wartości atrybutów wejściowych. Warto rozróżnić dwa główne modele nadzorowane: modele klasyfikacyjne (klasyfikatory) i modele regresji. Modele regresji odwzorowują przestrzeń wejściową na dziedzinę wartości rzeczywistych. Na przykład regresor może przewidzieć popyt na dany produkt na podstawie jego cech. Z drugiej strony, klasyfikatory odwzorowują przestrzeń wejściową na predefiniowane klasy. Koncepcje teorii zbiorów rozmytych mogą być włączone na wejściu, wyjściu lub do szkieletu klasyfikatora. Dane mogą być prezentowane w postaci rozmytej, a decyzja wyjściowa może być podana jako rozmyte wartości przynależności .W tym rozdziale skupimy się na rozmytych drzewach decyzyjnych. Zainteresowanego czytelnika zachęcamy również do zapoznania się z regresją miękką oraz neurorozmyciem . Drzewo decyzyjne to model predykcyjny, który może być używany do reprezentowania klasyfikatorów. Drzewa decyzyjne są często wykorzystywane w dziedzinach stosowanych, takich jak finanse, marketing, inżynieria i medycyna. Drzewa decyzyjne są samoobjaśniające. Nie trzeba być ekspertem w dziedzinie eksploracji danych, aby postępować zgodnie z określonym drzewem decyzyjnym. Istnieje kilka algorytmów indukcji rozmytych drzew decyzyjnych , z których większość rozszerza istniejące metody drzew decyzyjnych, takie jak: Fuzzy-CART , Fuzzy-ID3 . Inny kompletny framework do budowy drzewa rozmytego, obejmujący kilka procedur wnioskowania opartych na rozwiązywaniu konfliktów w systemach opartych na regułach i efektywnych metodach wnioskowania przybliżonego, został przedstawiony w (Janikow, 1998). W tej sekcji skupimy się na algorytmie zaproponowanym przez Yuan i Shaw (1995). Algorytm ten może poradzić sobie z problemami klasyfikacji zarówno z rozmytymi atrybutami, jak i rozmytymi klasami reprezentowanymi przez lingwistyczne terminy rozmyte. Może on również obsługiwać inne sytuacje w jednolity sposób, w których wartości liczbowe mogą być rozmyte do terminów rozmytych, a kategorie precyzyjne mogą być traktowane jako szczególny przypadek terminów rozmytych o zerowej rozmytości. Algorytm wykorzystuje niejednoznaczność klasyfikacji jako entropię rozmytą. Niejednoznaczność klasyfikacji bezpośrednio mierzy jakość reguł klasyfikacji w węźle decyzyjnym. Można ją obliczyć w ramach partycjonowania rozmytego i wielu klas rozmytych. Gdy dany atrybut jest numeryczny, musi zostać rozmyty do terminów lingwistycznych, zanim będzie mógł zostać użyty w algorytmie . Proces rozmycia może być przeprowadzany ręcznie przez ekspertów lub może być automatycznie wyprowadzony za pomocą pewnego rodzaju algorytmu klastrowania. Klastrowanie grupuje instancje danych w podzbiory w taki sposób, że podobne instancje są grupowane razem; różne instancje należą do różnych grup. Instancje są w ten sposób organizowane w wydajną reprezentację, która charakteryzuje próbkowaną populację. Można użyć prostego algorytmu do wygenerowania zestawu funkcji przynależności dla danych numerycznych. Załóżmy, że atrybut a_i ma wartość liczbową x z dziedziny X. Możemy pogrupować X do k terminów lingwistycznych v_i,j j = 1,...,k. Rozmiar k jest ręcznie predefiniowany. Rysunek 3 ilustruje tworzenie czterech grup zdefiniowanych na podstawie atrybutu wieku: "młody", "wczesna dorosłość", "w średnim wieku" i "starość".



Należy zauważyć, że pierwszy zestaw ("młody") i ostatni zestaw ("starość") mają formę trapezową, którą można jednoznacznie opisać za pomocą czterech narożników. Na przykład zestaw "młody" można przedstawić jako (0,0,16,32). Pomiędzy nimi wszystkie pozostałe zestawy ("wczesna dorosłość" i "w średnim wieku") mają formę trójkątną, którą można jednoznacznie opisać za pomocą trzech narożników. Na przykład zestaw "wczesna dorosłość" jest przedstawiony jako (16,32,48). Algorytm indukcyjny rozmytego drzewa decyzyjnego mierzy niejednoznaczność klasyfikacji związaną z każdym atrybutem i dzieli dane, używając atrybutu o najmniejszej niejednoznaczności klasyfikacji. Niejednoznaczność klasyfikacji atrybutu a_i z terminami językowymi v_i,j j = 1,…,k na dowodzie rozmytym S, oznaczonym jako G(a_i|S), jest średnią ważoną niejednoznaczności klasyfikacji obliczoną jako:



gdzie w(v_i,j> | S) jest wagą reprezentującą względny rozmiar v_i,j i jest zdefiniowana jako:



Niejednoznaczność klasyfikacji v_i,j jest definiowana jako



który jest mierzony na podstawie wektora rozkładu możliwości



Biorąc pod uwagę v_i,j, możliwość zaklasyfikowania obiektu do klasy cl można zdefiniować jako:



gdzie S(A,B) to rozmyty podzbiór mierzący stopień, w jakim A jest podzbiorem B. Podzbiór ten może być użyty do pomiaru poziomu prawdziwości reguły klasyfikacji. Na przykład, biorąc pod uwagę regułę klasyfikacji taką jak "JEŻELI wiek jest młody ORAZ nastrój jest wesoły, TO komediowy", musimy obliczyć S(gorący?słoneczny, pływacki), aby zmierzyć poziom prawdziwości reguły klasyfikacji. Funkcja jest posybilistyczną miarą niejednoznaczności lub niespecyficzności i jest zdefiniowana jako:



gdzie



jest permutacją rozkładu możliwości posortowanego tak, że . Wszystkie powyższe obliczenia są przeprowadzane na predefiniowanym poziomie istotności ?. Instancja uwzględni daną gałąź v_i,j tylko wtedy, gdy odpowiadająca jej przynależność jest większa niż α. Ten parametr służy do filtrowania nieistotnych gałęzi. Po partycjonowaniu danych za pomocą atrybutu o najmniejszej niejednoznaczności klasyfikacji, algorytm szuka niepustych gałęzi. Dla każdej niepustej gałęzi algorytm oblicza poziom prawdziwości klasyfikacji wszystkich instancji w gałęzi do każdej klasy. Poziom prawdziwości jest obliczany za pomocą miary rozmytego podzbioru S(A,B). Jeśli poziom prawdziwości jednej z klas przekracza predefiniowany próg β, wówczas nie jest potrzebne dodatkowe partycjonowanie, a węzeł staje się liściem, w którym wszystkie instancje zostaną przypisane do klasy o najwyższym poziomie prawdziwości. W przeciwnym razie procedura jest kontynuowana rekurencyjnie. Należy pamiętać, że małe wartości β prowadzą do mniejszych drzew, co wiąże się z ryzykiem niedopasowania. Wyższe β mogą prowadzić do większego drzewa o wyższej dokładności klasyfikacji. Jednak w pewnym momencie wyższe wartości β mogą prowadzić do przeuczenia. W standardowym drzewie decyzyjnym do każdej instancji można zastosować tylko jedną ścieżkę (regułę). W rozmytym drzewie decyzyjnym do jednej instancji można zastosować kilka ścieżek (reguł). Aby sklasyfikować instancję bez etykiety, należy wykonać następujące kroki:

o Krok 1: Oblicz przynależność instancji dla części warunkowej każdej ścieżki (reguły). Ta przynależność będzie powiązana z etykietą (klasą) ścieżki.
o Krok 2: Dla każdej klasy oblicz maksymalną przynależność uzyskaną ze wszystkich zastosowanych reguł.
o Krok 3: Instancję można zaklasyfikować do kilku klas o różnych stopniach na podstawie przynależności obliczonej w kroku 2.

Klastrowanie rozmyte

Celem klasteryzacji jest opis, a celem klasyfikacji - predykcja. Ponieważ celem klasteryzacji jest odkrycie nowego zestawu kategorii, nowe grupy są same w sobie interesujące, a ich ocena ma charakter wewnętrzny. W zadaniach klasyfikacyjnych istotna część oceny ma charakter zewnętrzny, ponieważ grupy muszą odzwierciedlać pewien zestaw klas odniesienia. Klastrowanie grupuje instancje danych w podzbiory w taki sposób, że podobne instancje są grupowane razem, podczas gdy różne instancje należą do różnych grup. W ten sposób instancje są organizowane w efektywną reprezentację, która charakteryzuje próbkowaną populację. Formalnie, struktura klasteryzacji jest reprezentowana jako zbiór podzbiorów C = C₁,…,C_k z S, taki że:



i C_i ∩ C_j = Ø dla i ≠ j. W konsekwencji, każda instancja w S należy do dokładnie jednego i tylko jednego podzbioru. Tradycyjne podejścia do klastrowania generują partycje; w partycji każda instancja należy do jednego i tylko jednego klastra. Zatem klastry w twardym klastrowaniu są rozłączne. Klastrowanie rozmyte rozszerza tę koncepcję i sugeruje schemat miękkiego klastrowania. W tym przypadku każdy wzorzec jest powiązany z każdym klastrem za pomocą pewnego rodzaju funkcji przynależności, a mianowicie, każdy klaster jest rozmytym zbiorem wszystkich wzorców. Większe wartości przynależności wskazują na większe zaufanie do przypisania wzorca do klastra. Twarde klasterowanie można uzyskać z rozmytego podziału, używając progu wartości przynależności. Najpopularniejszym algorytmem klastrowania rozmytego jest algorytm rozmytego c-średnich (FCM). FCM jest algorytmem iteracyjnym. Celem metody FCM jest znalezienie centrów klastrów (centroidów), które minimalizują funkcję niepodobieństwa. Aby uwzględnić wprowadzenie rozmytego podziału, macierz przynależności (U) jest inicjowana losowo zgodnie z równaniem 7.



Algorytm minimalizuje funkcję odmienności (lub odległości), która jest podana w równaniu 13:



gdzie u_ij mieści się w przedziale od 0 do 1; c_i to centroid klastra i; d_ij to euklidesowa odległość między i-tym centroidem a j-tym punktem danych; m to wykładnik ważenia. Aby osiągnąć minimum funkcji niepodobieństwa, konieczne są dwa warunki. Są one podane w równaniu 9 i równaniu 10.





Poprzez iteracyjną aktualizację centrów klastrów i ocen przynależności dla każdego punktu danych, metoda FCM iteracyjnie przesuwa centra klastrów do "właściwej" lokalizacji w zbiorze danych. Metoda FCM nie gwarantuje jednak zbieżności do optymalnego rozwiązania. Losowa inicjalizacja U może mieć nieodwracalny wpływ na ostateczną wydajność.

Rozmyte reguły asocjacyjne

Reguły asocjacyjne to reguły typu "70% klientów kupujących wino i ser kupuje również winogrona". Podczas gdy tradycyjnym obszarem zastosowania jest analiza koszyka rynkowego, eksploracja reguł asocjacyjnych była od tego czasu stosowana w różnych dziedzinach, co doprowadziło do szeregu istotnych modyfikacji i rozszerzeń. Algorytm rozmytej asocjacji został zaproponowany w pracy Komem i Schneider . Wartości ilościowe są najpierw przekształcane w zbiór ocen przynależności za pomocą predefiniowanych funkcji przynależności. Każda ocena przynależności reprezentuje zgodność wartości ilościowej z terminem lingwistycznym. Aby uniknąć rozróżnienia poziomu ważności danych, każdy punkt musi mieć ocenę przynależności równą 1 w jednej funkcji przynależności; Zatem funkcje przynależności każdego atrybutu generują linię ciągłą μ = 1. Dodatkowo, w celu zdiagnozowania kierunku odchylenia elementu od środka regionu funkcji przynależności, prawie każdy punkt otrzymuje inną ocenę przynależności, która jest niższa niż 1 w innych regionach funkcji przynależności. Zatem każdy koniec regionu funkcji przynależności dotyka, jest blisko lub nieznacznie zachodzi na koniec innej funkcji przynależności (oczywiście z wyjątkiem regionów zewnętrznych). Dzięki temu mechanizmowi, gdy punkt "a" przesuwa się w prawo, dalej od środka regionu "środek", otrzymuje wyższą wartość etykiety "środek-wysoki", dodatkowo do wartości 1 etykiety "środek".

PRZYSZŁE TRENDY

Niektóre z wyzwań związanych z wykorzystaniem teorii rozmytej w zadaniach eksploracji danych obejmują:

1. Włączenie wiedzy dziedzinowej w celu ulepszenia modelowania rozmytego.
2. Opracowanie metod prezentacji rozmytego modelu danych użytkownikom końcowym.
3. Efektywna integracja logiki rozmytej w narzędziach eksploracji danych.
4. Hybrydyzacja zbiorów rozmytych z technikami eksploracji danych.

WNIOSKI

Omówiono, jak logika rozmyta może być wykorzystana do rozwiązania kilku różnych zadań eksploracji danych, a mianowicie klasteryzacji klasyfikacji i odkrywania reguł asocjacyjnych. Dyskusja koncentrowała się głównie na jednym reprezentatywnym algorytmie dla każdego z tych zadań. Ogólnie rzecz biorąc, istnieją co najmniej dwa powody stosowania logiki rozmytej w eksploracji danych. Po pierwsze, jak wspomniano wcześniej, logika rozmyta może generować bardziej abstrakcyjne i elastyczne wzorce, ponieważ w zadaniach eksploracji danych zaangażowanych jest wiele cech ilościowych. Po drugie, precyzyjne stosowanie metryk lepiej zastąpić zestawami rozmytymi, które mogą w bardziej naturalny sposób odzwierciedlać stopień przynależności do klasy lub klastra.

WSTĘP

Obecne bazy danych mogą przechowywać kilka terabajtów dokumentów tekstowych. Głównym celem bazy danych z punktu widzenia użytkownika jest efektywne wyszukiwanie informacji. W przypadku danych tekstowych wyszukiwanie informacji dotyczy głównie selekcji i rankingu dokumentów. Kryteria selekcji mogą zawierać elementy odnoszące się do treści lub gramatyki języka. W tradycyjnych systemach zarządzania bazami danych (DBMS) manipulowanie tekstem ogranicza się do typowych funkcji manipulacji ciągami znaków, tj. dokładnego dopasowywania podciągów. Chociaż nowy standard SQL1999 umożliwia korzystanie z bardziej zaawansowanych wyrażeń regularnych, to tradycyjne podejście ma pewne istotne wady. Tradycyjne operacje na poziomie ciągów znaków są bardzo kosztowne w przypadku dużych dokumentów, ponieważ działają bez zorientowanych na zadania struktur indeksowych. Wymagane operacje zarządzania pełnotekstem należą do eksploracji tekstu, interdyscyplinarnej dziedziny przetwarzania języka naturalnego i eksploracji danych. Ponieważ tradycyjny silnik DBMS jest nieefektywny w zakresie tych operacji, systemy zarządzania bazami danych są zazwyczaj rozszerzane o specjalny moduł silnika wyszukiwania pełnotekstowego (FTS). Przedstawiamy tutaj konkretne rozwiązanie Oracle; aby usprawnić zapytania pełnotekstowe, opracowano specjalny silnik, który przygotowuje zapytania pełnotekstowe i udostępnia zestaw operatorów zapytań specyficznych dla języka i semantyki.

TŁO

Tradycyjne silniki DBMS nie są wystarczające, aby spełnić wymagania użytkowników w zakresie zarządzania danymi w postaci wolnego tekstu, ponieważ traktują całe pole tekstowe jako atom. Do efektywnej implementacji operacji manipulowania tekstem potrzebne jest specjalne rozszerzenie silnika DBMS. Na rynku istnieje duże zapotrzebowanie na wykorzystanie operacji w postaci wolnego tekstu i eksploracji tekstu, ponieważ informacje są często przechowywane w postaci wolnego tekstu. Typowe obszary zastosowań to np. analiza tekstu w systemach medycznych, analiza opinii klientów i bibliograficzne bazy danych. W takich przypadkach proste dopasowanie ciągów znaków pozwoliłoby na znalezienie tylko ułamka powiązanych dokumentów, dlatego wymagany jest silnik FST, który potrafi identyfikować podobieństwa semantyczne między terminami. Istnieje kilka alternatywnych rozwiązań dla implementacji silnika FTS. W niektórych produktach DBMS, takich jak Oracle, Microsoft SQLServer, Postgres i MySQL, zaimplementowano wbudowany moduł silnika FTS. Niektórzy dostawcy systemów DBMS rozszerzyli konfigurację DBMS o niezależny od DBMS silnik FTS. W tym segmencie głównymi dostawcami są: SPSS LexiQuest, SAS Text Miner , dtSearch i Statistica Text Miner . Rynek silników FTS jest bardzo obiecujący, ponieważ ilość informacji tekstowych przechowywanych w bazach danych stale rośnie. Według badań Meryll Lynch , 85% informacji biznesowych stanowią dokumenty tekstowe - e-maile, raporty biznesowe i badawcze, notatki, prezentacje, reklamy, wiadomości itp. - i ich udział nadal rośnie. W 2006 roku w Internecie dostępnych było ponad 20 miliardów dokumentów . Szacunkowa wielkość puli wzrasta do 550 miliardów dokumentów, jeśli uwzględnimy również dokumenty z ukrytej (lub głębokiej) sieci - np. generowane dynamicznie.

Eksploracja tekstu

Podobszarem zarządzania dokumentami, którego celem jest przetwarzanie, wyszukiwanie i analiza dokumentów tekstowych, jest eksploracja tekstu. Celem eksploracji tekstu jest odkrycie nietrywialnych lub ukrytych cech poszczególnych dokumentów lub zbiorów dokumentów. Eksploracja tekstu to zorientowana na aplikacje interdyscyplinarna dziedzina uczenia maszynowego, która wykorzystuje narzędzia i zasoby z zakresu lingwistyki obliczeniowej, przetwarzania języka naturalnego, wyszukiwania informacji i eksploracji danych. Ogólny schemat zastosowań eksploracji tekstu przedstawiono na rysunku 1 .



Dla krótkiego podsumowania eksploracji tekstu przedstawiono cztery główne obszary: ekstrakcję informacji, kategoryzację/klasyfikację tekstu, klasteryzację dokumentów i podsumowywanie.

Ekstrakcja informacji

Celem ekstrakcji informacji (IE) jest zebranie fragmentów tekstu (faktów, miejsc, osób itp.) z dokumentów istotnych dla danej aplikacji. Wyekstrahowane informacje mogą być przechowywane w ustrukturyzowanych bazach danych. Kategoryzacja tekstu (IE) jest zazwyczaj stosowana w procesach, w których z tekstów należy pobierać statystyki, analizy, podsumowania itp. Kategoryzacja tekstu obejmuje następujące podzadania:

o rozpoznawanie jednostek nazwanych - rozpoznawanie określonych typów jednostek w tekście swobodnym,
o rozwiązywanie koreferencji - identyfikacja fragmentów tekstu odnoszących się do tej samej jednostki,
o identyfikacja ról i ich relacji - określanie ról zdefiniowanych w szablonach zdarzeń.

Kategoryzacja tekstu

Techniki kategoryzacji tekstu (TC) mają na celu sortowanie dokumentów do danego systemu kategorii . W TC zazwyczaj model klasyfikatora jest budowany na podstawie zawartości zestawu przykładowych dokumentów, który następnie jest używany do klasyfikowania dokumentów niewidocznych. Typowe przykłady zastosowań TC obejmują między innymi:

o filtrowanie dokumentów - takie jak np. filtrowanie spamu lub kanałów informacyjnych ;
o routing dokumentów patentowych - wyznaczanie ekspertów w danych dziedzinach ;
o wspomagana kategoryzacja - pomoc ekspertom dziedzinowym w ręcznej kategoryzacji poprzez cenne sugestie ,
o automatyczne generowanie metadanych ,

Klastrowanie dokumentów

Metody klasteryzacji dokumentów (DC) grupują elementy zbioru dokumentów na podstawie ich podobieństwa. W tym przypadku dokumenty są zazwyczaj grupowane na podstawie ich zawartości. W zależności od charakteru wyników, można zastosować metody partycjonowania i hierarchicznego klasteryzacji. W pierwszym przypadku nie ma wyraźnej relacji między klastrami, podczas gdy w drugim przypadku tworzona jest hierarchia klastrów. DC jest stosowane np. do:

o grupowania wyników wyszukiwania (internetowego) w celu ułatwienia użytkownikom lokalizowania informacji,
o poprawy szybkości wyszukiwania informacji w oparciu o przestrzeń wektorową ,
o zapewnienia narzędzia nawigacyjnego podczas przeglądania zbioru dokumentów .

Podsumowanie

Podsumowanie tekstu ma na celu automatyczne generowanie krótkich i zrozumiałych streszczeń dokumentów. Algorytmy ekstrakcji tekstu tworzą podsumowanie poprzez wyodrębnienie odpowiednich fraz opisowych (zazwyczaj zdań) z tekstu oryginalnego, podczas gdy podsumowania generowane metodami abstrakcji mogą również zawierać tekst syntetyczny. Typowe obszary zastosowań podsumowań rozciągają się od wyszukiwania internetowego po dowolne systemy zarządzania dokumentami

SILNIKI WYSZUKIWANIA PEŁNOTEKSTOWEGO (FTS)

Wyszukiwanie pełnotekstowe

Na podstawie literatury (Maier, 2001, Curtmola, 2005) efektywny silnik FTS powinien obsługiwać kilka funkcji zapytań. Najprostszą operacją jest zapytanie oparte na ciągu znaków, które pobiera teksty dokładnie pasujące do ciągu zapytania. W niektórych przypadkach ważnym czynnikiem jest również pozycja słów kluczowych w dokumencie. Najprostsza forma dopasowania opartego na podobieństwie wykorzystuje funkcję edit-distance. Kolejną operacją jest zapytanie oparte na treści, w którym podobieństwo jest definiowane na poziomie semantycznym. Silnik FTS powinien również obsługiwać operatory specyficzne dla gramatyki (a zatem i języka) (np. stemming). Najwyższy poziom wyszukiwania tekstowego działa z dopasowaniem semantycznym (sąsiedztwo oparte na tezaurusie, generalizacja słowa, specjalizacja, synonimy). Z praktycznego punktu widzenia, efektywne wykonywanie zapytań jest również bardzo ważne. Ze względu na heterogeniczność puli źródeł, obsługa różnych formatów dokumentów jest kluczowym wymogiem. Minimalne wykorzystanie innych zasobów zapewnia niezależne, elastyczne rozwiązanie. Z punktu widzenia rozwoju oprogramowania, otwarty, ustandaryzowany interfejs jest dobrą inwestycją. Aby zapewnić łatwą w zarządzaniu i zrozumiałą odpowiedź, kluczowe jest efektywne rankingowanie zbioru wyników . Dostępne obecnie produkty i systemy testowe tylko częściowo spełniają powyższe wymagania.

Struktura ogólnego silnika FTS

Silniki FTS są strukturalnie podobne do systemów baz danych: przechowują dane i metadane; Ich celem jest zapewnienie efektywnego wyszukiwania informacji (Microsoft, 2007; Oracle Text, 2007). Ponieważ przetwarzanie zapytania pełnotekstowego wymaga kilku odrębnych kroków, silniki FTS zazwyczaj mają strukturę modułową (rysunek 2).



Moduł ładujący ładuje dokumenty do wspólnego obszaru przejściowego, do wspólnej reprezentacji. W kolejnych krokach elementy danych są również transformowane do wspólnego formatu. Załadowane dokumenty sąprzechowywane w jednostce magazynu danych. Przetwarzanie dokumentów składa się z kilku kroków. Jednostka sekcji musi odkryć większą wewnętrzną strukturę logiczną dokumentów. Moduł dzielenia słów analizuje tekst na mniejsze jednostki składniowe, takie jak akapity, zdania i terminy (słowa). W celu zmniejszenia długości i złożoności tekstu wykonywanych jest kilka kroków wstępnego przetwarzania. Najpierw stosowany jest moduł filtrujący, który odrzuca nieistotne słowa (słowa ignorowane, słowa ignorowane). Następnie jednostka rdzeniowania generuje formę rdzenia dla każdego słowa. W tle leksykon języka wspiera specyficzne dla języka kroki redukcji.Ten leksykon zawiera gramatykę obsługiwanych języków oraz listę słów kluczowych. Tezaurus to specjalny leksykon, który przechowuje terminy zorganizowane w formie grafu w oparciu o ich relacje semantyczne. Aby zapewnić efektywne zarządzanie terminami, tworzonych jest kilka rodzajów indeksów. Jednostka indeksująca zarządza różnymi indeksami dokumentów i terminów, co umożliwia efektywny dostęp do wystąpień terminów. Po stronie front-end, preprocesor zapytań przekształca zapytanie użytkownika do formatu wewnętrznego. Format ten jest przetwarzany przez moduł dopasowujący zapytania, co skutkuje zestawem pasujących dokumentów. Wyszukiwarka może zostać rozszerzona o moduł eksploracji tekstu, który wykonuje operacje eksploracji danych, takie jak klastrowanie lub klasyfikacja. Aby zapewnić dokładniejszą odpowiedź, moduł doprecyzowujący zapytania przetwarza informacje zwrotne dotyczące istotności. Lista pasujących dokumentów jest przesyłana potokowo do modułu rankingowego. Moduł eksportera generuje ostateczny format uporządkowanego zestawu dokumentów. Jak wspomniano, systemy baz danych wykorzystują indeksy do szybkiego dostępu do elementów danych. W przypadku wyszukiwania pełnotekstowego indeks odwrócony jest najefektywniejszą strukturą indeksowania . W prostym indeksie odwróconym kluczem indeksu jest termin. Każdy klucz jest powiązany z parą (df, dl). Gdzie df to liczba dokumentów zawierających klucz, a dl to lista dokumentów zawierających klucz. Każdy wpis na liście zawiera identyfikator dokumentu i wartość częstotliwości w dokumencie. Indeks odwrócony oparty na pozycji różni się od wersji prostej tym, że lista odpowiadająca dokumentowi zawiera również pozycje danego terminu w tekście.

Interfejs FTS Engine w Oracle Text

Funkcjonalność FTS w Oracle Text można aktywować za pomocą niektórych rozszerzeń języka SQL oraz proceduralnych pakietów SQL. Oracle Text obsługuje cztery typy indeksów:

o Indeks typu CONTEXT: indeks odwrócony dla długich dokumentów;
o Indeks typu CTXCAT: do obsługi indeksowania opartego na treści i atrybutach dla krótszych dokumentów;
o Indeks typu CTXRULE: reguły klastrowania dokumentów;
o Indeks typu CTXPATH: indeksowanie dokumentów XML.

Moduł stemmingu obsługuje tylko dwa języki: angielski i francuski. W zapytaniach operator CONTAINS obsługuje następujące tryby dopasowania:

o słowo kluczowe: dopasowanie dokładne;
o AND, OR, NOT: operatory boolowskie;
o NEAR (słowo kluczowe1, słowo kluczowe2): słowa kluczowe powinny występować w zbliżonych pozycjach w dokumencie;
o BT (słowo kluczowe): generalizacja słowa kluczowego;
o NT (słowo kluczowe): specjalizacja słowa kluczowego;
o REL(słowo kluczowe): słowa w tezaurusie w odniesieniu do słowa kluczowego;
o SYN(słowo kluczowe): synonimy słowa kluczowego;
o $słowo kluczowe: słowa o tym samym temacie;
o !słowo kluczowe: słowa o tej samej wymowie;
o ABOUT słowa kluczowe: słowa należące do danego tematu;
o FUZZY(słowo kluczowe): słowa, które są zbliżone do słowa kluczowego pod względem odległości edycyjnej;
o WITHIN (sekcja): dopasowanie jest ograniczone do danej sekcji dokumentów. Poniższy przykład pobiera dokumenty zawierające słowa o podobnym znaczeniu jak "jedzenie":SELECT opis FROM książki WHERE CONTAINS (opis, ′NT(jedzenie,1)′) > 0; Oracle Text obsługuje trzy metody partycjonowania dokumentów (kategoryzacja i klasteryzacja). Ręczna kategoryzacja pozwala użytkownikowi na wprowadzenie par słowo kluczowe-kategoria. Automatyczna kategoryzacja działa, jeśli podany jest zestaw szkoleniowy par dokument-kategoria. Metoda klastrowania automatycznie określa klastry w zestawie dokumentów na podstawie ich podobieństwa. Aby zapewnić dopasowanie semantyczne dla dowolnej domeny, użytkownicy mogą utworzyć własny tezaurus.

PRZYSZŁE TRENDY

Naszym zdaniem istnieją trzy główne obszary, w których rola silnika FTS powinna zostać ulepszona w przyszłości: wyszukiwarki internetowe, wyszukiwanie informacji oparte na ontologii oraz zarządzanie dokumentami XML. Głównym standardem wyszukiwania dokumentów XML jest obecnie język XQuery. Standard ten jest bardzo elastyczny w zakresie wyboru ustrukturyzowanych elementów danych, ale nie posiada specjalnych funkcji dla części nieustrukturyzowanej. W (Botev, 2004; Curtmola, 2005) zaproponowano rozszerzenie XQuery o funkcjonalność pełnotekstową. Rozszerzony język zapytań nosi nazwy TeXQuery i GalaTex. Język zawiera bogaty zestaw złożonych prymitywów pełnotekstowych, takich jak dopasowywanie fraz, odległość bliskości, stemming i tezaurusy. Połączenie zapytań opartych na strukturze i treści jest dogłębnie badane z teoretycznego punktu widzenia w (Amer, 2004). Efektywność wyszukiwania informacji można poprawić poprzez rozszerzenie dodatkowych informacji semantycznych. Projekt ALVIS (Luu, 2006) ma na celu zbudowanie rozproszonej, semantycznej wyszukiwarki peer-to-peer. Sieć peer-to-peer to samoorganizujący się system do zdecentralizowanego zarządzania danymi w środowiskach rozproszonych. Podczas operacji zapytania, partner rozgłasza żądania wyszukiwania w sieci. Partner może być przypisany do podzbioru elementów danych. Kluczowym elementem redukcji kosztów jest zastosowanie specjalnego typu indeksu w węzłach. Indeks zawiera, oprócz pojedynczych wpisów słów kluczowych, również encje dla kluczy złożonych o wysokich wartościach rozróżniających. Bardzo ważnym obszarem zastosowań wyszukiwania pełnotekstowego jest sieć WWW. Cechą szczególną wyszukiwania internetowego jest to, że użytkownicy stosują głównie proste zapytania. Tylko 10% zapytań wykorzystuje złożone prymitywy pełnotekstowe, takie jak operatory Boole′a, stemming lub dopasowanie rozmyte. Eastman (2003) zbadał przyczyny pomijania operatorów złożonych i doszedł do wniosku, że ich zastosowanie nie poprawia znacząco wyników wyszukiwania. Wydajność jest kluczowym czynnikiem w wyszukiwarkach internetowych. Celem badań jest ulepszenie mechanizmu indeksowania wyszukiwarek internetowych w celu zapewnienia wydajnych operatorów wyszukiwania pełnotekstowego.

WNIOSKI

Informacje są przechowywane w internecie i na komputerach głównie w formacie tekstu swobodnego. Obecne bazy danych umożliwiają przechowywanie i zarządzanie ogromnymi zbiorami dokumentów. Źródła danych tekstu swobodnego wymagają specyficznych operacji wyszukiwania. Systemy zarządzania bazami danych zazwyczaj zawierają oddzielną wyszukiwarkę pełnotekstową do wykonywania podstawowych operacji wyszukiwania pełnotekstowego. Ogólnie rzecz biorąc, obecne wyszukiwarki FTS obsługują następujące funkcjonalności: dopasowanie ścisłe, dopasowanie oparte na pozycji, dopasowanie oparte na podobieństwie (dopasowanie rozmyte), dopasowanie oparte na gramatyce (stemming) oraz dopasowanie oparte na semantyce (dopasowanie oparte na synonimach i tezaurusach). Wykazano, że przeciętny użytkownik potrzebuje dodatkowej pomocy, aby wykorzystać zalety tych dodatkowych operatorów. Aktualne badania koncentrują się na rozwiązaniu problemu uwzględnienia nowych formatów dokumentów, dostosowaniu zapytania do zachowań użytkownika oraz zapewnieniu wydajnej implementacji wyszukiwarki FTS.

WSTĘP

Tradycyjnie, zastosowanie sieci neuronowej do rozwiązania problemu wymagało wykonania pewnych kroków przed uzyskaniem pożądanej sieci. Niektóre z tych kroków to wstępne przetwarzanie danych, wybór modelu, optymalizacja topologii, a następnie szkolenie. Zazwyczaj poświęca się dużo czasu obliczeniowego i interakcji z człowiekiem na wykonanie każdego zadania, a w szczególności na optymalizację topologii i szkolenie sieci. Pojawiło się wiele propozycji zmniejszenia nakładu pracy niezbędnego do wykonania tych zadań i zapewnienia ekspertom solidnej metodologii. Na przykład Giles i inni (1995) przedstawiają konstruktywną metodę iteracyjnej optymalizacji topologii sieci rekurencyjnej. Inne metody starają się zmniejszyć złożoność struktury sieci poprzez usunięcie zbędnych węzłów i połączeń sieciowych, jak w (Morse, 1994). W ostatnich latach algorytmy ewolucyjne okazały się obiecującymi narzędziami do rozwiązania tego problemu, przy czym w literaturze istnieje wiele konkurencyjnych podejść. Na przykład Blanco i inni (2001) zaproponowali algorytm genetyczny typu master-slave do trenowania (algorytm master) i optymalizacji rozmiaru sieci (algorytm slave). Aby uzyskać ogólny pogląd na problem i wykorzystanie algorytmów ewolucyjnych do trenowania i optymalizacji sieci neuronowych, odsyłamy czytelnika do (Yao, 1999). Chociaż literatura na temat algorytmów genetycznych i sieci neuronowych jest bardzo obszerna, chcielibyśmy zwrócić uwagę na niedawną popularność optymalizacji wielokryterialnej , szczególnie w rozwiązywaniu problemu jednoczesnego trenowania i optymalizacji topologii sieci neuronowych. Metody te okazały się odpowiednie do tego zadania w poprzednich pracach, chociaż większość z nich jest proponowana dla modeli sprzężenia w przód. Próbują one zoptymalizować strukturę sieci (liczbę połączeń, ukryte jednostki lub warstwy), jednocześnie trenując sieć. Algorytmy wielokryterialne mogą zapewnić istotne korzyści w jednoczesnym szkoleniu i optymalizacji sieci neuronowych: mogą wymusić wyszukiwanie w celu zwrócenia zestawu optymalnych sieci zamiast jednej; są w stanie przyspieszyć proces optymalizacji; mogą być preferowane w stosunku do procedury agregacji wag w celu rozwiązania problemu regularyzacji w sieciach neuronowych; i są bardziej odpowiednie, gdy projektant chce połączyć różne miary błędów w celu szkolenia.

TŁO

Algorytmy wielokryterialne zyskały popularność w ostatnich latach, rozwiązując problem jednoczesnego treningu i optymalizacji topologii sieci neuronowych, ze względu na innowacje, jakie mogą one w tym zakresie zapewnić. Niektórzy autorzy rozwiązywali ten problem poprzez ewolucję pojedynczych zespołów, na przykład w DIVACE-II , który również implementuje różne poziomy koewolucji. W innych pracach sieci są w pełni ewoluowane, a operatory ewolucyjne są zaprojektowane do radzenia sobie zarówno z treningiem, jak i optymalizacją struktury. Niektórzy autorzy rozwiązywali problem optymalizacji struktury, dążąc do zmniejszenia liczby neuronów sieciowych lub liczby połączeń sieciowych. W pierwszych metodach optymalizacja jest łatwiejsza, ponieważ kodyfikacja sieci zawiera mniejszą liczbę stopni swobody niż w ostatnich metodach; Mają jednak wadę w tym sensie, że uzyskane sieci są w pełni połączone. Z drugiej strony, metody z drugiej kolejności starają się zmniejszyć liczbę połączeń, ale nie gwarantują, że liczba węzłów sieciowych będzie minimalna. Niemniej jednak wyniki eksperymentalne wykazały, że sieci uzyskane za pomocą tych propozycji mają niewielki rozmiar . Hybrydyzacja wielokryterialnych algorytmów ewolucyjnych z tradycyjnymi algorytmami uczenia opartymi na gradiencie również dała obiecujące rezultaty. Podczas gdy algorytm ewolucyjny szeroko eksploruje przestrzeń rozwiązań, algorytmy oparte na gradiencie są w stanie skierować poszukiwania obiecujących obszarów w trakcie ewolucji i odpowiednio wykorzystać rozwiązania. Ta hybrydyzacja jest zazwyczaj przeprowadzana poprzez włączenie metody uczenia opartej na gradiencie jako lokalnego operatora wyszukiwania w procesie ewolucyjnym. Następnie lokalny operator wyszukiwania jest stosowany po mutacji, a przed oceną rozwiązań. Przykładami są system MPANN opracowany przez H.A. Abbass (2001) oraz prace Y. Jin (2006). W następnej sekcji badamy różne aspekty dotyczące wielokryterialnej optymalizacji sieci neuronowych. Konkretnie, badamy cele, które mają zostać osiągnięte w algorytmie wielokryterialnym, oraz stosowane algorytmy wielokryterialne. Koncentrujemy naszą analizę na rekurencyjnych sieciach neuronowych , ponieważ modele te charakteryzują się wysoką złożonością ze względu na rekurencyjność. Eksperymenty zilustrowano na problemach predykcji szeregów czasowych, ponieważ ten typ problemów ma wiele zastosowań w wielu obszarach badań i przedsiębiorstw, a użyte modele neuronowe nadają się do tego zastosowania, jak sugerują wcześniejsze prace.

WIELOCELOWE ALGORYTMY EWOLUCYJNE DO SZKOLENIA I OPTYMALIZACJI SIECI NEURONOWYCH

Najnowsze wielocelowe algorytmy ewolucyjne opierają się na koncepcji dominacji Pareto jako kryterium określania, czy rozwiązanie jest optymalne, czy nie. Niech F(s)=(f₁(s), f₂(s),…, f_k(s)) będzie zbiorem k celów do osiągnięcia, a s₁ i s₂ dwoma rozwiązaniami. W problemie minimalizacji mówi się, że s2 jest zdominowane przez s1 wtedy i tylko wtedy, gdy:



Rozwiązania, które nie są nominowane przez żadne inne rozwiązanie, nazywane są zbiorem niezdominowanym lub granicą Pareto. Celem każdego algorytmu wielokryterialnego jest znalezienie rozwiązań na granicy Pareto. Zatem wybór celów, które mają zostać osiągnięte w algorytmie wielokryterialnym, jest kluczowym aspektem, ponieważ będą one wykorzystywane do kierowania poszukiwaniami w przestrzeni poszukiwań w celu uzyskania optymalnych rozwiązań. Jednak im większa liczba celów, tym większa złożoność przestrzeni poszukiwań. W niniejszej pracy podejmujemy próbę trenowania i optymalizacji rozmiaru sieci Elmana dla problemów predykcji szeregów czasowych. Ten typ sieci ma warstwę wejściową, warstwę wyjściową i warstwę ukrytą. Dane szeregów czasowych są dostarczane w czasie do wejść sieci, a celem jest wyjście sieci, aby zapewnić przyszłe wartości szeregów czasowych na wyjściu. Połączenia rekurencyjne znajdują się w warstwie ukrytej, tak że wyjście neuronu ukrytego w czasie t jest również wejściem dla wszystkich neuronów ukrytych w czasie t+1.



W przypadku problemu optymalizacji i uczenia sieci neuronowej rozważamy trzy cele do osiągnięcia (patrz równania (2)-(4)). Cel f₁(s) ma na celu minimalizację błędu sieci, podczas gdy f₂(s) służy do optymalizacji liczby neuronów ukrytych, a f₃(s) - liczby połączeń sieci. W równaniu (2), T to liczba wzorców treningowych, Y(t) to pożądany wynik dla wzorca t, a O(t) to wynik sieci. W równaniu (3), h(s) to liczba neuronów ukrytych dla sieci s; a n(s) to liczba połączeń sieci w równaniu (4). Innym problemem związanym z celami jest kodyfikacja sieci. Na przykład w pracach takich jak (Abbass, 2001) cele do osiągnięcia to (f1(s), f2(s)), uzyskanie w pełni spójnych sieci. W tym przypadku reprezentacja sieci próbuje kodyfikować neurony jako wektor binarny, a wagi sieci w macierzy o wartościach rzeczywistych. W innych pracach, takich jak (Jin 2006), połączenia sieciowe są kodowane w macierzy binarnej, a waga sieci w macierzy o wartościach rzeczywistych, ponieważ optymalizowane cele to (f₁(s),f₃(s)). Jeśli rozważalibyśmy optymalizację wszystkich celów, reprezentacja powinna zawierać strukturę sieci (ukryte neurony i połączenia) oraz wagi. W naszej propozycji liczba neuronów sieciowych jest kodowana wartością całkowitą zgodnie z wytycznymi , połączenia są kodowane w wektorze binarnym, a wagi sieci w wektorze o wartościach rzeczywistych. Rysunek 1 przedstawia przykład kodyfikacji sieci Elmana w rozwiązanie, gdzie V_ij to wagi sieci od wejścia j do ukrytego neuronu i, U_ir to waga rekurencyjna od neuronu r do neuronu i, a W_oi to wagi od ukrytego neuronu i do neuronu wyjściowego o.



Połączenie sieciowe jest aktywne, jeśli odpowiadający mu gen ma wartość 1. W przeciwnym razie połączenie jest nieaktywne. Operatory ewolucyjne, takie jak crossover i mutacja, powinny uwzględniać dwa różne obszary w rozwiązaniu: rekombinację strukturalną/mutację oraz rekombinację genetyczną/mutację. Rekombinacja genetyczna jest powiązana z obszarem wag sieci, podczas gdy rekombinacja strukturalna dotyczy topologii sieci. Dodatkowo, można uwzględnić operator wyszukiwania lokalnego, aby poprawić wydajność sieci lokalnie w obszarze, który kodyfikuje wagi sieci, jak zasugerowano w poprzedniej sekcji. W naszych eksperymentach wykorzystaliśmy prostą rekombinację, która generuje dwoje dzieci od dwojga rodziców, bez rekombinacji strukturalnej: Przetestowaliśmy, że rekombinacja strukturalna może zapewnić wysokie wykorzystanie przestrzeni rozwiązań, a presja selekcyjna wywoływana przez cele do osiągnięcia może następnie spowodować przedwczesną konwergencję. Z drugiej strony, dla mutacji uwzględniliśmy trzy prawdopodobieństwa, ponieważ mutacja strukturalna może mieć duży wpływ na populację rozwiązań: Mutacja strukturalna jest wybierana z prawdopodobieństwem p₁, a mutacja genetyczna z prawdopodobieństwem 1-p₁. W przypadku mutacji strukturalnej liczba ukrytych neuronów jest zmieniana z prawdopodobieństwem p₂; w przeciwnym razie połączenia aktywne/nieaktywne są mutowane. Wreszcie, gen jest zmieniany z prawdopodobieństwem p₃. Rysunek 2 przedstawia przykład crossovera, a rysunek 3 przedstawia przykład mutacji strukturalnej dla liczby ukrytych neuronów.





W tym ostatnim przypadku rozwiązanie rozrasta się do trzech ukrytych neuronów i generowane są nowe geny. Wartości tych genów są losową liczbą w granicach genu. Na rysunku 3 geny te można rozpoznać za pomocą symbolu. W ramach eksperymentów staramy się zbadać korzyści wynikające z uwzględnienia większej liczby celów do osiągnięcia w algorytmie wielokryterialnym oraz efekty algorytmu ewolucyjnego. Aby zilustrować nasze wyniki, wybraliśmy dwa szeregi czasowe o charakterze społeczno-ekonomicznym do prognozowania: ewolucję populacji Stanów Zjednoczonych w latach 1950-2004 w ujęciu miesięcznym (USPop) oraz ewolucję wahań kursu euro/dolar amerykański w latach 1995-2004 w ujęciu miesięcznym (EurDol). 80% danych służy do trenowania, a pozostałe 20% do testowania. Oba szeregi czasowe można pobrać bezpłatnie ze strony http://www.economagic.com. Parametry sieci w naszych eksperymentach są ograniczone liczbą ukrytych neuronów, od 3 do 12. Sieci mają jedno wejście dla wartości szeregu czasowego w czasie t i jedno wyjście dla wartości szeregu czasowego w czasie t+1, które mają być przewidywane. Przeprowadzono 30 eksperymentów z algorytmami wielokryterialnymi opartymi na algorytmach NSGA2 i SPEA2. NSGA2 i SPEA2 oznaczamy jako algorytmy optymalizujące cele (f₁(s), f₂(s)), a NSGA2.connect i SPEA2.connect jako algorytmy optymalizujące (f₁(s), f₂(s), f₃(s)). Kryterium zatrzymania jest ocena 10 000 rozwiązań, a wielkość populacji wynosi 50. Parametry mutacji to (p₁, p₂, p₃)=(0,5, 0,5, 0,1), a zakres dla genów zawierających wagi sieciowe wynosi [-5,0, 5,0]. Wykorzystaliśmy selekcję turniejową binarną, heurystyczną krzyżówkę Wrighta i mutację przemieszczenia dla operatorów ewolucyjnych. Rysunek 4 przedstawia rozkład wydajności sieci neuronowych uzyskanych w granicach Pareto dla 30 eksperymentów, w każdym zestawie danych.



Dodatkowo, Tabela 1 przedstawia najlepsze uzyskane granice Pareto, gdzie Kolumna 1 przedstawia algorytm, kolumny 2 i 5 ujawniają liczbę ukrytych neuronów, kolumny 3 i 6 opisują liczbę połączeń sieciowych, a kolumny 4 i 7 opisują średni błąd kwadratowy (MSE) w treningu.



Możemy zauważyć, że SPEA2.connect uzyskał granicę Pareto szerszą niż NSGA2.connect w obu problemach. W niektórych sytuacjach fakt ten może być pożądany, ponieważ dysponujemy większym zestawem optymalnych sieci, z których moglibyśmy wybrać najlepszą sieć do rozwiązania naszego problemu. Z drugiej strony, rysunki a i b sugerują, że uwzględnienie optymalizacji połączeń sieciowych w metodzie wielokryterialnej może przynieść gorsze rezultaty. W obu problemach najlepsze rozwiązania zapewnia algorytm NSGA2, który zwraca w pełni spójne sieci. Ten sam algorytm, który optymalizuje również liczbę połączeń, NSGA2.connect, zapewnia sieciom minimalny rozmiar, ale ich wydajność jest niższa. W przypadku algorytmów opartych na SPEA2, możemy zauważyć, że SPEA2.connect jest mniej odpornym algorytmem, ponieważ rozkład w MSE jest najszerszy. Jednak wykres pudełkowy pokazuje, że najlepsze rozwiązania tej metody mogą być podobne do tych z NSGA2. Fakt ten sugeruje, że możemy napotkać mniejsze sieci wykorzystujące trzy cele w SPEA2.connect, ale poświęcające pewne ulepszenia wydajności sieci i poświęcające więcej czasu obliczeniowego na uzyskanie odpowiedniego rozwiązania. Co więcej, sieci uzyskane z uwzględnieniem celu f₃(s) w procesie optymalizacji mają bardzo niski rozmiar w porównaniu z w pełni połączonymi sieciami z SPEA2 i NSGA2.

TRENDY NA PRZYSZŁOŚĆ

W poprzednim rozdziale zbadaliśmy, że uwzględnienie większej liczby celów optymalizacji sieci może zmniejszyć jej rozmiar, chociaż uzyskana wydajność jest gorsza. Jest to powszechne, ponieważ im więcej celów do optymalizacji, tym bardziej złożona jest przestrzeń poszukiwań, a tym samym znalezienie optymalnych rozwiązań. Hybrydyzacja wielokryterialnych algorytmów ewolucyjnych z metodami programowania nieliniowego w celu skierowania przestrzeni poszukiwań do obiecujących obszarów okazała się skuteczna w pracach, które proponują mniejszą liczbę celów optymalizacji. W przypadku badanym w tej pracy, ulepszenia tych procedur mogłyby być lepsze, ponieważ rozmiar przestrzeni poszukiwań jest szerszy. Innym ważnym problemem są badania ewolucji z uwzględnieniem różnorodności i konwergencji: stosowane cele zazwyczaj wprowadzają wysoką presję selekcyjną w populacji, a zwłaszcza cele optymalizacji topologicznej. Można to rozwiązać, wprowadzając komponenty do procesu ewolucyjnego, aby kontrolować równowagę różnorodności/konwergencji, a tym samym usprawniając proces wyszukiwania oraz eksplorację/eksploatację przestrzeni rozwiązań. Innym interesującym kierunkiem prac jest uwzględnienie celów poprawy innych właściwości sieci neuronowych, takich jak tolerancja szumów czy generalizacja. Na przykład, problem ten został zasugerowany w pracy, gdzie wprowadzono dodatkowy cel, jakim jest poprawa generalizacji sieci sprzężenia zwrotnego w klasyfikacji binarnej.

WNIOSKI

W niniejszej pracy zbadaliśmy zalety i wady uczenia wielokryterialnego i pełnej optymalizacji topologicznej rekurencyjnych sieci neuronowych. Przetestowaliśmy te metody w problemach predykcji szeregów czasowych i porównaliśmy je z metodami, które optymalizują również liczbę połączeń. Ogólnie rzecz biorąc, wszystkie algorytmy rozwiązały te problemy prawidłowo. Badane metody zapewniają sieciom minimalną liczbę ukrytych jednostek i połączeń, a wydajność sieci jest dobra. Jednak metody te mogą dawać gorsze wyniki niż te, które optymalizują jedynie liczbę ukrytych neuronów i zapewniają sieci w pełni połączone. Wykorzystując dłuższy czas obliczeniowy, wyniki algorytmów optymalizujących topologię pod względem ukrytych neuronów i połączeń mogą być konkurencyjne, zapewniając sieciom wydajność zbliżoną do technik, które nie optymalizują liczby połączeń sieciowych. Co więcej, metody te mają tę zaletę, że rozmiar sieci jest bardzo niski w porównaniu z sieciami w pełni połączonymi.

WSTĘP

Rzeczywiste problemy optymalizacyjne są często zbyt złożone, aby można je było rozwiązać metodami analitycznymi. Algorytmy ewolucyjne, klasa algorytmów zapożyczających paradygmaty z natury, są szczególnie dobrze dostosowane do rozwiązywania takich problemów. Algorytmy te to stochastyczne metody optymalizacji, które zyskały ostatnio ogromną popularność, ponieważ są metodami bezpochodnymi, nie są tak podatne na uwięzienie w minimach lokalnych (ponieważ opierają się na populacji) i okazały się skuteczne w przypadku wielu złożonych problemów optymalizacyjnych. Chociaż algorytmy ewolucyjne konwencjonalnie koncentrowały się na optymalizacji funkcji pojedynczego celu, większość praktycznych problemów inżynieryjnych ma z natury charakter wielokryterialny. Wielokryterialna optymalizacja ewolucyjna to stosunkowo nowy i szybko rozwijający się obszar badań w obliczeniach ewolucyjnych, który koncentruje się na sposobach rozwiązania tych problemów. W tym rozdziale przedstawiamy przegląd niektórych z najważniejszych problemów optymalizacji wielokryterialnej .

TŁO

Algorytmy genetyczne (GA) są prawdopodobnie jednym z najpowszechniejszych podejść do optymalizacji ewolucyjnej. Algorytmy te utrzymują populację rozwiązań kandydujących w każdym pokoleniu, zwanych chromosomami. Każdy chromosom odpowiada punktowi w przestrzeni poszukiwań algorytmu. Algorytmy te wykorzystują trzy operatory darwinowskie - selekcję, mutację i krzyżowanie do przeprowadzania poszukiwań (GTA) . Każde pokolenie jest ulepszane poprzez systematyczne usuwanie gorszych rozwiązań, a zachowywanie lepszych, w oparciu o miarę dopasowania. Ten proces nazywa się selekcją. Selekcja binarna turniejowa i selekcja koła ruletki to dwie popularne metody selekcji. W selekcji binarnej turniejowej dwa rozwiązania, zwane rodzicami, są losowo wybierane z populacji ze zwracaniem, a ich dopasowanie jest porównywane, podczas gdy w selekcji koła ruletki prawdopodobieństwo wybrania rozwiązania jest wprost proporcjonalne do jego dopasowania. Po selekcji stosowany jest operator krzyżowania. Zwykle dwa rozwiązania macierzyste z bieżącego pokolenia są wybierane losowo w celu wytworzenia potomstwa, które zapełni następną generację rozwiązań. Potomstwo jest tworzone z rozwiązań macierzystych w taki sposób, aby nosiło cechy obu. Chromosomy potomne są probabilistycznie poddawane innemu operatorowi zwanemu mutacją, który polega na dodaniu małych losowych zaburzeń. Mutacji ulega tylko kilka rozwiązań. Strategie Ewolucyjne (ES) stanowią kolejną klasę algorytmów ewolucyjnych, która jest blisko spokrewniona z algorytmami genetycznymi i również wykorzystuje podobne operatory. Optymalizacja Roju Cząstek (PSO) to nowsze podejście. Jest ono modelowane na podstawie zachowań społecznych organizmów, takich jak stado ptaków lub ławica ryb, i dlatego jest jedynie luźno klasyfikowane jako podejście ewolucyjne. Każde rozwiązanie w populacji w PSO, zwane cząstką, ma unikalną pozycję w przestrzeni poszukiwań. W każdym pokoleniu pozycja każdego przedmiotu jest aktualizowana poprzez dodanie do niego własnej elocity cząstki. Prędkość cząstki, wektor, jest następnie zwiększana w kierunku najlepszego położenia napotkanego w historii cząstki (nazywanego najlepszym położeniem indywidualnym), a także najlepszego położenia w bieżącej iteracji (nazywanego najlepszym położeniem globalnym).

Algorytmy ewolucyjne optymalizacji wielocelowej

Optymalizacja wielocelowa

W przypadku problemów optymalizacyjnych z wieloma celami nie można zastosować konwencjonalnych teorii optymalności. Zamiast tego stosuje się koncepcje dominacji i optymalności Pareto. Bez utraty ogólności założymy, że problem optymalizacji obejmuje jednoczesną minimalizację tylko kilku celów. Jeśli te funkcje celu to f_i(.), i = 1,…,M, rozwiązanie x dominuje nad innym rozwiązaniem y wtedy i tylko wtedy, gdy dla każdego i, f_i(x) ≤ f_i(y) przy czym co najmniej jedna z nierówności jest ostra. Innymi słowy, x dominuje nad y wtedy i tylko wtedy, gdy x jest tak samo dobre jak y dla wszystkich celów i lepsze od n co najmniej o jeden. Ta zależność jest zapisana jako x ?y . W zbiorze wszystkich dopuszczalnych rozwiązań, ten podzbiór, którego elementy nie są zdominowane przez żaden inny element w zbiorze, nazywany jest zbiorem Pareto. Innymi słowy, jeśli S jest przestrzenią poszukiwań, zbiór Pareto P jest dany wzorem:



. Obraz zbioru Pareto P w M-wymiarowej przestrzeni funkcji celu nazywany jest frontem Pareto, F. Zatem,

F={f₁(x),f₂(x),…f_M(x)|x ∈P}

Celem algorytmu optymalizacji wielokryterialnej jest dwojakie. Po pierwsze, jego wynik, zbiór niezdominowanych rozwiązań w populacji, musi być jak najbardziej zbliżony do prawdziwego frontu Pareto. Ta cecha nazywa się zbieżnością. Po drugie, oprócz dobrej konwergencji, wielokryterialny algorytm ewolucyjny powinien również generować rozwiązania, które próbkują front w mniej więcej regularnych odstępach czasu, co jest cechą zazwyczaj określaną jako różnorodność. Wyniki, w których rozwiązania są skupione w kilku obszarach frontu, podczas gdy inne obszary są pomijane lub słabo próbkowane, nie są pożądane. Rysunek 1 ilustruje koncepcje dobrej konwergencji i różnorodności.



Aby poradzić sobie z zadaniami optymalizacji wielokryterialnej, algorytm ewolucyjny musi być wyposażony w możliwość rozróżniania rozwiązań, wykorzystując konwergencję lub różnorodność jako kryterium porównania. W przypadku stosowania konwergencji, większość współczesnych algorytmów ewolucyjnych wykorzystuje jeden z dwóch podstawowych schematów rankingowych, pierwotnie zaproponowanych przez Goldberga . Pierwszy z nich to metoda, którą będziemy tutaj nazywać liczeniem dominacji. W populacji rozwiązań rangą dowolnego rozwiązania jest liczba innych rozwiązań w populacji, które je dominują. Oczywistym jest, że niezdominowanym rozwiązaniom w populacji przypisuje się liczbę zerową. Drugie podejście będzie nazywane sortowaniem niezdominowanym. W tym przypadku każdemu rozwiązaniu w populacji przypisuje się rangi w taki sposób, że rozwiązania o tej samej randze nie dominują nad sobą, każde rozwiązanie ma przypisaną niższą rangę niż inne, nad którym dominuje, a tym samym wyższą rangę niż te, które je dominują. Tak jak poprzednio, niezdominowanym rozwiązaniom w populacji przypisuje się rangę zerową. Obie koncepcje zilustrowano na rysunku 2.



Liczby odpowiadające każdemu rozwiązaniu na rysunku 2 (po lewej) to liczby dominacji. Rysunek pokazuje konkretnie rozwiązanie o liczbie 3, zdominowane przez trzy inne (o rangach 0, 0 i 2). Na rysunku 2 (po prawej) rozwiązania o równej randze (o randze 0, 1 lub 2) są zgrupowane razem. Rozwiązania o randze 0 to rozwiązania niezdominowane. Dominują te z rangami 1 lub 2. Po ich usunięciu, te z rangami 1 nie są już zdominowane. Usunięcie rozwiązań rangi 1 sprawia, że rozwiązanie rangi 2 staje się niezdominowane. Wielokryterialne algorytmy ewolucyjne muszą być również wyposażone w zdolność rozróżniania rozwiązań, które znajdują się w rzadszych obszarach M-wymiarowej przestrzeni funkcji celu, od tych w gęstszych. Trzy główne podejścia używane do tego celu zilustrowano na rysunku 3.



Pierwsza z tych metod polega na rozważeniu ograniczającego hipersześcianu wokół każdego rozwiązania w przestrzeni funkcji celu, który nie obejmuje żadnego innego rozwiązania . Sąsiednie rozwiązania będą zlokalizowane w niektórych narożnikach tego hipersześcianu. Jest to pokazane na rysunku 3 (po lewej), gdzie dwa rozwiązania, a i b, zostały otoczone hipersześcianami. Obwody hipersześcianów są uważane za miary różnorodności. Rozwiązania, których ograniczające hipersześciany mają większy obwód, uważa się za zlokalizowane w obszarach o mniejszej gęstości niż te o mniejszych gęstościach. Drugie podejście polega na nałożeniu M-wymiarowej hipersiatki na przestrzeń funkcji celu i rozważeniu liczby rozwiązań pozostających w każdej z komórek hipersiatki jako miary gęstości obszaru wokół komórki. Na rysunku 3 (środek), ponieważ b zajmuje tę samą komórkę, co inne rozwiązanie, podczas gdy a nie, to drugie uważa się za umieszczone w obszarze o mniejszej gęstości. Ostatnie podejście oblicza k-tego najbliższego sąsiada każdego rozwiązania . Tę sytuację przedstawiono na rysunku 3 (po prawej), gdzie rozwiązania a i b zostały połączone z ich najbliższymi sąsiadami (k = 1). Rozwiązania, które leżą w większej odległości od swoich sąsiadów, są uważane za znajdujące się w rzadszych obszarach przestrzeni funkcji celu. Ponieważ elitaryzm, gwarantowane przetrwanie najlepiej dostosowanych rozwiązań w każdym pokoleniu, wykazuje szybszą konwergencję w jednocelowych algorytmach ewolucyjnych, cecha ta została również włączona do większości obecnych wielocelowych algorytmów ewolucyjnych. Elitaryzm jest zapewniony za pomocą archiwum, które przechowuje najlepsze rozwiązania w każdym pokoleniu. Dość często zarchiwizowane rozwiązania są ponownie wprowadzane do populacji głównej. Archiwizacja jest realizowana za pomocą schematów, które będziemy nazywać zbiorczo zachowaniem elit.

Kilka najnowszych algorytmów ewolucyjnych

(i) NSGA-II : NSGA-II (niezdominowany algorytm sortowania genetycznego) utrzymuje populację i oddzielne archiwum, każde o rozmiarze N. W każdym pokoleniu populacja jest scalana z archiwum. Ten scalony zestaw jest następnie poddawany zachowaniu elitarnemu. Nowe archiwum jest wypełniane poprzez wzięcie N najlepiej sklasyfikowanych rozwiązań uzyskanych z zachowania elitarnego. Te same N osobników jest również poddawane selekcji turniejowej, krzyżowaniu i mutacji, aby utworzyć populację dla następnego pokolenia. Zachowanie elitarne jest zaimplementowane w NSGA-II poprzez zastosowanie sortowania niezdominowanego do konwergencji oraz metody hipersześcianu do zróżnicowania. Proponuje on podprogram O(MN²) do szybkiego sortowania niezdominowanego w celu przypisania rang rozwiązaniom w scalonej populacji. Zaczynając od rozwiązań o najniższej randze, archiwum jest wypełniane aż do osiągnięcia pełnej pojemności N. Różnorodność jest wywoływana w celu dalszego rozróżnienia rozwiązań wzajemnie niedominujących, gdy nie wszystkie rozwiązania o identycznej randze mogą być wstawione do archiwum. NSGA-II zawiera algorytm rzędu O(MN log(N)), aby to zrobić. Ponieważ sortowanie niedominujące jest częścią ograniczającą szybkość obliczeniową w NSGA-II, ogólna złożoność wynosi O(MN²) na pokolenie. (ii) SPEA-2 (Zitzler, Laumanns i Thiele, 2001): Metoda SPEA-2 jest dość podobna do NSGA-II. Utrzymuje ona również populację i archiwum o rozmiarze N, łącząc je na początku każdego pokolenia i wykorzystując zachowanie elit, aby zidentyfikować najlepsze do przejścia krzyżowania i mutacji w następnym pokoleniu. W SPEA-2 indywidualne dopasowanie obliczane jest w sposób dwuetapowy, co stanowi ulepszoną wersję podstawowego podejścia do liczenia dominacji, omówioną wcześniej. Najpierw obliczana jest siła każdego rozwiązania w połączonej populacji, tj. liczba rozwiązań, nad którymi dominuje. Następnie surowe dopasowanie każdego osobnika obliczane jest jako suma sił wszystkich rozwiązań, które go dominują. W pracy (Zitzler, Laumanns i Thiele, 2001) argumentuje się, że ta metoda obliczania dopasowania nadaje SPEA-2 pewną zdolność do zachowania różnorodności. Jednak samo surowe dopasowanie jest do tego niewystarczające, dlatego dodano do niego osobny składnik, który wyraźnie uwzględnia różnorodność. Ten drugi składnik, dodany do dopasowania każdego rozwiązania, jest odwrotnie proporcjonalny do odległości między rozwiązaniem a jego k-tym najbliższym sąsiadem w przestrzeni funkcji celu. Całkowita złożoność algorytmu SPEA-2 wynosi O(MN³. (iii) MOPSO : MOPSO (Multi-objective Particle Swarm Optimization) to podejście do szybkiej optymalizacji wielokryterialnej oparte na PSO. Narzuca ono różnorodność populacji za pomocą opisanej wcześniej hipersiatki M-wymiarowej i zliczania liczby rozwiązań obecnych w każdej z komórek hipersiatki. Rozwiązania zajmujące komórki o mniejszej liczbie cząstek są preferowane względem tych o większej liczbie cząstek. Równomierny rozkład rozwiązań wzdłuż frontu Pareto uzyskuje się poprzez nastawienie cząstek na aktualizację ich prędkości w kierunku globalnie najlepszych cząstek, które znajdują się w rzadszych komórkach hipersiatki, tj. o mniejszej liczbie cząstek. Odbywa się to za pomocą algorytmu selekcji koła ruletki, który wybiera komórkę probabilistycznie na podstawie liczby komórek, tak że im większa liczba komórek, tym mniejsze prawdopodobieństwo selekcji. MOPSO implementuje również operator mutacji. (iv) ParEGO : ParEGO (Parallel Efficient Global Optimization) został zaprojektowany specjalnie dla problemów, w których ocena funkcji celu jest bardzo kosztowna pod względem czasu obliczeniowego. Dlatego ParEGO osiąga zbieżność przy jak najmniejszej liczbie ocen funkcji. Algorytm wykorzystuje model procesu Gaussa do aproksymacji krajobrazu dopasowania, który jest adaptacyjnie poznawany za pomocą uczenia nadzorowanego. Więcej szczegółów można znaleźć w publikacji (Knowles, 2006). (v) FSGA : FSGA (Fuzzy Simplex Genetic Algorithm) ma złożoność O(MN²) na pokolenie, podobnie jak NSGA-II. Różni się od NSGA-II i SPEA-2 metodą stosowaną do zachowania elit. W tym celu stosuje się miarę zwaną dominacją rozmytą. Rozwiązaniu, które nie jest zdominowane przez żadne inne, przypisuje się dominację rozmytą równą zero. Im słabsze rozwiązanie, tym wyższa jest przypisana mu wartość dominacji rozmytej. Dominacja rozmyta w FSGA to metoda numeryczna, która nie tylko wykorzystuje optymalność Pareto, ale także uwzględnia stopień dominacji jednego rozwiązania nad drugim, efektywnie wykorzystując różnice między wartościami funkcji celu. Została ona zaprojektowana specjalnie w celu umożliwienia łatwej hybrydyzacji FSGA z lokalnym algorytmem wyszukiwania. PAES (Strategia Ewolucyjna Archiwum Pareto) i PESA (Algorytm Selekcji oparty na Kopercie Pareto) to inne skuteczne wielokryterialne algorytmy ewolucyjne, które wykorzystują hipersiatkę do pomiaru różnorodności . Inny algorytm, RDGA (Algorytm Genetyczny oparty na Gęstości Rank), wykorzystuje tę metodę wraz ze schematem rankingowym, w którym osobnikowi niezdominowanemu przypisuje się rangę jednostkową, a pozostałym przypisuje się jeden plus sumę rang wszystkich rozwiązań dominujących (Lu i Yen, 2003). Niedawno wykorzystanie dominacji rozmytej zostało z powodzeniem zastosowane w innym wielokryterialnym algorytmie PSO

TRENDY NA PRZYSZŁOŚĆ

Wielokryterialna optymalizacja ewolucyjna to szybko rozwijająca się, nowa dziedzina badań. Chociaż w najnowszej literaturze zaproponowano kilka interesujących podejść, konieczne są dalsze badania, zanim algorytmy wielokryterialne będą mogły w pełni sprostać potrzebom dziedzin zastosowań. Jednym z obecnych obszarów zainteresowania badawczego jest opracowywanie metryk numerycznych do porównywania rozwiązań. Jest to szczególnie przydatne, gdy problem zawiera dużą liczbę celów. W przestrzeni funkcji celu o wyższym wymiarze mniejsze jest prawdopodobieństwo znalezienia rozwiązania, które dominuje nad innym, tj. jest lepsze lub równe innemu pod względem wszystkich celów. W takich okolicznościach porównywanie rozwiązań, które już mieszczą się w granicy Pareto, jest niezbędne. Jedna z takich metod została niedawno zaproponowana (Farina i Amato, 2004). Metoda ta zlicza liczbę celów, w których jedno rozwiązanie jest lepsze i gorsze od drugiego, i proponuje metryki rozmyte oparte na tych liczbach. Jednak takie koncepcje nie zostały jeszcze uwzględnione w algorytmach ewolucyjnych. Powiązanym kierunkiem badań jest opracowywanie schematów porównywania rozwiązań w przypadku niepewności funkcji celu. Badania te mają oczywiste implikacje praktyczne w inżynierii i innych zastosowaniach, w których mierzenie celów, takich jak koszt, wydajność czy oczekiwany czas życia, jest trudnym zadaniem . Innym kierunkiem, który z pewnością będzie przedmiotem zainteresowania w przyszłości, jest optymalizacja wielokryterialna z wykorzystaniem nowych paradygmatów biologicznych. Zaproponowano zaledwie kilka wielokryterialnych algorytmów PSO, takich jak MOPSO i metoda PSO oparta na dominacji rozmytej (Koduru, Das i Welch, 2007); w związku z tym istnieje duże zainteresowanie opracowaniem lepszych strategii wyszukiwania PSO w środowisku obliczeń ewolucyjnych. Pojawia się kolejna klasa algorytmów opartych na obliczeniach zaangażowanych w układ odpornościowy kręgowców, zwana Sztucznymi Systemami Odpornościowymi (AIS). Chociaż ostatnio zaproponowano kilka wielokryterialnych algorytmów AIS , istnieje znaczny potencjał udoskonalenia w tym kierunku. Inne trendy dotyczą opracowywania trudniejszych problemów testów porównawczych. Huband i inni zaproponowali najnowsze testy porównawcze , a wydajność metod ewolucyjnych dla tych funkcji wymaga zbadania.

WNIOSKI

Przedstawiliśmy przegląd nowej i rozwijającej się dziedziny optymalizacji wielokryterialnej, omawiając niektóre z najważniejszych podejść. Zdecydowaliśmy się opisać NSGA-II i SPEA-2, ponieważ są to obecnie najpopularniejsze algorytmy. Omawiamy również najnowszy algorytm ParEGO, który jest bardzo obiecujący dla niektórych specjalistycznych zastosowań, a także jeszcze nowszy FSGA, obecnie w fazie rozwoju, który zaspokaja zapotrzebowanie na hybrydowe algorytmy wielokryterialne. Na koniec omówiliśmy również MOPSO, oparty na nowym paradygmacie ewolucyjnym PSO. Na koniec, aby uzupełnić dyskusję, omawiamy przyszłe trendy w ewolucyjnej optymalizacji wielokryterialnej.

WSTĘP

Jednym z podstawowych terminów w inżynierii informacji są dane. W naszym podejściu element danych definiuje się jako reprezentację atomu informacji przechowywanego w komputerach cyfrowych. Chociaż atom informacji można traktować jako triplet podmiot-predykat-wartość , dane są zazwyczaj podawane wyłącznie z ich reprezentacją wartości. Fakt ten może prowadzić do definicji, w których dane to po prostu liczby, słowa lub obrazy bez kontekstu. Na przykład w (WO, 2007) dane są podawane jako informacje w postaci numerycznej, które można przesyłać lub przetwarzać cyfrowo. Interesujące jest to, że często możemy zauważyć, że termin "dane" jest używany bez dokładnej definicji terminologicznej, co powoduje, że termin ten często pozostaje mylący, a czasami nawet sprzeczny z zaprezentowanymi definicjami. Sieber i Kammerer (2006) wprowadzają nową interpretację danych zawierającą kilka poziomów. Najniższy poziom należy do instancji danych, które opisują formę i wygląd symboli. Poziom pośredni to poziom reprezentantów, który obejmuje zastosowany system kodowania. Najwyższy poziom jest powiązany ze znaczeniem i opisem kontekstu. Wszystkie trzy poziomy są potrzebne do poznania atomu informacji. Na przykład symbol "36" w bazie danych określa jedynie wartość i system reprezentacji, ale nie znaczenie. Aby objąć cały atom informacji, baza danych powinna przechowywać dodatkowe elementy danych opisujące dane oryginalne. Głównym celemsemantycznych modeli danych jest opisanie zarówno kontekstu, jak i głównej struktury elementów danych w obszarze problemowym. Te dodatkowe elementy danych nazywane są metadanymi. Ważne jest, aby zrozumieć, że:

o metadane to dane,
o metadane są względne i
o metadane opisują dane.

Metadane stanowią podstawę do łączenia danych powiązanych pod względem treści i do ich dalszego przetwarzania. Można je rozumieć jako warunek wstępny inteligentnego i wydajnego administrowania i przetwarzania, a także jako ukierunkowany, formalny sposób dostarczania odpowiednich danych.

TŁO

W systemach zarządzania danymi kontekst wartości jest zazwyczaj definiowany za pomocą struktury pamięci. Każdej pozycji struktury przypisana jest nazwa identyfikacyjna (wartość tekstowa). Opis pamięci (struktura, nazewnictwo i ograniczenia) nazywa się schematem. Dużym problemem strukturalnego modelowania danych jest to, że nie jest ono w stanie dostarczyć wszystkich informacji potrzebnych do zrozumienia pełnego kontekstu danych. Na przykład, sam schemat relacyjny

RT (NM INT, KNEV CHAR(20), RU DATE)

nie wystarczy do uchwycenia znaczenia przechowywanych elementów danych. Głównymi elementami składowymi opisu kontekstu w semantycznych modelach danych (SDM) są koncepcje i relacje. Pierwszymi powszechnie znanymi strukturalnymi modelami semantycznymi w projektowaniu baz danych są model relacji encji (ER) i model EER . Model ER składa się z trzech podstawowych elementów: encji (pojęcia), relacji i atrybutu. Atrybuty są traktowane jako elementy struktury encji, a jeden atrybut może należeć tylko do jednej encji. Model EER jest rozszerzeniem modelu ER o relacje IS_A i HAS_A. Inne rozszerzenia to SIM, IFO i RM/T. Jedną z głównych wad SDM zorientowanego na strukturę są ograniczenia mocy ekspresji.Później opracowano modele takie jak UML lub ODL , aby uzupełnić brakujące elementy obiektowe. W przypadku ODL opis klasy może zawierać następujące elementy: atrybuty, metody, parametry dziedziczenia, widoczność, relacje i reguły integralności. Modele te zapewniają znaczną złożoność dla inżynierii oprogramowania, ale nie są zbyt elastyczne, aby opisywać modele danych o wyższym poziomie abstrakcji. Globalne badania koncentrowały się na modelu SDM z prostszymi i bardziej uniwersalnymi elementami. Najbardziej znanymi modelami semantycznymi wysokiego poziomu są sieci semantyczne i modele ontologiczne. Sieć semantyczna jest reprezentowana za pomocą grafu skierowanego, w którym wierzchołki są pojęciami, a krawędzie relacjami. Główne różnice między modelami ontologicznymi a tradycyjnym modelem SDM są następujące: brak ustalonej hierarchii strukturalnej między pojęciami, elastyczne relacje, niezależność od dziedziny zastosowań, struktura jest odwzorowana na formułę logiczną, można ją powiązać z silnikiem wnioskowania. Powszechnie przyjmuje się, że wszystko na wysokim poziomie przetwarzania informacji musi opierać się na ontologii . Więcej szczegółów na temat obecnych zastosowań ontologii można znaleźć między innymi w (Taniar, 2006). Jednym z pierwszych języków ontologii jest RDF . RDF służy do opisu pojęć w neutralnym, czytelnym dla maszyn formacie. Zgodnie ze specyfikacją, podstawowymi elementami języka są zasoby, literały i instrukcje. Istnieją dwa rodzaje zasobów: zasoby encji i właściwości. Instrukcja to triplet (p, s, o), gdzie p jest właściwością, s jest zasobem, a o jest literałem lub zasobem. W innym podejściu p nazywane jest predykatem, s jest podmiotem, a o jest obiektem w instrukcji. Jak widać, instrukcja odpowiada atomowi informacji. Pionierskim przedstawicielem kolejnej generacji języków jest OWL , który można uznać za rozszerzenie RDF, zawierające dodatkowe elementy opisujące między innymi typizację, charakterystykę własności, kardynalność i właściwości behawioralne. Język OWL-DL opiera się na logice opisowej (Description Logic), która opisuje strukturalne relacje domeny w języku logicznym, co umożliwia automatyczne wnioskowanie i sprawdzanie ograniczeń w systemie. Język logiki stosowanej opiera się na logice predykatów pierwszego rzędu. Najczęściej używanymi produktami związanymi z OWL są Protégé, Pellet i KAON2.

WIELOWARSTWOWE MODELE SEMANTYCZNE

Schematy wielowarstwowe

W przypadku systemów o złożonej funkcjonalności jednym ze sposobów na zmniejszenie złożoności jest zbudowanie systemu modułowego. Modularyzacja to udana koncepcja we wszystkich dziedzinach inżynierii. Modularyzacja może być pionowa lub pozioma. Modularyzacja pionowa nazywana jest warstwowaniem. Podstawowe właściwości systemu warstwowego to:

o elementy są przypisane do klastrów (zwanych warstwami);
o między klastrami istnieje hierarchiczna relacja;
o relacje wewnątrz klastrów różnią się od relacji między klastrami;
o klastry współpracują ze sobą w roli klienta lub serwera.

Każda warstwa oferuje zestaw funkcjonalności, w których funkcje są zbudowane na usługach warstw bazowych. W przypadku systemu wielowarstwowego wdrożenie może przynieść korzyści w postaci redukcji kosztów w porównaniu ze strukturą jednowarstwową. Warstwy oznaczają modularność z punktu widzenia implementacji i przynoszą następujące korzyści jakościowe i ilościowe :

o enkapsulacja (warstwy są w dużej mierze autonomiczne, spójność),
o niezależność,
o elastyczność (warstwy można wymieniać bez wpływu na pozostałe warstwy),
o redukcja kosztów (prostota testowania i projektowania, możliwość ponownego wykorzystania).

Struktura warstwowa jest obecnie powszechną technologią, m.in. w sieciach (Hnatyshin, 2007), przetwarzaniu obrazu , sterowaniu procesami i tworzeniu oprogramowania.

Wielowarstwowa natura ludzkiego poznania

Bardzo wcześnie zdano sobie sprawę, że ludzkie poznanie przestrzenne opiera się na częściowo hierarchicznym, konceptualnym spojrzeniu na przestrzeń . Zazwyczaj mapowanie środowiska przestrzennego przeprowadza się za pomocą hierarchii semantycznej . W propozycji Slomana (2003) wewnętrzna reprezentacja środowiska przestrzennego jest realizowana za pomocą modelu trójwarstwowego. Najniższa warstwa nazywana jest warstwą metryczną. Ustanawia ona absolutny układ odniesienia. Składa się ona z grafu nawigacyjnego, który opisuje ważne pozycje w środowisku. W kolejnej, topologicznej warstwie, węzły nawigacyjnesą mapowane na obszary, gdzie obszar odpowiada zestawowi połączonych węzłów. Obszar oznacza złożone pojęcie przestrzenne. Najwyższy poziom należy do warstwy konceptualnej. W tej warstwie obszary są mapowane na ogólne pojęcia abstrakcyjne. Poziom ten odpowiada warstwie ontologii, która zapewnia różne relacje i mechanizm wnioskowania. Zgodnie z aktualną koncepcją H-Cogaffa dotyczącą architektury przetwarzania informacji u człowieka , system poznawczy składa się z kilku regionów wykonujących współbieżne czynności. Regiony te są ustrukturyzowane w hierarchie. Hierarchia percepcji może na przykład aktywować różne koncepcje jednocześnie dla pojedynczego obrazu wejściowego z czujnika. Percepcja wzrokowa może wykrywać różne poziomy struktury i różne poziomy pojęć. Opracowany wielowarstwowy model ontologii składa się z trzech warstw: reaktywnej, celowej i meta-zarządzania. Również w sztucznej inteligencji zastosowanie struktur wielowarstwowych zyskało na popularności. W pracy (Kamimura, 2003) zaimplementowano metodę konkurencyjnego uczenia się opartą na teorii informacji z sieciami wielowarstwowymi w celu rozwiązywania złożonych problemów. Sieci składają się z kilku warstw konkurencyjnych. W każdej warstwie konkurencyjnej informacja jest maksymalizowana. Ta sukcesywna maksymalizacja informacji umożliwia sieciom stopniową ekstrakcję cech. Wyniki eksperymentów potwierdziły, że informacja może być maksymalizowana w sieciach wielowarstwowych, a sieci te mogą ekstrahować cechy, których nie mogą wykryć sieci jednowarstwowe.

Wielowarstwowe modele koncepcyjne

Tradycyjne modele SDM miały na celu zarządzanie wyłącznie strukturą jednowarstwową. Żadna z oryginalnych wersji ER, RDF ani OWL nie wykorzystuje warstw w modelu. Z drugiej strony, widać, że struktura warstwowa ma wiele zalet:

o zwiększenie prostoty zarządzania,
o zmniejszenie złożoności,
o wzrost elastyczności i
o wzrost możliwości ponownego wykorzystania.

Pierwsze klasyczne modele warstwowe dla sieci semantycznych powstały w latach 80. XX wieku. W proponowanych modelach można łatwo zaobserwować silny wpływ teorii psychologicznych na ludzkie poznanie. Model warstwowy Thompsona (1990) składa się z pięciu warstw,podobnie jak model Greenwalda (1988). Warstwa bazowa reprezentuje dane sensoryczne (obrazy, dźwięki, znaki) oraz relacje czasowe między tymi elementami danych. Kolejna warstwa poświęcona jest podstawowym pojęciom. Powiązanie pojęcia z jego wrażeniami sensorycznymi może być zmienne i bardzo złożone (transformacje). To połączenie powinno wykonywać bardziej złożone czynności niż tylko proste skojarzenia. Następny poziom nazywany jest poziomem zdarzeń. Na tej warstwie proste instancje obiektów są powiązane z seriami i zdaniami. Ta warstwa powinna zawierać logikę wspierającą idee czasu i przyczynowości. Następny poziom generuje obiekty abstrakcyjne, które grupują instancje obiektów. Kolejny poziom modelu opisuje działania dotyczące pojęć abstrakcyjnych, takich jak planowanie i modelowanie. Najwyższy poziom jest związany z pojęciami abstrakcyjnymi i działaniami abstrakcyjnymi, takimi jak wnioskowanie i zarządzanie metadanymi. W propozycji Khosli (2004) warstwowanie ontologii jest silnie skorelowane z warstwowaniem funkcjonalnym systemu. Artykuł opisuje strukturę ogólnego modułu obliczeń miękkich. Najbardziej wewnętrzną warstwą jest warstwa obiektów, opisująca schemat danych. Na szczycie warstwy danych znajdują się warstwa agenta rozproszonego, warstwa agenta narzędziowego i warstwa agenta optymalizacyjnego. Warstwy te wykonują między innymi wstępne przetwarzanie, transformację i podejmowanie decyzji. Koncepcję wielowarstwowości można zastosować również do tradycyjnych modeli danych. Warstwowy model UML jest reprezentowany między innymi w (Kreku, 2006). Warstwy tutaj również odpowiadają różnym obszarom funkcjonalnym w aplikacji. Trzy proponowane warstwy to warstwa komponentów, warstwa architektury sprzętowej i warstwa architektury platformy. W (Sunitha, 2007) badanie koncentruje się wyłącznie na części SDM. Semantyczny model danych jest podzielony na trzy warstwy. Dolna część to warstwa miary pojęć, która zawiera opisy samych pojęć. Środkowa warstwa służy do przechowywania relacji (takich jak specjalizacja, klasyfikacja) między pojęciami. Górna warstwa jest przeznaczona dla elementów wiedzy związanych z kontekstem, opisujących środowisko pola aplikacji. W niektórych innych propozycjach warstwowanie odnosi się nie do struktury funkcjonalnej, ale do poziomów abstrakcji. W klasycznym UML stosowana jest czterowarstwowa architektura metamodelu. Dolna warstwa to warstwa obiektów, a kolejna warstwa to warstwa modelu. Na górze warstwy modelu znajduje się warstwa metamodelu. Na górze znajduje się warstwa metametamodelu. Model metaobiektu (MOF) opiera się na warstwowej, konceptualnej strukturze metamodelu. Zawartość warstwy konceptualnej opisuje elementy w warstwie niższej. Zarówno UML, jak i MOF oparte są na reprezentacjach zorientowanych klasowo. W (Melnik, 2000) zdefiniowano trójwarstwowy model abstrakcji dla sieci semantycznej. Warstwy te to warstwa składni, warstwa obiektów i warstwa semantyczna. Semantyczny model danych przedstawiony w (Sieber, 2006) został opracowany jako model łączący dane z semiotyką w ujęciu Peirce′a, ze szczególnym uwzględnieniem procesów dokumentacji technicznej. Wiedza może być współdzielona między wieloma osobami w różnych działach, różnych lokalizacjach produkcyjnych (w tym w różnych krajach) i w różnych aplikacjach. W konsekwencji w takim procesie prawie każdy pełni dwie role: jedną posiadania i datowania wiedzy; drugą poszukiwania i potrzeby posiadania wiedzy datowanej. Do celów matematycznych model ten został rozszerzony za pomocą sieci semantycznej opartej na kratownicy pojęć. Rezultatem jest wielowarstwowy model danych semantycznych, który można wykorzystać do wizualizacji bardziej ogólnego przetwarzania dekodowania i kodowania pomiędzy sygnałami a pojęciami (semantycznymi).

TRENDY NA PRZYSZŁOŚĆ

Termin ontologii warstwowej pojawia się w literaturze bardzo rzadko. Głównym powodem jest to, że ontologia podstawowa może opisywać dowolne poziomy abstrakcji. Zatem pojedyncza warstwa może obejmować dowolne poziomy pojęć. Ta monolityczna struktura będzie utrudniać integrację istniejących ontologii, ponieważ trudniej jest wykryć nakładanie się pojęć. Obecne projekty badawcze dotyczące ontologii zazwyczaj ukierunkowane są na rozwój precyzyjnych ontologii dla różnych dziedzin zastosowań. Główne obecne obszary to: systemy medyczne, systemy geograficzne, lingwistyka, nauki społeczne, systemy informatyczne przedsiębiorstw, logika, reprezentacja wiedzy i automatyczne wnioskowanie. Bardzo niewiele propozycji dotyczy zastosowania modułowych, wielowarstwowych ontologii. Na przykład w pracy (Purao, 2005) analizowana jest specyficzna dziedzina projektu bazy danych, w której zdefiniowano trzy warstwy: poziom rdzenia (lokalny), poziom sąsiedztwa i poziom domeny globalnej. Chociaż znaczenie ontologii niezależnej od dziedziny jest widoczne i oczywiste dla każdego, obecne prace zdają się pomijać ten wymóg. Według (Mikroyannidis, 2006) zarządzanie ontologią w większości systemów informatycznych opiera się na prostocie, warstwowanie ontologii jest rzadko stosowane, a wymagania dotyczące ewolucji i integracji ontologii są zazwyczaj pomijane. Można przewidywać, że modułowe, warstwowe modele ontologii zyskają na znaczeniu w niedalekiej przyszłości.

WNIOSKI

Tradycyjne modele semantyczne opierają się na strukturze jednowarstwowej. Takie podejście stanowi wadę w rozwoju złożonych systemów. Ponieważ model ludzkiego poznania opiera się na podejściu wielowarstwowym, a celem modeli semantycznych jest opisywanie pojęć z naszego świata, modele wielowarstwowe wydają się być bardziej precyzyjne w tworzeniu globalnego modelu semantycznego. Obecne modele semantyczne, takie jak UML czy ontologia, oferują pewne możliwości warstwowania, ale szczegółowa analiza wielowarstwowych modeli semantycznych to zadanie przyszłości.

WSTĘP

Projektowanie rozmytych systemów wnioskowania wiąże się z szeregiem decyzji podejmowanych przez projektantów, ponieważ konieczne jest spójne określenie liczby funkcji przynależności dla danych wejściowych i wyjściowych, a także specyfikacji zbioru reguł rozmytych systemu, a także zdefiniowanie strategii agregacji reguł i defuzyfikacji zbiorów wyjściowych. Potrzeba opracowania systematycznych procedur wspomagających projektantów była powszechna, ponieważ metoda prób i błędów jest często dostępna . Ogólnie rzecz biorąc, w zastosowaniach obejmujących identyfikację systemów i modelowanie rozmyte, wygodne jest użycie funkcji energii, które wyrażają błąd między wynikami pożądanymi a wynikami dostarczanymi przez system rozmyty. Przykładem jest użycie średniego błędu kwadratowego lub znormalizowanego średniego błędu kwadratowego jako funkcji energii. W kontekście identyfikacji systemów, oprócz błędu średniokwadratowego, do funkcji energii można dodać wskaźniki regularyzacji danych w celu poprawy odpowiedzi systemu w obecności szumów (z danych uczących) . W przypadku braku zestawu dostrajania, takiego jak ma to miejsce w przypadku regulacji parametrów regulatora procesu, funkcję energii można zdefiniować za pomocą funkcji uwzględniających pożądane wymagania konkretnego projektu , tj. maksymalny sygnał przeregulowania, czas narastania, nietłumioną częstotliwość własną itp. Z tego punktu widzenia niniejszy artykuł przedstawia nową metodologię opartą na wstecznej propagacji błędu do regulacji rozmytych systemów wnioskowania, które można następnie zaprojektować jako model trójwarstwowy. Każda z tych warstw reprezentuje zadania wykonywane przez rozmyty system wnioskowania, takie jak rozmycie, wnioskowanie reguł rozmytych i defuzzowanie. Proponowana w niniejszym artykule procedura regulacji jest realizowana poprzez adaptację dowolnych parametrów z każdej z tych warstw w celu zminimalizowania wcześniej określonej funkcji energii. Zasadniczo, regulacja może być przeprowadzana warstwa po warstwie oddzielnie. Różnice operacyjne związane z każdą warstwą, gdzie regulacja parametrów jednej warstwy nie wpływa na wydajność innej, pozwalają na pojedynczą regulację każdej warstwy. W ten sposób procedura regulacji rozmytego systemu wnioskowania zyskuje większą elastyczność w porównaniu z procesem uczenia stosowanym w sztucznych sieciach neuronowych. Metodologia ta jest interesująca nie tylko ze względu na wyniki prezentowane i uzyskiwane za pomocą symulacji komputerowych, ale także ze względu na jej ogólność w odniesieniu do rodzaju używanego rozmytego systemu wnioskowania. Dlatego też, metodologia ta jest rozszerzalna zarówno na architekturę Mandani, jak i na architekturę sugerowaną przez Takagi-Sugeno.

TŁO

W ostatnich latach obserwuje się szerokie i rosnące zainteresowanie zastosowaniami wykorzystującymi logikę rozmytą. Zastosowania te obejmują produkty konsumenckie, takie jak aparaty fotograficzne, kamery wideo, pralki i kuchenki mikrofalowe, a nawet zastosowania przemysłowe, takie jak sterowanie procesami, aparatura medyczna i systemy wspomagania decyzji . Systemy wnioskowania rozmytego można traktować jako metody wykorzystujące koncepcje i operacje zdefiniowane przez teorię zbiorów rozmytych i metody wnioskowania rozmytego . Zasadniczo te funkcje operacyjne obejmują rozmycie danych wejściowych, stosowanie reguł wnioskowania, agregację reguł i defuzyfikację, która reprezentuje precyzyjne dane wyjściowe systemu rozmytego . Obecnie wielu badaczy zajmuje się badaniami związanymi z technikami projektowania wykorzystującymi systemy wnioskowania rozmytego. Pierwszy typ techniki projektowania rozmytego systemu wnioskowania koncentruje się na umożliwieniu modelowania procesu z ich eksperckich baz wiedzy, gdzie zarówno poprzedniki, jak i następniki reguł są zawsze zbiorami rozmytymi, oferując tym samym wysoki poziom semantyczny i dobrą zdolność interpretacyjną . Jednakże zastosowanie tej techniki w mapowaniu złożonych systemów składających się z wielu zmiennych wejściowych i wyjściowych było żmudnym zadaniem, które może dawać zarówno niedokładne wyniki, jak i słabą wydajność . Drugi typ techniki projektowania rozmytego systemu wnioskowania można zidentyfikować jako techniki, które włączają uczenie się, w sposób automatyczny, z danych reprezentujących zachowanie zmiennych wejściowych i wyjściowych procesu. Dlatego ta strategia projektowania wykorzystuje zbiór wartości wejściowych i wyjściowych uzyskanych z modelowanego procesu, co różni się od pierwszej strategii projektowania, w której rozmyty system został zdefiniowany przy użyciu wyłącznie wiedzy eksperckiej uzyskanej z obserwacji danego systemu. Ogólnie rzecz biorąc, metody wyprowadzone z tej drugiej strategii można interpretować jako oparte na technikach automatycznego generowania reguł rozmytych, które wykorzystują dostępne dane do swoich procedur dostosowawczych (lub treningowych). Spośród głównych podejść należących do tej drugiej strategii projektowania wyróżniono algorytm ANFIS (Adaptive-Network-based Fuzzy Inference Systems) zaproponowany przez Janga (1993),który można zastosować do architektur rozmytych tworzonych przez rzeczywiste funkcje wielomianowe jako wyrazy następcze reguł rozmytych, takich jak te przedstawione przez Takagi i Sugeno (1985) oraz Sugeno i Kanga (1988). Nowsze podejścia, takie jak te zaproponowane przez Panellę i Gallo (2005), Huanga i Babriego (2006) oraz Li i Horiego (2006), również należą do tej strategii projektowania. Jednakże reprezentacja procesu za pomocą tych automatycznych architektur może implikować redukcję interpretowalności w odniesieniu do utworzonej bazy reguł, których terminy następcze są w większości przypadków wyrażone funkcjami wielomianowymi, a nie zmiennymi lingwistycznymi (Kamimura, Takagi i Nakanishi, 1994). W związku z tym szeroko motywowano rozwój algorytmów dopasowujących rozmyte systemy wnioskowania, w których terminy następcze reguł rozmytych są również reprezentowane przez zbiory rozmyte.

GŁÓWNY CEL

Biorąc pod uwagę funkcje operacyjne realizowane przez rozmyte systemy wnioskowania, wygodnie jest przedstawić je za pomocą modelu trójwarstwowego. Zatem rozmyty system wnioskowania przedstawiony w niniejszym artykule można przedstawić za pomocą sekwencyjnej kompozycji trzech warstw, tj. warstwy wejściowej, warstwy wnioskowania i warstwy wyjściowej. Warstwa wejściowa ma funkcje łączenia zmiennych wejściowych (pochodzących z zewnątrz) z rozmytym systemem wnioskowania, wykonując ich odpowiednie rozmycia za pomocą odpowiednich funkcji przynależności. W warstwie wnioskowania reguł rozmytych, rozmyte zmienne wejściowe są łączone ze sobą zgodnie ze zdefiniowanymi regułami, wykorzystując jako wsparcie operacje zdefiniowane przez teorię rozmytą. Wynikowy zbiór tego procesu agregacji jest następnie defuzyzowany w celu wygenerowania rozmytego systemu wnioskowania. Zarówno proces agregacji, jak i defuzyfikacji rozmytego systemu wyjściowego są realizowane przez warstwę wyjściową. Należy zauważyć, że w odniesieniu do warstwy wyjściowej, chociaż wykonuje ona dwa opisane powyżej procesy, jest ona również odpowiedzialna za przechowywanie funkcji przynależności zmiennych wyjściowych. Jako ilustrację, rysunek 1 przedstawia proponowany model wielowarstwowy, który składa się z dwóch danych wejściowych i jednego danych wyjściowych, z trzema regułami rozmytymi w warstwie wnioskowania.



W kolejnych podrozdziałach zostaną przedstawione dalsze szczegóły dotyczące tego, jak rozmyte systemy wnioskowania mogą być reprezentowane przez model trójwarstwowy.

Warstwa wejściowa

Rozmycie danych wejściowych ma na celu określenie stopnia przynależności każdego wejścia w odniesieniu do zbiorów rozmytych powiązanych z każdą zmienną wejściową. Do każdej zmiennej wejściowej systemu rozmytego można przypisać dowolną liczbę zbiorów rozmytych. W ten sposób, niech system rozmyty składa się tylko z jednego wejścia z N zbiorami rozmytymi, to wyjściem warstwy wejściowej będzie wektor kolumnowy z N elementami, które reprezentują stopnie przynależności tego wejścia w odniesieniu do tych zbiorów rozmytych. Jeżeli zdefiniujemy wejście tego układu rozmytego za pomocą unikalnego wejścia x, to wyjściem warstwy wejściowej będzie wektor I₁ reprezentowany przez:



gdzie μ_Ak(.) jest funkcją przynależności zdefiniowaną dla wejścia x, która odnosi się do k-tego zbioru rozmytego z nim powiązanego. Uogólnienie koncepcji warstwy wejściowej dla układu rozmytego o p zmiennych wejściowych można osiągnąć, traktując każde wejście jako podwarstwę warstwy wejściowej. Biorąc to pod uwagę, wektor wyjściowy warstwy wejściowej I_(x) jest wówczas zdefiniowany przez:



gdzie x_i jest i-tym wejściem układu rozmytego, a I_k(.) jest k-tym wektorem funkcji przynależności powiązanych z wejściem x_k. Na rysunku zilustrowano warstwę wejściową układu rozmytego złożonego z dwóch wejść, które są odwzorowane wektorami I₁ i I₂. W proponowanym podejściu można wykorzystać kilka funkcji przynależności. Jednym z niezbędnych warunków dla tych funkcji jest ich normalizacja w domkniętej dziedzinie [0,1].

Warstwa wnioskowania

Warstwa wnioskowania układu rozmytego ma funkcjonalność przetwarzania zdefiniowanych dla niego reguł wnioskowania rozmytego. Inną funkcjonalnością jest zapewnienie bazy wiedzy dla procesu. W niniejszym artykule układ wnioskowania rozmytego ma początkowo wszystkie możliwe wywnioskowane reguły. Dlatego algorytm dostrajania ma za zadanie ważenie reguł wnioskowania. Ważenie reguł wnioskowania jest właściwym sposobem reprezentowania najważniejszych reguł, a nawet umożliwienia powiązania ze sobą sprzecznych reguł bez utraty zupełności językowej. W ten sposób i-tą regułę rozmytą można wyrazić następująco:



gdzie R_i(.) jest funkcją reprezentującą ważenie rozmyte i-tej reguły rozmytej, wi jest wagą i-tej reguły rozmytej, a r_i(.) reprezentuje wartość rozmytą i-tej reguły rozmytej. Na rysunku przedstawiono kompozycję obejmującą r_i(.) i R_i(.) dla trzech reguł rozmytych należących do warstwy wnioskowania.

Warstwa wyjściowa

Warstwa wyjściowa systemu wnioskowania rozmytego ma na celu agregację reguł wnioskowania, a także defuzzyfikację zbioru rozmytego wygenerowanego z agregacji tych reguł wnioskowania. Oprócz aspektów operacyjnych, metody agregacji i defuzzyfikacji muszą uwzględniać wymagania wydajności sprzętowej, aby zmniejszyć nakład obliczeniowy potrzebny do przetwarzania systemu rozmytego. W niniejszym artykule dostosowano również warstwę wyjściową systemu wnioskowania. Dostosowanie tej warstwy odbywa się w podobny sposób, jak w przypadku warstwy wejściowej systemu rozmytego. Przykładowo, na rys. 1 pokazano ilustrację procedur związanych z warstwą wyjściową.

Dopasowanie rozmytego systemu wnioskowania

Rozważmy rozmyty system z dwoma wejściami, z których każde składa się z trzech funkcji przynależności gaussowskiej, z łącznie pięcioma regułami wnioskowania i wyjściem zdefiniowanym przez dwie funkcje przynależności gaussowskiej. Wiadomo, że dla każdej funkcji przynależności gaussowskiej należy uwzględnić dwa parametry wolne, tj. średnią i odchylenie standardowe. W związku z tym liczba parametrów wolnych warstwy wejściowej wynosi 12. Dla każdej reguły wnioskowania przypisano współczynnik ważenia, co daje łącznie 5 parametrów wolnych w warstwie wnioskowania. W odniesieniu do warstwy wyjściowej obowiązują te same założenia, co dla warstwy wejściowej. Zatem z warstwą wyjściową skojarzone są cztery parametry wolne. Zatem odwzorowanie f między przestrzenią wejściową x a przestrzenią wyjściową y można zdefiniować wzorem:



gdzie mf_In to wektor parametrów powiązany z wejściowymi funkcjami przynależności, w to wektor wag reguł wnioskowania, a mf_Out to wektor parametrów powiązany z wyjściowymi funkcjami przynależności. Zatem mf_In, w i mf_Out reprezentują parametry swobodne układu rozmytego, co można zapisać następująco:

y =f(x.(Θ)

gdzie Θ jest wektorem powstałym w wyniku połączenia parametrów swobodnych wchodzących w skład układu rozmytego, tj.



Funkcja energii, która ma zostać zminimalizowana, biorąc pod uwagę ustalony zestaw dostrojeń {x,d}, jest zdefiniowana wzorem:



gdzie ξ reprezentuje funkcję energii związaną z rozmytym systemem wnioskowania f.

Techniki optymalizacji bez ograniczeń

Niech funkcja energii ξ_(x,y)(Θ) jest różniczkowalna względem parametrów swobodnych rozmytego systemu wnioskowania. Zatem celem jest znalezienie optymalnego rozwiązania Θ*, przy spełnieniu następujących warunków:

ξ(Θ*)≤ ξ(Θ) (8) Możemy zatem zauważyć, że aby spełnić warunek wyrażony w (8), konieczne jest rozwiązanie problemu optymalizacji bez ograniczeń w celu uzyskania rozwiązania Θ* które jest dane wzorem:



Warunek wyrażający rozwiązanie optymalne w równaniu (9) można również zapisać w następujący sposób:



gdzie ∇ jest operatorem gradientu zdefiniowanym przez:



Istnieje kilka technik rozwiązywania problemów optymalizacji nieograniczonej. Szczegółowy opis tych metod można znaleźć w pracy Bertsekasa (1999). Wybór najwłaściwszej metody zależy od złożoności związanej z funkcją energii. Na przykład metoda Gaussa-Newtona do optymalizacji nieograniczonej może być bardziej przydatna w problemach, w których funkcja energii jest zdefiniowana wzorem:



gdzie e(i) jest błędem bezwzględnym względem i-tego wzorca strojenia. W niniejszym artykule wyprowadzenie metody Gaussa-Newtona jest wykorzystywane do strojenia rozmytego systemu wnioskowania, który jest zdefiniowany następującym wyrażeniem:



gdzie g jest gradientem ξ wyrażonym w (11), a J jest macierzą Jacobesa e zdefiniowaną w (12). Zastosowanym algorytmem optymalizacyjnym była metoda Levenberga-Marquardta , która może efektywnie obsługiwać źle uwarunkowane macierze J^TJ poprzez modyfikację równania (13) w następujący sposób:



Obliczenia macierzy J i wektorów g przeprowadzono metodą różnic skończonych. Wyniki symulacji

W tej sekcji przedstawiono wyniki symulacji proponowanej metodologii dla modelu rozmytego Mandaniego. W dwóch poniższych przykładach układ rozmyty jest używany do modelowania funkcji nieliniowych. W pierwszym przykładzie układ wnioskowania rozmytego jest używany do przewidywania szeregów czasowych Mackeya-Glassa. W drugim przykładzie dwuwymiarowa funkcja sinc jest modelowana przez układ wnioskowania rozmytego.

Przykład 1: Modelowanie funkcji Mackeya-Grassa

Wykorzystując metodologię korekcji przedstawioną w niniejszym artykule, opracowano układ wnioskowania rozmytego typu Mandaniego, którego celem jest przewidywanie szeregów czasowych Mackeya-Glassa ), zdefiniowanych przez:



gdzie wartości stałych są zwykle przyjmowane jako a = 0,2, b = 0,1 i c = 10. Wartość stałej opóźnienia τ wynosiła 17. Zestaw dostrajający składał się z 500 wzorców. Zmiennymi wejściowymi rozmytego systemu wnioskowania były cztery, które odpowiadają wartościom x(t- 18), x(t- 12), x(t- 6) i x(t). Jako zmienną wyjściową przyjęto x(t + 6). Rozmyty system wnioskowania został zdefiniowany z 4 zbiorami rozmytymi przypisanymi do każdej zmiennej wejściowej, a także do zmiennej wyjściowej. W procesie wnioskowania wykorzystano łącznie 64 reguły wnioskowania. Funkcja energetyczna systemu została zdefiniowana jako średni błąd kwadratowy między wartościami pożądanymi x(t + 6) a wartościami (xt+6), tj.



gdzie L to liczba danych użytych w procesie strojenia (L = 500).Po minimalizacji równania (16), funkcje przynależności rozmytego systemu wnioskowania zostały dostosowane, jak pokazano na rysunku 2.



Na rysunku 3 przedstawiono wyniki predykcji uzyskane przez rozmyty system wnioskowania dla 1000 punktów próbkowania.



Średni kwadratowy błąd estymacji dla proponowanego problemu wyniósł 0,000598 przy odchyleniu standardowym 0,02448. Błąd predykcji dla 1000 punktów próbkowania przedstawiono na rysunku 4.



Dla porównania opracowano rozmyty system wnioskowania skorygowany przez ANFIS (Adaptacyjny Neural-Fuzzy Inference System). Ten rozmyty system wnioskowania składał się z 10 funkcji przynależności dla każdego wejścia, stanowiąc bazę wiedzy utworzoną z 10 reguł. Średni kwadratowy błąd oszacowania dla proponowanego problemu wyniósł 0,000165 przy odchyleniu standardowym 0,0041.

Przykład 2: Modelowanie dwuwejściowej funkcji sinc. W tym przykładzie zastosowano proponowaną metodologię do modelowania dwuwymiarowej funkcji sinc zdefiniowanej wzorem:



Z równomiernie rozłożonych punktów siatki w zakresie wejściowym [-10,10] x [-10,10] równania (17) uzyskano 225 par danych dostrajających. Zastosowany tu rozmyty system wnioskowania zawiera 11 reguł, z 8 funkcjami przynależności przypisanymi do zmiennej wejściowej x, 7 funkcjami przynależności przypisanymi do zmiennej wejściowej y i 3 funkcjami przynależności przypisanymi do zmiennej wyjściowej z. Dane dostrajające i zrekonstruowana powierzchnia są zilustrowane na rysunku 5.



TRENDY NA PRZYSZŁOŚĆ

Metodologię dostosowywania rozmytych systemów wnioskowania przedstawioną w niniejszym artykule można uznać za bardzo obiecującą, nie tylko pod względem wydajności i precyzji uzyskiwanych za pomocą symulacji komputerowych, ale także pod względem jej interpretowalności w odniesieniu do zmiennej wyjściowej, co jest wysoce pożądaną cechą systemu rozmytego. W rzeczywistości jest to najważniejsza cecha, która odróżnia systemy rozmyte od wielu innych technik modelowania. Uważamy, że architektury dostosowywania systemów rozmytych, takie jak proponowana tutaj, idealnie nadają się do wyjaśniania rozwiązań użytkownikom, ponieważ zarówno przesłanki (poprzedniki), jak i konsekwencje reguł są definiowane przez zbiory rozmyte. Przyszłe badania i zastosowania powinny powrócić i skoncentrować się na cechach lingwistycznych systemów rozmytych i ich możliwościach reprezentacji wiedzy, wykorzystując tolerancję na niedokładność i niepewność do podsumowania danych i skupienia się na informacjach istotnych dla decyzji.

WNIOSKI

W niniejszym artykule podkreślono podstawowe założenia związane z procesem dostosowywania rozmytych systemów wnioskowania z wykorzystaniem technik optymalizacji bez ograniczeń. Aby uzyskać bardziej efektywne dostrajanie, konieczne jest prawidłowe określenie funkcji energii dla procesu regulacji. W celu walidacji proponowanej metodologii, wyniki uzyskane za pomocą proponowanego podejścia porównano z wynikami uzyskanymi za pomocą metodologii ANFIS, a także za pomocą problemów modelowania matematycznego. Wyniki uzyskane tą metodologią otwierają nowe perspektywy badań związanych z rozmytymi systemami wnioskowania, umożliwiając tym samym, że problemy dotychczas rozpatrywane wyłącznie za pomocą sztucznych sieci neuronowych mogą być również rozpatrywane za pomocą rozmytych systemów wnioskowania.

WSTĘP

Wielokryterialna optymalizacja ewolucyjna to nowy obszar badań, który zajmuje się optymalizacją problemów składających się z dużej liczby kryteriów wydajnościowych z wykorzystaniem algorytmów ewolucyjnych. Pomimo ogromnego rozwoju wielokryterialnych algorytmów ewolucyjnych (MOEA) w ciągu ostatniej dekady, badania dotyczące problemów składających się z dużej liczby celów są nadal rzadkie. Głównym powodem jest to, że problemy te stwarzają dodatkowe wyzwania w porównaniu z problemami niskowymiarowymi. Niniejsza sekcja zawiera szczegółową analizę tych wyzwań, krytyczny przegląd tradycyjnych rozwiązań i metod optymalizacji ewolucyjnej problemów wielokryterialnych oraz prezentuje najnowsze osiągnięcia w tej dziedzinie.

TŁO

Ostatnio obserwuje się znaczne zainteresowanie optymalizacją problemów składających się z więcej niż trzech kryteriów wydajnościowych, dziedziną, którą Farina i Amato nazwali optymalizacją wieloobiektywową . Do tej pory zdecydowana większość literatury koncentrowała się na problemach dwu- i trójwymiarowych . Jednak w ostatnich latach uwzględnienie wielu wskaźników w sformułowaniu problemu stało się wyraźnym warunkiem wstępnym dla solidnego podejścia w wielu zastosowaniach inżynierskich . Pomimo ogromnego rozwoju, jaki przeszły metody MOEA w ciągu ostatniej dekady i ich dużego sukcesu w różnorodnych zastosowaniach, badania dotyczące wielowymiarowych problemów rzeczywistych są nadal rzadkie . Głównym powodem jest to, że problemy wieloobiektowe stwarzają dodatkowe wyzwania w porównaniu z problemami niskowymiarowymi:

Jeśli wymiarowość przestrzeni obiektywnej wzrasta, to generalnie wymiarowość frontu Pareto-optymalnego również wzrasta.

Liczba punktów potrzebnych do scharakteryzowania frontu Pareto-optymalnego rośnie wykładniczo wraz z liczbą rozpatrywanych celów.

Oczywiste jest, że te dwie cechy stanowią przeszkodę dla większości metod populacyjnych, w tym MOEA. W rzeczywistości, aby zapewnić dobre przybliżenie wielowymiarowego optymalnego frontu Pareto, ta klasa algorytmów musi ewoluować populacje rozwiązań o znacznej wielkości. Ma to głęboki wpływ na ich wydajność, ponieważ ocena każdego pojedynczego rozwiązania może być zadaniem czasochłonnym. Użycie mniejszych populacji nie byłoby realną opcją, przynajmniej w przypadku algorytmów opartych na Pareto, biorąc pod uwagę postępującą utratę presji selekcyjnej, której doświadczają wraz ze wzrostem liczby celów, a co za tym idzie, pogorszenie wydajności, co teoretycznie wykazano w (Farina i Amato, 2004) i empirycznie potwierdzono w (Deb, 2001, str. 404-405). W przeciwieństwie do metod opartych na równaniu Pareto, tradycyjne podejścia optymalizacji wielokryterialnej, które polegają na redukcji problemu wielokryterialnego do serii sparametryzowanych, jednokryterialnych, rozwiązywanych kolejno problemów, nie są dotknięte klątwą wymiarowości. Jednak takie strategie powodują, że każda optymalizacja jest wykonywana niezależnie od siebie, tracąc tym samym niejawny paralelizm algorytmów wielokryterialnych opartych na populacjach. Pozostała część rozdziału zawiera szczegółowy przegląd metod proponowanych w celu rozwiązania pierwszych dwóch problemów wpływających na wielokryterialną optymalizację ewolucyjną oraz omówienie najnowszych postępów w tej dziedzinie.

ŚRODKI ZARADCZE: NAJNOWSZY STAN TECHNIKI

Możliwe rozwiązania zaproponowane w celu rozwiązania problemów pojawiających się w ewolucyjnej optymalizacji wielokryterialnej można ogólnie sklasyfikować w następujący sposób:

o agregacja, cele i priorytety
o warunki optymalności
o redukcja wymiarowości

W kolejnych podrozdziałach przedstawiamy przegląd każdej z tych metod i przegląd podejść, które zostały dotychczas zaproponowane.

Agregacja, cele i priorytety

Ta klasa metod próbuje przezwyciężyć trudności opisane w poprzedniej sekcji poprzez dekompozycję pierwotnego problemu na szereg sparametryzowanych, jednocelowych problemów, które następnie można rozwiązać dowolnym algorytmem klasycznym lub ewolucyjnym. Do tej pory zaprezentowano wiele metod opartych na agregacji, które zazwyczaj opierają się na modyfikacjach podejścia sum ważonych, takich jak rozszerzona funkcja Czebyszewa, które umożliwiają identyfikację odkrytych rozwiązań i eksplorację niewypukłych obszarów powierzchni kompromisu. Jednak problem wyboru skutecznej strategii zmiany wag lub celów, tak aby można było uzyskać reprezentatywne przybliżenie krzywej kompromisu, pozostaje nierozwiązany. Podejście ε-ograniczeń , które opiera się na minimalizacji jednej (najbardziej preferowanej lub podstawowej) funkcji celu, przy jednoczesnym traktowaniu pozostałych celów jako ograniczeń ograniczonych dopuszczalnymi poziomami, było również stosowane w kontekście obliczeń ewolucyjnych. Głównym ograniczeniem tego podejścia jest;koszt obliczeniowy i brak skutecznej strategii zmiany poziomów granicznych (ε). Laumanns i inni zaproponowali wariant oryginalnego podejścia, w którym opracowali schemat wariacyjny oparty na koncepcji dominacji ε-Pareto (efektywności) , który adaptacyjnie generuje wartości ograniczeń, umożliwiając w ten sposób wyczerpującą eksplorację frontu Pareto, pod warunkiem, że schemat ten jest sprzężony z precyzyjnym optymalizatorem jednocelowym. Należy jednak zaznaczyć, że żadna z opisanych powyżej metod nigdy nie została gruntownie przetestowana w kontekście optymalizacji wielocelowej. Metoda wielokrotnego próbkowania pareto jednocelowego (MSOPS 1 i 2), interesująca hybrydyzacja metody agregacji ze specyfikacją celu, została zaprezentowana w (Hughes, 2003, Hughes, 2005). W programie MSOPS presja selekcyjna nie jest zapewniana przez ranking Pareto. Zamiast tego, zestaw zdefiniowanych przez użytkownika wektorów docelowych jest z kolei używany, w połączeniu z metodą agregacji, do oceny wydajności każdego rozwiązania w każdej generacji modelu MOEA. Im większa liczba celów jest bliska rozwiązaniu, tym lepsza jest jego ranga. Autorzy zaproponowali dwie metody agregacji: ważone podejście min-max (zaimplementowane w programie MSOPS) oraz metodę wektor-kąt-odległość-skalowanie (zaimplementowaną w programie MSOPS 2). Wyniki wskazały istotnie statystycznie, że NSGA-II, model MOEA oparty na modelu Pareto, używany do celów porównawczych, był skuteczniejszy w przypadku wielu problemów obiektywnych. Zostało to niedawno potwierdzone przez Wagnera w (Wagner, Beume i Naujoks, 2007), gdzie porównali tradycyjne modele MOEA, metody oparte na agregacji i metody oparte na wskaźnikach dla problemów do 6 celów i zasugerowali bardziej efektywną metodę generowania wektorów docelowych.

Warunki optymalności

Ostatnio wiele uwagi poświęcono roli, jaką warunki optymalności mogą odgrywać w kontekście wielokryterialnej optymalizacji ewolucyjnej, gdy są stosowane do rangowania rozwiązań próbnych na etapie selekcji modelu MOEA, alternatywnie lub w połączeniu z efektywnością Pareto. Farina i inni zaproponowali zastosowanie rozmytego warunku optymalności, ale nie podali bezpośredniego sposobu jego włączenia do modelu MOEA. Köppen i inni zasugerowali również rozmycie relacji dominacji Pareto, które zostało wykorzystane w elitarnym algorytmie genetycznym generacji na syntetycznym modelu MOP. Koncepcja kolana została również wykorzystana w kontekście ewolucyjnej optymalizacji wielokryterialnej. Mówiąc prościej, kolano to fragment powierzchni Pareto, w którym marginalne wskaźniki substytucji są szczególnie wysokie, tj. niewielka poprawa w jednym celu prowadzi do znacznego pogorszenia pozostałych. Graficzną reprezentację przedstawiono na rysunku 1.



Koncepcja polega na tym, że bez wcześniejszych informacji o strukturach preferencji DM kolano prawdopodobnie będzie najbardziej interesującym obszarem. Branke i inni opracowali dwie metodologie wykrywania rozwiązań leżących na kolanach i włączyli je do drugiego etapu (miara zatłoczenia) procedury rankingowej NSGA-II. Pierwsza metodologia polega na ocenie dla każdego osobnika w populacji kąta między nim samym a niektórymi sąsiednimi rozwiązaniami i wykorzystaniu tej wartości do faworyzowania rozwiązań o większych kątach, tj. bliżej kolana. Metodologia ta jednak słabo skaluje się wraz z liczbą celów. Druga strategia odwołuje się do oczekiwanej funkcji użyteczności brzegowej w celu wykrywania rozwiązań położonych blisko kolana. To podejście łatwo rozszerza się wraz z liczbą celów; jednak próbkowanie niezbędne do oceny wartości oczekiwanej funkcji użyteczności brzegowej z pewnym poziomem ufności może być kosztowne. Żadne z tych podejść nie zostało przetestowane w przypadku problemów wielokryterialnych. Koncepcja przybliżonych optymalnych rozwiązań została również w pewnym stopniu zbadana w kontekście ewolucyjnej optymalizacji wielokryterialnej. W szczególności uznano, że ?-efektywność może potencjalnie skutecznie łagodzić niektóre trudności związane z problemami wielokryterialnymi. Niedawne badanie Wagnera wykazało doskonałą skuteczność ?-MOEA w przypadku 6-kryterialnej instancji dwóch syntetycznych funkcji testowych. Dobry przegląd dotyczący zastosowania przybliżonych warunków optymalności przedstawiono w pracy (Burke i Landa Silva, 2006), gdzie autorzy porównali również efekt zastosowania dwóch rozluźnionych form dominacji Pareto jako metod oceny w ramach dwóch MOEA. Niedawno, di Pierro i inni zaproponowali schemat rankingowy oparty na Preference Ordering , warunku optymalności, który uogólnia efektywność Pareto, ale jest bardziej rygorystyczny, i przetestowali go, używając NSGA-II jako powłoki optymalizacyjnej na zestawie siedmiu problemów testowych z maksymalnie ośmioma celami. Wyniki wskazały, że proponowana metodologia znacząco poprawiła właściwości zbieżności standardowego algorytmu NSGA-II we wszystkich problemach testowych. Mocnymi stronami tego podejścia są brak parametrów do dostrajania i fakt, że wykazało bardzo dobrą wydajność przy różnych cechach problemu; wadami jego czas wykonania obliczeń i fakt, że jego połączenie z mechanizmami zachowania różnorodności, które faworyzują ekstremalne rozwiązania, może generować zbyt wysoką presję selekcyjną. W (Sato, Aguirre i Tanaka, 2007) Sato wprowadził podejście mające na celu modyfikację warunku dominacji Pareto stosowanego na etapie selekcji algorytmów Pareto MOEA, zgodnie z którym obszar zdominowany przez dowolny punkt jest zwężany lub rozszerzany zgodnie ze wzorem wyprowadzonym z twierdzenia sinusa, a zakres zwężenia/rozszerzenia jest kontrolowany przez stały współczynnik. Wyniki serii eksperymentów przeprowadzonych z użyciem algorytmu NSGA-II wyposażonego w mechanizm zwężenia/rozszerzenia dla wielokryterialnych problemów plecakowych 0/1 wykazały znacząco lepszą wydajność zbieżności i różnorodności w porównaniu ze standardowym algorytmem NSGA-II. Wykazano jednak również, że optymalna wartość współczynnika zwężenia/rozszerzenia zależy silnie od różnych cech problemu, a nie podano żadnych wskazówek wspierających prawidłowy wybór. Większość współczesnych algorytmów Pareto opiera się na dwuetapowym rankingu w procesie selekcji. Na pierwszym etapie rangi są przypisywane zgodnie z jakąś formą relacji dominacji opartej na Pareto; jeśli istnieją remisy, są one rozwiązywane za pomocą mechanizmów sprzyjających dobremu rozkładowi wzdłuż frontu Pareto badanych rozwiązań. Obecnie uznaje się, że ten drugi etap procedury rankingowej może być w rzeczywistości szkodliwy w przypadku wielu celów, co wykazano w pracy (Purshouse i Fleming, 2003b) w przypadku NSGA-II. Ostatnie wysiłki koncentrują się zatem na zastąpieniu mechanizmów zachowania różnorodności na tym drugim etapie bardziej efektywnymi. Koppen i Yoshida zaproponowali cztery drugorzędne metody rankingowe i przetestowali je, zastępując metodę odległości tłumu w NSGA-II. Wyniki wskazały na lepszą konwergencję we wszystkich przypadkach w porównaniu ze standardowym NSGA-II. Autorzy nie przedstawili jednak żadnych wyników dotyczących wydajności algorytmów w zakresie różnorodności.

Metody redukcji wymiarowości

Celem tej klasy metod jest zazwyczaj transformacja przestrzeni obiektywnej do reprezentacji o niższym wymiarze, jednorazowo (przed optymalizacją) lub iteracyjnie (w miarę postępu poszukiwań). Deb i Saxena opracowali procedurę opartą na analizie głównych składowych (PCA) w celu redukcji wymiaru rozwiązywanego problemu. Procedura polega na przeprowadzeniu serii optymalizacji z wykorzystaniem najnowocześniejszej metody MOEA, z których każda koncentruje się wyłącznie na celach, które PCA znalazła, wyjaśniając większość wariancji na podstawie frontu Pareto uzyskanego w poprzedniej optymalizacji. Niedawno Saxena i Deb rozszerzyli swoją pracę i zastąpili PCA dwuwymiarowymi technikami redukcji: korentropijną PCA i zmodyfikowaną aksjomalną metodą rozwijania wariancji, która może również wykrywać interakcje nieliniowe w przestrzeni obiektywnej. Wyniki wskazały, że pierwsza metoda w pewnym stopniu charakteryzowała się trudnym wyborem najlepszej funkcji jądra, podczas gdy w przypadku drugiej autorzy przeprowadzili znaczną liczbę eksperymentów, aby zasugerować wartości graniczne jedynego wolnego parametru procedury. Należy podkreślić, że te dwa badania są jedynymi, które zakwestionowały nowe algorytmy dla problemów testowych o dużej liczbie wymiarów (do 50 celów). W niedawnym badaniu Brockhoff i Zitzler wprowadzili problem minimalnego podzbioru celów (MOSS), który koncentruje się na identyfikacji największego zbioru celów, który można usunąć bez zmiany struktury dominacji problemu (tj. zbiór rozwiązań optymalnych w sensie Pareto uzyskanych przy uwzględnieniu wszystkich celów lub tylko MOSS jest taki sam) i opracowali dokładny algorytm oraz heurystykę zachłanną do jego rozwiązania. Następnie (Brockhoff i Zitzler, 2006) zaproponowali miarę zmienności dla struktury dominacji i rozszerzyli model MOSS o redukcję wymiarowości z wykorzystaniem predefiniowanych progów zmian struktury problemu. Nie zaproponowali jednak mechanizmu włączania tych algorytmów do modelu MOEA. Ostatnio analiza zależności między celami problemu optymalizacyjnego została z powodzeniem wykorzystana do opracowania skutecznych metod redukcji. Zgodnie z definicjami konfliktu, wsparcia lub harmonii oraz niezależności zaproponowanymi w pracy (Carlsson i Fuller, 1995), Purshouse i Fleming omówili wpływ tych zależności w kontekście wielocelowej optymalizacji ewolucyjnej. W późniejszym badaniu Purshouse i Fleming zasugerowali również, w przypadku niezależności celów, algorytm "dziel i zwyciężaj" oparty na dekompozycji przestrzeni celów.

PRZYSZŁE TRENDY

Jak wynika z powyższej dyskusji, coraz częściej podejmuje się wysiłki na rzecz opracowania strategii, które są w stanie przezwyciężyć ograniczenia metod opartych na równaniu Pareto w rozwiązywaniu problemów o wielu celach. Chociaż ogólnie zgłaszano obiecujące wyniki, większość prezentowanych podejść ma charakter empiryczny, co utrudnia wyciąganie wniosków, które można by uogólnić. Z wyjątkiem technik redukcji wymiarowości, większość dotychczas przedstawionych badań koncentruje się na mechanizmach poprawy rankingu rozwiązań w procesie selekcji. Jednak analiza tych mechanizmów jest zazwyczaj przeprowadzana w izolacji od pozostałych komponentów algorytmów. Naszym zdaniem jest to istotne ograniczenie, z którym będą musiały zmierzyć się algorytmy nowej generacji, w szczególności poprzez analizę tych mechanizmów w odniesieniu do operatorów wariacyjnych. Co więcej, niewiele uwagi poświęcono próbom scharakteryzowania rozwiązań, które dana metoda (należąca do pierwszej lub drugiej kategorii zidentyfikowanej w poprzedniej sekcji) preferuje w odniesieniu do właściwości rozwiązywanego problemu. Potrzebne są zatem ramy teoretyczne do analizy istniejących metod i opracowania bardziej ukierunkowanych podejść. Jak zauważył di Pierro w swojej pracy , gdzie przedstawił teoretyczne ramy do analizy wpływu procedury rankingowej opartej na kolejności preferencji w odniesieniu do relacji współzależności problemu, podejście to umożliwia przewidywanie wpływu zastosowania danej metodologii do konkretnego problemu przy ograniczonej wiedzy a priori, co jest z pewnością zaletą, ponieważ celem opracowywania wydajnych algorytmów jest rozwiązywanie (często po raz pierwszy) rzeczywistych problemów.

WNIOSKI

Przedstawiliśmy kompleksowy przegląd najnowocześniejszych algorytmów ewolucyjnych służących do optymalizacji wielu obiektywnych problemów, omawiając ograniczenia i mocne strony opisanych podejść, a także zasugerowaliśmy przyszłe trendy badawcze w dziedzinie, która zyskuje na popularności.

WSTĘP

Od organizmów jednokomórkowych do bardziej złożonych organizmów wielokomórkowych, aby przetrwać, muszą przetwarzać sygnały ze swojego otoczenia. Nauki obliczeniowe już to zaobserwowały, co można udowodnić, posługując się sztucznymi sieciami neuronowymi (SSN). To narzędzie obliczeniowe opiera się na układzie nerwowym zwierząt, ale nie tylko komórki nerwowe przetwarzają informacje w organizmie. Każda komórka musi przetworzyć plan rozwoju i funkcjonowania zakodowany w jej DNA, a każda z tych komórek wykonuje ten program równolegle z pozostałymi. Inną interesującą cechą komórek naturalnych jest to, że tworzą one systemy odporne na częściowe awarie: drobne błędy nie powodują globalnego załamania systemu. Niniejsza praca proponuje model oparty na przetwarzaniu informacji DNA, ale adaptujący go do ogólnego przetwarzania informacji. Model ten może opierać się na zestawie technik zwanych sztuczną embriogenezą , które adaptują cechy komórek biologicznych do rozwiązywania różnych problemów.

TŁO

Dziedzina obliczeń ewolucyjnych (EC) dała początek zestawowi modeli zgrupowanych pod nazwą sztucznej embriologii (AE), wprowadzonej po raz pierwszy przez Stanleya i Miikkulainnena . Grupa ta odnosi się do wszystkich modeli, które próbują zastosować pewne cechy biologicznych komórek embrionalnych do komputerowego rozwiązywania problemów, tj. samoorganizacji, odporności na awarie i równoległego przetwarzania informacji. Prace nad obliczeniami ewolucyjnymi (AE) obejmują dwa punkty widzenia. Z jednej strony można znaleźć modele gramatyczne oparte na L-systemach (Lindenmayer A. 1968), które stosują podejście odgórnego problemu. Z drugiej strony można znaleźć modele chemiczne oparte na ideach Turinga (Turing A. 1952), które stosują podejście odgórne. Podejście gramatyczne czasami wykorzystywało te modele do badania ewolucji sieci neuronowych (SN), znanej jako neuroewolucja. Pierwszy system neuroewolucji został opracowany przez Kitano . W swojej pracy Kitano pokazuje, że możliwe było rozwinięcie macierzy łączności ANN poprzez zestaw reguł przepisywania. Inną godną uwagi pracą jest zastosowanie systemów L przez Hornby′ego i Pollacka mulowanym trójwymiarowym środowisku fizycznym. Na koniec warto wspomnieć o pracach Gruau , w których autor wykorzystuje drzewa gramatyczne do kodowania kroków rozwoju sieci neuronowej z pojedynczej komórki poprzednika. W podejściu chemicznym punktem wyjścia w tej dziedzinie jest modelowanie sieci regulacji genów, przeprowadzone przez Kauffmanna w 1969 roku . Następnie przeprowadzono szereg prac na tematy takie jak złożone zachowanie generowane przez fakt, że zróżnicowana ekspresja niektórych genów ma kaskadowy wpływ na ekspresję innych . Biorąc pod uwagę prace dotyczące sieci regulacji genów, najbardziej istotne modele to: model Kumara i Bentleya , który wykorzystuje teorię białek fraktalnych Bentley, P.J., Kumar, S. 1999; do obliczania stężenia białka; model Eggenbergera ), który wykorzystuje koncepcje różnicowania komórkowego i ruchu komórkowego do określania połączeń komórkowych; oraz prace Dellaerta i Beera , którzy proponują model uwzględniający ideę operonów biologicznych w celu kontrolowania ekspresji modelu, w którym funkcja przyjmuje matematyczne znaczenie funkcji boolowskiej.

MODEL SIECI REGULACJI GENETYCZNEJ

Komórki układu biologicznego są głównie determinowane przez nić DNA, geny i białka zawarte w cytoplazmie. DNA to struktura, która przechowuje zakodowaną w genach informację niezbędną do rozwoju układu. Geny są aktywowane lub transkrybowane dzięki informacji o kształcie białek, która znajduje się w cytoplazmie i składa się z dwóch głównych części: sekwencji, która identyfikuje białko, które powstanie w wyniku transkrypcji genu, oraz promotora, który identyfikuje białka potrzebne do transkrypcji genu. Innym istotnym aspektem genów biologicznych jest różnica między genami konstytutywnymi a genami regulacyjnymi. Te drugie są transkrybowane tylko wtedy, gdy obecne są białka zidentyfikowane w części promotorowej. Geny konstytutywne są transkrybowane zawsze, chyba że są hamowane przez obecność białek zidentyfikowanych w części promotorowej, działając wówczas jako opresory genów. W niniejszej pracy podjęto próbę częściowego modelowania tej struktury w celu dopasowania niektórych jej możliwości do modelu obliczeniowego; w ten sposób system miałby strukturę podobną do powyższej

Proponowany model

Opracowano różne warianty modelu w oparciu o koncepcje biologiczne. Proponowany sztuczny system komórkowy opiera się na interakcji sztucznych komórek za pomocą wiadomości zwanych białkami. Komórki te mogą się dzielić, umierać lub generować białka,które będą działać jako wiadomości zarówno dla nich samych, jak i dla komórek sąsiednich. System ma wyrażać globalne zachowaniew zakresie przetwarzania informacji. Takie zachowanie wynikałoby z informacji zakodowanej w zestawie zmiennych komórki, które, analogicznie do komórek biologicznych, zostaną nazwane genami. Centralnym elementem naszego modelu jest sztuczna komórka. Każda komórka posiada zakodowany ciąg binarny informacji regulujący jej funkcjonowanie. Zgodnie z analogią biologiczną, ciąg ten będzie nazywany DNA. Komórka posiada również strukturę do przechowywania i zarządzania białkami generowanymi przez własną komórkę i tymi otrzymanymi z komórek sąsiednich; Zgodnie z modelem biologicznym, struktura ta nazywana jest cytoplazmą. DNA sztucznej komórki składa się z jednostek funkcjonalnych, zwanych genami. Każdy gen koduje białko lub informację (wytwarzaną przez gen). Struktura genu składa się z czterech części :

o Sekwencja: ciąg binarny odpowiadający białku kodującemu gen
o Promotory: to obszar genu, który wskazuje białka potrzebne do transkrypcji genu.
o Składnik: ten bit określa, czy gen jest składowy, czy regulujący
o Procent aktywacji (wartość binarna): procent minimalnego stężenia białek promotorowych wewnątrz komórki, który powoduje transkrypcję genu.

Transkrypcja kodowanego białka zachodzi, gdy promotory genów nieskładowych pojawiają się w cytoplazmie komórki z określoną częstością. Z drugiej strony, geny składowe są ekspresjonowane, dopóki ekspresja ta nie zostanie zahamowana przez obecną częstość genów promotorowych. Innym fundamentalnym elementem odpowiedzialnym za przechowywanie i zarządzanie białkami otrzymywanymi lub produkowanymi przez sztuczną komórkę jest cytoplazma. Przechowywane białka mają określony czas życia, zanim zostaną usunięte. Cytoplazma sprawdza, które i ile białek jest potrzebnych komórce do aktywacji genów DNA, i w ten sposób odpowiada na wszystkie wymagania komórkowe dotyczące stężenia danego rodzaju białka. Cytoplazma również pobiera białka ze struktury, jeśli są one potrzebne do transkrypcji genu.

Możliwości przetwarzania informacji

Komórki biologiczne, oprócz generowania struktur, działają jako małe procesory do równoległego przetwarzania informacji z pozostałymi komórkami. Informacje, które przetwarzają, pochodzą zarówno z ich własnej generacji, jak i z ich otoczenia. Na podstawie tego faktu, niniejsza praca zbadała możliwości generacji struktury modelu, chociaż wykorzystując strukturę genu i białka, można zdefiniować zbiór operacji o strukturze podobnej do algebry Boole′a. Przestrzenią do zdefiniowania operacji byłaby obecność lub brak określonych białek w systemie, podczas gdy wynikiem operacji byłoby białko zawarte/zakodowane w genie. Operacja AND byłaby modelowana za pomocą genu, który do swojej ekspresji potrzebowałby wszystkich białek swoich promotorów. Operacja OR byłaby modelowana za pomocą dwóch genów, które pomimo różnych promotorów, dawałyby to samo białko. Wreszcie, operacja NOT byłaby modelowana za pomocą części składowej, która zmienia wydajność tego genu. Obecność białek należących do promotorów implikowałaby brak białka będącego wynikiem genu w systemie. To zachowanie jest podobne do sieci regulacji genów Sztuczne Sieci Neuronowe (ANN) można skonfigurować do realizacji tych zadań przetwarzania. To analogiczne działanie wydaje się wskazywać, że system może wykonywać bardziej złożone zadania, podobnie jak ANN .

TRENDY NA PRZYSZŁOŚĆ

Ostatecznym celem tej grupy jest opracowanie sztucznego modelu opartego na modelu biologicznym, o podobnej pojemności przetwarzania informacji jak ANN. Aby zrealizować ten cel, opracowano kilka prostych testów sprawdzających działanie modelu. Wyniki tych testów pokazują, że możliwe jest przetwarzanie informacji z wykorzystaniem sieci regulacji genów jako systemu bazowego. Od tego momentu należy przejść do kolejnych etapów rozwoju, aby opracować bardziej złożone zadania i zbadać działanie modelu. Innym celem przyszłych prac może być połączenie możliwości modelu w zakresie przetwarzania informacji z możliwościami generowania struktury przedstawionymi w pracach

WNIOSKI

W niniejszej pracy niektóre właściwości komórek biologicznych zostały zaadaptowane do sztucznego modelu. W szczególności koncepcja sieci regulacji genów została zaadaptowana do przetwarzania informacji. Ta adaptacja opiera się na wykorzystaniu reguły transkrypcji do określenia struktury podobnej do algebry Boole′a. Rezultatem tej adaptacji jest to, że obecnie możemy ją wykorzystać do opracowania testów przetwarzania informacji. Na koniec należy zauważyć, że ten nowy sposób generowania sieci przetwarzania informacji wymaga wielu testów i badań, zanim zostanie ustabilizowany jako skonsolidowana technika przetwarzania informacji.

Wizualizacja baz danych dotyczących raka z wykorzystaniem przestrzeni hybrydowych

WSTĘP

Według Światowej Organizacji Zdrowia (WHO), organu zarządzającego i koordynującego działania w zakresie zdrowia w ramach systemu Narodów Zjednoczonych (http://www.who.int/cancer/en/), spośród 58 milionów zgonów w 2005 roku, nowotwory odpowiadają za 7,6 miliona (czyli 13%) wszystkich zgonówna świecie. To plasuje nowotwory jako jedną z głównych przyczyn zgonów na świecie, a rak płuc (główny nowotwór prowadzący do śmiertelności) odpowiada za 1,3 miliona zgonów rocznie. Zatem znaczenie zrozumienia mechanizmów raka płuc jest oczywiste. Jednym z podejść jest szybka kwantyfikacja poziomów ekspresji genów w próbkach zdrowej i chorej tkanki płucnej. Ta nowa dziedzina, łącząca wiedzę biologów, informatyków i matematyków, znana jest jako bioinformatyka i dostarcza ogromnych ilości danych o bardzo wielowymiarowej naturze, które wymagają zrozumienia.

TŁO

Rosnąca złożoność procedur analizy danych utrudnia użytkownikowi (niekoniecznie matematykowi ani ekspertowi w dziedzinie eksploracji danych) wyodrębnianie użytecznych informacji z wyników generowanych różnymi technikami. To sprawia, że graficzna reprezentacja staje się bezpośrednio atrakcyjna, a wirtualna rzeczywistość (VR) jest dla niej odpowiednim paradygmatem. Wirtualna rzeczywistość jest elastyczna; pozwala na konstruowanie różnych wirtualnych światów reprezentujących te same podstawowe informacje, ale o odmiennym wyglądzie i charakterze. VR umożliwia immersję, czyli pozwala użytkownikowi nawigować wewnątrz danych i wchodzić w interakcje z obiektami w świecie. VR tworzy żywe doświadczenie. Użytkownik nie jest jedynie biernym obserwatorem, ale aktorem w świecie. VR jest szeroki i głęboki. Użytkownik może postrzegać świat VR jako całość i/lub skupić uwagę na określonych szczegółach. Nie mniej ważny jest fakt, że do interakcji ze światem wirtualnym nie jest wymagana żadna wiedza matematyczna, a użytkownik potrzebuje jedynie minimalnych umiejętności obsługi komputera. Technika rzeczywistości wirtualnej do wizualnej eksploracji danych w heterogenicznych, niedokładnych i niekompletnych systemach informacyjnych została wprowadzona w (Valdés, J.J., 2002) . Celem niniejszego artykułu jest zbadanie możliwości konstrukcji wysokiej jakości przestrzeni VR do wizualnej eksploracji danych (w przeciwieństwie do klasycznej eksploracji danych z wykorzystaniem techniki optymalizacji wielokryterialnej zastosowanej do zrozumienia publicznie dostępnego zbioru danych o ekspresji genu raka płuc. Podejście to zapewnia zarówno rozwiązanie wcześniej omówionego problemu, jak i możliwość uzyskania zbioru przestrzeni, w których różne cele są wyrażone w różnym stopniu, pod warunkiem, że żadna inna przestrzeń nie mogłaby poprawić żadnego z rozważanych kryteriów indywidualnie (jeśli przestrzenie są konstruowane przy użyciu rozwiązań wzdłuż frontu Pareto). Strategia ta stanowi udoskonalenie koncepcyjne w porównaniu z przestrzeniami obliczonymi na podstawie rozwiązań uzyskanych za pomocą algorytmów optymalizacji jednokryterialnej, w których funkcją celu jest ważona kompozycja obejmująca różne kryteria.

PODEJŚCIE WIELOCELOWE: PERSPEKTYWA HYBRYDOWA

Aby sformułować problem w oparciu o optymalizację wielocechową, należy określić zbiór funkcji celu, reprezentujących odpowiadające im kryteria, które muszą być jednocześnie spełnione przez rozwiązanie. W pierwszym przybliżeniu można wykorzystać minimalizację miary utraty informacji o podobieństwie między przestrzenią oryginalną a przekształconą oraz miarę błędu klasyfikacji obiektów w nowej przestrzeni. Oczywiście, można narzucić więcej wymagań rozwiązaniu, dodając odpowiednie funkcje celu. Zgodnie z zasadą oszczędności, niniejszy artykuł rozważy zastosowanie tylko dwóch kryteriów, a mianowicie błędu Sammona dla przypadku nienadzorowanego oraz średniego błędu klasyfikacji walidowanego krzyżowo z rozpoznawaczem wzorców k najbliższych sąsiadów dla przypadku nadzorowanego. Bliskość (lub podobieństwo) obiektu do innego obiektu można zdefiniować za pomocą odległości (lub podobieństwa) obliczonej na podstawie zmiennych niezależnych i można ją zdefiniować za pomocą różnych miar. W niniejszym przypadku wybrano znormalizowaną odległość euklidesową:

Zachowanie struktury: perspektywa nienadzorowana

Przykłady miar błędów często stosowanych do zachowania struktury to:

W przypadku danych heterogenicznych obejmujących mieszaniny zmiennych nominalnych i ilorazowych, miara podobieństwa Gowera okazała się odpowiednia. Podobieństwo między obiektami i i j jest określone wzorem

gdzie waga atrybutu (w_ijk) jest równa 0 lub 1 w zależności od tego, czy porównanie jest uznane za prawidłowe dla atrybutu k. Jeśli v_k(i), v_k(j) są wartościami atrybutu k odpowiednio dla obiektów i i j, porównanie nieprawidłowe występuje, gdy brakuje co najmniej jednego z nich. W takiej sytuacji w,sub>ijk jest ustawione na 0. W przypadku atrybutów ilościowych (takich jak te z zestawów danych użytych w artykule), oceny s_ijk są przypisywane jako

gdzie R<sub>k
Miarę tę można łatwo rozszerzyć na zmienne porządkowe, interwałowe i inne. Można również zastosować schematy ważenia, aby uwzględnić zróżnicowaną istotność zmiennych deskryptorowych.

Optymalizacja wielokryterialna z wykorzystaniem algorytmów genetycznych

Ulepszeniem tradycyjnego algorytmu ewolucyjnego jest umożliwienie osobnikowi posiadania więcej niż jednej miary dostosowania w populacji. Jednym ze sposobówzastosowania takiego ulepszenia jest na przykład użycie ważonej sumy więcej niż jednej wartości dostosowania. Optymalizacja wielokryterialna oferuje jednak inny możliwy sposób na umożliwienie takiego ulepszenia. W drugim przypadku pojawia się problem dla algorytmu ewolucyjnego w wyborze osobników do włączenia do następnej populacji, ponieważ zbiór osobników zawarty w jednej populacji wykazuje front Pareto najlepszych aktualnych osobników, a nie pojedynczego najlepszego osobnika. Większość algorytmów wielokryterialnych wykorzystuje koncepcję dominacji, aby rozwiązać ten problem.

Rozwiązanie x(1) dominuje nad rozwiązaniem x(2) dla zbioru m funkcji celów 12</sub>(x), …, f_m(x)>, jeśli •  x₍₁₎ nie jest gorsze niż x(sub>(2) dla wszystkich celów. Na przykład, f₃(x(₁₎) ? f₃x₍₂₎), jeśli f,sub>3(x) jest celem minimalizacji.

•  x₍₁₎6(x,sub>(1)) > f₆(x(₂)), jeśli f₆(x) jest celem maksymalizacji.

Jednym z konkretnych algorytmów optymalizacji wielokryterialnej jest elitarny, niezdominowany algorytm sortowania genetycznego (NSGA-II) . Cechuje go to, że i) wykorzystuje elitaryzm, ii) wykorzystuje jawny mechanizm zachowania różnorodności oraziii) kładzie nacisk na rozwiązania niezdominowane.

Badanie oryginalne

Porównano ekspresję genów w dla tkanki płucnej z ciężką rozedmą (od palaczy poddanych operacji redukcji objętości płuc) oraz dla tkanki płucnej z prawidłową lub łagodną rozedmą (od palaczy poddanych resekcji guzków płucnych). Oryginalna baza danych zawierała 30 próbek (18 z ciężką rozedmą, 12 z łagodną rozedmą lub bez rozedmy) z 22 283 atrybutami. Geny o wysokich wartościach p detekcji zostały odfiltrowane, co doprowadziło do zestawu danych zawierającego 9336 genów, które wykorzystano do dalszej analizy. Do zidentyfikowania grupy genów, których ekspresja w płucach pozwalała odróżnić ciężką rozedmę od łagodnej rozedmy lub jej braku, wykorzystano dziewięć algorytmów klasyfikacyjnych. Najpierwdla każdego algorytmu przeprowadzono selekcję modelu metodą walidacji krzyżowej z pominięciem jednego genu, a listę genów odpowiadającą najlepszemu modelowi zapisano. Do dalszej analizy wybrano geny zgłoszone przez co najmniej cztery algorytmy klasyfikacyjne (102 geny). W oparciu o tegeny przeprowadzono dwuwymiarowe klasteryzacje hierarchiczne z wykorzystaniem korelacji Pearsona, które pozwoliły odróżnić ciężką rozedmę płuc od łagodnej rozedmy lub jej braku. Zidentyfikowano również inne geny, które mogą być przyczynowo zaangażowane w patogenezę rozedmy płuc.

Ustawienia eksperymentalne

Każda próbka w tym badaniu jest wektorem w przestrzeni wielowymiarowej, a zatem bezpośrednia analiza struktury tych danych oraz relacji między zmiennymi deskryptorowymi (genami) a rodzajem próbki (prawidłowa lub nowotworowa) jest niemożliwa. Co więcej, w zbiorze genów występuje mieszanina genów potencjalnie istotnych z innymi, które są nieistotne, zaszumione itd. Konieczność jednoczesnego znalezienia reprezentacji wizualnej (3D) uwzględniającej (w jak największym stopniu) zbiór wzajemnych powiązań obiektów zdefiniowanych przez pierwotne atrybuty oraz konstrukcja nowej przestrzeni cech skutecznie różnicującej dwie klasy obecnych obiektów sprawia, że problem ten nadaje się do wielokryterialnego podejścia optymalizacyjnego. Zastosowano niewielką liczebność populacji i liczbę pokoleń, ze stosunkowo wysokim prawdopodobieństwem mutacji, aby umożliwić bogatszą różnorodność genetyczną. Zastosowano randomizacjęzestawu obiektów danych w celu zmniejszenia błędu w składzie walidowanych krzyżowo zestawów, zapewniając bardziej równomierny rozkład klas między kolejnymi podzbiorami trenującymi i testowymi. Liczbę zestawów ustalono z uwzględnieniem liczebności próby.

Wyniki

Zestaw rozwiązań niezdominowanych uzyskanych za pomocą algorytmu NSGA-II przedstawiono na wykresie punktowym na Rysunku 1(a), gdzie oś pozioma przedstawia średni błąd knn walidowanych krzyżowo, a oś pionowa błąd Sammona. Przybliżone położenie frontu Pareto jest określone przez wielokąt wypukły łączący rozwiązania dostarczane przez chromosomy 2, 1, 10 itd. Chromosom 2 definiuje przestrzeń z idealnym rozwiązaniem problemu nadzorowanego w kategoriach klas "brak lub łagodna rozedma" i "ciężka rozedma" (błąd k_nn = 0), ale kosztem poważnego zniekształcenia przestrzeni. Natomiast chromosom 1 aproksymuje czyste rozwiązanie nienadzorowane (z niskim błędem Sammona). Jego błąd klasyfikacji jest duży, co wskazuje, że niewiele nieliniowych cech zachowujących strukturę podobieństwa nie ma mocy klasyfikacyjnej. Może to być spowodowane dużą ilością szumu atrybutów, redundancji i nieistotności w zestawie 22 283 oryginalnych genów. Oczywiste jest, że nie jest możliwe przedstawienie przestrzeni rzeczywistości wirtualnej na statycznym nośniku. Jednakże kompozycja migawek przestrzeni VR przy użyciu rozwiązań wzdłuż aproksymacji frontu Paret. Różne odwzorowania (nawet z istotnymi różnicami z punktu widzenia błędu odwzorowania) prowadzą do podobnych trójwymiarowych reprezentacji wizualnych, co wskazuje na dobrą powtarzalność rozwiązań. Podobieństwa są związane z głównymi rozkładami chmur punktów, które są zachowane, podczas gdy mogą występować lokalne rozbieżności w odniesieniu do rozmieszczenia niektórych obiektów. Rozwiązanie spełniające błąd klasyfikacji w możliwie największym stopniu (w rzeczywistości z błędem 0) pokazano na rys. 1(b), gdzie obie klasy są podzielone na 2 główne chmury punktów i odrębny punkt, Obiekt 6, umieszczony oddzielnie od chmur. Widać, że Obiekt 6 jest umieszczony stosunkowo inaczej w przestrzeniach, które obejmują najlepszy błąd Sammona (rys. 1(d) i kompromisy między celem błędu klasyfikacji a celem błędu Sammona . Dlatego też wizualnie ta druga przestrzeń reprezentuje rozwiązanie kompromisowe między dwoma celami i jest kompromisem między dwiema funkcjami celu. Należy pamiętać, że informacja o klasie nie jest w ogóle wykorzystywana do obliczania przestrzeni. Chromosom 10, można uznać za najlepsze wielokryterialne rozwiązanie kompromisowe, w którym oba kryteria błędu są jednocześnie tak niskie, jak to możliwe. Wykazuje on rozsądne rozróżnianie klas z niedużym zniekształceniem struktury podobieństwa, co jest bardzo miarodajnym wynikiem.

TRENDY NA PRZYSZŁOŚĆ

Wizualizacja danych jest potencjalnie interesująca dla różnych środowisk badawczych, a autorzy zastosowali różne podejścia wizualizacyjne do innych chorób związanych z danymi medycznymi, takich jak twardzina skóry, rak piersi, choroba Alzheimera i białaczka. Jednak w rzeczywistości autorzy nie ograniczają się do danych medycznych, dla których wstępnie zbadali również dane pochodzące na przykład z dziedzin hydrochemii i poszukiwań geofizycznych.

WNIOSKI

Wprowadzono podejście optymalizacji wielokryterialnej do problemu obliczania przestrzeni rzeczywistości wirtualnej w kontekście wizualnej eksploracji danych i odkrywania wiedzy w odniesieniu do struktur relacyjnych (np. baz danych). Wielokryterialna procedura została oparta na NSGA-II, wykorzystując dwie funkcje obiektywne reprezentatywne dla kryteriów nienadzorowanych i nadzorowanych (średni błąd knn z walidacją krzyżową jako miara błędnej klasyfikacji oraz błąd Sammona jako miara utraty struktury podobieństwa). Metodologię tę zastosowano do analizy wielowymiarowych danych genomicznych zebranych w ramach badań nad rakiem płuc. Przybliżenie frontu Pareto było rozpoznawalne w rozwiązaniach dostarczonych przez populację końcową. Wybrane rozwiązania z tego przybliżenia zostały wykorzystane do skonstruowania sekwencji wizualizacji pokazujących przejście od przestrzeni z całkowitą separacją klas i słabym zachowaniem podobieństwa do przestrzeni o odwróconych cechach. Zidentyfikowano rozwiązanie z rozsądnym kompromisem między tymi dwoma kryteriami, które wyraźnie zawierało właściwości obu skrajnych przestrzeni rozwiązań. Wyniki tych badań, choć wstępne, wykazały duży potencjał i wymagają dalszych badań.