Transcript
Algorytmy ewolucyjne `
Wstęp Czym są algorytmy ewolucyjne? Rodzaje algorytmów ewolucyjnych Algorytmy genetyczne Strategie ewolucyjne Programowanie genetyczne
Zarys historyczny Alan Turing, 1950 Nils Aall Barricelli, Pierwsza komputerowa symulacja ewolucji, 1954 Bienert, Rechenberg, Schwefel, 1960, Strategie ewolucyjne i zastosowanie w praktyce J. Holland, Książka popularyzująca algorytmy ewolucyjne,1960 r. Fogel, lata 80-te, Współczesna wersja programowania ewolucyjnego Od początku lat 90-tych algorytmy genetyczne są coraz częściej stosowane w praktyce
Podstawowe pojęcia Osobnik Populacja Fenotyp Genotyp Chromosom Kodowanie rozwiązań Funkcja przystosowania
- Rozwiązanie zadania - Zbiór rozwiązań branych pod uwagę - Parametry, cechy rozwiązania - Ciąg bitów - Miejsce przechowywania rozwiązania - Sposób kodowanie (np. ciąg bitów) - Fitess, funkcja celu. Wskaźnik poprawności, stosowalności
Algorytm genetyczny - przebieg Genotypy osobników z populacji ulegają modyfikacji podczas rozmnażania. Zmiany te wynikają z: Mutacji Mieszania
Oceniamy przystosowanie nowopowstałych osobników Czym lepiej przystosowany jest osobnik, tym większe ma prawdopodobieństwo na wzięcie udziało w tworzeniu następnego pokolenia. Osobniki z najmniejszym przystosowaniem giną
Algorytm genetyczny - przykład Problem: Znaleźć maksimum funkcji rzeczywistej f(x) na pewnym zboiorze X.
Algorytm genetyczny - przykład 1. Wstęp – kodowanie problemu 1. 2.
Wszystkie potencjalne rozwiązania to np. binarne przedstawienie liczby long f(x) – w tym przypadku może być wskaźnikiem przystosowania rozwiązania
2. Ustalamy wielkość populacji N, a następnie losujemy N genotypów (osobników) 3. Ustalamy ile procent bitów („genów”) w populacji ulega mutacji w jednym pokoleniu (najczęściej od 0.1% do 0.5%). Ustalamy też prawdopodobieństwo skrzyżowania dwóch osobników (najczęściej od 20% do 80%) 4. Sprawdzamy „dostosowanie” naszych osobników przy użyciu funkcji celu. Oceniamy fenotyp, czyli zinterpretowany (dla danego problemu) kod genetyczny
Algorytm genetyczny - przykład 5. Selekcja osobników na podstawie wskaźnika przystosowania. Z obecniej populacji N osobników losujemy N osobników nowej populacji stosując tzw. Roulette Selection, gdzie prawdopodobieństwo wylosowania każdego z osobników: 6. Nowa populacja staje się populacją bierzącą i wracamy do punktu 3.
Algorytm genetyczny – podsumowanie Zalety
Algorytm jest uniwersalny Nie musimy wiedzieć co optymalizujemy (metoda czarno skrzynkowa) Wystarczy nawet selekcja turniejowa Algorytm niedeterministyczny, więc możemy próbować optymalizować wielokrotnie Stosunkowo duża szybkość działania
Algorytm genetyczny – podsumowanie Wady
Uniwersalność – mniejsza skuteczność niż alg. Specjalistyczne Wolniejsza od metod zachłannych Małe prawdopodobieństwo znalezienia rozwiązania optymalnego Wszystko zależy od dobranej funkcji fitness
Algorytm genetyczny – przykłady Evolved antenna
Algorytm genetyczny – przykłady Evolved Virtual Creatures, Karl Sims, 1994 Starfish Self Modeling Robot
Strategie ewolucyjne Zmienna długość kodu genetycznego (liczby zmiennoprzecinkowe) Opiera się na mutacji, a nie na rekombinacji Autoadaptacja – możliwość zmiany parametrów w czasie W prostych strategiach: tzw. Reguła 1/5 sukcesów Rechenberga Możliwe kodowanie parametrów w osobniku
Strategie ewolucyjne – problem Maksymilizacja funkjci f: Rn -> R na zadanym przedziale [a1, b1] x … x [an, bn]
Strategie ewolucyjne – Algorytm ES(1 + 1) Populacja: 1 Kolejne populacje wybierane są ze zbioru rodziców (rodzica) i zbioru dzieci (dziecka) Mechanizm adaptacji: Reguła 1/5 sukcesów Rechenberga
Strategie ewolucyjne – Algorytm ES(1 + 1) EVOLUTION-STRATEGY(F, σ0, θ1, θ2) 1. σ ← σ0; 2. x ← RANDOM-INDIVIDUAL(); 3. INDIVIDUAL-EVALUATION(x, F); 4. while not TERMINATION-CONDITION(σ) 5. do 6. y ← MUTATION(x, σ); 7. INDIVIDUAL-EVALUATION(y, F); 8. if F(x) < F(y) 9. then 10. x ← y; 11. SIGMA-UPDATING(σ, θ1, θ2);
Strategie ewolucyjne – Algorytm ES(1 + 1) Mutacja Osobnik x = (x1, x2, …, xd) ∈ Rd Z osobnika x tworzymy nowego osobnika y = (y1, y2, …, yd) ∈ Rd yi = xi + εi dla i = 1, 2, …, d gdzie εi jest liczbą rzeczywistą wygenerowaną losowo z rozkładen normalnym 𝑁(0, 𝜎 2 ) o średniej 0 i wariacji σ2. Parametr σ określa zasięg mutacji. Jest on modyfikowany podczas działania algorytmu (Sigma-Updating, Reguła 1/5 sukcesów Rechenberga)
Strategie ewolucyjne – Algorytm ES(1 + 1) Sigma-Updating Aktualizuje σ przy użyciu reguły 1/5 sukcesów Rechenberga z parametrami θ1 i θ2. Parametry te można dowolnie dobrać, ale doświadczenie pokazało, że 1 najlepsze uzyskuje się dla 𝜃1 = ≈ 1.22 i 𝜃2 = 0.82 0.82
Strategie ewolucyjne – Algorytm ES(1 + 1) Reguła 1/5 sukcesów Rechenberga Jeżeli prez k iteracji liczba mutacji zakończonych sukcesem była większa niż 1/5 ogólnej liczby wykonanych mutacji, to zasięg mutacji jest zwiększany 𝜎 ← 𝜃1 𝜎 dla pewnego 𝜃1 > 1 Jeżeli przez ostatnie k iteracji liczba mitacji zakończonych sukscesem była mniejsza niż 1/5 ogólnej liczby wykonanych mutacji, to zasięg mutacji jest zmienszany 𝜎 ← 𝜃2 𝜎 dla pewnego 𝜃2 < 1 W przeciwnym wypadku, zasięg mutacji nie zmienia się
Strategie ewolucyjne – Algorytm ES(1 + 1) Wrażliwość na minima lokalne funkcji Użyta metoda autoadaptacji może prowadzić do przedwczesnej zbieżności Rozszerzenie ES(μ + 1)
Strategie ewolucyjne – Algorytm ES(1 + 1) Przykład zastosowania Optymlizacja dyszy dwufazowej (Hans-Paul Schwefel)
Wydajność ok. 55%
Wydajność ok. 80%
Strategie ewolucyjne – Algorytmy ES(μ + λ) i ES(μ, λ) ES(μ + λ) Populacja μ osobników generuje λ potomków Kolejne pokolenie (populację) wybieramy z sumy zbiorów rodziców i dzieci, czyli z μ + λ osobników
ES(μ, λ) Populacja μ osobników generuje λ potomków Kolejne pokolenie (populację) wybieramy ze zbioru potomków, czyli z λ osobników
Mechaniz autoadaptacji oparty o kodowanie parametrów ewolucyjnych w pojedynczym osobniku Zazwyczaj μ = 20 i λ = 7μ
Strategie ewolucyjne – Algorytmy ES(μ + λ) i ES(μ, λ) Obserwacja W początkowej fazie działania algorytmu pożyteczne są „duże” mutacje „Małe mutacje” są korzystniejsze w końcowej fazie algorytmu Możliwy jest przypadek, gdzie kożystna „wielkość” mutacji będzie się zmieniać naprzemiennie: duża, mała, duża, mała itd.
Strategie ewolucyjne – Algorytmy ES(μ + λ) i ES(μ, λ) Wnioski Algorytm musi sam dostosowywać (optymalizować) „wielkość” mutacji potrzebnej w danym momencie na podstawie obserwacji (np. przy użyciu reguły 1/5 sukcesów) Każdy osobnik powinien przechowywać własną „wielkość” mutacji
Strategie ewolucyjne – Algorytmy ES(μ + λ) i ES(μ, λ) Osobnik w populacji ma postać: 𝒚 = [𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 , 𝝈] gdzie 𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 ∈ ℝ𝒏
Strategie ewolucyjne – Algorytmy ES(μ + λ) i ES(μ, λ) • Mutacja osobnika y tworzy nowego osobnika 𝑦′ 𝑦 = 𝑥1 , 𝑥2 , … , 𝑥𝑛 , 𝜎
𝑦 ′ = 𝑥 ′1 , 𝑥 ′ 2 , … , 𝑥 ′ 𝑛 , 𝜎 ′
• Obliczenie następnej „wielkości” (kroku) mutacji 𝜎′ 𝜎 ′ = 𝜎 ∗ 𝑒𝑥𝑝 𝜏0 ∗ 𝑁 0, 1 𝑖𝑓 𝜎 ′ == 𝜀0 𝜎 ′ = 𝜀0 • Następnie dla każdego 𝑥𝑖 : 𝑥′𝑖 = 𝑥𝑖 + 𝑁𝑖 (0, 𝜎′) Parametr 𝜏0 to parametr „szybkości uczenia”
1 𝑛 (Schwefal, 1995) 𝜏0 ~
Strategie ewolucyjne – Algorytmy ES(μ + λ) i ES(μ, λ) Każdy gen ma swój własny krok „wielkość” mutacji 𝑦 = 𝑥1 , 𝑥2 , … , 𝑥𝑛 , 𝜎1 , 𝜎2 , … , 𝜎𝑛 𝑦 ′ = 𝑥 ′1 , 𝑥 ′ 2 , … , 𝑥 ′ 𝑛 , 𝜎 ′1 , 𝜎 ′ 2 , … , 𝜎′𝑛
Uaktualnienie kroku mutacji 𝜎′𝑖 = 𝜎𝑖 ∗ 𝑒𝑥𝑝 𝜏0 ∗ 𝑁 0, 1 + 𝜏1 ∗ 𝑁𝑖 0,1
Proponowane paramerty: 𝜏0 ~
1
2𝑛
𝜏1 ~
Dla każdego 𝑥𝑖 : 𝑥′𝑖 = 𝑥𝑖 + 𝑁𝑖 (0, 𝜎′𝑖 )
1
2 𝑛
Strategie ewolucyjne – Algorytmy ES(μ + λ) i ES(μ, λ) Problemy: • W alkorytmie ES(μ + λ) może dojść do utworzenia „niezastępowalnego” osobnika • ES(μ, λ) dla funkcji wielomodalnych daje zazwyczaj lepsze wyniki
Strategie ewolucyjne – Algorytmy ES(μ/ρ + λ) i ES(μ/ρ, λ) Rekombinacja – tworzenie „dzieci” 1. Wybieramy 𝜌 osobników z 𝜇 rodziców 2. Tworzymy potomka poprzez rekombinacje chromosomów wybranych 𝜌 rodziców 3. Poddajemu mutacji nowopowstałe dziecko i dodajemy je do populacji dzieci Takich potomków tworzymy 𝜆. Algorytmy z rekombinacją to: ES(μ/ρ + λ) i ES(μ/ρ, λ)
Strategie ewolucyjne – Algorytmy ES(μ/ρ + λ) i ES(μ/ρ, λ) Przy rekombinacji wartości genów nowego osobnika obliczamy: 𝑟𝑗
𝑥′𝑗 = 𝑥𝑗
gdzie 𝑟𝑗 jest wylosowanym numerem rodzica „Wielkość” mutacji obliczamy w sposób: 1 𝜎′𝑗 = 𝜌
𝜌
𝜎𝑗𝑖 𝑖=1
Programowanie genetyczne - Wstęp Programowanie genetyczne to zautomatyzowana metoda mająca na celu tworzenie programów komputerowych w oparciu o ogólną definicję problemu. (Wikipedia)
Programowanie genetyczne - Wstęp Po raz pierwszy przedstawone w pracy Nichaela L. Cramera w 1985 r. Spopularyzowane przez Johna Kozę w 1992 r. (Genetic Programming: On the Programming of Computers by Means of Natural Selection)
Programowanie genetyczne - Wstęp Tzw. Drzewa składowe (parse tree) reprezentują program Wymaga potężnych zasobów obliczeniowych Rozmiar populacji to często miliony osobników Populacja programów
Tworzenie potomków (nowe programy)
Ewolucja (testowanie i selekcja)
Programowanie genetyczne – Parse tree Reprezentacja wyrażenia logicznego 𝑥
𝑦⇒ 𝑥
𝑧
( 𝑧 ⟺ (𝑤
𝑣)
Programowanie genetyczne – Parse tree Reprezentacja kodu 1. 2. 3. 4. 5.
i = 1; while ( i < 20 ) { i = i + 1 }
;
= i
while 1
< i
= 20
i
+ i
1
