Obliczenia ewolucyjne

Soft computing:

  • Sieci neuronowe
  • Systemy rozmyte
  • Algorytmy ewolucyjne
    • Programowanie ewolucyjne (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)

  1. Początkowa populacja
  2. Selekcja
  3. Rekombinacja (krosowanie)
  4. mutacja
  5. 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:

  1. Reprezentacja rozwiązania (binarna, całkowitoliczbowa, grafowa, …)
  2. Metoda generowania losowego zbioru genotypów
  3. Operatory genetyczne (rekombinacja, mutacja) lub wyspecjalizowane dla danego problemu
  4. Przejście do przestrzeni fenotypów (odwzorowanie genotyp → fenotyp)
  5. 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ą:
    1. niski rząd
    2. małą rozpiętość
    3. ponad przeciętne przystosowanie
    • takie schematy nazywamy blokami budującymi

Ciąg pokoleń generowanych przez SGA jest odwzorowaniem zwężającym:

  1. istnieje punkt stały takiego odwzorowania
  2. 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
  1. stepping stones
  2. random migration
  3. 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:

  1. Stepping stones (docelowa wyspa wcześniej określona)
  2. Random migration
  3. 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:
    1. Inicjalizacja
    2. Faza filtracji (primordial phase / „faza pierwotna”)
    3. 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:

  1. zapobieganie kazirodztwu
  2. jednorodne krzyżowanie
  3. wykrywanie jednakowych łańcuchów
  4. machanizm próbkowania
  5. skalowanie f-cji celu

możliwe jest krzyżowanie z użyciem maski

zadania wielokryterialne

  • skalaryzacja zadania
  1. maksymalne dopuszczalne wartości składników
  2. 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
    1. wygenerowanie losowej populacji rozwiązań
    2. ocena osobników
    3. wybór operatora genetycznego: mutacja, rekombinacja, repredukcja
    4. wykonywanie w pętli dla wytworzenia nowej pop
    5. 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