Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

przedmioty:algorytmy_ewolucyjne [2008/05/22 15:30] (aktualna)
Linia 1: Linia 1:
 +====== 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
 +
 +
  
Recent changes RSS feed Creative Commons License Donate Minima Template by Wikidesign Driven by DokuWiki