====== Obliczenia ewolucyjne ====== Soft computing: * Sieci neuronowe * Systemy rozmyte * **Algorytmy ewolucyjne** * <del>Programowanie ewolucyjne</del> (tego nie omawiano na wykładzie) - ale jest to oparte na ewoluowaniu automatów skończonych. * Strategie ewolucyjne * Algorytmy genetyczne * Programowanie genetyczne Twierdzenie Hollanda (tylko do SGA): Liczba pewnych wzorców (tzw. bloków budujących rośnie w tempie wykładniczym w kolejnych iteracjach algorytmu genetycznego SGA. SGA (simple genetic algorithm) - Początkowa populacja - Selekcja - Rekombinacja (krosowanie) - mutacja - wymiana populacji * kodowanie binarne * dwa operatory 1-punktowe (krzyżowanie i mutacja) Niezależnie od problemu i konkretnej metody, należy zawsze ustalić następujące elementy: - Reprezentacja rozwiązania (binarna, całkowitoliczbowa, grafowa, ...) - Metoda generowania losowego zbioru genotypów - Operatory genetyczne (rekombinacja, mutacja) lub wyspecjalizowane dla danego problemu - Przejście do przestrzeni fenotypów (odwzorowanie genotyp -> fenotyp) - Funkcja oceny jakości rozwiązań Pojęcia: * Injection Island * Premature convergence * Genetic diversity * Selection pressure * crowding * fitness sharing * genetic drift * implicit parallelism * stagnacja * locus * linkage problem * allel * Wybranie reprezenacji * Sposób inicjalizacji * Odwzorowanie genotyp -> fenotyp * Sposób oceny osobników * Zaprojektowanie op. mutacji, rekombinacji * Sposób wyboru osobników rodzicielskich, zastępowania * Kryterium zatrzymywania Selekcja: * Turniejowa * Rankingowa * Ruletka * Strategia elitarna Reprezentacje chromosomów: * Reprezentacja dyskretna (alf. binarny) * Reprezentacja rzeczywista (op. np. średnia aryt.) * Reprezentacja uporządkowana * Reprezentacja drzewiasta Przy naruszaniu ograniczeń: * Kara - stopień penalizacji * Likwidacja (kara śmierci) * lub specyficzne metody (algorytmy naprawcze) Strategie ewolucyjne * lata 60, Niemcy * 1 osobnik * tylko operator mutacji * zaburzanie chromosomu np. białym szumem (np. rozkład Gaussa) Messy Genetic Algorithms: * messy - __niechlujny__, nieporządny * gen to para (locus, wartość) * zmienna długość reprezentacji * rozwiązują linkage problem * Cut-N-Slice Schematy: * rząd schematu o(S) (liczba *) * rozpiętość schematu (odległość między pier. i ost. nie*) * dobre schematy mają: - niski rząd - małą rozpiętość - ponad przeciętne przystosowanie * takie schematy nazywamy **blokami budującymi** Ciąg pokoleń generowanych przez SGA jest odwzorowaniem zwężającym: - istnieje punkt stały takiego odwzorowania - SGA jest zbieżny dla dowolnej populacji początkowej (przy liczbie iteracji dążącej do nieskończoności) metaheurystyka Simulated Annealing (symulowane wychładzanie): * Dodanie elementów stochastycznych DGA - distributed genetic algorithm HFC (Hierarchical Fair Competition): * "równa rywalizacja hierarchiczna"? * ile osobników może migrować * __włączenie wiedzy apriorycznej__ * migration interval, migration rate * calibration gen - stepping stones - random migration - hierarchical parallel * competion & cooperation * DGA/rmr - random migration rate * PEA - parallel evolutionary algorithm * VC - wymiar ukłądu dynamicznego * MGA (Maximum Gap Allowed) * acceptance/admission treshold * DAS (dynamic artiber strategy) - wykrywa stagnacje * Combined MGA-DAS (cMGA-DAS) * podpopulacje mogą się róznić parametrami, strategiami Modele wyspowe: - Stepping stones (docelowa wyspa wcześniej określona) - Random migration - Hierarchical Paralel model HFC - szeroka eksploracja przestrzeni, unikanie nieuczciwej rywalizacji, podobnie jak w naturze balans między szerokością eksploracji a dokładnością poszukiwań powody przedwczesnej zbieżności: * selection pressure * promowanie najlepszych osobników * eliminacja młodych, dobrze rokujących osobników * dyskryminacja "nie fair" dobrego materiału genetycznego Messy Genetic Algorithm: * Genom osobniczy reprezentowany jako zbiór par (locus, wartość) * nadspecyfikacja, podspecyfikacja * Cut-N-Splice * Nie ma mutacji * W algorytmach niechlujnych pierwsza faza jest pracochłonna ale potem wystarczy tylko kilka epok, by znaleźć dobre rozwiązanie * first-come-first-served * Fazy: - Inicjalizacja - Faza filtracji (primordial phase / "faza pierwotna") - Faza rekombinacji (juxtapositional) - Cut-N-Splice * pętla zewnętrzna zwiększa k, będące wielkością bloków budujących ===== Druga część wykładu ===== algorytm zachłanny modele selekcji: * elitarny * wartości oczekiwanej * elitarny model wartości oczekiwanej * ze współczynnikiem zatłoczenia brachistochrona metoda uwzględniania ograniczeń zapobieganie przedwczesnej zbieżności: - zapobieganie kazirodztwu - jednorodne krzyżowanie - wykrywanie jednakowych łańcuchów - machanizm próbkowania - skalowanie f-cji celu możliwe jest krzyżowanie z użyciem maski zadania wielokryterialne * skalaryzacja zadania - maksymalne dopuszczalne wartości składników - Funkcje agregujące * suma ważona * metoda wartości docelowych * metoda punktu idealnego, metoda osiągania celów, * metoda punktu najgorszych oczekiwań ===== strategie ewolucyjne: ===== * domyślnie jeden chromosom * kodowanie rzeczywiste * początkowo była tylko mutacja * zastępowanie chromosomu, jeśli jest lepszy * zaburzanie losową modyfikacją (rozkład gaussa) * malejący zasięg mutacji (większy w początkowej fazie) * np. reguła 1/5 sukcesów (0.82, 1/0.82) * (1-1) -- (P^0, m, s, cd, ci, f, G, t) * twierdzenie o zbieżności * Regularne zadanie optymalizacji * funkcja celu ciągła * dziedzina domknięta * dla dowolnie małego eps istnieje w dziedzinie element, w którym wartość funkcji różni się od optimum o mniej niż eps * strategie ewolucyjne (mi + lamda) * **(mi+1)** -- strategia wieloelementowa * licznośc populacji jest mi * osobniki łączą się w pary (te same p-stwa) * możliwa rekombinacja * usuwa się najsłabszego osobnika * samoadaptacja parametrów sterujących * **(mi+lambda)** * bardziej odporna na minima lokalne * samoczynna adaptacja zasięgu mutacji * chwilowa populacja (mi+lambda)-osobnikowa * osobniki mogą żyć dłużej niż jedno pokolenie * krzyżowanie * dyskretne -- kolejne pary (x,sigma) brane z losowego rodzica * pośrednie -- obliczanie średnich x i sigma, np (x1^2+x2^2)/2 * osobniki reprezentowane przez (x, sigma, theta) * sigma <- sigma * exp(rozklad_norm(delta theta)) * theta <- theta + rozklad_norm(delta theta) programowanie genetyczne * algorytm - wygenerowanie losowej populacji rozwiązań - ocena osobników - wybór operatora genetycznego: mutacja, rekombinacja, repredukcja - wykonywanie w pętli dla wytworzenia nowej pop - wykonywanie tego, aż do warunku stopu * maksymalna głebokość drzewa * selekcja * ruletka * turniej * metoda rankingowa * używane operatory * rekombinacja * losowy wybór węzłów w obydwu drzewach * przeniesienie poddrzew między drzewami * mutacja * pojedyncze węzły (zamiana funkcji + na - itp) * mutacja całych poddrzew (zastępowanie) * zamiana kolejności argumentów * hoist -- uczynienie losowego węzła korzeniem problem komiwojażera * NP-zupełny * znalezienie cyklicznej permutacji liczb 1..n, minimalizującej sumę ... * reprezentacja binarna * reprezentacja ścieżkowa (32417586). operatory: * PMX (partially mapped crossover) * cykliczne krzyżowanie * order crossover * matrix reprezentation sztuka ewolucyjna * obrazy ewolucyjne * muzykologia ewolucyjna ===== Literatura ===== * Algorytmy genetyczne + struktury danych * Goldberg - Algorytmy genetyczne i ich zastosowania

przedmioty/algorytmy_ewolucyjne.txt · ostatnio zmienione: 2008/05/22 15:30 (edycja zewnętrzna)
Recent changes RSS feed Creative Commons License Donate Minima Template by Wikidesign Driven by DokuWiki