SZAU 173-186, SZAU
[ Pobierz całość w formacie PDF ]
//-->1735. Algorytmy ewolucyjne5.1. Pojęcia podstawoweW trakcie projektowania bardzo często korzysta się z optymalizacji. Na przykład, problemwyznaczenia parametrów modeli, w tym równie modeli neuronowych, sprowadza się wistocie do minimalizacji funkcji błędu. Chocia dobór struktury modeli odbywa się zwykle wpraktyce na drodze empirycznej (wyznacza się kilka, kilkanaście lub nawet kilkadziesiątmodeli o ró nej strukturze i wejściach, a potem wybiera się najlepszy), to zadanie doborupostaci modelu mo na równie sformułować jako problem optymalizacji. Kolejnymproblemem, w rozwiązaniu którego mo na zastosować optymalizację, jest wyznaczenieparametrów algorytmu regulacji, na przykład typu PID, w taki sposób, aby wybrany wskaźnikjakości był mo liwie mały. Do rozwiązania wymienionych zadań zazwyczaj wykorzystuje sięoptymalizację gradientową: przede wszystkim algorytmy zmiennej metryki, Levenberga-Marquardta i gradientów sprzę onych, znacznie rzadziej algorytm najszybszego spadku. Gdymuszą być spełnione ograniczenia nale y zastosować odpowiednio zmodyfikowane wersjetych algorytmów, a mianowicie podejścia z tzw. funkcją kary.Głównym problemem związanym z optymalizacją jest nieliniowość, wielomodalność,często równie niewypukłość funkcji celu. Zjawiska te są znane wszystkim uczącym siecineuronowe: aby otrzymać dobry model nale y uczyć model wielokrotnie, rozpoczynającobliczenia z ró nych punktów początkowych. Wszystkie wymienione algorytmyoptymalizacji do wyznaczenia nowego punktu wykorzystują gradient minimalizowanejfunkcji, czasami równie drugie pochodne. Naturalnie, algorytmy tego typu kończą działaniepo znalezieniu minimum lokalnego. Wartość funkcji celu w znalezionym punkcie, którą jestna przykład błąd modelu neuronowego, mo e być zbyt du a.Uwzględniając wady gradientowych algorytmów optymalizacji, oczywiste jest, e dorozwiązania wielu praktycznych problemów wskazane by było zastosowanie algorytmów,które miałyby mo liwość wyznaczania minimum globalnego. Jak dotąd nie opracowanouniwersalnego, zawsze skutecznego algorytmu, ale wraz ze wzrostem mo liwościobliczeniowych komputerów pojawiło się wiele nowych metod, które pozwalają skutecznierozwiązać problemy praktyczne. Co ciekawe, algorytmy te, w przeciwieństwie do metodgradientowych, nie są tak sformalizowane matematycznie, lecz wykorzystują ró ne koncepcjeheurystyczne. Wśród wielu podejść najbardziej popularne (i skuteczne) są algorytmyewolucyjne [3, 33]. Inspiracją do opracowania algorytmów ewolucyjnych była chęćnaśladowania natury. Wszystkie organizmy ywe mają pewne cechy (geny), które określająich przystosowanie dośrodowiska,w którym yją. Geny rodziców krzy ują się, kolejnepokolenia dziedziczą cechy rodziców. Dzieci nie są oczywiście wierną kopią rodziców,niektóre geny zostają zmutowane. Osobniki, które są dobrze przystosowane dośrodowiska,łatwo przekazują swoje geny kolejnym pokoleniom, natomiast osobniki gorzej lubźleprzystosowane mają du o mniejsze szanse na potomstwo.Okazuje się, e przedstawiony w poprzednim akapicie schemat dziedziczenia mo e byćwykorzystany do optymalizacji.Środowisko,w którym yją osobniki, to rozwiązywanyproblem. Ka dy z yjących w tymśrodowiskuosobników (ściśle jego geny) reprezentujepotencjalne rozwiązanie problemu optymalizacji. Stopień dopasowania osobników określaoptymalizowana funkcja celu. W pamięci komputera symuluje się setki, tysiące, a nawetmiliony pokoleń, ka de z pokoleń mo e liczyć kilkadziesiąt lub kilkaset osobników. Zgodniez zasadami panującymi wświecieorganizmów ywych, w kolejnych pokoleniach„prze ywają” i posiadają potomstwo osobniki dobrze przystosowane dośrodowiska,a więcte, dla których optymalizacji ulega funkcja celu.174Algorytmy ewolucyjne są w istocie wyspecjalizowanymi procedurami przeszukiwaniaprzestrzeni rozwiązań. W przeciwieństwie do prostej, ale bardzo zło onej obliczeniowometody przeszukiwania siatki mo liwych rozwiązań zadania optymalizacji i wybraniunajlepszego wyniku, wykorzystują mechanizmy doboru naturalnego i dziedziczenia. Cechy,wyró niające algorytmy ewolucyjne w stosunku do klasycznych gradientowych algorytmówoptymalizacji numerycznej są następujące:3. Algorytmy ewolucyjne przetwarzają pewien zbiór potencjalnych rozwiązań, a niepojedynczy punkt.4. W algorytmach ewolucyjnych do przetwarzania zbioru potencjalnych rozwiązańwykorzystuje się metody probabilistyczne, a nie deterministyczne.5. Algorytmy ewolucyjne korzystają jedynie z wartości optymalizowanej funkcji celu,informacja o gradiencie i drugich pochodnych nie jest potrzebna.Przed omówieniem najpopularniejszych algorytmów ewolucyjnych warto wprowadzićspecyficzne dla nich określenia.Populacjato zbiór pewnej liczby osobników.Osobnikitozakodowane w postaci chromosomów zbiory parametrów zadania (wyznaczane rozwiązaniaproblemu optymalizacji).Chromosomysą uporządkowanymi ciągami genów.Gen(nazywanyrównie cechą, znakiem lub detektorem) stanowi pojedynczy element genotypu, wszczególności chromosomu.Genotyp(inaczej struktura) to zespół chromosomów danegoosobnika. Osobnikami populacji mogą być genotypy lub pojedyncze chromosomy (gdygenotyp składa się z jednego chromosomu).Fenotypto zestaw wartości odpowiadającychdanemu genotypowi, czyli fenotyp jest zbiorem parametrów zadania.Allelto wartość danegogenu, inaczej wartość cechy lub wariant cechy.Locusto pozycja wskazująca poło eniedanego genu w łańcuchu genów (chromosomie).Funkcja przystosowania(inaczej funkcjadopasowania) stanowi miarę przystosowania (dopasowania) danego osobnika dośrodowiska.Na podstawie wartości tej funkcji przeprowadza się selekcję osobników.W klasycznych algorytmach optymalizacji funkcja celuJulega zwykle minimalizacji,natomiast w algorytmach ewolucyjnych funkcja przystosowaniaFjest maksymalizowana.Mo na zastosować podstawienieF= −JlubF=11+J(5.1)5.2. Przegląd algorytmów ewolucyjnych5.2.1. Klasyczny algorytm genetycznySiećdziałańklasycznego algorytmu genetycznego przedstawiono na rys. 5.1. W trakcieinicjalizacji utworzona zostaje w sposób losowy populacja początkowa. Osobniki sąreprezentowane przez ciągi binarne o określonej długości. Ocena przystosowaniachromosomów w populacji polega na obliczaniu wartości funkcji przystosowania dla ka degochromosomu. Poniewa algorytm maksymalizuje funkcjęprzystosowania, im większa jest jejwartość, tym jakośćdanego chromosomu jest większa. Warunek zatrzymania algorytmuzale y od konkretnego zastosowania. Poniewa optymalna wartośćfunkcji przystosowanianie jest zwykle znana, algorytm mo na zatrzymaćpo osiągnięciu pewnej wartości progowej,akceptowalnej. W praktyce algorytm musi zakończyćpracę, je eli obliczenia nie przynosząpoprawy funkcji przystosowania, algorytm musi równie przerwaćpracępo wykonaniupewnej maksymalnej liczby iteracji (pokoleń). Je eli warunek stopu jest spełniony, najlepszychromosom, dla którego wartośćfunkcji przystosowania jest największa, zostaje uznany zarozwiązanie.175Inicjalizacja: wybór początkowejpopulacji chromosomówOcena przystosowaniachromosomów w populacjiNIEZatrzymaniealgorytmuTAKSelekcja chromosomówWyprowadzenienajlepszego chromosomuZastosowanie operatorówgenetycznychStopUtworzenie nowejpopulacjiRys. 5.1. Siećdziałańklasycznego algorytmu genetycznegoPodczas selekcji chromosomów, na podstawie wartości funkcji przystosowania, wybranezostająte chromosomy, które będąbrały udział w tworzeniu nowego pokolenia. Opracowanowiele ró nych metod selekcji, najczęściej wykorzystuje siętzw. metodęruletki. W metodzietej ka demu chromosomowi mo na przyporządkowaćwycinek koła ruletki proporcjonalny dowartości jego funkcji przystosowania. Selekcja chromosomu następuje w wyniku obrotu kołaruletki: zostaje wybrany chromosom naleący do wybranego wycinka koła (im większawartośćfunkcji przystosowania, tym większy wycinek koła, a tym samymprawdopodobieństwo wylosowania danego chromosomu). Alternatywnąmetodąselekcji jestmetoda rankingowa, w której chromosomy sąszeregowane kolejno od najlepiejprzystosowanego do najgorzej przystosowanego. Największąszansęna reprodukcjęmająosobniki z początku kolejki. Jeszcze innym podejściem jest selekcja turniejowa, w którejosobniki z danej populacji dzieli sięna podgrupy, a następnie w ka dej z nich wybiera sięosobnik najlepiej przystosowany. Najczęściej przyjmuje sięmałe grupy, 2 lub 3 osobniki.Po selekcji chromosomów zostajązastosowane operatory genetyczne, a mianowiciekrzy owanie i mutacja. Z populacji rodzicielskiej losowo wybiera siępary chromosomów dokrzy owania. Dla ka dej pary rodziców losuje siępozycjęgenu, która określa punktkrzy owania. Na przykład, niech schemat krzy owania będzie następujący (symbolem „|”oznaczono losowo wyznaczone miejsce krzy owania)para rodzicówpara potomków[100 | 1110101]⇒[100 | 0101100][111 | 0101100][111 | 1110101](5.2)176Prawdopodobieństwo krzy owania jest zwykle du e (0,5 lub więcej), natomiastprawdopodobieństwo mutacji jest zazwyczaj małe (mniejsze ni 0,1). Mutacja polega nanegacji pojedynczego bitu chromosomu. Mo e byćona dokonana na populacji rodziców(jeszcze przed krzy owaniem) lub te na następnej populacji.Chromosomy otrzymane w wyniku przeprowadzenia operacji genetycznych tworząnowąpopulację, o liczności równej liczności poprzedniej populacji. W kolejnej iteracji algorytmugenetycznego populacja ta staje siępopulacjąbieącą, tzn. z niej wybiera sięchromosomy ina niej przeprowadza sięoperacje genetyczne.W ogólności istnieje kilka metod uwzględnienia ograniczeńw algorytmach ewolucyjnych[3]. Najprostsze ograniczenia (kostkowe) mogąbyćbardzo łatwo uwzględnione. Ułatwiająone znacznie zdefiniowanie zbioru zainteresowania, w którym generowana będzie populacjapoczątkowa.Metody uwzględniania ograniczeńmo na podzielićna kilka kategorii:6. Metody modyfikujące zadanie:a) zmiana funkcji celu,b) transformacja zmiennych niezale nych,7. Metody modyfikujące algorytmMo na wyró nićdwa sposoby modyfikacji zadania: zmianęfunkcji celu oraztransformacjęzmiennych niezale nych. W pierwszym przypadku w minimalizowanej funkcjicelu uwzględnia sięczłon kary zastępujący ograniczenia. Uproszczenie ograniczeńnierównościowych polega najczęściej na sprowadzeniu ich do postaci kostkowej.Jako przykłady metod modyfikujących algorytm mo na podaćmetody „profilaktyki” oraz„naprawy”. „Profilaktyka” polega na niedopuszczeniu do wygenerowania osobnika pozaobszarem dopuszczalnym. Poza tym, stosuje sięspecjalne operatory genetyczne, którezapewniają, e rodzice i dzieci naleądo obszaru dopuszczalnego. Jest to szczególnie łatwe wprzypadku liniowych ograniczeńrównościowych. „Naprawa” polega na tym, e punkt leącypoza obszarem dopuszczalnym poddaje sięspecjalnemu algorytmowi, którego zadaniem jestsprowadzenie go do takiego obszaru, który spełnia ograniczenia.5.2.2. Strategie ewolucyjneStrategie ewolucyjne, analogicznie jak algorytmy genetyczne, przetwarzającałe populacjeosobników, reprezentujących potencjalne rozwiązania zadania optymalizacji, wykorzystującdo tego celu zasady ewolucji. Istniejąjednak między nimi zasadnicze ró nice:8. W algorytmie genetycznym stosuje siękodowanie binarne, natomiast w strategiachewolucyjnych kodowanie zmiennoprzecinkowe.9. W algorytmach genetycznych osobniki do reprodukcji sąlosowane, największe szansemająosobniki najlepsze (mogąbyćwybrane wielokrotnie), ale osobnikiźleprzystosowane równie mogąbyćwybrane. W strategiach ewolucyjnych osobnikiwybierane sąbez powtórzeń, selekcja jest deterministyczna.10. W strategiach ewolucyjnych najpierw następuje rekombinacja, a później selekcja.Podczas selekcji tworzy siępopulacjętymczasową, o liczności ró nej ni licznośćpopulacji rodziców. Populacja tymczasowa podlega selekcji, która redukuje jej rozmiardo rozmiaru populacji rodziców. W klasycznych algorytmach genetycznych najpierwodbywa sięselekcja osobników, dopiero później dla wybranych osobników stosuje sięoperatory genetyczne. W strategiach ewolucyjnych prawdopodobieństwo mutacji ikrzy owania jest zmienne w kolejnych pokoleniach.Istnieje kilka typów strategii ewolucyjnych. Historycznie pierwsza została opracowana177strategia (1+1). Siećdziałańtej strategii została przedstawiona na rys. 5.2. Jej cechącharakterystycznąjest to, e przetwarzany jest jeden chromosom bazowyx. Algorytmrozpoczyna sięod losowej inicjalizacji tego chromosomu. W ka dej generacji, w wynikumutacji, powstaje nowy osobniky. Do ka dego z genów chromosomux(xi) dodaje siępewnąliczbęlosową, wygenerowanązgodnie z rozkładem normalnym, otrzymuje sięposzczególnegeny (yi) chromosomuyyi=xi+σNi(0,1)(5.3)przy czymσjest parametrem określającym zasięg mutacji. Wybierany jest osobnik (xluby),dla którego funkcja przystosowaniaFma większąwartość. Wybrany osobnik jestchromosomem bazowym dla kolejnej iteracji. W strategii (1+1) nie występuje krzy owanie.Inicjalizacja chromosomux(1)Ocena chromosomux(1)t:=1NIEZatrzymaniealgorytmuTAKy(t):=x(t)+σN(0,1)Wyprowadzenierozwiązaniax(t)Ocena chromosomuy(t)StopNIEF(y(t))>F(x(t))TAKx(t+1):=x(t)x(t+1):=y(t)t:=1Rys. 5.2. Siećdziałaństrategii ewolucyjnej (1+1)Adaptacja parametrów w strategii ewolucyjnej (1+1) odbywa sięw wyniku zmiany zasięgumutacji (σ). Stosuje siętzw. regułę1/5 sukcesów, w której relacja między udanymi awszystkimi mutacjami wynosi 1/5. Gdy w trakcie pewnej liczby kolejnych generacji (np. 5)stosunek udanych mutacji do wszystkich mutacji przewy sza wartość1/5, wówczas parametrσzostaje zwiększony, w przeciwnym przypadku parametrσzostaje zmniejszony.
[ Pobierz całość w formacie PDF ]