WSTĘP

Neuro-rozmyte to systemy hybrydowe, które łączą zdolność uczenia się sieci neuronowych z interpretacją lingwistyczną rozmytych systemów wnioskowania . Systemy te były dość intensywnie testowane w zadaniach uczenia maszynowego. Wynika to głównie z szeregu czynników: stosowalności algorytmów uczenia opracowanych dla sieci neuronowych; możliwości promowania integracji wiedzy jawnej i ukrytej; oraz możliwości ekstrakcji wiedzy w postaci reguł rozmytych. Większość znanych systemów neuro-rozmytych ma jednak ograniczenia dotyczące liczby dozwolonych danych wejściowych lub ograniczonej (lub nieistniejącej) formy tworzenia własnej struktury i reguł. W niniejszym artykule opisano nową klasę modeli neuro-rozmytych, zwanych Hierarchicznymi Neuro-Rozmytymi Systemami BSP (HNFB). Modele te wykorzystują partycjonowanie BSP (Binary Space Partitioning) przestrzeni wejściowej i zostały opracowane w celu ominięcia tradycyjnych wad systemów neuro-rozmytych. Niniejszy artykuł przedstawia modele HNFB oparte na algorytmie uczenia nadzorowanego. Modele te zostały ocenione w wielu zastosowaniach testowych związanych z klasyfikacją i prognozowaniem szeregów czasowych. Drugi artykuł, zatytułowany Hierarchiczne Systemy Neuro-Rozmyte Część II, koncentruje się na hierarchicznych modelach neuro-rozmytych opartych na algorytmach uczenia się przez wzmacnianie.

TŁO

Hybrydowe systemy inteligentne, opracowane z wykorzystaniem technik takich jak logika rozmyta i sieci neuronowe, znalazły zastosowanie w obszarach, w których tradycyjne podejścia nie były w stanie zapewnić satysfakcjonujących rozwiązań. Wielu badaczy próbowało zintegrować te dwie techniki, tworząc modele hybrydowe, które łączą ich zalety i minimalizują ich ograniczenia i wady. W tym celu stworzono hybrydowe systemy neuro-rozmyte . Tradycyjne modele neuro-rozmyte, takie jak ANFIS , NEFCLASS i FSOM , mają ograniczoną zdolność tworzenia własnej struktury i reguł . Ponadto większość tych modeli wykorzystuje podział siatki przestrzeni wejściowej, który ze względu na problem eksplozji reguł jest bardziej odpowiedni dla aplikacji z mniejszą liczbą danych wejściowych. Gdy potrzebna jest większa liczba zmiennych wejściowych, wydajność systemu ulega pogorszeniu. W związku z tym opracowano hierarchiczne systemy neuro-rozmyte, aby przezwyciężyć te podstawowe ograniczenia. Opracowano różne modele tej klasy systemów neuro-rozmytych, oparte na technice nadzorowanej.

HIERARCHICZNE SYSTEMY NEURO-FUZZY

W tej sekcji przedstawiono nową klasę systemów neuro-fuzzy opartych na partycjonowaniu hierarchicznym. Opracowano dwa podzbiory hierarchicznych systemów neuro-fuzzy (HNF), w zależności od zastosowanego procesu uczenia: modele uczenia nadzorowanego (HNFB , HNFB-1 , HNFB-Mamdani ); oraz modele uczenia się przez wzmacnianie (RL-HNFB, RL-HNFP ). Niniejszy artykuł koncentruje się na pierwszym podzbiorze modeli, które opisano w następnych sekcjach.

HIERACHICZNY NEURO-FUZZY BSP MODEL

Podstawowa komórka BSP Neuro-Fuzzy

Komórka HNFB to neuro-fuzzy minisystem, który wykonuje rozmyte partycjonowanie binarne przestrzeni wejściowej. Komórka HNFB generuje ostre dane wyjściowe po procesie defuzyfikacji. Rysunek 1(a)



ilustruje funkcjonalność komórki, gdzie "x" reprezentuje zmienną wejściową; ?ρ(x) i μ(x) to odpowiednio funkcje przynależności low i high, które generują poprzedniki dwóch reguł rozmytych; a y to ostre dane wyjściowe. Lingwistyczna interpretacja odwzorowania implementowanego przez komórkę HNFB jest podana przez następujące reguły: o Jeśli x∈ ρ, to y = d₁
o Jeśli x ∈μ, to y = d₂.

Każda reguła odpowiada jednej z dwóch partycji wygenerowanych przez BSP. Każda partycja może być z kolei podzielona na dwie części za pomocą innej komórki HNFB. Profile funkcji przynależności ρ(x) i μ(x) są komplementarnymi funkcjami logistycznymi. Wyjście y komórki HNFB (proces defuzyfikacji) jest dane przez średnią ważoną. Ponieważ funkcja przynależności ρ(x) jest dopełnieniem do 1 funkcji przynależności μ(x), stosuje się następujące równanie:



gdzie α_i symbolizuje poziom aktywacji reguły w partycji i i jest podane wzorem: α₁ = ρ(x); α₂ = μ(x). Każde di odpowiada jednemu z trzech możliwych następników poniżej:

o Singleton: Przypadek, w którym d_i = stała.
o Liniowa kombinacja danych wejściowych:



gdzie: x_k jest k-tym wejściem systemu; w_k reprezentuje wagę związaną z wejściem x_k; "n" jest równe całkowitej liczbie wejść; a w₀ odpowiada wartości stałej.

o Wyjście etapu poprzedniego poziomu: Przypadek, w którym d_i = y_j, gdzie y_j reprezentuje wyjście ogólnej komórki "j", której wartość jest również obliczana za pomocą równania (1).

Architektura HNFB

Model HNFB można opisać jako system zbudowany z połączeń między komórkami HNFB. Rysunek 1(b) ilustruje system HNFB wraz z odpowiednim podziałem przestrzeni wejściowej. W tym systemie początkowe podziały 1 i 2 (komórka "BSP0") zostały podzielone; stąd konsekwencją jego reguł są odpowiednio wyjścia BSP1 i BSP2. Z kolei te podsystemy mają odpowiednio wartości d₁₁, y₁₂, d₂₁ i d₂₂. Następna wartość y₁₂ jest wartością wyjściową komórki "BSP12". Wartość wyjściowa układu na rysunku 1(b) jest podana równaniem (2).



Należy podkreślić, że chociaż każda komórka BSP dzieli przestrzeń wejściową tylko na dwa zbiory rozmyte (niski i wysoki), cała architektura HNFB dzieli wszechświat dyskursu każdej zmiennej na tyle partycji, ile jest to konieczne. Liczba partycji jest określana w trakcie procesu uczenia. Na przykład na rysunku 1(c), lewa górna część przestrzeni wejściowej (partycja 12 w kolorze szarym) została dodatkowo podzielona przez zmienną poziomą x1, co daje trzy zbiory rozmyte dla całego wszechświata dyskursu tej konkretnej zmiennej.

Algorytm uczenia

System HNFB posiada algorytm uczenia oparty na metodzie gradientu prostego, który uczy się struktury modelu, a co za tym idzie, reguł lingwistycznych. Parametry definiujące profile funkcji przynależności poprzedników i następników są traktowane jako wagi rozmyte systemu neuro-rozmytego. Aby zapobiec nieskończonemu wzrostowi struktury, stworzono bezwymiarowy parametr o nazwie tempo dekompozycji (δ). Wyniki uzyskane w problemach klasyfikacji i prognozowania szeregów czasowych przedstawiono w sekcji "Studia przypadków".

HIERARCHICZNY NEURO-FUZZY BPS DO KLASYFIKACJI

Oryginalny model HNFB zapewnia bardzo dobre wyniki w aproksymacji funkcji i prognozowaniu szeregów czasowych. Nie jest on jednak idealny do zastosowań w klasyfikacji wzorców, ponieważ ma tylko jedno wyjście i wykorzystuje metodę wnioskowania Takagi-Sugeno ,co zmniejsza interpretowalność bazy reguł. Dlatego opracowano nowy hierarchiczny neuro-fuzzy model BSP dedykowany klasyfikacji wzorców i ekstrakcji reguł, zwany odwróconym modelem HNFB lub HNFB-1, który jest w stanie wyodrębnić reguły klasyfikacji, takie jak: Jeśli x to A, a y to B, to wzorzec wejściowy należy do klasy Z. Ten nowy hierarchiczny model neuro-fuzzy jest nazywany odwróconym, ponieważ wykorzystuje proces uczenia się oryginalnego modelu HNFB do generowania struktury modelu. Po tej pierwszej fazie uczenia się struktura jest odwracana, a uzyskiwana jest architektura modelu HNFB-1. Poniżej opisano podstawową komórkę tej nowej odwróconej struktury.

Podstawowa komórka odwróconego HNFB

Podobnie jak w oryginalnym modelu HNFB, podstawowa komórka odwróconego HNFB to neuro-rozmyty minisystem, który wykonuje rozmyte partycjonowanie binarne w określonej przestrzeni zgodnie z tymi samymi funkcjami przynależności ρ i μ. Jednak po procesie defuzyfikacji komórka odwróconego HNFB generuje dwa wyraźne wyjścia zamiast jednego. Rysunek(a) ilustruje wnętrze komórki odwróconego HNFB.



Zakładając, że funkcje przynależności są komplementarne, wyjścia komórki HNFB_-1 są podane: y₁ = β * ρ(x) i y₂ = β * μ(x) , gdzie ? odpowiada jednemu z dwóch możliwych przypadków poniżej:

o β = wejście pierwszej komórki: zatem β = 1. o β= jest wyjściem komórki z poprzedniego poziomu: zatem ?=y_j, gdzie y_j reprezentuje jedno z dwóch wyjść ogólnej komórki "j".

Odwrócona architektura HNFB

Rysunek(b) przedstawia przykład oryginalnej architektury HNFB uzyskanej podczas fazy uczenia bazy danych zawierającej trzy odrębne klasy, natomiast rysunek (c) pokazuje, jak uzyskano model HNFB-1 po procesie inwersji.





W architekturze HNFB_-1 przedstawionej na rysunku(c) można zauważyć, że system klasyfikacji ma kilka wyjść (od y₁ do y₅), po jednym dla każdego istniejącego liścia w oryginalnej architekturze HNFB. Wyjścia komórek liści oblicza się za pomocą następujących równań (z wykorzystaniem komplementarnych funkcji przynależności):



gdzie ρ_i i μ_i to funkcje przynależności dla BSP_i.

Wyjścia systemu HNFB_-1

Po wykonaniu inwersji, wyjścia są łączone z komórkami T-conorm (operator OR), które definiują klasy



. Początkowa procedura łączenia komórek liściowych z neuronami T-conorm polega na połączeniu wszystkich komórek liściowych ze wszystkimi neuronami T-conorm. Po utworzeniu tych połączeń konieczne jest ustalenie ich wag. W celu przypisania tych wag zastosowano metodę uczenia opartą na najmniejszych średnich kwadratach . Po określeniu wag, do przetwarzania wyjścia neuronu użyto operacji T-conorm (operator T-conorm o ograniczonej sumie. Końcowy wynik systemu HNFB_-1 jest określony przez najwyższy wynik uzyskany spośród wszystkich neuronów zgodnych z normą T, determinujący klasę, do której należy wzorzec wejściowy. Wyniki uzyskane z modelem HNFB_-1 w różnych problemach klasyfikacji porównawczej przedstawiono w sekcji Studia przypadków.

HIERARCHICZNY NEURO-FUZZY BPS MAMDANI

Hierarchiczny neuro-fuzzy BSP Mamdani (HNFB-Mamdani), podobnie jak HNFB_-1, został również opracowany w celu zwiększenia interpretowalności hierarchicznych systemów neuro-fuzzy. Ponieważ jednak HNFB_-1 jest dedykowany problemom klasyfikacji, opracowano model bardziej ogólny. HNFB-Mamdani wykorzystuje metodę wnioskowania Mamdaniego w następstwach reguł i może być stosowany w systemach sterowania, klasyfikacji wzorców, prognozowaniu i ekstrakcji reguł. Architektura HNFB-Mamdani. Architektura HNFB-Mamdani powstaje w wyniku połączenia komórek HNFB_-1 w strukturze drzewa binarnego i jest podzielona na trzy podstawowe moduły: strukturę partycjonowania wejściowego; ważone połączenie z komórek liściowych struktury binarnej (di) do neuronów T-conorm (T_i); oraz proces defuzyfikacji. Pierwsze dwa moduły są identyczne z architekturą HNFB-1, z tym wyjątkiem, że każdy neuron T-conorm jest powiązany ze zbiorem rozmytym M następnika. Wszystkie komórki liściowe są połączone ze wszystkimi neuronami T-conorm. Z każdym połączeniem powiązana jest waga, której wartość jest również ustalana za pomocą algorytmu najmniejszych średnich kwadratów. Następnikiem reguły rozmytej w modelu HNFB-Mamdani jest zbiór rozmyty reprezentowany przez trójkątną funkcję przynależności. Całkowita liczba zbiorów rozmytych powiązanych ze zmienną wyjściową jest określana przez użytkownika.

Metoda defuzzyfikacji

Proces defuzzyfikacji wybrany dla modelu HNFB-Mamdani jest średnią ważoną wartości maksymalnych. Rysunek 3 ilustruje proces defuzzyfikacji dla modelu z trzema wyjściowymi zbiorami rozmytymi.



Następnie wyjście y oblicza się według równania (8).



gdzie:

y_j: wyjście HNFB-Mamdani dla wzorca wejściowego j;
α_i^j: wartość wyjściowa i-tego neuronu T-conorm (T_i) dla wzorca wejściowego j;
C_i: wartość w uniwersum dyskursu zmiennej wyjściowej, gdzie zbiór rozmyty M_i prezentuje wartość maksymalną;
*: operator iloczynu.
n: całkowita liczba zbiorów rozmytych powiązanych ze zmienną wyjściową.

STUDIA PRZYPADKÓW

Aby ocenić wydajność nadzorowanych modeli HNFB, wybrano dwie bazy danych klasyfikacji porównawczej i sześć szeregów czasowych obciążenia z zakładów energetycznych brazylijskiego sektora elektroenergetycznego.

Klasyfikacja wzorców

Klasyfikacja wzorców ma na celu określenie, do której grupy z predefiniowanego zbioru należy dany wzorzec wejściowy. Wybrano dwie aplikacje porównawcze spośród tych najczęściej wykorzystywanych w obszarze uczenia maszynowego. Wyniki uzyskane z proponowanymi modelami HNFB porównano z wynikami opisanymi w [Goncalves, 2006]. Aby wygenerować zbiory treningowe i testowe, cały zbiór wzorców został losowo podzielony na dwie równe części. Każdy z tych dwóch zbiorów był naprzemiennie używany jako zbiór treningowy lubtestowy. Tabela 1 poniżej podsumowuje średnią wydajność klasyfikacji uzyskaną dla obu zbiorów testowych.



Wydajność modeli HNFB jest lepsza niż innych modeli, z wyjątkiem przypadku HNFB-Mamdani. Ponieważ model HNFB-Mamdani jest modelem ogólnego przeznaczenia, zazwyczaj zapewnia gorsze wyniki w porównaniu z modelami specyficznymi dla konkretnych zastosowań, takimi jak Inverted-HNFB i HNFB-Class. Z drugiej strony, HNFB i HNFQ [Souza, 2002a] są również modelami ogólnego przeznaczenia, ale nadal zapewniają lepszą wydajność niż HNFB-Mamdani. Wynika to z metody wnioskowania Takagi-Sugeno stosowanej w tych modelach, która jest zazwyczaj dokładniejsza niż metoda wnioskowania Mamdaniego. Wadą metody Takagi-Sugeno jest jej ograniczona interpretowalność.

Prognozowanie obciążenia elektrycznego

W tym eksperymencie wykorzystano dane dotyczące miesięcznego obciążenia elektrycznego 6 przedsiębiorstw energetycznych brazylijskiego sektora elektroenergetycznego. Wyniki uzyskane z modelami HNFB porównano z algorytmem propagacji wstecznej, technikami statystycznymi, takimi jak Holt-Winters i Box & Jenkins, oraz z bayesowskimi sieciami neuronowymi (BNN) , trenowanymi aproksymacją Gaussa i metodą MCMC. Tabela 2 poniżej przedstawia wyniki wydajności w postaci "średniego bezwzględnego błędu procentowego".



Można zauważyć, że ogólna wydajność modeli HNFB jest zazwyczaj lepsza od wyników uzyskanych metodami statystycznymi. Wyniki uzyskane z BNN są generalnie lepsze niż z modelami HNFB. Jednak według czas treningu z BNN wynosił około 8 godzin. Był to okres znacznie dłuższy niż czas wymagany przez modele HNFB do wykonania tego samego zadania, który wynosił od dziesiątek do setek sekund na podobnym sprzęcie. Ponadto dane wykorzystane w modelach HNFB nie były traktowane pod kątemsezonowości ani nie były stacjonarne, jak miało to miejsce w przypadku sieci neuronowych neuronów rozmytych (BNN) testowanych w [Tito, 1999].

TRENDY NA PRZYSZŁOŚĆ

Jak wynika z przedstawionych wyników, modele HNFB zapewniają bardzo dobrą wydajność w różnych zastosowaniach. Aby poprawić wydajność modelu HNFB-Mamdani, który zapewnił najgorsze wyniki wśród nadzorowanych modeli HNFB, model ten jest rozszerzany o możliwość wykorzystania różnych typów wyjściowych zbiorów rozmytych (takich jak gaussowskie, trapezoidalne itp.) oraz poprzez dodanie algorytmu optymalizującego całkowitą liczbę wyjściowych zbiorów rozmytych.

WNIOSKI

Celem niniejszego artykułu było wprowadzenie nowej klasy modeli neuro-rozmytych, których celem jest poprawa słabych punktów konwencjonalnych systemów neuro-rozmytych. Wyniki uzyskane przez modele HNFB pokazały, że zapewniają one dobrą wydajność jako klasyfikatory wzorców baz danych lub jako prognostycy szeregów czasowych. Modele te potrafią tworzyć własne struktury i pozwalają na ekstrakcję wiedzy w postaci niejasnych reguł lingwistycznych.

WSTĘP

Proces automatycznego rozpoznawania płaczu niemowląt (AICR) to zasadniczo problem przetwarzania wzorców, bardzo podobny do procesu automatycznego rozpoznawania mowy (ASR) . W AICR najpierw przeprowadzamy analizę akustyczną, w której analizowany jest sygnał płaczu, aby wyodrębnić ważniejsze cechy akustyczne, takie jak: LPC, MFCC itp. . Uzyskane cechy są reprezentowane przez wektory cech, a każdy wektor reprezentuje wzorzec. Wzorce te są następnie klasyfikowane według odpowiadającej im patologii . W opisywanym przypadku automatycznie klasyfikujemy płacz niemowląt zdrowych, głuchych i duszących się. Wykorzystujemy algorytm genetyczny do znalezienia kilku optymalnych parametrów wymaganych przez rozmytą relacyjną sieć neuronową (FRNN) , takich jak: Liczba właściwości lingwistycznych, typ funkcji przynależności, metoda obliczania wyniku oraz tempo uczenia. Cały model został przetestowany na kilku zbiorach danych pod kątem klasyfikacji płaczu niemowląt. Opisano proces, a także niektóre wyniki.

TŁO

W pierwszej części niniejszego dokumentu przedstawiono pełny opis systemu AICR oraz sieci FRNN. Dlatego, w celu zachowania ciągłości, w tej części skoncentrujemy się na opisie algorytmu genetycznego oraz implementacji i testowaniu całego systemu. Algorytm genetyczny odnosi się do modelu wprowadzonego i zbadanego przez Johna Hollanda i jego studentów . Algorytmy genetyczne są często postrzegane jako optymalizatory funkcji, chociaż zakres problemów, do których stosowano algorytmy genetyczne, jest dość szeroki. Ostatnio pojawiło się wiele artykułów i aplikacji łączących koncepcje rozmyte i algorytmy genetyczne (GA), a integracja tych dwóch zagadnień budzi coraz większe zainteresowanie. W szczególności istnieje wiele publikacji badających zastosowanie algorytmów genetycznych do tworzenia lub ulepszania układów rozmytych, zwanych genetycznymi układami rozmytymi (GFS) .

PROJEKTOWANIE EWOLUCYJNE

Wśród technik ewolucyjnych jednym z najpopularniejszych jest prawdopodobnie algorytm genetyczny (AG). Jego struktura nawiązuje do biologicznej teorii ewolucji i opiera się na zasadzie przetrwania najlepiej przystosowanych osobników (Holland, 1975). Generalnie algorytm genetyczny składa się z pięciu podstawowych komponentów (Michalewicz, 1992): reprezentacji potencjalnych rozwiązań problemu, formy do tworzenia potencjalnych rozwiązań początkowych, funkcji dopasowania, która odpowiada za ocenę rozwiązań, operatorów genetycznych, które zmieniają skład potomstwa, oraz wartości parametrów, takich jak liczebność populacji, prawdopodobieństwo krzyżowania, prawdopodobieństwo mutacji, liczba pokoleń i inne. W niniejszym artykule przedstawiamy różne cechy algorytmu genetycznego używanego do znalezienia kombinacji parametrów dla FRNN.

Reprezentacja chromosomów

Kodyfikacja binarna jest stosowana w algorytmach genetycznych, a Holland w swojej pracy (Holland, 1975) podał teoretyczne uzasadnienie jej stosowania. Holland argumentował, że kodyfikacja binarna pozwala na posiadanie większej liczby schematów niż reprezentacja dziesiętna. Schemat jest szablonem opisującym podgrupę ciągów znaków, które mają pewne podobieństwa w niektórych pozycjach na całej swojej długości. Zmienne problemowe składają się z liczby właściwości lingwistycznych, typu funkcji przynależności, metody klasyfikacji i współczynnika uczenia. Jesteśmy zainteresowani posiadaniem od 3 do 7 właściwości lingwistycznych, więc liczba zmiennych lingwistycznych jest zakodowana w ciągu binarnym o długości 3 bitów. Funkcja przynależności jest reprezentowana jako ciąg 2-bitowy, gdzie [00] dekoduje trapezową funkcję przynależności, [01] dekoduje funkcję Π, [10] dekoduje funkcję trójkątną, [11] dekoduje funkcję przynależności Gaussa. Metody klasyfikacji są również kodowane jako ciąg 2-bitowy, gdzie [00] reprezentuje kompozycję max-min, [01] reprezentuje średnią geometryczną, a [10] reprezentuje relacyjny iloczyn kwadratowy. Ostatecznie, szybkość uczenia się jest reprezentowana jako ciąg binarny o długości 3 bitów, gdzie [000] dekoduje do szybkości uczenia się 0,1, [001] dekoduje do szybkości uczenia się 0,2, [010] dekoduje do szybkości uczenia się 0,31, [011] dekoduje do szybkości uczenia się 0,4, a [100] dekoduje do szybkości uczenia się 0,5. Większa szybkość uczenia się nie jest pożądana, więc wszystkie inne wartości bitowe są ignorowane. Chromosom uzyskuje się poprzez połączenie wszystkich powyższych ciągów. Rysunek 1 przedstawia przykład reprezentacji chromosomowej. Początkowa populacja jest generowana z losowego wyboru chromosomów, przyjęto rozmiar populacji 50.

Operacje genetyczne

Wykorzystujemy cztery operacje genetyczne: elitaryzm, selekcję typu koło ruletki, krzyżowanie i mutację. Elitaryzm: Aby zapewnić, że członkowie populacji o najwyższej wartości dostosowania pozostaną w następnym pokoleniu, stosujemy elitaryzm. Wykazano, że algorytm genetyczny musi wykorzystywać elitaryzm, aby móc wykazać konwergencję. W każdej iteracji algorytmu genetycznego wybieramy członków o czterech najwyższych wartościach dostosowania i umieszczamy ich w następnym pokoleniu. Selekcja: W algorytmie genetycznym proces selekcji odbywa się w sposób probabilistyczny, co oznacza, że osobniki mniej predysponowane mają nawet pewną szansę na zostanie wybranymi. Istnieje wiele różnych rodzajów podejść do selekcji; stosujemy selekcję typu koło ruletki, w której członkowie populacji mają prawdopodobieństwo bycia wybranymi, które jest wprost proporcjonalne do ich dostosowania. Krzyżowanie: W tej pracy stosujemy krzyżowanie jednopunktowe. Obserwując działanie różnych operatorów krzyżowania, De Jong doszedł do wniosku, że chociaż zwiększenie liczby punktów krzyżowania wpływa na schematy z teoretycznego punktu widzenia, w praktyce nie wydaje się to mieć znaczącego wpływu. Krzyżowanie jest głównym operatorem w algorytmie genetycznym. Na podstawie kilku eksperymentów postanowiliśmy wyznaczyć punkt krzyżowania losowo, a prawdopodobieństwo krzyżowania ustalono na 0,8. Mutacja: Ten operator pozwala na wprowadzenie nowego materiału chromosomowego do populacji. Wybraliśmy gen losowo i zastąpiliśmy go jego dopełnieniem, zero jest zastępowane przez jedynkę, a jedynka przez zero. Niektórzy autorzy sugerują, że prawdopodobieństwo mutacji równe 1/L, gdzie L jest długością łańcucha bitów, jest dolną granicą akceptowalną dla optymalnego odsetka mutacji . W tej pracy prawdopodobieństwo mutacji ustalono na 0,05.

Funkcja dopasowania

Funkcja celu naszego problemu optymalizacyjnego nazywana jest funkcją dopasowania. Funkcja ta musi być w stanie karać rozwiązania, które nie są dobre, i nagradzać dobre, aby mogły się szybko rozprzestrzeniać. Jako funkcję dopasowania wykorzystujemy błąd klasyfikacji podany przez rozmytą relacyjną sieć neuronową. Następnie funkcję dopasowania definiujemy za pomocą następującego równania.

F =e_FRNN

W tym przypadku definiujemy błąd klasyfikacji w następujący sposób

e_FRNN=No.PM/No.S

gdzie No.PM reprezentuje liczbę idealnych dopasowań, innymi słowy, reprezentuje liczbę próbek poprawnie sklasyfikowanych. Termin Nr S reprezentuje całkowitą liczbę próbek przekazanych do FC.

IMPLEMENTACJA I WYNIKI

Przetwarzanie sygnałów

Analiza surowego sygnału cry dostarcza informacji niezbędnych do jego rozpoznania. Jednocześnie odrzuca niepożądane informacje, takie jak szum tła i zniekształcenia kanału . Ekstrakcja cech akustycznych to transformacja danych pomiarowych w dane wzorcowe. Do najważniejszych technik stosowanych do analizy sygnałów cry należą: dyskretna transformata Fouriera (DFT), przetwarzanie cepstralne i liniowa analiza predykcyjna (LPA) . Zastosowanie tych technik podczas przetwarzania sygnału pozwala uzyskać wartości zbioru cech akustycznych. Cechy mogą być współczynnikami widmowymi, liniowymi współczynnikami predykcji (LPC), współczynnikami częstotliwości cepstralnych Mel (MFCC). Zbiór wartości dla n cech może być reprezentowany przez wektor w przestrzeni n-wymiarowej. Każdy wektor reprezentuje wzór. W niniejszych eksperymentach pracujemy z próbkami płaczu niemowląt. Płacz niemowląt został zebrany za pomocą nagrań wykonanych bezpośrednio przez lekarzy, a następnie każda fala sygnału została podzielona na segmenty 1-sekundowe, każdy segment reprezentuje próbkę. Następnie cechy akustyczne uzyskano za pomocą technik takich jak liniowe współczynniki predykcji (LPC) i współczynniki częstotliwości cepstralnych Mel (MFCC), przy użyciu darmowego programu Praat v4.0.8 . Każda próbka trwająca 1 sekundę jest dzielona na klatki 50-milisekundowe, a z każdej klatki wyodrębniamy 16 współczynników. Ta procedura generuje wektory z 304 współczynnikami na próbkę. W niniejszym artykule przedstawiamy wyniki uzyskane za pomocą współczynników częstotliwości cepstralnej (MEL). Aby zredukować wymiary wektorów próbek, stosujemy analizę głównych składowych. Sieć neuronów neuronalnych (FRNN) i algorytm genetyczny są zaimplementowane w programie Matlab. Dysponujemy korpusem 157 próbek normalnego płaczu niemowlęcego, 340 próbek płaczu niemowlęcego uduszonego i 879 próbek płaczu hipoakustycznego. Dysponujemy również korpusem 192 próbek bólu i 350 próbek płaczu głodowego. Pracowaliśmy z populacją 50 osobników, a liczbę epok treningowych dla sieci neuronowej neuronów neuronalnych (FRNN) ustawiono na trzy. Populacja początkowa została wybrana losowo. Liczba pokoleń potrzebnych dla algorytmu genetycznego wyniosła tylko trzy. Wartości te ustalono na podstawie obserwacji wyników kilku eksperymentów.

Wyniki wstępne

Przeprowadzono trzy różne eksperymenty klasyfikacyjne. Pierwszy z nich polegał na klasyfikowaniu płaczu głuchego i normalnego niemowlęcia, drugi na klasyfikowaniu płaczu niemowlęcia w kategoriach asfiksji i normalnego, a trzeci na klasyfikowaniu płaczu głodowego i bólowego. W każdym zadaniu próby treningowe i testowe zostały wybrane losowo. Wyniki modelu w klasyfikacji płaczu głuchego i normalnego przedstawiono w tabeli I. W tabeli II przedstawiono wyniki uzyskane w drugim zadaniu klasyfikacyjnym. Wreszcie, tabela III przedstawia wyniki w klasyfikacji płaczu głodowego i bólowego. W każdymzadaniu klasyfikacyjnym algorytm genetyczny był uruchamiany około 15 razy, a przedstawione wyniki przedstawiają średnią z najlepszej klasyfikacji w każdym eksperymencie.

Porównanie wydajności z innymi modelami

Reyes i Orozco sklasyfikowali próbki płaczu u niemowląt głuchych i zdrowych, uzyskując wyniki rozpoznania na poziomie około 97,43%. Reyes i inni przedstawili implementację lingwistycznej rozmytej relacyjnej sieci neuronowej do klasyfikacji normalnego i patologicznego płaczu niemowląt, uzyskując odsetek prawidłowej klasyfikacji na poziomie 97,3% i 98%. Petroni, Malowany, Johnston i Stevens (1995) sklasyfikowali płacz u niemowląt zdrowych, aby zidentyfikować ból za pomocą sztucznych sieci neuronowych i przedstawili wyniki prawidłowej klasyfikacji, które wahają się od 61% w przypadku sieci korelacji kaskadowej do 86,2% w przypadku sieci neuronowych z sprzężeniem zwrotnym. W pracy (Lederman, 2002) Dror Lederman przedstawia niektóre wyniki klasyfikacji niemowląt z zespołem zaburzeń oddechowych RDS (związanym z asfiksją) w porównaniu z niemowlętami zdrowymi. Do klasyfikacji wykorzystał architekturę ukrytego modelu Markowa z 8 stanami i 5 rozkładami Gaussa na stan. Przedstawione wyniki stanowią 63% całkowitej średniej poprawnej klasyfikacji.

TRENDY NA PRZYSZŁOŚĆ

Systemy AICR mogą rozszerzyć swoją użyteczność poprzez trenowanie ich w rozpoznawaniu większej liczby patologii. Pierwszym warunkiem osiągnięcia tego celu jest zebranie odpowiedniego zestawu oznaczonych próbek dla dowolnej patologii docelowej. Przedstawiony tutaj algorytm genetyczny optymalizuje niektóre parametry FRNN, ale model ma ich więcej. W związku z tym do reprezentacji chromosomowej można dodać inne parametry w celu ulepszenia modelu, takie jak wartości początkowe macierzy relacyjnej i wektorów odchyleń, liczba epok treningowych oraz wartości wykładniczego i denominacyjnego generatora rozmytego używanego przez DOE.

WNIOSKI

Proponowany algorytm genetyczny oblicza wybór liczby właściwości lingwistycznych, funkcję przynależności używaną do obliczania cech lingwistycznych, metodę obliczania wyników klasyfikatora w sekcji przetwarzania rozmytego oraz szybkość uczenia FRNN. Rozwiązanie uzyskane dzięki proponowanemu algorytmowi genetycznemu to zestaw cech, które FRNN może wykorzystać do klasyfikacji płaczu niemowlęcego. Wykorzystanie właściwości lingwistycznych pozwala nam uporać się z nieprecyzyjnością płaczu niemowlęcego i dostarcza klasyfikatorowi bardzo użytecznych informacji. Dzięki zastosowaniu informacji lingwistycznych i biorąc pod uwagę charakter modelu, nie jest konieczne uczenie przez dużą liczbę epok uczenia się, ani też duża liczba iteracji w algorytmie genetycznym. Wyniki klasyfikacji głuchego i normalnego płaczu niemowlęcego są bardzo podobne do wyników uzyskanych w innych modelach, ale w przypadku klasyfikacji głodu i bólu wyniki są znacznie lepsze niż w przypadku innych modeli.

WSTĘP

Płacz u niemowląt jest podstawową funkcją komunikacyjną, sterowaną bezpośrednio przez mózg; wszelkie zmiany w normalnym funkcjonowaniu ciała niemowląt znajdują odzwierciedlenie w płaczu . Na podstawie informacji zawartych w fali płaczu można określić stan fizyczny niemowlęcia, a nawet wykryć patologie w bardzo wczesnych stadiach życia . Do przeprowadzenia tego wykrywania zastosowano rozmytą relacyjną sieć neuronową (FRNN). Cechy wejściowe są reprezentowane przez rozmyte funkcje przynależności, a powiązania między węzłami, zamiast wag, są reprezentowane przez rozmyte relacje . Niniejszy artykuł, jako pierwsza z dwóch części dokumentu, opisuje architekturę systemu rozpoznawania płaczu niemowląt oraz model FRNN. Implementacja i testowanie są opisane w artykule uzupełniającym.

TŁO

Pionierskie prace nad płaczem niemowląt zostały zainicjowane przez Wasza-Hockerta na początku lat 60. XX wieku. W jednej z tych prac jego grupa badawcza wykazała, że cztery podstawowe rodzaje płaczu można zidentyfikować poprzez słuchanie: bólu, głodu, przyjemności i porodu. Dalsze badania doprowadziły do opracowania modeli konceptualnych opisujących anatomiczne i fizjologiczne podstawy powstawania i neurologicznej kontroli płaczu . Później Wasz-Hockert (1970) zastosował analizę widmową do identyfikacji kilku rodzajów płaczu. Inne prace wykazały, że istnieją istotne różnice między różnymi rodzajami płaczu, takimi jak płacz zdrowego niemowlęcia, płacz z bólu i płacz patologiczny niemowlęcia. W jednym z badań Petroni wykorzystał sieci neuronowe do rozróżnienia płaczu z bólem i bez bólu. Cano kierował kilkoma pracami poświęconymi ekstrakcji i automatycznej klasyfikacji charakterystyk akustycznych płaczu niemowląt. W jednym z tych badań, w 1999 roku, Cano przedstawił pracę, w której wykazał użyteczność samoorganizujących się map Kohonena w klasyfikacji Jednostek Płaczu Niemowląt. Niedawno, w pracy (Orozco i Reyes, 2003), przedstawiliśmy klasyfikację próbek płaczu niemowląt głuchych i zdrowych za pomocą sieci neuronowych z wyprzedzeniem. W 2004 roku Cano i jego zespół, w pracy (Cano, Escobedo, Ekkel, 2004), przedstawili zastosowanie radialnej sieci bazowej (RBN) w celu określenia istotnych aspektów związanych z obecnością chorób ośrodkowego układu nerwowego (OUN). W pracy (Suaste, Reyes, Diaz i Reyes, 2004) przedstawiliśmy implementację rozmytej relacyjnej sieci neuronowej (FRNN) do wykrywania patologii poprzez rozpoznawanie płaczu niemowląt. Badania modeli koneksjonistycznych, znanych również jako sztuczne sieci neuronowe (ANN), cieszą się odrodzeniem zainteresowania po ich upadku w latach 60. XX wieku. Badania koncentrowały się na ocenie nowych sieci neuronowych pod kątem klasyfikacji wzorców, trenowaniu algorytmów z wykorzystaniem rzeczywistych danych mowy oraz na określeniu, czy możliwe jest zaprojektowanie równoległych architektur sieci neuronowych w celu wydajnego wykonywania zadań wymaganych przez złożone algorytmy rozpoznawania mowy. W podejściu koneksjonistycznym klasyfikacja wzorców odbywa się za pomocą wielowarstwowej sieci neuronowej. Każdemu połączeniu między neuronami w sąsiednich warstwach przypisana jest waga. W warstwie wejściowej każdy neuron otrzymuje jedną z cech obecnych w wejściowych wektorach wzorców. Każdy neuron w warstwie wyjściowej odpowiada każdej klasie jednostki mowy (słowu lub podsłowu). Sieć neuronowa kojarzy wzorce wejściowe z klasami wyjściowymi poprzez modelowanie relacji między dwoma zestawami wzorców. Wzorzec jest szacowany lub uczony przez sieć na podstawie reprezentatywnej próbki wzorców wejściowych i wyjściowych . Aby ustabilizować zachowanie perceptronu, wielu badaczy próbowało włączyć teorię zbiorów rozmytych do sieci neuronowych. Teoria zbiorów rozmytych, opracowana przez Zadeha w 1965 roku (Zadeh, 1965), została od tego czasu wykorzystana do uogólnienia istniejących technik i opracowania nowych algorytmów rozpoznawania wzorców. Pal zasugerował, że aby umożliwić systemom radzenie sobie z sytuacjami z życia wziętymi, zbiory rozmyte powinny być włączone do sieci neuronowych, a wzrost ilości obliczeń wymaganych wraz z ich włączeniem jest kompensowany przez potencjał obliczeń równoległych z dużą elastycznością, jaką mają rozmyte sieci neuronowe. Pal proponuje sposób rozmycia danych, ogólną architekturę systemu rozmytej sieci neuronowej oraz wykorzystanie trójwymiarowych wektorów do reprezentacji rozmytych wartości przynależności cech wejściowych do podstawowych właściwości lingwistycznych: niskiego, średniego i wysokiego poziomu . Z drugiej strony, pomysł wykorzystania relacyjnej sieci neuronowej jako klasyfikatora wzorców został rozwinięty przez Pedrycza. W wyniku połączenia metodologii zaproponowanych przez Pala i Pedrycza, w 1994 roku C. A. Reyes (1994) opracował hybrydowy model znany jako rozmyta relacyjna sieć neuronowa (FRNN).

PROCES AUTOMATYCZNEGO ROZPOZNAWANIA PŁACZU NIEMOWLĄT

Proces automatycznej klasyfikacji płaczu niemowlęcia jest generalnie problemem rozpoznawania wzorców, podobnym do automatycznego rozpoznawania mowy (ASR) . Celem jest przyjęcie fali płaczu niemowlęcia jako wzorca wejściowego i na końcu uzyskanie rodzaju płaczu lub patologii wykrytej u dziecka . Generalnie proces automatycznego rozpoznawania płaczu niemowlęcia przebiega dwuetapowo. Pierwszy etap to przetwarzanie sygnału lub ekstrakcja cech, a drugi to klasyfikacja wzorców. W fazie analizy akustycznej sygnał krzywej jest najpierw normalizowany i oczyszczany, a następnie analizowany w celu wyodrębnienia najważniejszych cech w funkcji czasu. Zbiór uzyskanych cech jest reprezentowany przez wektor, który reprezentuje wzorzec. Zbiór wszystkich wektorów jest następnie wykorzystywany do trenowania klasyfikatora. Następnie zbiór nieznanych wektorów cech jest porównywany z uzyskaną wiedzą, aby zmierzyć efektywność klasyfikacji. Rysunek 1 przedstawia poszczególne etapy opisanego procesu rozpoznawania.



Klasyfikacja Wzorców Krzyku

Wektory, reprezentujące wzorce, uzyskane na etapie ekstrakcji, są później wykorzystywane w procesie klasyfikacji. Istnieją cztery podstawowe szkoły rozwiązania problemu klasyfikacji wzorców, a są to: a) Porównywanie wzorców (programowanie dynamiczne), b) Modele Statystyczne (Ukryte Modele Markowa HMM), c) Systemy oparte na wiedzy (systemy eksperckie) oraz d) Modele Koneksjonistów (sieci neuronowe). W ostatnich latach pojawił się nowy, silny trend w kierunku bardziej niezawodnych klasyfikatorów hybrydowych. Niektóre z lepiej znanych modeli hybrydowych są wynikiem połączenia podejść neuronowych i rozmytych . W prezentowanej pracy zaimplementowaliśmy hybrydowy model tego typu, zwany Rozmytą Relacyjną Siecią Neuronową (Fuzzy Relational Neural Network), którego parametry są znajdowane poprzez zastosowanie algorytmów genetycznych. Wybraliśmy ten rodzaj modelu ze względu na jego możliwości adaptacji, uczenia się i reprezentacji wiedzy. Ponadto jedną z jego głównych funkcji jest rozpoznawanie wzorców. W automatycznym systemie klasyfikacji płaczu niemowląt celem jest identyfikacja modelu nieznanego wzorca uzyskanego po akustycznej analizie oryginalnej fali dźwiękowej i redukcji jej wymiarowości. Zatem na tym etapie określamy klasę lub kategorię, do której należy każdy wzorzec płaczu. Zbiór próbek, z których każda jest reprezentowana przez wektor n cech, jest podzielony na dwa podzbiory: zbiór treningowy i zbiór testowy. Najpierw zbiór treningowy służy do nauczenia klasyfikatora rozróżniania różnych typów płaczu. Następnie zbiór testowy służy do określenia, jak dobrze klasyfikator przypisuje odpowiednią klasę do wzorca za pomocą schematu klasyfikacji wygenerowanego podczas treningu.

MODEL ROZMYTEJ SIECI NEURONOWEJ

Proponowany w niniejszej pracy system opiera się na operacjach na zbiorach rozmytych zarówno w strukturze sieci neuronowej, jak i w procesie uczenia. Zgodnie z koncepcją Pala dotyczącą ogólnego rozpoznawania , model jest podzielony na dwie główne części, jedną do uczenia się i drugą do przetwarzania, jak pokazano na rysunku 2.



Uczenie rozmyte

Sekcja uczenia rozmytego składa się z trzech modułów: Ekstraktora Cech Lingwistycznych (LFE), Estymatora Pożądanego Wyniku (DOE) i Trenera Sieci Neuronowej (NNT). Ekstraktor Cech Lingwistycznych pobiera próbki treningowe w postaci n-wymiarowych wektorów zawierających n cech i konwertuje je na wektory w postaci n-wymiarowej, gdzie N to liczba cech lingwistycznych. W tym przypadku właściwości lingwistyczne są niskie, średnie i wysokie. Otrzymany 3n-wymiarowy wektor nazywany jest Wektorem Właściwości Lingwistycznych (LPV). W ten sposób wzorzec wejściowy F_i = [F_i1, F_i2, …,F_in] zawierający n cech można przedstawić jako :



DOE pobiera każdy wektor z próbek treningowych i oblicza jego przynależność do klasy k, w domenie problemowej klasy l. Wektor zawierający wartości przynależności do klasy nazywany jest Wektorem Pożądanym (DV). Zarówno wektory LPV, jak i DV są wykorzystywane przez Trenera Sieci Neuronowej (NNT), który wykorzystuje je do trenowania sieci. Sieć neuronowa ma tylko jedną warstwę wejściową i jedną warstwę wyjściową. Warstwa wejściowa jest utworzona przez zestaw Nn neuronów, z których każdy odpowiada jednej z właściwości lingwistycznych przypisanych do n cech wejściowych. W warstwie wyjściowej znajduje się l neuronów, a każdy węzeł odpowiada jednej z l klas; w tej implementacji każda klasa reprezentuje jeden rodzaj płaczu. Istnieje połączenie z każdego węzła w warstwie wejściowej do każdego węzła w warstwie wyjściowej. Wszystkie połączenia są opisane za pomocą relacji rozmytych R: X × Y ? [0, 1] między węzłami wejściowymi i wyjściowymi. Błąd jest reprezentowany przez odległość między rzeczywistym wyjściem a docelowym lub pożądanym wyjściem. Podczas każdego etapu uczenia, po obliczeniu błędu, trener dostosowuje wartości relacji lub wagi odpowiednich połączeń, aż do uzyskania minimalnego błędu lub do ukończenia określonej liczby iteracji. Wyjściem NNT, po procesie uczenia, jest rozmyta macierz relacyjna (R na rysunku 1), zawierająca wiedzę potrzebną do dalszego mapowania nieznanych wektorów wejściowych na odpowiadające im klasy w trakcie procesu klasyfikacji.

Przetwarzanie rozmyte

Sekcja przetwarzania rozmytego składa się z trzech różnych modułów: Ekstraktora Cech Lingwistycznych (LFE), Klasyfikatora Rozmytego (FC) i Modułu Podejmowania Decyzji (DMM). LFE działa tak samo, jak moduł w fazie uczenia, opisany w poprzedniej sekcji. Wyjściem tego modułu jest wektor LPV, który wraz z rozmytą macierzą relacyjną R jest wykorzystywany przez Klasyfikator Rozmyty, który uzyskuje rzeczywiste dane wyjściowe z sieci neuronowej. Klasyfikator stosuje kompozycję max-min do obliczenia danych wyjściowych. Wyjściem tego modułu jest wektor wyjściowy zawierający wartości przynależności wektora wejściowego do każdej z klas. Na koniec moduł podejmowania decyzji wybiera najwyższą wartość z klasyfikatora i przypisuje odpowiednią klasę do wektora testującego.

Funkcje przynależności

Funkcja przynależności odwzorowuje wartości w domenie na ich wartości przynależności w zbiorze rozmytym. Dostępnych jest kilka rodzajów funkcji przynależności. W opisanych eksperymentach zastosowano trójkątne funkcje przynależności. Według (Park, Cae i Kandel, 1992) użycie większej liczby właściwości lingwistycznych do opisu punktu wzorcowego zwiększa dokładność modelu, ale ich zbyt wiele może sprawić, że opis stanie się niepraktyczny. Dlatego tutaj używamy siedmiu właściwości lingwistycznych: bardzo niski, niski, mniej więcej niski, średni, mniej więcej wysoki, wysoki i bardzo wysoki.

Pożądane wartości przynależności

Przed zdefiniowaniem wyjściowej funkcji przynależności definiujemy równanie obliczające ważoną odległość wzorca treningowego F_j do k-tej klasy w domenie problemu klasy l, jak w (Pal, 1992a).



gdzie F_ij jest j-tą cechą i-tego wektora wzorca, σ?_kj oznacza średnią, a v_kjj oznacza odchylenie standardowe j-tej cechy dla k-tej klasy. Wartość przynależności i-tego wzorca do klasy k jest zdefiniowana następująco:



gdzie f_e jest wykładniczym generatorem rozmycia, a f_d jest mianownikowym generatorem rozmycia kontrolującym liczbę rozmyć w tym zbiorze przynależności do klas. W tym przypadku im większa odległość wzorca od klasy, tym mniejsze jego przynależność do tej klasy. Ponieważ dane treningowe mają rozmyte granice klas, punkt wzorca zazwyczaj należy do więcej niż jednej klasy w różnym stopniu.

Trener sieci neuronowej

Omawiany tutaj model sieci neuronowej oparty jest na relacyjnej strukturze neuronowej zaproponowanej przez Pedrycza . Relacyjna Sieć Neuronowa (RNN): Niech X = {x₁, x₂,… x_n} będzie skończonym zbiorem węzłów wejściowych, a Y = {y₁, y₂, …, y_l} będzie zbiorem węzłów wyjściowych w domenie problemu klasy l. Gdy operator składania max-min oznaczony X ? R zostanie zastosowany do zbioru rozmytego X i relacji rozmytej R, wynikiem będzie nowy zbiór rozmyty Y, mamy



gdzie X jest zbiorem rozmytym, Y jest wynikowym zbiorem rozmytym, a R jest rozmytą relacją R : X × Y ? [0,1] opisującą wszystkie relacje między węzłami wejściowymi i wyjściowymi. Całą sieć neuronową reprezentowaną przez wyrażenie (1) przyjmiemy jako zbiór l oddzielnych n-wejściowych komórek jednowyjściowych. Uczenie się w rozmytej sieci neuronowej: Jeśli rzeczywista odpowiedź sieci nie pasuje do wzorca docelowego, sieć jest korygowana poprzez modyfikację wag łączy w celu zmniejszenia różnicy między wzorcami obserwowanymi a docelowymi. Aby zmierzyć różnicę,definiuje się wskaźnik wydajności zwany wskaźnikiem równości, który jest



gdzie T(y) jest docelowym wyjściem w węźle y, a Y(y) jest rzeczywistym wyjściem w tym samym węźle. W problemie z n wzorcami wejściowymi istnieje n par wejście-wyjście (x_ij, t_i), gdzie t_i jest wartością docelową, gdy wejściem jest X_ij. Aktualizacja parametrów: Pedricz proponuje również, aby proces uczenia się został przeprowadzony osobno dla każdego węzła wyjściowego. Algorytm uczenia się jest wersją algorytmu propagacji wstecznej. Rozważmy sieć neuronową o n wejściach i L wyjściach mającą następującą postać



gdzie a = [a₁, a₂, … , a_L] to wektor zawierający wszystkie wagi lub relacje, x_i = [x_i1, x_i2,…, x_in] to wektor z wartościami obserwowanymi w węzłach wejściowych. Parametry a i ? są aktualizowane iteracyjnie poprzez uwzględnienie przyrostu Δam wynikającego z odchyleń między wszystkimi parami y_i i t_i w następujący sposób.



gdzie k jest krokiem uczenia. Ψ₁ i Ψ₂ to nierosnące funkcje k kontrolujące malejący wpływ przyrostów Δam. Ψ to moment uczenia się określający poziom modyfikacji parametrów uczenia się w odniesieniu do ich wartości w poprzednim kroku uczenia się k. Inkrementy Δam można określić w odniesieniu do m-tych współrzędnych a, m = 1, 2,..., L. Obliczanie ogólnego wskaźnika wydajności oraz pochodne do obliczania przyrostów dla każdej współrzędnej a i ? są szczegółowo wyjaśnione w (Reyes, C. A., 1994). Po zakończeniu uczenia, wyjściem trenującego jest zaktualizowana macierz relacyjna, która będzie zawierała wiedzę potrzebną do mapowania nieznanych wzorców na odpowiadające im klasy.

TRENDY NA PRZYSZŁOŚĆ

Jedną z niezbadanych możliwości poprawy wydajności FRNN jest zastosowanie innych rozmytych produktów relacyjnych zamiast kompozycji max-min. Ponadto funkcje przynależności posiadają parametry, które można optymalizować za pomocą algorytmów genetycznych i innych technik optymalizacyjnych. Odpowiednie parametry mogą poprawić efektywność uczenia się i rozpoznawania sieci FRNN.

WNIOSKI

Zaprezentowano opracowanie i wdrożenie systemu AICR oraz wydajnego klasyfikatora hybrydowego, sieci FRNN, która jest modelem utworzonym z połączenia relacji rozmytych i sztucznych sieci neuronowych. Zaprezentowano synergistyczną symbiozę uzyskaną dzięki połączeniu obu metodologii. W powiązanym artykule dotyczącym zastosowań tego modelu przedstawimy kilka praktycznych wyników, a także model ulepszony za pomocą algorytmów genetycznych.

WSTĘP

Złożoność współczesnych systemów komputerowych skłoniła środowiska inżynierii oprogramowania, systemów rozproszonych i zarządzania do poszukiwania inspiracji w różnych dziedzinach, np. robotyce, sztucznej inteligencji czy biologii, w celu znalezienia nowych sposobów projektowania i zarządzaniasystemami. Hybrydyzacja i łączenie różnych podejść wydaje się obiecującym obszarem badań inteligencji obliczeniowej, koncentrującym się na rozwoju kolejnej generacji inteligentnych systemów. System produkcyjny ma naturalną, dynamiczną naturę, obserwowaną poprzez kilka rodzajów zdarzeń losowych i zaburzeń warunków pracy i wymagań w czasie. W tego typu środowisku ważna jest możliwość efektywnego i skutecznego, ciągłego dostosowywania istniejących harmonogramów zgodnie z wykrytymi zakłóceniami, przy jednoczesnym utrzymaniu poziomu wydajności.Zastosowanie metaheurystyki do rozwiązywania tej klasy problemów dynamicznego harmonogramowania wydaje się niezwykle obiecujące. W niniejszym artykule proponujemy hybrydowe podejście oparte na metaheurystyce do złożonego harmonogramowania z wieloma operacjami produkcyjnymi i montażowymi w dynamicznych środowiskach Extended Job-Shop. Zaproponowano kilka mechanizmów samoadaptacji.

TŁO

Problem harmonogramowania

Planowanie systemów produkcyjnych często wiąże się z rozwiązywaniem ogromnej liczby różnorodnych problemów optymalizacji kombinatorycznej, które mają istotny wpływ na wydajność organizacji produkcyjnych. Przykładami takich problemów są problemy z sekwencjonowaniem i harmonogramowaniem w zarządzaniu produkcją, marszrutyzacją i transportem, projektowaniem rozmieszczenia maszyn i harmonogramowaniem. Harmonogramowanie można zdefiniować jako przypisanie zadań o ograniczonym czasie realizacji do zasobów o ograniczonym czasie realizacji w ramach z góry określonych ram czasowych, które reprezentują pełny horyzont czasowy harmonogramu. Dopuszczalny harmonogram musi spełniać zestaw ograniczeń nałożonych na zadania i zasoby. Zatem problem harmonogramowania można postrzegać jako proces podejmowania decyzji dotyczących rozpoczęcia operacji i wykorzystania zasobów. Różnorodne cechy i ograniczenia związane z zadaniami i systemem produkcyjnym, takie jak czas przetwarzania operacji, daty wydania i terminy wykonania, ograniczenia pierwszeństwa i dostępność zasobów, mogą wpływać na decyzje dotyczące harmonogramowania . Rzeczywiste wymagania dotyczące harmonogramowania są związane ze złożonymi systemami działającymi w dynamicznych środowiskach. Oznacza to, że często podlegają one różnego rodzaju zdarzeniom losowym i perturbacjom, takim jak pojawienie się nowych zadań, awarie maszyn, choroby pracowników, anulowanie zadań oraz zmiany terminów i godzin przetwarzania, co powoduje, że przygotowane harmonogramy łatwo stają się nieaktualne i nieodpowiednie. Harmonogramowanie w takim środowisku jest znane jako dynamiczne. Problemy dynamicznego harmonogramowania można sklasyfikować jako deterministyczne, gdy czasy wydania i wszystkie inne parametry są znane i ustalone, oraz jako niedeterministyczne, gdy niektóre lub wszystkie parametry systemu i zadania są niepewne, na przykład gdy zadania docierają do systemu losowo w czasie. Tradycyjne heurystyczne metody harmonogramowania napotykają na duże trudności w zastosowaniu do pewnych sytuacji rzeczywistych. Wynika to z trzech głównych powodów. Po pierwsze, tradycyjne metody harmonogramowania wykorzystują uproszczone i deterministyczne modele teoretyczne, w których wszystkie dane problemu są znane przed rozpoczęciem harmonogramowania. Jednak wiele rzeczywistych problemów optymalizacyjnych ma charakter dynamiczny i niedeterministyczny, a zmiany mogą w nich zachodzić w sposób ciągły. W praktyce harmonogramowanie statyczne nie jest w stanie reagować dynamicznie i szybko w obecności dynamicznych informacji, które nie zostały wcześniej przewidziane w bieżącym harmonogramie.Po drugie, większość metod aproksymacyjnych proponowanych dla problemów harmonogramowania zadań w miejscu pracy (Job-Shop Scheduling Problems - JSSP) to metody zorientowane, tj. opracowane specjalnie dla rozpatrywanego problemu. Przykładami tej klasy metod są reguły priorytetów i metoda "przesuwającego się wąskiego gardła" . Wreszcie, tradycyjne metody harmonogramowania są zasadniczo scentralizowane w tym sensie, że wszystkie obliczenia są wykonywane w centralnej jednostce obliczeniowej i logicznej. Wszystkie informacje dotyczące każdego zadania i każdego zasobu muszą przejść przez tę jednostkę. To scentralizowane podejście jest szczególnie podatne na problemy z obsługą, ponieważ liczba oddziałujących na siebie jednostek, którymi należy zarządzać wspólnie, jest duża i prowadzi do eksplozji kombinatorycznej. Zwłaszcza że szczegółowy harmonogram jest generowany na długi horyzont czasowy, a planowanie i realizacja są realizowane w dyskretnych przedziałach czasu. Scentralizowane harmonogramowanie jest zatem rozległe, złożone i trudne do utrzymania i rekonfiguracji. Z drugiej strony, nieodłączną cechą wielu procesów przemysłowych i usługowych jest rozproszenie. W konsekwencji tradycyjne metody są często zbyt nieelastyczne, kosztowne i powolne, aby sprostać potrzebom rzeczywistych systemów harmonogramowania. Wykorzystując specyficzne dla danego problemu cechy, klasyczne metody optymalizacji nie wystarczają do efektywnego rozwiązywania tych problemów lub są opracowywane dla konkretnych sytuacji .

Metaheurystyka

Jako istotne odejście od technik klasycznych, metoda metaheurystyczna (MH) implikuje strategię wyższego poziomu kontrolującą metody heurystyczne niższego poziomu. Metaheurystyka wykorzystuje nie tylko cechy problemu, ale także idee oparte na racjonalności sztucznej inteligencji, takie jak różne typy struktur pamięci i mechanizmy uczenia się, a także analogię z innymi metodami optymalizacji występującymi w naturze. Zainteresowanie podejściami metaheurystycznymi polega na tym, że na ogół zbiegają się one do satysfakcjonujących rozwiązań w sposób efektywny i wydajny (czas obliczeniowy i nakład pracy implementacyjnej). Rodzina metod metaheurystycznych obejmuje między innymi przeszukiwanie z tabu, symulowane wyżarzanie, obliczenia miękkie, algorytmy ewolucyjne, procedury pamięci adaptacyjnej, przeszukiwanie punktowe, optymalizację kolonii mrówek, inteligencję roju i ich hybrydy. Literaturę na ten temat można znaleźć na przykład w publikacjach (Glover i Gary, 2003) i (Gonzalez, 2007). W ostatnich dekadach zaobserwowano znaczny poziom zainteresowania badawczego podejściami metaheurystycznymi do rozwiązywania dużych rzeczywistych problemów harmonogramowania, które często są złożone, ograniczone i dynamiczne. Algorytmy harmonogramowania, które osiągają dobre lub prawie optymalne rozwiązania i mogą je skutecznie dostosowywać do zaburzeń, są w większości przypadków preferowane od tych, które osiągają rozwiązania optymalne, ale nie potrafią wdrożyć takiej adaptacji. Dzieje się tak w przypadku większości algorytmów rozwiązujących tzw. problem statycznego szeregowania zadań dla różnych ustawień systemów, zarówno pojedynczych, jak i wielomaszynowych. Ta rzeczywistość zmotywowała nas do skoncentrowania się na narzędziach, które mogłyby poradzić sobie z takimi dynamicznymi, zaburzonymi problemami szeregowania zadań, mimo że ze względu na złożoność tych problemów znalezienie optymalnych rozwiązań może być niemożliwe. Podjęto szereg prób modyfikacji algorytmów w celu dostrojenia ich do optymalizacji w zmieniającym się środowisku. We wszystkich tych badaniach zaobserwowano, że dynamiczne środowisko wymaga algorytmu, który utrzyma wystarczającą różnorodność, aby zapewnić ciągłą adaptację do zmian otoczenia. Chociaż zainteresowanie algorytmami optymalizacyjnymi dla problemów optymalizacji dynamicznej rośnie, a wielu autorów zaproponowało jeszcze więcej nowych podejść, w tej dziedzinie brakuje ogólnego zrozumienia odpowiednich problemów testowych, rzetelnych porównań i pomiaru jakości algorytmów . Pomimo wszystkich wcześniejszych prób, problem szeregowania zadań nadal jest znany jako NP-zupełny. Fakt ten zachęca badaczy do poszukiwania nowych kierunków.

Hybrydowe Systemy Inteligentne

Hybrydyzacja systemów inteligentnych to obiecujący obszar badań w dziedzinie inteligencji obliczeniowej, koncentrujący się na łączeniu wielu podejść w celu opracowania kolejnej generacji systemów inteligentnych. Ważnym impulsem dla badań w obszarze Hybrydowych Systemów Inteligentnych jest świadomość, że łączenie podejść będzie konieczne, aby rozwiązać pozostałe trudne problemy sztucznej inteligencji. Metaheurystyki, techniki inspirowane biologią, obliczenia neuronowe, uczenie maszynowe, systemy logiki rozmytej, algorytmy ewolucyjne, metody oparte na agentach i inne, zostały już opracowane i wykazały swoje mocne i słabe strony. Ostatnio hybrydowe systemy inteligentne zyskują na popularności ze względu na ich zdolność do radzenia sobie z wieloma złożonościami świata rzeczywistego, obejmującymi niedokładność, niepewność i niejasność.

HYBRYDOWY SYSTEM HARMONOGRAMOWANIA OPARTY NA METAHEURYSTYKACH

Celem niniejszego artykułu jest opisanie ram opartych na połączeniu metaheurystyki, przeszukiwania z wykorzystaniem tabu (TS) i algorytmów genetycznych (GA) oraz metod optymalizacji konstruktywnej do rozwiązywania pewnej klasy rzeczywistych problemów harmonogramowania, w których produkty (zadania) do przetworzenia mają terminy realizacji, czasy wydania i różne poziomy montażu. Oznacza to, że części do montażu mogą być wytwarzane równolegle, tj. jednocześnie. Problem, który omawiamy w niniejszej pracy, który nazywamy Problemem Rozszerzonego Harmonogramowania w Zakładzie Produkcyjnym (EJSSP), posiada istotne rozszerzenia i różnice w stosunku do klasycznego Problemu Harmonogramowania w Zakładzie Produkcyjnym. W niniejszej pracy definiujemy zadanie jako zlecenie produkcyjne na element finalny, który może być prosty lub złożony. Może być prosty, jak część, wymagający przetworzenia zestawu operacji. Omówiono również złożone elementy finalne, wymagające przetworzenia kilku operacji na wielu częściach, a następnie operacji montażu na kilku etapach. Co więcej, w praktyce środowisko harmonogramowania ma tendencję do bycia dynamicznym, tj. nowe zadania pojawiają się w nieprzewidywalnych odstępach czasu, maszyny ulegają awariom, zadania mogą być anulowane, a terminy i czasy przetwarzania mogą się często zmieniać . Zaczyna się od skupienia na rozwiązywaniu dynamicznych, deterministycznych problemów EJSSP. W tym celu opracowaliśmy ramy, prowadzące do dynamicznego systemu harmonogramowania, którego podstawowym narzędziem jest hybrydowy system harmonogramowania z dwoma głównymi elementami inteligencji (rysunek 1).



Jednym z takich elementów jest połączenie metody opartej na TS i GA oraz mechanizmu koordynacji działań między maszynami. Celem tego mechanizmu jest koordynacja działania maszyn z uwzględnieniem ograniczeń technologicznych zadań, tj. relacji pierwszeństwa operacji zadań, w celu uzyskania dobrych harmonogramów. Drugim elementem jest moduł dynamicznej adaptacji, który obejmuje mechanizmy regeneracji sąsiedztwa/populacji w dynamicznym otoczeniu, zwiększając lub zmniejszając ją w zależności od pojawienia się lub likwidacji nowych miejsc pracy. Szczegółowy opis podejścia, metod i ich zastosowania do konkretnych problemów można znaleźć w Madureira (2003).

Moduł przetwarzania wstępnego

Moduł przetwarzania wstępnego zajmuje się przetwarzaniem informacji wejściowych, a mianowicie definiowaniem problemu i tworzeniem instancji komponentów i parametrów algorytmu, takich jak początkowe rozwiązanie i mechanizmy generowania sąsiedztw, rozmiar sąsiedztwa/populacji, atrybuty listy tabu i długość listy tabu.

Moduł planowania hybrydowego

Na początku dekomponujemy deterministyczny problem EJSSP na serię deterministycznych problemów planowania pojedynczej maszyny (SMSP). Zakładamy istnienie różnych i znanych czasów zwolnienia zadania rj, przed którymi nie można wykonać żadnego przetwarzania, a także terminów wykonania zadania dj. Na ich podstawie określane są daty zwolnienia i terminy wykonania zadania dla każdego SMSP, a następnie każdy taki problem jest rozwiązywany niezależnie przez TS lub GA (biorąc pod uwagę problem samoparametryzacji). Następnie rozwiązania uzyskane dla każdego SMSP są integrowane w celu uzyskania rozwiązania głównego problemu EJSSP. Integracja rozwiązań SMSP może spowodować, że harmonogram EJSSP będzie niewykonalny. Dlatego naprawa harmonogramu może być konieczna, aby uzyskać wykonalne rozwiązanie. Realizuje to mechanizm naprawczy o nazwie Mechanizm Koordynacji Aktywności Międzymaszynowej (IMACM). Naprawa opiera się na koordynacji aktywności maszyn, z uwzględnieniem priorytetu operacji zadań i innych ograniczeń problemu. Odbywa się to przy zachowaniu niezmienionej kolejności alokacji zadań na każdej maszynie. Mechanizm IMACM ustala czas rozpoczęcia i zakończenia każdej operacji. Zapewnia on, że czas rozpoczęcia każdej operacji jest wyższy z dwóch następujących wartości:

o czas zakończenia operacji bezpośrednio poprzedzającej zadanie, jeśli jest tylko jedna, lub najwyższy ze wszystkich, jeśli jest ich więcej;
o czas zakończenia operacji bezpośrednio poprzedzającej zadanie na maszynie.

Moduł adaptacji dynamicznej

W przypadku problemów niedeterministycznych niektóre lub wszystkie parametry są niepewne, tj. nie są stałe, jak zakładaliśmy w problemie deterministycznym. Niedeterminizm zmiennych musi być uwzględniany w rzeczywistych problemach. Aby wygenerować akceptowalne rozwiązania w takich okolicznościach, nasze podejście rozpoczyna się od wygenerowania harmonogramu predykcyjnego z wykorzystaniem dostępnych informacji, a następnie, jeśli w systemie wystąpią zaburzenia podczas wykonywania, harmonogram może wymagać odpowiedniej modyfikacji lub korekty, tj. przeprowadzana jest reharmonogramacja/adaptacja dynamiczna. Dlatego w tym procesie należy podjąć ważną decyzję, a mianowicie o tym, czy i kiedy należy przeprowadzić reharmonogramowanie. Strategie decyzyjne dotyczące reharmonogramowania można podzielić na trzy kategorie: ciągłe, okresowe i hybrydowe. W przypadku reharmonogramowania ciągłego reharmonogramowanie jest przeprowadzane za każdym razem, gdy wystąpi zdarzenie modyfikujące stan systemu. W przypadku reharmonogramowania okresowego bieżący harmonogram jest modyfikowany w regularnych odstępach czasu, z uwzględnieniem zaburzeń harmonogramu, które wystąpiły. Wreszcie, w przypadku hybrydowego reharmonogramowania, bieżący harmonogram jest modyfikowany w regularnych odstępach czasu w przypadku wystąpienia zakłóceń. W systemie harmonogramowania dla EJSSP dynamiczna adaptacja jest konieczna ze względu na dwie klasy zdarzeń:

o Zdarzenia częściowe, które implikują zmienność atrybutów zadań lub operacji, takich jak czasy przetwarzania, terminy i czasy zwolnienia.
o Zdarzenia całkowite, które implikują zmienność struktury sąsiedztwa, wynikającą z pojawienia się nowych zadań lub anulowania zadań.

Podczas gdy, z jednej strony, zdarzenia częściowe wymagają jedynie przedefiniowania atrybutów zadań i ponownej oceny funkcji celu rozwiązań, zdarzenia całkowite, z drugiej strony, wymagają zmiany struktury i rozmiaru rozwiązania, przeprowadzanej poprzez wstawianie lub usuwanie operacji, a także ponownej oceny funkcji celu. Dlatego w przypadku zdarzenia całkowitego modyfikacja bieżącego rozwiązania jest konieczna. W niniejszej pracy jest to realizowane za pomocą mechanizmów opisanych w (Madureira, Ramos i Silva, 2004) dla SMSP. Biorąc pod uwagę czas przetwarzania i wysoką częstotliwość zakłóceń, należy unikać ponownego planowania wszystkich zadań od początku. Jeśli jednak praca jeszcze się nie rozpoczęła i czas jest dostępny, oczywistym i prostym podejściem do ponownego planowania byłoby ponowne rozpoczęcie planowania od nowa z nowym, zmodyfikowanym rozwiązaniem, uwzględniającym zakłócenia, na przykład pojawienie się nowego zadania. Gdy nie ma wystarczająco dużo czasu na ponowne zaplanowanie od podstaw lub przetwarzanie zadań już się rozpoczęło, należy zastosować strategię dostosowującą bieżący harmonogram, uwzględniając rodzaj zaistniałego zaburzenia. Wystąpienie zdarzenia częściowego wymaga ponownego zdefiniowania atrybutów zadania i ponownej oceny funkcji celu harmonogramu. Zmiana terminu wykonania zadania wymaga ponownego obliczenia czasu rozpoczęcia i zakończenia operacji dla wszystkich odpowiednich operacji. Natomiast zmiany czasu przetwarzania operacji wymagają jedynie ponownego obliczenia czasu rozpoczęcia i zakończenia operacji kolejnych operacji. Przybycie nowego zadania wymaga zdefiniowania czasu rozpoczęcia i zakończenia odpowiedniej operacji oraz mechanizmu regenerującego w celu zintegrowania wszystkich operacji na poszczególnych problemach pojedynczej maszyny. W przypadku anulowania zadania, zastosowanie mechanizmu regenerującego eliminuje operacje zadań z SMSP, w którym się pojawiają. Po dodaniu lub usunięciu pozycji, regeneracja sąsiedztwa odbywa się poprzez aktualizację rozmiaru sąsiedztwa i zapewnienie struktury identycznej z istniejącą. Następnie moduł planowania może zastosować proces wyszukiwania lepszych rozwiązań z nowym, zmodyfikowanym rozwiązaniem.

Mechanizm integracji przybycia zadania

Gdy nowe zadanie jest gotowe do przetworzenia, potrzebny jest mechanizm integracji. Analizuje on graf pierwszeństwa zadań, który reprezentuje uporządkowany przydział maszyn do każdej operacji zadania, i integruje każdą operację w odpowiedni problem pojedynczej maszyny. Dla każdej operacji można zastosować dwie alternatywne procedury: albo losowo wybrać jedną pozycję do wstawienia nowej operacji do bieżącego rozwiązania/chromosomu, albo użyć inteligentnego mechanizmu do wstawienia tej operacji do harmonogramów, na przykład w oparciu o priorytet zadania.

Mechanizm eliminacji zadania

Gdy zadanie zostanie anulowane, należy zaimplementować mechanizm eliminacji, aby odpowiadająca mu pozycja/gen została usunięta z rozwiązań.

Mechanizmy regeneracji

Po przeprowadzeniu integracji/eliminacji operacji, poprzez wstawienie/usunięcie pozycji/genów w bieżącym rozwiązaniu/chromosomie, regeneracja populacji odbywa się poprzez aktualizację jej rozmiaru. Rozmiar populacji dla SMSP jest proporcjonalny do liczby operacji. Po procesie dynamicznej adaptacji można zastosować metodę harmonogramowania i poszukiwać lepszych rozwiązań z wykorzystaniem zmodyfikowanego rozwiązania. W ten sposób zaproponowaliśmy system hybrydowy, w którym pewne aspekty samoorganizacji można uwzględnić w zależności od rozwiązywanego problemu: metoda i/lub parametry mogą zmieniać się w czasie wykonywania, używany MH może zmieniać się w zależności od charakterystyki problemu itd.

TRENDY NA PRZYSZŁOŚĆ

Biorąc pod uwagę złożoność inherentną systemom produkcyjnym, dynamiczne harmonogramowanie jest uważane za doskonałego kandydata do zastosowania technologii opartej na agentach. Naturalną ewolucją zaproponowanego powyżej podejścia jest System Harmonogramowania Wieloagentowego, który zakłada istnienie kilku Agentów Maszynowych (będących jednostkami decyzyjnymi) rozproszonych w Systemie Produkcyjnym, które oddziałują i współpracują z innymi agentami w celu uzyskania optymalnej lub bliskiej optymalnej wydajności globalnej. Główną ideą jest to, że z lokalnych, autonomicznych i często sprzecznych zachowań agentów wyłania się globalne rozwiązanie, będące wynikiem działania społeczności agentów maszynowych, realizujących lokalnie swoje harmonogramy i współpracujących z innymi agentami maszynowymi (Madureira, Gomes i Santos, 2006). Agenci muszą być w stanie uczyć się i zarządzać swoimi wewnętrznymi zachowaniami oraz relacjami z innymi agentami, poprzez negocjacje kooperacyjne, zgodnie z politykami biznesowymi zdefiniowanymi przez menedżera użytkowników. Niektóre aspekty samoorganizacji można rozważyć w zależności od rozwiązywanego problemu: metoda i/lub parametry mogą zmieniać się w czasie wykonywania, agenci mogą używać różnych MH w zależności od charakterystyki problemu itp.

WNIOSKI

W niniejszym artykule zaproponowano architekturę systemu, która dobrze wykorzystuje i łączy zalety dwóch różnych metaheurystyk: przeszukiwania z tabu i algorytmów genetycznych. Uważamy, że opisano nowy wkład w rozwiązywanie bardziej realistycznych problemów harmonogramowania - rozszerzone problemy warsztatowe (Job-Shop Problems). Specyfiką naszego podejścia jest procedura harmonogramowania operacji, ponieważ każda maszyna najpierw znajduje lokalne rozwiązania optymalne lub prawie optymalne, a następnie, poprzez interakcję z innymi maszynami za pośrednictwem mechanizmów współpracy, znajduje optymalny harmonogram globalny w dynamicznych środowiskach. Proponowany system jest przygotowany do wykorzystania innych metaheurystyk wyszukiwania lokalnego do sterowania harmonogramami w oparciu o praktycznie dowolną miarę wydajności i nie jest ograniczony do konkretnego typu problemów harmonogramowania.

WSTĘP

Wiele znanych w przyrodzie systemów wzrokowych charakteryzuje się szerokim polem widzenia, pozwalającym zwierzętom na kontrolowanie całego otaczającego środowiska. Ważki są pod tym względem jednym z najlepszych przykładów: ich oczy złożone składają się z tysięcy oddzielnych, światłoczułych organów, ułożonych tak, aby zapewnić niemal 360-stopniowe pole widzenia. Zwierzęta z oczami po bokach głowy charakteryzują się jednak wysoką peryskopowością, ale niską obuocznością, co oznacza, że ich pola widzenia nakładają się w niewielkim stopniu. Z kolei oczy ptaków drapieżnych posiadają centralną część, która pozwala im widzieć odległe szczegóły z imponującą rozdzielczością, a ich pola widzenia nakładają się na siebie w zakresie około dziewięćdziesięciu stopni. Te cechy zapewniają jednocześnie szerokie pole widzenia i dokładne widzenie stereoskopowe, co z kolei pozwala na określenie odległości, co z kolei prowadzi do uzyskania ostrego, trójwymiarowego obrazu dużej części pola widzenia. W zastosowaniach robotyki mobilnej od robotów autonomicznych wymaga się reagowania na bodźce wzrokowe, które mogą pochodzić z dowolnego kierunku w dowolnym momencie ich aktywności. W zastosowaniach monitoringu, możliwość uzyskania jak najszerszego pola widzenia jest również kluczowym wymogiem. Z tych powodów pojawiło się rosnące zainteresowanie wielokierunkowymi systemami wizyjnymi ,które wciąż stanowią szczególnie intrygujący obszar badań. Z drugiej strony, wymagania dotyczące możliwości rozpoznawania i klasyfikacji obiektów/wzorców są odmienne, a wysoka rozdzielczość i dokładność oraz niskie zniekształcenia są prawdopodobnie najważniejsze.Wreszcie, ekstrakcję informacji trójwymiarowych można zazwyczaj osiągnąć za pomocą systemów wizyjnych, które łączą wykorzystanie co najmniej dwóch czujników jednocześnie. Niniejszy artykuł przedstawia klasę hybrydowych systemów wizyjnych z dwiema kamerami. Tego rodzaju czujniki, inspirowane istniejącymi w naturze systemami wizyjnymi, łączą czujnik wielokierunkowy z kamerą perspektywiczną. W ten sposób możliwe jest obserwowanie całej otaczającej sceny w niskiej rozdzielczości, a jednocześnie kamera perspektywiczna może być skierowana na obiekty zainteresowania o wyższej rozdzielczości.

TŁO

Istnieją zasadniczo dwa sposoby obserwacji bardzo szerokiego obszaru. Możliwe jest użycie wielu kamer skierowanych na nienakładające się obszary lub odwrotnie, jednej kamery o szerokim polu widzenia. W pierwszym przypadku ilość analizowanych danych jest znacznie większa niż w drugim. Ponadto należy uporać się z problemami kalibracji i synchronizacji sieci kamer. Z drugiej strony, w drugim podejściu system jest tańszy, łatwy do kalibracji, a analiza pojedynczego obrazu jest prosta. W tym przypadku wadą jest jednak utrata rozdzielczości, w której widoczne są szczegóły obiektów, ponieważ szersze pole widzenia jest rzutowane na ten sam obszar czujnika wideo i w ten sposób opisane tą samą liczbą pikseli, co w przypadku zwykłego czujnika. Było to oczywiste od połowy lat 90. XX wieku dzięki wcześniejszym eksperymentom z wielokierunkowymi systemami wizyjnymi. W związku z tym pojawiło się wiele badań nad czujnikami wielokierunkowymi "wzbogaconymi" o co najmniej jedno drugie źródło danych środowiskowych, aby uzyskać szerokie pola widzenia bez utraty rozdzielczości. Na przykład niektóre prace, zorientowane na zastosowania w robotyce, dotyczyły kamery katadioptrycznej współpracującej ze skanerem laserowym, jak, by wymienić tylko kilka ostatnich, w (Kobilarov 2006; Mei 2006). Bardziej zorientowane na zastosowania w nadzorze prace obejmowały systemy wielokamerowe, łączące kamery dookólne i tradycyjne, podczas gdy inne prace dotyczyły geometrycznych aspektów hybrydowych relacji stereo/wielowidokowych, jak w (Sturm 2002; Chen 2003). Naturalnym wyborem w celu opracowania taniego systemu wizyjnego łączącego w sobie dookólną i wysoką rozdzielczość szczegółową jest połączenie kamery dookólnej z ruchomą kamerą tradycyjną. W dalszej części skupimy się na tego rodzaju systemach, które są zwykle nazywane "hybrydowymi systemami dualnymi".

Widzenie dookólne

Istnieją dwa sposoby uzyskiwania obrazów dookólnych. Za pomocą specjalnego rodzaju obiektywów zamontowanych na standardowej kamerze, zwanych "obiektywami typu rybie oko", możliwe jest uzyskanie pola widzenia do około 180 stopni w obu kierunkach. Najszerszy obiektyw typu rybie oko, jaki kiedykolwiek wyprodukowano, charakteryzował się polem widzenia 220 stopni. Niestety, bardzo trudno jest zaprojektować obiektyw typu rybie oko, który spełniałby ograniczenie pojedynczego punktu widzenia. Chociaż obrazy uzyskiwane za pomocą obiektywów typu rybie oko mogą okazać się wystarczająco dobre dla niektórych zastosowań wizualizacyjnych, problem kompensacji zniekształceń nie został jeszcze rozwiązany, a wysoki koszt jednostkowy stanowi poważną wadę w przypadku ich powszechnego zastosowania. Połączenie soczewki prostoliniowej ze zwierciadłem to inny sposób uzyskiwania obrazów dookólnych. W tzw. soczewkach katadioptrycznych zwierciadło wypukłe jest umieszczane przed soczewką prostoliniową, co pozwala uzyskać pole widzenia być może nawet większe niż w przypadku obiektywu typu rybie oko. Zastosowanie luster o specjalnym kształcie, precyzyjnie umieszczonych względem kamery, umożliwia również spełnienie ograniczenia pojedynczego punktu widzenia, a tym samym uzyskanie obrazu poprawnego perspektywicznie. Co więcej, obiektywy katadioptryczne są zazwyczaj tańsze niż obiektywy typu "rybie oko". Na rysunku przedstawiono porównanie tych dwóch rodzajów obiektywów.



PRZEGLĄD HYBRYDOWYCH SYSTEMÓW Z PODWÓJNĄ KAMERĄ

Pierwszą pracą dotyczącą hybrydowych czujników wizyjnych jest prawdopodobnie praca wspomniana w (Nayar 1997) i określana jako "Wielokierunkowy system obrotu/pochylenia/zoomu", w którym jednostka PTZ była sterowana sygnałami wejściowymi uzyskanymi z obrazu wielokierunkowego. W następnym roku zaprezentowano rozproszony system monitoringu wewnętrznego: kamerę peryferyjną skalibrowano w celu oszacowania odległości między celem a rzutem kamery na podłogę. W ten sposób możliwe było precyzyjne skierowanie czujnika dołka środkowego o znanej pozycji na cel i śledzenie go. Hybrydowy system wykrywania przeszkód w nawigacji robotów został opisany w pracy kilka lat później. W tej pracy kamera katadioptryczna została skalibrowana wraz z kamerą perspektywiczną jako pojedynczy czujnik: procedura kalibracji pozwoliła na obliczenie odwrotnego mapowania perspektywy (IPM) w oparciu o płaszczyznę odniesienia, podłogę, dla obu obrazów, a tym samym, dzięki różnicom kamer, na wykrywanie przeszkód poprzez obliczenie różnicy między nimi. Chociaż było to możliwe tylko w obrębie wspólnego pola widzenia obu kamer, to dzięki widokowi omni-view potencjalnie możliwe były zadania takie jak ocena ruchu własnego. System ten został dodatkowo ulepszony i przetestowany głównie w zastosowaniach RoboCup . Na rysunku 2 można zobaczyć parę obrazów uzyskanych za pomocą takiego systemu.



Niektóre ostatnie prace koncentrowały się na wykorzystaniu systemów z dwiema kamerami w zastosowaniach monitoringu. W (Scotti 2005), po wykryciu alarmu przez czujnik dookólny, kamera PTZ zostaje uruchomiona, a oba widoki rozpoczynają autonomiczne śledzenie celu. Pozyskane sekwencje wideo i inne metadane, takie jak informacje o klasyfikacji obiektów, są następnie wykorzystywane do aktualizacji rozproszonej bazy danych, z której użytkownicy mogą później korzystać. Podobnie w (Yao 2006), po uruchomieniu kamery PTZ przez kamerę dookólną, cel jest śledzony niezależnie w obu widokach, ale następnie do fuzji danych używany jest zmodyfikowany filtr Kalmana: takie podejście zapewnia lepszą dokładność śledzenia i pozwala wyeliminować sporadyczne przesłonięcia, co prowadzi do powstania solidnego systemu nadzoru.

TRENDY PRZYSZŁOŚCI

Współczesne utrzymanie porządku publicznego, kontrola dostępu do nieruchomości prywatnych i monitoring wizyjny to powody, dla których musimy monitorować rozległe obszary naszego otoczenia. Monitoring to stale rozwijający się rynek, a automatyczny monitoring stanowi interesujące wyzwanie: wiele projektów jest ukierunkowanych na ten kierunek, a w niektórych z nichistotną rolę odgrywają już hybrydowe systemy z dwiema kamerami. System monitoringu zainstalowany między Eagle Pass w Teksasie a Piedras Negras w Meksyku przez inżynierów z Laboratorium Wizji Komputerowej i Robotyki Uniwersytetu Kalifornijskiego w San Diego, powiązanego z Kalifornijskim Instytutem Telekomunikacji i Technologii Informacyjnych, jest przykładem bardzo złożonego systemu monitoringu, w którym wykorzystano hybrydowe systemy z dwiema kamerami . Ze względu na konkurencyjną cenę, kompaktowość i możliwości oferowane przez te systemy, prawdopodobnie będą one coraz częściej wykorzystywane w przyszłości w inteligentnych systemach monitoringu. Kolejnym obszarem budzącym duże zainteresowanie jest nawigacja pojazdów autonomicznych. Chociaż obecnie istnieje jeszcze wiele problemów do rozwiązania, zanim autonomiczne pojazdy publiczne staną się powszechne, zastosowania przemysłowe są już możliwe. Ponieważ dookólne serwonapędy wizualne i estymacja ruchu własnego mogą być faktycznie implementowane również przy użyciu hybrydowych systemów z dwiema kamerami, a obecność drugiego obrazu o wysokiej rozdzielczości oferuje znacznie więcej możliwości, ich przyszłe zaangażowanie w tej dziedzinie jest pożądane.

WNIOSKI

Opisano i krótko omówiono klasę hybrydowych systemów z dwiema kamerami. Łączne zastosowanie standardowej kamery i czujnika katadioptrycznego zapewnia tego typu czujnikom ich różne i uzupełniające się cechy: podczas gdy tradycyjna kamera może być używana do pozyskiwania szczegółowych informacji o ograniczonym obszarze zainteresowania ("widzenie dośrodkowe"), czujnik dookólny dostarcza szerokozakresowych, ale mniej szczegółowych informacji o otoczeniu ("widzenie peryferyjne"). Śledzenie wielu obiektów/osób w oparciu o obrazy o wysokiej rozdzielczości w celu rozpoznania i kontroli dostępu lub szacowanie prędkości, wymiarów i trajektorii obiektu/osoby to tylko niektóre przykłady możliwych zadań automatycznego nadzoru, do których nadają się hybrydowe systemy z dwiema kamerami. Co więcej, ich zastosowanie w (autonomicznej) nawigacji robotów umożliwia precyzyjne wykrywanie przeszkód, szacowanie ruchów własnych i trójwymiarową rekonstrukcję otoczenia. Dzięki jednemu z tych czujników na pokładzie, robot mobilny może otrzymać wszystkie niezbędne informacje potrzebne do bezpiecznego poruszania się w dynamicznym środowisku.

WSTĘP

Biologiczne procesy widzenia zazwyczaj charakteryzują się następującymi fazami:

o Świadomość: naturalne lub sztuczne czynniki działające w dynamicznych środowiskach mogą korzystać z możliwie przybliżonego, globalnego opisu otoczenia. U ludzi nazywa się to widzeniem peryferyjnym,ponieważ powstaje ono w wyniku bodźców pochodzących z krawędzi siatkówki.
o Uwaga: po wykryciu interesującego obiektu/zdarzenia wymagana jest wyższa rozdzielczość, aby skupić na nim wzrok i zaplanować odpowiednią reakcję. U ludzi odpowiada to tzw. widzeniu dołkowemu, ponieważ pochodzi ono z centrum siatkówki (dołka środkowego).
o Analiza: uzyskanie szczegółowych informacji o interesujących obiektach, ich trójwymiarowej strukturze i relacjach przestrzennych kończy proces widzenia. Osiągnięcie tych celów wymaga co najmniej dwóch widoków otaczającej sceny ze znanymi relacjami geometrycznymi. U ludzi funkcja ta jest realizowana z wykorzystaniem widzenia obuocznego (stereo).

Widzenie komputerowe często próbowało naśladować systemy naturalne lub przynajmniej czerpać z nich inspirację. W rzeczywistości różne poziomy rozdzielczości są przydatne również w wizji maszynowej. W ostatniej dekadzie w literaturze pojawiło się wiele badań dotyczących wielu kamer o różnych rozdzielczościach. Co więcej, stale rosnąca wydajność komputerów i stale malejący koszt sprzętu wideo umożliwiają rozwój systemów, które opierają się głównie, a nawet wyłącznie, na wizji do nawigacji i reagowania na zmiany otoczenia w czasie rzeczywistym. Co więcej, wykorzystanie wizji jako unikalnego źródła bodźców sensorycznych zbliża sztuczną percepcję do percepcji ludzkiej, w przeciwieństwie do systemów opartych na innych rodzajach czujników, i umożliwia rozwój bardziej bezpośrednich, inspirowanych biologicznie podejść do interakcji ze środowiskiem zewnętrznym . Niniejszy artykuł przedstawia HOPS (Hybrid Omnidirectional Pin-hole Sensor), klasę czujników wizyjnych z dwiema kamerami, które starają się podkreślić związek między wizją maszynową a wizją biologiczną.

TŁO

W ostatniej dekadzie przeprowadzono kilka badań nad hybrydowymi systemami z podwójną kamerą . Łączne zastosowanie ruchomej kamery standardowej i czujnika katadioptrycznego zapewnia tym czujnikom ich różne i uzupełniające się cechy: podczas gdy tradycyjna kamera może być używana do pozyskiwania szczegółowych informacji o ograniczonym obszarze zainteresowania ("widzenie dośrodkowe"), czujnik dookólny dostarcza szerokozakresowych, ale mniej szczegółowych informacji o otoczeniu ("widzenie peryferyjne"). Możliwe zastosowania tej klasy systemów wizyjnych to aplikacje do monitoringu wizyjnego, a także zadania nawigacji robotów mobilnych. Co więcej, ich konkretna konfiguracja umożliwia realizację różnych strategiikontroli orientacji kamery standardowej; na przykład rozproszone skupienie na różnych obiektach umożliwia wykonywanie zadań rozpoznawania/klasyfikacji, podczas gdy ciągłe ruchy pozwalają śledzić dowolny interesujący ruchomy obiekt. Możliwa jest również rekonstrukcja trójwymiarowa oparta na widzeniu stereoskopowym.

HOPS: Hybrydowy wielokierunkowy czujnik otworkowy

Niniejszy artykuł koncentruje się na najnowszym prototypie czujnika HOPS (hybrydowy wielokierunkowy czujnik otworkowy) . HOPS to dwukamerowy system wizyjny, który zapewnia wysokiej rozdzielczości 360-stopniowe pole widzenia, a także możliwości rekonstrukcji 3D. Skuteczność tego hybrydowego czujnika wynika z połączenia tradycyjnej kamery i centralnej kamery katadioptrycznej, które spełniają ograniczenie pojedynczego punktu widzenia. Dzięki dwóm różnym punktom widzenia, z których obserwuje się świat, czujnik może działać jako para stereo, znajdując skuteczne zastosowania w nadzorze i nawigacji robotów. Aby stworzyć poręczny i wszechstronny system, który mógłby sprostać wymaganiom całego procesu wizyjnego w szerokiej gamie zastosowań, HOPS został zaprojektowany tak, aby można go było traktować jako pojedynczy, zintegrowany obiekt: jedną z najbardziej bezpośrednich zalet tego rozwiązania jest to, że po zmontowaniu i skalibrowaniu można go umieścić i przesuwać w dowolnym miejscu (na przykład na środku sufitu pomieszczenia lub na robocie mobilnym) bez konieczności dalszych kalibracji. Rysunek 1 przedstawia dwa najnowsze prototypy HOPS. W tym, który został użyty w opisanych tutaj eksperymentach, tradycyjna kamera, która w tej wersji nie obraca się, została umieszczona na górze i może być skierowana w dół z odpowiednim, stałym kątem nachylenia, aby uzyskać obraz o wysokiej rozdzielczości ograniczonego obszaru w pobliżu czujnika. Na środku widać kamerę katadioptryczną składającą się z tradycyjnej kamery skierowanej w górę na wiszące nad nią lustro hiperboliczne i podtrzymywane przez cylinder z pleksiglasu. Jak widać, lustro można przesuwać w górę i w dół, aby umożliwić optymalne pozycjonowanie podczas kalibracji. Ponadto, aby uniknąć niepożądanych odbić światła na wewnętrznej powierzchni cylindra z pleksiglasu, na wierzchołku lustra umieszczono czarną igłę, zgodnie z sugestią . Wreszcie, w dolnej części, niektóre obwody generują sygnały synchronizacji wideo i umożliwiają połączenia zewnętrzne. Nowsza wersja HOPS (patrz rysunek 1, po prawej) przezwycięża pewne ograniczenia obecnej wersji.



Wykorzystuje ona dwie cyfrowe kamery Firewire o wysokiej rozdzielczości, w połączeniu z obiektywami megapikselowymi charakteryzującymi się bardzo niskimi zniekształceniami telewizyjnymi, aby uzyskać lepszą jakość obrazu. Co więcej, w tej nowej wersji tradycyjna kamera jest zawieszona na silniku krokowym, sterowanym przez interfejs USB, dzięki czemu może się obracać. Tym razem tradycyjną kamerę umieszczono poniżej części katadioptrycznej: dzięki temu w polu widzenia obrazu dookólnego nie ma żadnych przewodów, a ponadto w zastosowaniach monitorujących możliwe jest zobaczenie również martwego obszaru obrazu dookólnego ze względu na odbicie kamery od lustra.

Kalibracja czujnika

Aby uzyskać informacje metryczne z obrazów dwuwymiarowych, należy przeprowadzić kalibrację kamery i oszacować parametry geometryczne niezbędne do opisu procesu tworzenia obrazu. Dlatego po kalibracji relacje między punktami na obrazach a ich rzeczywistym położeniem w przestrzeni 3D można wyrazić za pomocą równań matematycznych, które pozwalają rozwiązać problemy metryczne. Kalibracja czujnika może opierać się na standardowej kalibracji fotogrametrycznej (Kraus 1993; Zhang 2000) z wykorzystaniem silnie ustrukturyzowanego środowiska z siatkami punktów o znanych współrzędnych. Najpierw obie kamery są kalibrowane niezależnie, przed montażem na czujniku, w celu oszacowania ich zniekształceń wewnętrznych, a także zniekształceń radialnych wprowadzanych przez układ optyczny. Następnie lustro jest precyzyjnie ustawiane względem kamery, aby uzyskać obraz z jednego punktu widzenia dla części katadioptrycznej czujnika, zgodnie z opisem . Ostatnia, ale prawdopodobnie najważniejsza faza kalibracji ma na celu wykrycie zależności geometrycznych między obrazem tradycyjnym a wielokierunkowym: ponownie, do oszacowania parametrów odwzorowania wykorzystano zbiór znanych punktów. Należy zauważyć, że zależności obliczone między dwoma widokami są stałe w czasie ze względu na strukturę czujnika. W ten sposób, po zakończeniu procedury kalibracji, nie są już potrzebne żadne zewnętrzne stałe punkty odniesienia, a czujnik można umieścić w dowolnym miejscu i wykonywać zadania związane z widzeniem stereoskopowym bez konieczności dalszej kalibracji. Pozycjonowanie lustra względem kamery Aby ustawić lustro hiperboliczne względem standardowej kamery i uzyskać charakterystykę pojedynczego punktu widzenia, charakterystyczną dla części katadioptrycznej czujnika, można postępować w następujący sposób. Zakładając, że ograniczenie pojedynczego punktu widzenia jest spełnione, a profil lustra jest znany, dane kalibracyjne kamery i kilka prostych równań można wykorzystać do obliczenia oczekiwanych rzutów dowolnego znanego zestawu punktów 3D na obraz wielokierunkowy. Aby zweryfikować poprawność względnego położenia lustra względem kamery, zbudowano skrzynkę kalibracyjną, z siatkami o znanych współrzędnych namalowanymi na jej wewnętrznych ściankach. Dzięki temu, po umieszczeniu w niej czujnika, lustro można ręcznie przesuwać, aż siatki pojawiające się na obrazie rejestrowanym w czasie rzeczywistym będą odpowiadały siatkom teoretycznym nałożonym na nie, tak jak powinny wyglądać, gdyby lustro zostało prawidłowo umieszczone .



Jest to bardzo tania metoda, która jednak daje bardzo dobre rezultaty.

Wspólna kalibracja kamer

Aby uzyskać w pełni efektywny system stereo, niezbędna jest wspólna kalibracja kamer, w celu uzyskania informacji o względnym położeniu pary kamer. Zazwyczaj jako globalny punkt odniesienia dla pary wybiera się wewnętrzny układ odniesienia jednej z dwóch kamer: ponieważ dostępne są dwa różne rodzaje kamer, najprostszym rozwiązaniem jest ustawienie układu kamery dookólnej jako globalnego punktu odniesienia dla całego czujnika. Wykorzystując ponownie wspomniane siatki punktów, uzyskuje się pary obrazów (dookólną i tradycyjną) siatek leżących na różnych (równoległych) płaszczyznach o znanych względnych położeniach. Po oszacowaniu współrzędnych 3D położenia punktów, odniesionych do układu odniesienia czujnika, za pomocą obrazu dookólnego, rozwiązanie ograniczeń geometrycznych między rzutami punktów w tradycyjnym obrazie pozwala oszacować względne położenie tradycyjnej kamery. Aby uwzględnić obrót standardowej kamery, jej położenie musi zostać opisane za pomocą bardziej złożonej transformacji niż po prostu ustalona rototranslacja: geometryczne i kinematyczne sprzężenie między dwiema kamerami musi zostać zrozumiane i zamodelowane z większą liczbą parametrów. Oczywiście wymaga to wykonania zdjęć tradycyjną kamerą w wielu różnych położeniach. Po tej wspólnej kalibracji kamery, HOPS może być użyty do wykonania pomiarów metrycznych na obrazach, uzyskując dane trójwymiarowe odniesione do jej własnego globalnego układu odniesienia: oznacza to, że nie są potrzebne dalsze kalibracje w celu uwzględnienia przemieszczeń czujnika.

Reprojekcje perspektywiczne i odwrotne mapowanie perspektywy

Jedną z możliwości oferowanych przez obraz perspektywiczny jest możliwość zastosowania transformacji Odwrotnego Mapowania Perspektywicznego (IPM) w celu uzyskania innego obrazu, w którym zawartość informacji jest jednorodnie rozłożona na wszystkie piksele. Ponieważ centralne kamery katadioptryczne charakteryzują się pojedynczym punktem widzenia, obrazy przez nie uzyskiwane są obrazami perspektywicznymi nadającymi się do wykorzystania w IPM. Wybierając wirtualną płaszczyznę obrazu jako nową domenę dla IPM, z części tych obrazów dookólnych można uzyskać reprojekcję perspektywiczną podobną do obrazów tradycyjnych. Rysunek 3 przedstawia parę obrazów uzyskanych metodą HOPS oraz rekonstrukcję perspektywiczną widoku dookólnego uzyskaną za pomocą IPM na odpowiadającym mu obszarze widzianym przez tradycyjną kamerę.



Jak widać, różnica w rozdzielczości między tymi dwoma widokami perspektywicznymi jest znaczna. Wybierając płaszczyznę poziomą jako punkt odniesienia dla IPM, można uzyskać coś bardzo zbliżonego do widoku ortograficznego tego obszaru, zwykle określanego jako "widok z lotu ptaka". Jeśli podłoga zostanie użyta jako punkt odniesienia do wykonania IPM na obu obrazach, możliwe jest uzyskanie użytecznych informacji o obiektach/przeszkodach otaczających system .

Testy rekonstrukcji 3D

Aby zweryfikować poprawność procesu kalibracji, można przeprowadzić oszacowanie położenia punktów w przestrzeni trójwymiarowej wraz z innymi testami. Po przechwyceniu jednego obrazu z każdego z dwóch widoków, punkty we wzorze testowym są automatycznie wykrywane, a dla każdego z nich obliczane są promienie światła, z których został wygenerowany, na podstawie modelu projekcji uzyskanego podczas kalibracji. Ponieważ oszacowane promienie homologiczne są zazwyczaj liniami skośnymi, można znaleźć najkrótszy odcinek łączący oba promienie, a jego punkt środkowy wykorzystać jako oszacowanie położenia punktu w przestrzeni trójwymiarowej. W tabeli 1 przedstawiono wyniki uzyskane przy użyciu wzorca testowego 4x3 punktów z odległością 60 mm między środkami punktów. Nawet jeśli początek układu odniesienia czujnika jest fizycznie niedostępny i nie ma dostępu do precyzyjnych przyrządów, wzór ten został umieszczony tak dokładnie, jak to możliwe, 390 mm prostopadle przed samym czujnikiem (wzdłuż kierunku y w wybranym układzie odniesienia) i wyśrodkowany wzdłuż kierunku x: zmierzone współrzędne z punktów w górnym rzędzie wyniosły 55 mm. To ustawienie znajduje odzwierciedlenie w wartościach szacunkowych dla pierwszego eksperymentu podanych w Tabeli 1. Co ważniejsze, średnia odległość między punktami została oszacowana na 59,45 mm przy odchyleniu standardowym ? = 1,14: wartości te są w pełni zgodne z rozdzielczością dostępną do pomiaru odległości na wzorze testowym oraz z rozdzielczością lustra (również ograniczoną rozdzielczością obrazu). W drugim eksperymencie wykorzystano wzór testowy z sześcioma punktami oddalonymi o 110 mm, zlokalizowanymi około 1 m przed, 0,25 m na prawo i nieco poniżej czujnika. W dolnej części Tabeli 1 przedstawiono szacowane położenia: szacowana średnia odległość wyniosła 109,09 mm przy odchyleniu standardowym ? = 8,89. W innym teście z tym samym wzorcem, zlokalizowanym 1,3 m przed, 0,6 m na lewo i 0,5 m poniżej czujnika (patrz Rysunek 4), szacowana średnia odległość wyniosła około 102 mm przy odchyleniu standardowym ? = 9,98. Należy zauważyć, że przy tych odległościach, biorąc pod uwagę rozdzielczość obrazu, a także profil lustra, rozdzielczość czujnika jest tego samego rzędu wielkości, co uzyskane błędy. Ponadto metoda używana do znajdowania środka okręgów jest obarczona wadami w postaci wahań jasności i kontrastu: zastąpienie okręgów sąsiednimi naprzemiennymi czarnymi i białymi kwadratami oraz użycie detektora narożnego o dokładności subpikselowej prawdopodobnie dałoby lepsze rezultaty.

TRENDY PRZYSZŁOŚCI

Dziedziną, która obecnie cieszy się dużym zainteresowaniem, jest nawigacja pojazdów autonomicznych. Choć obecnie wciąż wiele problemów pozostaje do rozwiązania, zanim autonomiczne pojazdy publiczne staną się powszechne, możliwe są już zastosowania przemysłowe. Ponieważ wyniki w zakresie wielokierunkowego serwoserwisowania wizualnego i estymacji ruchu autonomicznego znajdują również zastosowanie w hybrydowych systemach z dwiema kamerami, a obecność drugiego obrazu o wysokiej rozdzielczości oferuje znacznie więcej możliwości, wykorzystanie takich urządzeń w tej dziedzinie jest pożądane. Nawet jeśli większość zastosowań tych systemów jest związana z nadzorem, mogłyby one znaleźć zastosowaniejeszcze bardziej bezpośrednio w robotycznych działaniach człowieka, ponieważ roboty/pojazdy biorące udział w tych sytuacjach są mniej krytyczne, a ich sterowanie jest łatwiejsze.

WNIOSKI

Opisano hybrydowy system z dwoma kamerami i wielokierunkowym czujnikiem otworkowym (HOPS). Ponieważ jego wspólna kalibracja kamery prowadzi do w pełni skalibrowanej hybrydowej pary stereo, z której można wyodrębnić informacje 3D, HOPS nadaje się do wielu rodzajów zastosowań. Na przykład,może być używany do nadzoru i samolokalizacji robotów lub wykrywania przeszkód, oferując możliwość integracji detekcji stereoskopowej ze strategiami aktywnego widzenia peryferyjnego/dołkowego: po zlokalizowaniu obiektów lub obszarów zainteresowania na czujniku szerokozakresowym, tradycyjna kamera może zostać użyta do zwiększenia rozdzielczości, z jaką można analizować te obszary. Śledzenie wielu obiektów/osób w oparciu oobrazy o wysokiej rozdzielczości do rozpoznawania i kontroli dostępu lub szacowania prędkości, wymiarów i trajektorii to niektóre przykłady zadań nadzoru, do których nadaje się HOPS. Dokładne wykrywanie przeszkód, lokalizacja punktów orientacyjnych, solidna estymacja ruchu własnego lub trójwymiarowa rekonstrukcja środowiska to inne przykłady możliwych zastosowań związanych z (autonomiczną/holonomiczną) nawigacją robotów w środowiskach częściowo ustrukturyzowanych lub całkowicie nieustrukturyzowanych. Przeprowadzono kilka wstępnych eksperymentów, aby rozwiązać zarówno kwestie nadzoru, jak i nawigacji robotów, z obiecującymi wynikami.

WSTĘP

Uczenie się przez wzmacnianie (RL) zajmuje się problemem agenta, który musi nauczyć się, jak zachowywać się, aby zmaksymalizować swoją użyteczność poprzez interakcje z otoczeniem . Problemy uczenia się przez wzmacnianie są zazwyczaj formalizowane jako Procesy Decyzyjne Markowa (MDP), które składają się ze skończonego zbioru stanów i skończonej liczby możliwych działań, które agent może wykonać. W dowolnym momencie agent znajduje się w określonym stanie i wybiera działanie. Następnie może obserwować nowy stan, do którego prowadzi to działanie, i otrzymuje sygnał nagrody. Celem agenta jest maksymalizacja długoterminowej nagrody. W tej standardowej formalizacji nie zakłada się żadnej szczególnej struktury ani relacji między stanami. Jednak uczenie się w środowiskach o ekstremalnie dużych przestrzeniach stanów jest niewykonalne bez jakiejś formy generalizacji. Wykorzystanie ukrytej struktury problemu może wpłynąć na generalizację i od dawna jest uznawane za ważny aspekt w reprezentowaniu sekwencyjnych zadań decyzyjnych . Hierarchiczne uczenie się przez wzmacnianie (Hierarchical Reinforcement Learning) to poddziedzina uczenia maszynowego (RL), która zajmuje się odkrywaniem i/lub wykorzystywaniem tej ukrytej struktury. W hierarchicznym uczeniu maszynowym (RL) stosuje się dwie główne idee. Pierwsza z nich polega na rozbiciu zadania na hierarchię mniejszych podzadań, z których każde można opanować szybciej i łatwiej niż cały problem. Podzadania można również wykonywać wielokrotnie w trakcie realizacji większego zadania, ponownie wykorzystując zgromadzoną wiedzę i umiejętności. Druga koncepcja polega na wykorzystaniu abstrakcji stanu w podzadaniach: nie każde zadanie musi dotyczyć każdego aspektu przestrzeni stanów, więc niektóre stany można w rzeczywistości wyabstrahować i traktować jako takie same dla celów danego podzadania.

TŁO

W tej sekcji przedstawimy formalizm MDP, na którym opiera się większość badań w standardowym uczeniu maszynowym (RL). Następnie omówimy dwa główne podejścia stosowane do uczenia MDP: RL oparte na modelu i RL bez modelu. Na koniec przedstawimy dwa formalizmy rozszerzające MDP i szeroko stosowane w dziedzinie hierarchicznego RL: semi-Markov Decision Processes (SMDP) i MDP faktoryzowane. Procesy decyzyjne Markowa (MDP) Proces decyzyjny Markowa składa się z:

o zbioru stanów S
o zbioru działań A
o funkcji prawdopodobieństwa przejścia: Pr(s′ | s, a), reprezentującej prawdopodobieństwo przejścia środowiska do stanu s′, gdy agent wykonuje działanie a ze stanu s. Czasami jest ona oznaczana jako T(s, a, s′).
o funkcji nagrody: E[r | s, a], reprezentującej oczekiwaną natychmiastową nagrodę uzyskaną poprzez podjęcie działania a ze stanu s.
o czynnik dyskontowy γ ∈ (0, 1], który obniża wagę przyszłych nagród i którego dokładna rola stanie się jaśniejsza w poniższych równaniach.

Deterministyczna polityka π:S -> A jest funkcją, która określa, dla każdego stanu, jakie działanie należy podjąć. Dla dowolnej danej polityki ? możemy zdefiniować funkcję wartości V?, reprezentującą oczekiwany zdyskontowany zwrot w nieskończonym horyzoncie czasowym, jaki można uzyskać z takiej polityki, rozpoczynając od stanu s:



Bellman (1957) przedstawia rekurencyjny sposób określania funkcji wartości, gdy znane są prawdopodobieństwo nagrody i przejścia MDP, zwany równaniem Bellmana:



często zapisywana jako funkcja akcji-wartości lub funkcja Q:



Optymalna polityka π*(s) to polityka, która zwraca działanie a maksymalizujące funkcję wartości:

π*s=argmax_aQ*(s,a) Stany można przedstawić jako zbiór zmiennych stanu lub czynników, reprezentujących różne cechy środowiska: s = 1, f₂, f₃, … , f_n>.

Uczenie się w Procesach Decyzyjnych Markowa (mDP)

Problem uczenia się przez wzmacnianie polega na określeniu lub aproksymacji optymalnej strategii poprzez powtarzające się interakcje ze środowiskiem (tj. na podstawie próby doświadczeń w postaci ). Istnieją trzy główne podejścia do uczenia się takiej optymalnej lub prawie optymalnej strategii:

o Metody poszukiwania strategii: uczenie się strategii bezpośrednio poprzez ewaluację w środowisku.
o Metody bezmodelowe (lub bezpośrednie): uczenie się strategii poprzez bezpośrednią aproksymację funkcji Q aktualizacjami z bezpośredniego doświadczenia.
o Metody oparte na modelu (lub pośrednie): najpierw uczenie się funkcji prawdopodobieństwa przejścia i funkcji nagrody, a następnie wykorzystanie ich do obliczenia funkcji Q za pomocą, na przykład, równań Bellmana.

Algorytmy bezmodelowe są czasami określane jako rodzina algorytmów uczenia się Q. Pierwsze najbardziej znane przykłady można znaleźć w pracach Suttona (1988) lub Watkinsa (1989). Wiadomo, że metody bezmodelowe nieefektywnie wykorzystują doświadczenie, ale nie wymagają kosztownych obliczeń, aby uzyskać funkcję Q i odpowiadającą jej optymalną strategię. Metody oparte na modelach efektywniej wykorzystują doświadczenie, a tym samym wymagają mniej danych, ale wymagają dodatkowego etapu planowania, aby obliczyć funkcję wartości, co może być kosztowne obliczeniowo. Niektóre znane algorytmy można znaleźć w literaturze . Algorytmy uczenia się przez wzmacnianie w środowiskach MDP cierpią na tzw. przekleństwo wymiarowości: wykładniczy wzrost całkowitej liczby stanów w funkcji liczby zmiennych stanu. Aby poradzić sobie z tym problemem, metody hierarchiczne starają się rozbić trudną przestrzeń stanów na mniejsze fragmenty, które można uczyć się niezależnie i ponownie wykorzystywać w razie potrzeby. Aby osiągnąć ten cel, konieczne jest wprowadzenie zmian do standardowego formalizmu MDP. We wstępie wspomnieliśmy o dwóch głównych ideach hierarchicznego RL: dekompozycji zadań i abstrakcji stanu. Dekompozycja zadań oznacza, że agent będzie wykonywał nie tylko pojedyncze czynności, ale także pełne podzadania, które można rozszerzyć w czasie. Procesy decyzyjne Semi-Markowa (SMDP) pozwolą nam przedstawić te rozszerzone czynności. Abstrakcja stanu oznacza, że w pewnych kontekstach pewne aspekty przestrzeni stanów będą ignorowane, a stany grupowane. Reprezentacje stanu czynnikowego to jeden ze sposobów radzenia sobie z tym problemem.

Poza MDP: SMDP i reprezentacje stanu czynnikowego

Rozważymy ograniczenia standardowego formalizmu MDP za pomocą ilustrującego przykładu. Wyobraźmy sobie agenta, którego zadaniem jest wyjście z wielopiętrowego budynku biurowego. Pozycją startową agenta jest określone biuro na określonym piętrze, a celem jest dotarcie do drzwi wejściowych na poziomie parteru. Aby wykonać zadanie, agent musi najpierw wyjść z pokoju, znaleźć drogę przez korytarze do windy, zjechać windą na parter, a na końcu znaleźć drogę z windy do wyjścia. Chcielibyśmy móc rozumować w kategoriach podzadań (np. "wyjście z pokoju", "idź do windy", "idź na piętro X" itd.), z których każde miałoby inny czas trwania i inny poziom abstrakcji, a każde obejmowałoby serię działań niższego poziomu lub działań prymitywnych. Każde z tych podzadań dotyczy również tylko pewnych aspektów pełnej przestrzeni stanów: dopóki agent znajduje się w pokoju, a aktualnym zadaniem jest wyjście z niego, piętro, na którym znajduje się winda, ani to, czy drzwi wejściowe budynku są otwarte, czy zamknięte, nie ma znaczenia. Cechy te staną się jednak kluczowe później, gdy podzadanie agenta ulegnie zmianie. W formalizacji MDP czas jest reprezentowany jako dyskretny krok o unitarnym i stałym czasie trwania. Ta formuła nie pozwala na reprezentację rozciągniętych w czasie działań o różnym czasie trwania, które mogłyby reprezentować rodzaj działań wyższego rzędu zidentyfikowanych w przykładzie. Formalizm procesów decyzyjnych semi-Markowa (SMDP) umożliwia taką reprezentację. W SMDP funkcja przejścia jest modyfikowana, aby reprezentować prawdopodobieństwo, że działanie a ze stanu s doprowadzi do następnego stanu s′ po t krokach czasowych:

Pr(s′,t|s,a) Odpowiednia funkcja wartości wygląda teraz następująco:



Sieci SMDP umożliwiają również reprezentację czasu ciągłego. Algorytmy programowania dynamicznego do rozwiązywania sieci SMDP omówiono w pracach Puterman (1994) oraz Mahadevan (1997). Sieci MDP z rozłożonym stanem uwzględniają fakt, że pewne aspekty przestrzeni stanu są nieistotne dla określonych działań. W sieciach MDP z rozłożonym stanem zmienne stanu są rozkładane na niezależnie określone składowe, a prawdopodobieństwa przejścia są definiowane jako iloczyn prawdopodobieństw czynnikowych. Powszechnym sposobem reprezentacji relacji niezależności między zmiennymi stanu są dynamiczne sieci Bayesa (DBN). Na przykład wyobraźmy sobie, że stan jest reprezentowany przez cztery zmienne stanu: s = 1, f₂, f₃,f₄, i wiemy, że dla działania a wartość zmiennej f₁ w następnym stanie zależy tylko od wcześniejszych wartości f₁ i f₄, f₂ zależy od f₂ i f₃, a pozostałe zależą tylko od swoich własnych wcześniejszych wartości. To prawdopodobieństwo przejścia w sieci MDP z rozłożonym stanem byłoby przedstawione jako:



HIERARCHICZNE METODY UCZENIA SIĘ PRZEZ WZMACNIANIE

W ramach hierarchicznej dziedziny uczenia się przez wzmacnianie można zidentyfikować różne podejścia i cele. Niektóre algorytmy koncentrują się na uczeniu się hierarchicznego widoku środowiska lub wykonywanego zadania, podczas gdy inne koncentrują się jedynie na wykorzystaniu tej wiedzy, gdy jest ona dostarczana jako dane wejściowe. Niektóre techniki starają się uczyć się lub wykorzystywać działania rozciągnięte w czasie, abstrahując zestaw działań prowadzących do ukończenia podzadania lub podcelu. Inne metody starają się abstrahować różne stany, traktując je tak, jakby były równe z punktu widzenia problemu uczenia się. Krótko omówimy zestaw algorytmów wykorzystujących kombinację tych podejść. Zidentyfikujemy również, które z tych metod opierają się na paradygmacie uczenia się bezmodelowego, a które na tych, które próbują zbudować model środowiska.

Opcje: Uczenie się działań rozszerzonych czasowo w ramach SMDP

Opcje wykorzystują ramy SMDP, aby umożliwić agentowi grupowanie serii działań (strategii opcji), które prowadzą do określonego stanu lub zestawu stanów określanych jako podcele. Dla każdej opcji identyfikowany jest również zestaw prawidłowych stanów początkowych, w których agent może zdecydować, czy wykonać jednokrokową czynność prymitywną, czy skorzystać z opcji. Opcje można traktować jako wstępnie zapisane strategie wykonywania abstrakcyjnych podzadań. Algorytm uczenia się opcji został opisany przez Suttona, Precupa i Singha (1999) i należy do rodziny bezmodelowych metod uczenia Q. W obecnej postaci ramy opcji pozwalają na dwupoziomowe hierarchie zadań, chociaż potencjalnie można je uogólnić na wiele poziomów. Stany końcowe (tj. podcele) są podawane jako dane wejściowe do algorytmu. Prowadzone są prace poświęcone odkrywaniu tych podcelów i konstruowaniu na ich podstawie użytecznych opcji . Chociaż wykazano, że opcje skracają czas uczenia się algorytmów bezmodelowych, nie jest jasne, czy istnieje przewaga w zakresie czasu uczenia się nad metodami opartymi na modelach. Jak każda metoda bezmodelowa, nie wiążą się one jednak z kosztami obliczeniowymi związanymi z etapem planowania. Nadal otwarte pozostaje pytanie, czy opcje można uogólnić na hierarchie wielopoziomowe, a większość prac ma charakter empiryczny i nie ma ograniczeń teoretycznych.

MaxQ: Połączenie hierarchicznej dekompozycji zadań z abstrakcją stanu MaxQ to również algorytm bezmodelowy z rodziny algorytmów uczenia się Q. Otrzymuje on jako dane wejściowe wielopoziomową hierarchiczną dekompozycję zadań, która rozkłada cały bazowy MDP na addytywną kombinację mniejszych MDP. W obrębie każdego zadania stosowana jest abstrakcja, dzięki czemu zmienne stanu, które nie mają znaczenia dla zadania, są ignorowane . Główną wadą MaxQ jest konieczność dostarczenia hierarchii i abstrakcji jako danych wejściowych, a w formie bezmodelowej uniemożliwia ona szybsze uczenie się.
DSHP: Hierarchiczna dekompozycja oparta na modelu dla efektywnego uczenia i planowania

Deterministyczne hierarchiczne planowanie oparte na próbkach (DSHP) łączy reprezentacje MDP w stanach faktorowych, hierarchiczną dekompozycję zadań MaxQ oraz uczenie się oparte na modelu, aby osiągnąć udowodnioną efektywność uczenia się i planowania w domenach deterministycznych . Chociaż DSHP, jako algorytm oparty na modelu, umożliwia szybsze uczenie się i planowanie, nadal boryka się z problemem konieczności dostarczenia hierarchii i abstrakcji jako danych wejściowych.

HEXQ: Odkrywanie hierarchii

W przeciwieństwie do MaxQ, DSHP i innych metod, które otrzymują hierarchiczną dekompozycję zadań jako dane wejściowe, HEXQ próbuje ją automatycznie odkryć. HEXQ analizuje ślady doświadczenia i identyfikuje obszary MDP o powtarzających się cechach. Wykorzystuje to doświadczenie do budowania abstrakcji czasowych i stanowych, konstruując hierarchię mniejszych, powiązanych MDP. HEXQ jest bezmodelowy i oparty na uczeniu się Q. HEXQ stanowi obiecującą metodę odkrywania abstrakcji i hierarchii, ale wciąż brakuje jej jakichkolwiek ograniczeń teoretycznych lub dowodów. Wszystkie pracez wykorzystaniem HEXQ miały charakter empiryczny, a jego ogólna moc wciąż pozostaje otwarta.

HAM-PHAM: Ograniczanie klasy możliwych strategii

Hierarchie maszyn abstrakcyjnych (HAM) również wykorzystują formalizm SMDP. Główną ideą jest ograniczenie klasy możliwych strategii za pomocą małych, niedeterministycznych maszyn skończonych, które ograniczają dozwolone sekwencje działań. Elementy w HAM-ach można traktować jako małe programy, które w pewnych momentach mogą decydować o wywołaniach innych programów niższego poziomu . Zobacz także Programmable HAM (PHAM), rozszerzenie Andre i Russella (2000). HAM oferuje interesujące podejście ułatwiające naukę i planowanie, ale jego skuteczność została udowodniona jedynie w pewnych przykładach empirycznych.

TRENDY NA PRZYSZŁOŚĆ

Spodziewamy się, że większość nowych prac w dziedzinie Hierarchical Reinforcement Learning będzie dotyczyć dwóch obszarów: odkrywania hierarchii i abstrakcji oraz transferu wiedzy. Uważamy, że głównym otwartym pytaniem jest to, jak strukturę można wyuczyć się z doświadczenia, a raz poznaną zastosować do zadań i problemów innych niż pierwotne. Obecnie powstaje również obiecująca, ale wciąż niewiele prac teoretycznych w tej dziedzinie, prac, które mogłyby udowodnić ogólną skuteczność różnych metod. Większość prac ma charakter empiryczny i ich skuteczność została udowodniona jedynie poprzez eksperymenty w małych domenach.

WNIOSKI

Celem hierarchicznego uczenia się przez wzmacnianie jest zwalczanie "klątwy wymiarowości", głównej przeszkody w osiągnięciu skalowalnego uczenia rzeczywistego, które można zastosować do rzeczywistych problemów, za pomocą hierarchicznych dekompozycji zadań i abstrakcji stanu. Ten aktywny obszar badań osiągnął mieszane rezultaty, a algorytmy i frameworki skupiały się tylko na jednej lub dwóch kombinacjach różnych aspektów problemu. Pojedyncze podejście, które poradziłoby sobie z odkrywaniem struktur i ich wykorzystaniem, zarówno z abstrakcją czasową, jak i stanową, oraz które mogłoby w sposób udowodniony uczyć się i planować w czasie wielomianowym, jest nadal głównym punktem programu badawczego tej dziedziny.

WSTĘP

Niniejszy artykuł opisuje nową klasę modeli neuro-rozmytych, zwanych Hierarchicznymi Systemami Neuro-Rozmytymi z Uczeniem Wzmocnień (RL-HNF). Modele te wykorzystują partycjonowanie przestrzeni wejściowej metodą BSP (Binary Space Partitioning) i Politree i zostały opracowane w celu ominięcia tradycyjnych wad systemów neuro-rozmytych: ograniczonej liczby dozwolonych danych wejściowych i ograniczonej zdolności do tworzenia własnej struktury i reguł (ANFIS , NEFCLASS i FSOM ).Te nowe modele, nazwane Reinforcement Learning Hierarchical Neuro-Fuzzy BSP (RL-HNFB) i Reinforcement Learning Hierarchical Neuro-Fuzzy Politree (RL-HNFP), wywodzą się z oryginalnego HNFB, który wykorzystuje partycjonowanie przestrzeni binarnej . Dzięki zastosowaniu partycjonowania hierarchicznego wraz z metodologią Reinforcement Learning (RL) uzyskano nową klasę systemów neuro-rozmytych (SNF), które oprócz automatycznego uczenia się swojej struktury, wykonują autonomiczne uczenie się działań, które ma podjąć agent, ignorując informacje a priori (liczba reguł, reguł rozmytych i zbiorów) odnoszące się do procesu uczenia. Te cechy stanowią istotną różnicę w porównaniu z istniejącymi systemami uczenia się inteligentnych agentów, ponieważ w aplikacjach obejmujących środowiska ciągłe i/lub środowiska uważane za wysoce wymiarowe, stosowanie tradycyjnych metod uczenia się przez wzmacnianie (Reinforcement Learning) opartych na tablicach wyszukiwania (tablicach przechowujących funkcje wartości dla małej lub dyskretnej przestrzeni stanów) nie jest już możliwe, ponieważ przestrzeń stanów staje się zbyt duża. Ta druga część hierarchicznych systemów neuro-rozmytych koncentruje się na wykorzystaniu procesu uczenia się przez wzmacnianie. W pierwszej części przedstawiono modele HNFB oparte na metodach uczenia nadzorowanego. Modele RL-HNFB i RL-HNFP zostały ocenione w testowej aplikacji sterującej oraz symulowanym środowisku robota Khepera z wieloma przeszkodami.

TŁO

Model opisany w niniejszym artykule został opracowany w oparciu o analizę ograniczeń istniejących modeli oraz pożądanych cech systemów uczenia się opartych na RL, szczególnie w aplikacjach obejmujących środowiska ciągłe i/lub wysoko wymiarowe . W związku z tym, aby pokonać te podstawowe ograniczenia, opracowano hierarchiczne systemy neuro-rozmyte oparte na uczeniu się przez wzmacnianie. Opracowano dwa różne modele tej klasy systemów neuro-rozmytych, oparte na technikach uczenia się przez wzmacnianie.

HIERARCHICZNE SYSTEMY NEURO-ROZMYTE

W tej sekcji przedstawiono nową klasę systemów neuro-rozmytych opartych na partycjonowaniu hierarchicznym. Jak wspomniano w pierwszej części, opracowano dwa podzbiory hierarchicznych systemów neuro-rozmytych, w zależności od zastosowanego procesu uczenia: modele uczenia się z nadzorem (HNFB , HNFB-1 , HNFB-Mamdani ); oraz modele uczenia się przez wzmacnianie (RL-HNFB , RL-HNFP ). Niniejszy artykuł koncentruje się na drugim podzbiorze modeli. Modele te opisano w kolejnych sekcjach.

HIERARCHICZNE MODELE NEURO-FUZZY DO UCZENIA SIĘ PRZEZ WZMOCNIENIE

Modele RL-HNFB i RL-HNFP składają się z jednej lub kilku standardowych komórek, zwanych odpowiednio RL-neuro-fuzzy-BSP (RL-NFB) i RL-neuro-fuzzy-Politree (RLNFP). W kolejnych podsekcjachopisano podstawowe komórki, struktury hierarchiczne i algorytm uczenia się.

Neuro-rozmyte komórki BSP i Politree w uczeniu wzmacniającym

Komórka RL-NFB to mini-neuro-rozmyty system, który wykonuje binarne partycjonowanie danej przestrzeni zgodnie z funkcjami przynależności ρ i μ. Podobnie, komórka RL-NFP to mini-neuro-rozmyty system, który wykonuje partycjonowanie 2ⁿ danej przestrzeni wejściowej, również wykorzystując komplementarne funkcje przynależności w każdym wymiarze wejściowym. Komórki RL-NFB i RL-NFP generują precyzyjny (wyraźny) wynik po procesie defuzyfikacji . Komórka RL-NFB ma tylko jedno wejście (x) z nią powiązane. Komórka RL-NFP odbiera wszystkie wejścia, które są rozpatrywane w problemie. Dla celów ilustracyjnych, rysunek 1(a) przedstawia komórkę z dwoma wejściami - x₁ i x₂ - (partycjonowanie Quadtree), zapewniając prostszą reprezentację niż n-wymiarowa forma Politree.



Na rysunku 1(a) każde partycjonowanie jest generowane przez połączenie dwóch funkcji przynależności - ρ (niska) i μ (wysoka) każdej zmiennej wejściowej. Następniki partycjonowań poli komórki mogą być typu singletonowego lub wyjściami etapu poprzedniego poziomu. Chociaż następnik singletonowy jest prosty, nie jest on wcześniej znany, ponieważ każdy następnik singletonowy jest powiązany z działaniem, które nie zostało zdefiniowane a priori. Każdy podział poli ma zbiór możliwych działań (a₁, a₂, … a_n), jak pokazano na rysunku 1(a), a każde działanie jest powiązane z funkcją wartości Q. Wartość Q jest definiowana jako suma oczekiwanych wartości nagród uzyskanych przez wykonanie działania a w stanie s, zgodnie z strategią π. Więcej szczegółów na temat teorii RL można znaleźć w [Sutton, 1998]. Interpretacja językowa mapowania realizowanego przez komórkę RL-NFP przedstawioną na rysunku 1(a) opiera się na następującym zestawie reguł:



gdzie następnik a_i odpowiada jednemu z dwóch możliwych następników poniżej:

singleton (rozmyty następnik singletonu lub Sugeno zerowego rzędu): przypadek, gdy a_i = stała;
wyjście etapu poprzedniego poziomu: przypadek, gdzie a_i = y_m, gdzie y_m reprezentuje wyjście komórki ogólnej "m".

Architektury RL-HNFB i RL-HNFP

Modele RL-HNFB i RL-HNFP można tworzyć w oparciu o wzajemne połączenia komórek podstawowych. Komórki tworzą strukturę hierarchiczną, która skutkuje regułami składającymi się na rozumowanie agenta. W przykładzie architektury przedstawionej na rysunku 1(b),



partycje poli 1, 3, 4, …, m-1 nie zostały podzielone, mając jako następniki swoich reguł wartości odpowiednio a₁, a₃, a₄, … a_m-1. Z drugiej strony, partycje poli 2 i m zostały podzielone; zatem konsekwencją ich reguł są wyjścia (y₂ i y_m) odpowiednio podsystemów 2 i m. Z kolei te podsystemy mają, jako konsekwencję, wartości a₂₁, a₂₂, ..… a_2m i a_m1, a_m2, .…, a_mm. Każde "a_i" odpowiada konsekwencji Sugeno zerowego rzędu (singleton), reprezentującej działanie, które zostanie zidentyfikowane (pomiędzy możliwymi działaniami) poprzez uczenie ze wzmocnieniem jako najkorzystniejsze dla określonego stanu środowiska. Należy podkreślić, że definicja, która partycja ma zostać podzielona, a która nie, jest definiowana automatycznie przez algorytm uczenia. Wyjście systemu przedstawionego na rysunku 1(b) (defuzzyfikacja) jest dane równaniem (1). W tych równaniach ?i odpowiada poziomowi aktywacji partycji i, a ai jest następstwem pojedynczym reguły związanej z partycją i.



Algorytm uczenia się RL-HNFB i RL-HNFP

Proces uczenia się rozpoczyna się od zdefiniowania odpowiednich danych wejściowych dla systemu/środowiska, w którym znajduje się agent, oraz zestawów działań, które może on wykorzystać, aby osiągnąć swoje cele. Agent musi wykonać wiele cykli, aby zapewnić uczenie się w systemie/środowisku, w którym się znajduje. Cykl jest definiowany jako liczba kroków podejmowanych przez agenta w środowisku, rozciągająca się od punktu inicjacji do punktu docelowego. Modele RL-HNFB i RL-HNFP wykorzystująten sam algorytm uczenia się. Każda partycja wybiera działanie ze swojego zestawu działań; działanie wynikowe jest obliczane przez proces defuzzyfikacji i reprezentuje działanie, które zostanie wykonane przez elementy wykonawcze agentów. Po wykonaniu działania wynikowego,środowisko jest ponownie odczytywane. Odczyt ten umożliwia obliczenie wartości wzmocnienia środowiska, która zostanie użyta do oceny działania podjętego przez agenta. Wzmocnienie jest obliczane dla każdej partycji wszystkich aktywnych komórek, poprzez jej udział w działaniu wynikowym. W ten sposób wzmocnienie środowiskowe obliczone przez funkcję oceny jest propagowane wstecz z komórki korzeniowej do komórek liściowych. Następnie wartości Q powiązane z działaniami, które przyczyniły się do działania wynikowego, są aktualizowane w oparciu o algorytm SARSA [Sutton, 1998]. Modele RL_HNFB i RL_HNFP zostały ocenione w różnych aplikacjach sterowania. Dwa z tych zastosowań sterowania przedstawiono w następnej sekcji.

STUDIA PRZYPADKÓW

Centrowanie wózka

Problem centrowania wózka [Koza, 1992] jest powszechnie używany jako punkt odniesienia w obszarze programowania ewolucyjnego, gdzie siła przyłożona do samochodu jest typu "bang bang" . Ten problem został wykorzystany głównie w celu oceny, jak dobrze modele RL-HNFB i RL-HNFP dostosowują się do zmian w domenie zmiennych wejściowych bez konieczności przechodzenia przez nową fazę uczenia. Problem polega na zaparkowaniu w centrum jednowymiarowego środowiska samochodu o masie m, który porusza się wzdłuż tego środowiska pod wpływem przyłożonej siły F. Zmiennymi wejściowymi są położenie (x) samochodu i jego prędkość (v). Celem jest zaparkowanie samochodu w położeniu x = 0 z prędkością v = 0. Równania ruchu są następujące (gdzie parametr τ reprezentuje jednostkę czasu):



Globalne wzmocnienie oblicza się za pomocą poniższego równania (3): Jeśli (x>0 i v<0) lub (x<0 i v>0)



W przeciwnym razie R_global = 0 .Funkcja oceny rośnie, gdy samochód zbliża się do środka otoczenia z prędkością zerową. Współczynniki k₁ i k₂ to stałe większe od 1, służące do dostosowania wartości wzmocnienia do struktury modelu. Wartości użyte dla jednostki czasu i masy to τ = 0,02 i m = 2,0. Kryterium zatrzymania jest spełnione, gdy różnica między wartością prędkości a wartością położenia w odniesieniu do celu (x = 0 i v = 0) jest mniejsza niż 5% uniwersum dyskursu danych wejściowych położenia i prędkości. Tabela 1 przedstawia średnią wyników uzyskanych w 5 eksperymentach dla każdej konfiguracji

.

Kolumny "limity położenia" i "limity prędkości" odnoszą się do limitów narzuconych zmiennym stanu (położenia i prędkości) podczasuczenia się i testowania. Działania użyte w tych eksperymentach to: F1={-150,-75,-50,-30,-20,-10,-5,0,5,10,20, 30,50,75,150}. Rozmiar kolumny struktury pokazuje średnią liczbę komórek na końcu każdego eksperymentu, a ostatnia kolumna pokazuje średnią liczbę kroków podczas fazy uczenia się. Liczbę cykli ustalono na 1000. W każdym cyklu punkty startowe samochodu wynosiły x=-3 lub x=3. Jak widać z Tabeli 1, struktura RL-HNFP jest mniejsza, ponieważ każda komórka otrzymuje obie zmienne wejściowe, podczas gdy w przypadku modelu RL-HNFB na każdym poziomie drzewa BSP stosowana jest inna zmienna wejściowa. Tabela 2 przedstawia wyniki uzyskane dla jednego z 5 eksperymentów przeprowadzonych dla każdej konfiguracji pokazanej w Tabeli 1, gdy samochód startuje w punktach (-2, -1, 1, 2), które nie były używane w fazie uczenia się.



W pierwszej konfiguracji każdego modelu wyniki pokazują, że im szersze są granice położenia i prędkości (w tym przypadku równe |10|), tym trudniej jest się uczyć. W takich przypadkach występuje niewielka oscylacja wokół punktu centralnego. W rzeczywistości prędkość końcowa jest bardzo mała, ale po pewnym czasie ma tendencję do wypychania samochodu poza obszar zbieżności, co skutkuje szczytem prędkości w przeciwnym kierunku, korygującym położenie samochodu. W drugiej konfiguracji występuje mniej oscylacji, ponieważ granice położenia i prędkości zostały obniżone do |3|.

Robot Khepera

Model RL-HNFP został również przetestowany za pomocą symulatora robota Khepera . Model testowano w środowisku kwadratowym, w którym agent przemieszczał się z jednego z rogów, aby dotrzeć do przeciwległego rogu. Niemniej jednak nie mógł przejść przez środek otoczenia z powodu przeszkody. Robot Khepera rejestruje sygnały otoczenia za pomocą 8 czujników zgrupowanych w 4: jeden przed, po jednym z każdej strony i jeden za. Jego działania są wykonywane za pomocą 2 niezależnych silników o mocy wahającej się od -20 do 20, jeden po prawej stronie, a drugi po lewej stronie. Model RL-HNFP został wytrenowany w jednym środowisku z dużą przeszkodą w kształcie centralnego kwadratu, zwanym środowiskiem I (Rysunek 2).



Został przetestowany w dwóch środowiskach: tym samym środowisku I (z dużą przeszkodą w kształcie centralnego kwadratu), ale z różnymi pozycjami początkowymi; oraz innym środowisku z czterema dodatkowymi przeszkodami. To nowe środowisko z wieloma przeszkodami (środowisko II) składa się z: dużej przeszkody centralnej, małych przeszkód u góry po lewej stronie, u dołu po prawej stronie i po lewej stronie .



We wszystkich eksperymentach z wykorzystaniem obu środowisk celem robota było osiągnięcie pozycji (5, 5). Na rysunkach 2 i 3 białe kółka wskazują pozycje początkowe robota, a szare kółka pokazują ich pozycje końcowe. Rysunek 2 przedstawia eksperymenty w środowisku I. Wyniki odnoszą się do testów wykonanych przy użyciu struktury wytrenowanej z różnych pozycji, różniących się od tych użytych w testach, co dowodzi, że nabyta wiedza została uogólniona, a uzyskane wyniki są zgodne z oczekiwaniami. Rysunki 3(a), 3(b) i 3(c) przedstawiają eksperymenty w środowisku II. Wyniki opisane na tych rysunkach odnoszą się do testów wykonanych w środowisku II z wiedzą nabytą w środowisku I. Należy zauważyć, że trzy dodatkowe przeszkody nie wpływają na wyniki w tych eksperymentach. Jak wykazano na tych rysunkach, wyniki wskazują na dobrą wydajność modelu. Jest to tym ważniejsze, że liczba cykli uczenia była bardzo mała (tylko 400 cykli). Wynik przedstawiony na rysunku 3(c) podkreśla ten fakt. W tym przypadku agent nie podąża najkrótszą ścieżką do punktu docelowego. Wręcz przeciwnie, w niektórych punktach obraca się wokół środowiska, aż dotrze do punktu docelowego. Aby poprawić wydajność robota, model powinien być wykonywany przez co najmniej 2000 cykli, co zostało już wykazane w poprzednich przypadkach z wykorzystaniem tej aplikacji.

TRENDY NA PRZYSZŁOŚĆ

Jeśli chodzi o hierarchiczne modele neuro-fuzzy oparte na uczeniu się przez wzmocnienie, trwają również prace nad pewnymi ulepszeniami. Aby poprawić ich wydajność, planuje się przeprowadzanie testów z wykorzystaniem śladów kwalifikowalności. Jest to metoda, która aktualizuje nie tylko bieżącą wartość funkcji stanu, ale także wartość funkcji poprzednich stanów w ramach predefiniowanego limitu. Inną propozycją ulepszenia modelu RL-NFHP jest wykorzystanie zasady WoLF (Wygraj lub Ucz się Szybko) [Bowling, 2002] w celu modyfikacji tempa uczenia się, które dostosowuje politykę. Zasada WoLF polega na szybkim uczeniu się, gdy przegrywa, i wolniejszym, gdy wygrywa. Planuje się również ocenę tych modeli z wykorzystaniem rzeczywistych robotów. Model RL-HNFP jest również modyfikowany do użytku w środowisku kooperacyjnym z wieloma agentami. W tym środowisku proces uczenia się odbywa się poprzez dzielenie się zdobytą wiedzą między istniejącymi agentami.

WNIOSKI

Celem niniejszego artykułu było wprowadzenie nowej klasy modeli neuro-rozmytych, których celem jest poprawa słabych punktów konwencjonalnych systemów neuro-rozmytych. Modele RL-NFHB i RL-HNFP należą do tej nowej klasy systemów neuro-rozmytych, zwanej Hierarchicznym Systemem Neuro-Rozmytym. Modele RL-NFHB i RL-HNFP były w stanie tworzyć i rozszerzać strukturę reguł bez wcześniejszej wiedzy (reguły lub zbiory rozmyte); wydobywać wiedzę z bezpośredniej interakcji agenta z dużymi i/lub ciągłymi środowiskami (poprzez uczenie się przez wzmacnianie), aby nauczyć się, jakie działania mają zostać wykonane; oraz generować interpretowalne reguły rozmyte, które składają się na inteligencję agenta, aby osiągnąć jego cel(e). Agent był w stanie uogólniać swoje działania, wykazując odpowiednie zachowanie, gdy znajdował się w stanach, których działania nie zostały szczegółowo wyuczone. Ta zdolność zwiększa autonomię agenta.

WSTĘP

Zapora to ściana, która zatrzymuje wodę, a eksploatacja wielu zapór to skomplikowany proces decyzyjny, stanowiący problem optymalizacyjny . Tradycyjnie badacze stosowali matematyczne techniki optymalizacji z formułą programowania liniowego (LP) lub programowania dynamicznego (DP) w celu znalezienia harmonogramu. Jednak większość modeli matematycznych jest ważna tylko dla uproszczonych systemów zapór. W związku z tym w ciągu ostatniej dekady niektóre techniki metaheurystyczne, takie jak algorytm genetyczny (GA) i symulowane wyżarzanie (SA), zyskały duże zainteresowanie wśród badaczy zapór. Ostatnio opracowano kolejny algorytm metaheurystyczny - algorytm wyszukiwania harmonijnego (HS - harmony search), który zastosowano do różnych problemów sztucznej inteligencji, takich jak komponowanie muzyki i rozwiązywanie łamigłówek sudoku. Algorytm HS zastosowano również do różnych problemów inżynieryjnych, takich jak projektowanie konstrukcji , projektowanie sieci wodociągowych , analiza stateczności gruntu, projektowanie satelitarnych rur cieplnych , projektowanie konstrukcji morskich , projektowanie systemów rusztowych oraz estymacja parametrów hydrologicznych . Algorytm HS może być kompetentną alternatywą dla istniejących metaheurystyk, takich jak algorytmy genetyczne (GA), ponieważ pierwszy z nichprzezwyciężył wadę (taką jak teoria bloków konstrukcyjnych) drugiego . Aby przetestować możliwości algorytmu HS w problemie eksploatacji wielu zapór, niniejszy artykuł przedstawia model HS i stosuje go do systemu testowego, a następnie porównuje wyniki z wynikami wcześniej opracowanego modelu algorytmu genetycznego (GA).

TŁO

Przed niniejszym badaniem różni badacze zajmowali się problemem harmonogramowania zapór, wykorzystując techniki inspirowane zjawiskami. Esat i Hall (1994) wprowadzili model algorytmu genetycznego do analizy eksploatacji zapór. Porównali oni algorytm genetyczny z techniką dyskretnego różniczkowego programowania dynamicznego (DDDP). GA może przezwyciężyć wadę DDDP, która wymaga wykładniczo zwiększonego obciążenia obliczeniowego. Oliveira i Loucks (1997) zaproponowali praktyczne strategie eksploatacji zapór, wykorzystując ulepszone algorytmy genetyczne (chromosom kodu rzeczywistego, elitaryzm i krzyżowanie arytmetyczne). Wardlaw i Sharif (1999) wypróbowali inne ulepszone schematy GA i doszli do wniosku, że najlepszy model GA dla eksploatacji zapory może składać się z kodowania wartości rzeczywistych, selekcji turniejowej, krzyżowania jednorodnego i zmodyfikowanej mutacji jednorodnej. Chen (2003) opracowali model GA kodowany w wartościach rzeczywistych dla długoterminowej eksploatacji zapory, a Kim i inni(2006) zastosowali ulepszone wielokryterialne GA o nazwie NSGA-II do rzeczywistego systemu wielu zapór. Teegavarapu i Simonovic (2002) zastosowali inny algorytm metaheurystyczny, symulowane wyżarzanie (SA), do rozwiązania problemu eksploatacji zapory. Chociaż kilka algorytmów metaheurystycznych zostało już zastosowanych do problemu harmonogramowania zapory, niedawno opracowany algorytm HS nie był wcześniej stosowany do tego problemu. Dlatego niniejszy artykuł omawia pionierskie zastosowanie algorytmu HS do tego problemu.

Model harmonogramowania pracy zapór z wykorzystaniem HS

Model HS ma następującą formułę dla harmonogramowania pracy wielu zapór. Maksymalizacja korzyści uzyskanych z wytwarzania energii wodnej i nawadniania. Z zastrzeżeniem następujących ograniczeń:

1. Zakres przepływu wody: ilość wody odprowadzanej z każdej zapory powinna mieścić się w przedziale od minimalnego do maksymalnego.
2. Zakres retencji wody w zaporze: ilość wody odprowadzanej z każdej zapory powinna mieścić się w przedziale od minimalnego do maksymalnego.
3. Ciągłość przepływu wody: ilość wody odprowadzanej z zapory w kolejnym etapie powinna być sumą ilości wody odprowadzanej z bieżącego etapu, ilości dopływu i ilości wody odprowadzanej.
Algorytm HS rozpoczyna się od wypełnienia losowych wektorów harmonogramowania w pamięci harmonicznej (HM). Struktura HM dla harmonogramowania pracy zapór jest następująca:



Każdy wiersz odpowiada każdemu wektorowi rozwiązania, a każda kolumna odpowiada każdej zmiennej decyzyjnej (ilość uwolnionej wody na każdym etapie i w każdej tamie). Na końcu każdego wiersza znajduje się wartość funkcji celu. HMS (rozmiar pamięci harmonii) to liczba wektorów rozwiązania, a HM to HM. Na podstawie początkowego HM można wygenerować nowy harmonogram za pomocą następującej funkcji:



gdzie R_i^NEW to nowa ilość uwolnionej wody dla zmiennej decyzyjnej i; pierwszy wiersz po prawej stronie oznacza, że nowa ilość jest wybierana losowo z całego zakresu; drugi wiersz oznacza, że nowa ilość jest wybierana z HM; trzeci i czwarty wiersz oznaczają, że nowa ilość jest o określoną jednostkę (Δ) wyższa lub niższa od pierwotnej ilości R_i(k) uzyskanej z HM. Suma prawdopodobieństw jest równa jeden (p₁ + p₂ + p₃ + p₄ = 1). Jeśli nowo wygenerowany wektor, R^NEW, jest lepszy niż najgorsza harmonia w HM pod względem funkcji celu, nowa harmonia jest uwzględniana w HM, a istniejąca najgorsza harmonia jest z niego wykluczana. Jeśli model HS osiągnie MaxImp (maksymalną liczbę ocen funkcji), obliczenia są przerywane. W przeciwnym razie generowana jest kolejna nowa harmonia (= wektor), uwzględniając jeden z trzech wyżej wymienionych mechanizmów.

Zastosowanie HS do problemu referencyjnego

Model HS został zastosowany do popularnego systemu z wieloma zaporami, jak pokazano na rysunku 1 . Problem obejmuje 12 dwugodzinnych okresów działania, a tylko zapora 4 zapewnia korzyści nawadniające, ponieważ odpływy z innych zapór nie są kierowane do gospodarstw rolnych. Zakres zrzutów wody jest następujący:



Zakres zbiorników zaporowych przedstawia się następująco:



Początkowe i końcowe warunki przechowywania są następujące:



Istnieją tylko dwa dopływy: 2 jednostki do zapory 1; 3 jednostki do zapory 2.

I₁ = 2,I₂ =3 (7) Wardlaw i Sharif (1999) rozwiązali ten problem harmonogramowania tamy, wykorzystując ulepszony model algorytmu genetycznego (wielkość populacji = 100; współczynnik krzyżowania = 0,70; współczynnik mutacji = 0,02; liczba pokoleń = 500; liczba ocen funkcji = 35 000; reprezentacje binarne, Graya i wartości rzeczywistych; selekcja turniejowa; krzyżowania jednopunktowe, dwupunktowe i jednorodne; oraz mutacje jednorodne i zmodyfikowane jednorodne). Model algorytmu genetycznego znalazł najlepsze, bliskie optymalnemu, rozwiązanie wynoszące 400,5, co stanowi 99,8% globalnego optimum (401,3). Model HS zastosowano do tego samego problemu z następującymi parametrami algorytmu: HMS = 30; HMCR = 0,95; PAR = 0,05; i MaxImp = 35 000. Model HS mógł znaleźć pięć różnych globalnych optymalnych rozwiązań (HS1 ~ HS5) o identycznym koszcie 401,3. Tabela 1 przedstawia jeden przykład z pięciu optymalnych harmonogramów zrzutu wody. Rysunek 2 przedstawia odpowiadające trajektorie zrzutu wody we wszystkich zaporach. Po dalszych testach modelu HS z różnymi wartościami parametrów algorytmu, w siedmiu z ośmiu przypadków znaleziono lepsze rozwiązanie niż model GA (400,5).

TRENDY NA PRZYSZŁOŚĆ

Sukces tego badania wskazuje, że przyszły model HS powinien uwzględniać bardziej złożone problemy harmonogramowania zapór w różnych sytuacjach rzeczywistych. Ponadto wytyczne dotyczące parametrów algorytmu uzyskane w wyniku licznych eksperymentów z wartościami będą pomocne dla inżynierów w praktyce, ponieważ algorytmy metaheurystyczne, w tym HS i GA, wymagają wielu prób, aby uzyskać najlepsze parametry algorytmu.

WNIOSKI

Algorytm HS, inspirowany muzyką, został z powodzeniem zastosowany do problemu optymalnego harmonogramowania systemu wielozaporowego, przewyższając wyniki GA. Podczas gdy model GA uzyskał rozwiązania bliskie optymalnym, model HS znalazł pięć różnych optimów globalnych przy tej samej liczbie ewaluacji funkcji. Co więcej, model HS nie przeprowadzał analizy wrażliwości parametrów algorytmu, podczas gdy model GA testował wiele wartości parametrów i różne schematy działania. Mogło to skrócić czas i zmniejszyć problemy związane z wyborem wartości parametrów w modelu HS.