Podstawy algorytmów ewolucyjnych

Содержание

Слайд 2

Ewolucyjne przeszukiwanie ... oznaczać będzie poszukiwanie rozwiązania problemu – zadania poprzez

Ewolucyjne przeszukiwanie

... oznaczać będzie poszukiwanie rozwiązania problemu – zadania poprzez wprowadzenie

losowego generowania rozwiązań z wykorzystaniem operatorów genetycznych.

W celu porównania skuteczności ewolucyjnego i losowego przeszukiwania należałoby porównać czas poszukiwania satysfakcjonującego rozwiązania obiema metodami.

Aktywne przeszukiwane nazywać będziemy aktywnym, jeżeli w poszukiwaniu rozwiązania będzie wykorzystana wiedza o problemie ułatwiająca podjęcie decyzji o kierunku poszukiwań rozwiązania.

Слайд 3

Metody ewolucyjne ... algorytmy ewolucyjne obejmują następujące metody rozwiązywania problemów: algorytmy

Metody ewolucyjne

... algorytmy ewolucyjne obejmują następujące metody rozwiązywania problemów:
algorytmy ewolucyjne „ciągłe”,
algorytmy

genetyczne,
programowanie genetyczne,
projektowanie ewolucyjne DNA
Слайд 4

Pokrewne metody metod ewolucyjnych ... , w których wprost lub pośrednio

Pokrewne metody metod ewolucyjnych

... , w których wprost lub pośrednio występuje

ewoluująca bądź operacje na populacjach np.:
metoda sztucznej immunologii
PSO – (ang. particle swarm optimization) – optymalizacja roju cząstek
Слайд 5

Ewolucyjne projektowanie

Ewolucyjne projektowanie

Слайд 6

Algorytm ewolucyjny Inicjacja populacji Ocena populacji Selekcja osobników Tworzenie nowej populacji

Algorytm ewolucyjny

Inicjacja
populacji

Ocena
populacji

Selekcja
osobników

Tworzenie
nowej
populacji

Operacje
genetyczne

Rozwią-
zanie

czy spełniony
war. term. ?

Слайд 7

Rozwiązanie problemu z wykorzystaniem algorytmów ewolucyjnych Problem Kodowanie rozwiązania funkcja oceniająca

Rozwiązanie problemu z wykorzystaniem algorytmów ewolucyjnych

Problem

Kodowanie
rozwiązania

funkcja
oceniająca

operatory
genetyczne

wiedza

genetyczne poszukiwanie

ocena
osobników

Rozwiązanie

selekcja

replikacja

operacje
genetyczne

mutacja

Слайд 8

Kodowanie rozwiązania EA – algorytmy ewolucyjne GA – algorytmy genetyczne GP

Kodowanie rozwiązania

EA – algorytmy ewolucyjne
GA – algorytmy genetyczne
GP – programowanie genetyczne
DNA

– algorytmy oparte o mechanizmy biologiczno-chemiczne DNA-RNA
Слайд 9

Kodowanie rozwiązania Genotyp – zakodowany opis rozwiązania, na którym wykonywane są

Kodowanie rozwiązania

Genotyp – zakodowany opis rozwiązania, na którym wykonywane są operację

genetyczne; często ma postać łańcucha cech rozwiązania
Fenotyp –zdekodowany obraz rozwiązania, który przede wszystkim podczas realizacji algorytmu służy do wyznaczania funkcji oceny/ wartości dopasowania
Слайд 10

Przykład kodowania – problem komiwojażera Rozwiązaniem problemu jest łańcuch prezentujący kolejność

Przykład kodowania – problem komiwojażera

Rozwiązaniem problemu jest łańcuch prezentujący kolejność węzłów

(miast) w grafie (odwiedzanych przez komiwojażera).
Najprostsze kodowanie odpowiada ciągowi numerów węzłów w grafie. Takie kodowanie jest jednak źródłem problemów podczas realizacji algorytmów i wymaga stosowania procedur „naprawczych”
Innym sposobem kodowania tego problemu jest na przykład wskazanie numeru aktualnej pozycji węzła w ciągu liczonej od aktualnej pozycji łańcucha, przy czym wskazywanie tego miejsca jest procesem
Слайд 11

Kodowanie ciągu węzłów Procedura opisuje sposób uzyskania konstrukcji na podstawie kodu

Kodowanie ciągu węzłów

Procedura opisuje sposób uzyskania konstrukcji na podstawie kodu genów

– odwrotnie do metody uzyskania kodu.
Kodowanie zapewnia poprawność operacji genetycznych.
Wadą jest zmienna wartościowość pozycji

numer pozycji, z którą dokonano zamiany

wartościowość

Слайд 12

Operatory genetyczne Selekcja Krzyżowanie Mutacja

Operatory genetyczne

Selekcja
Krzyżowanie
Mutacja

Слайд 13

Podstawy operacji selekcji Funkcja oceny / funkcja dostosowania proporcjonalne przypisanie wartości

Podstawy operacji selekcji

Funkcja oceny / funkcja dostosowania
proporcjonalne przypisanie wartości dostosowania
przypisanie wartości

dostosowania na podstawie rankingu
Слайд 14

Selekcja – zasady ogólne Podczas selekcji wyznaczane są osobniki biorące udział

Selekcja – zasady ogólne

Podczas selekcji wyznaczane są osobniki biorące udział w

doborze osobników przed tworzeniem osobników potomnych.
Krok pierwszy – przypisanie wartości przystosowania.
Krok drugi – przypisanie prawdopodobieństwa reprodukcji zależne od jego wartości dostosowania oraz od wartości pozostałych osobników puli selekcyjnej.
Слайд 15

Selekcja Osobniki rodzicielskie są wybierane na podstawie wartości funkcji dostosowania za

Selekcja

Osobniki rodzicielskie są wybierane na podstawie wartości funkcji dostosowania za pomocą

następujących algorytmów:
selekcja koła ruletki,
stochastycznego uniwersalnego próbkowania,
selekcja lokalna,
selekcji odcięcia lub
selekcji turniejowej.
Слайд 16

Selekcja – parametry Presja selekcji – selective pressure: Prawdopodobieństwo najlepszego osobnika

Selekcja – parametry

Presja selekcji – selective pressure:
Prawdopodobieństwo najlepszego osobnika

będącego w selekcji porównane do średniego prawdopodobieństwa selekcji wszystkich osobników.
Skłonność – bias:
Wartość absolutna różnicy pomiędzy znormalizowaną wartością przystosowania osobnika i jego oczekiwanego prawdopodobieństwa reprodukcji.
Rozpostarcie – spread:
Zakres możliwych wartości liczby potomstwa pochodzących od osobników.
Слайд 17

Selekcja – parametry Utrata różnorodności – loss of diversity: Proporcja osobników

Selekcja – parametry

Utrata różnorodności – loss of diversity:
Proporcja osobników populacji,

które nie zostały wyselekcjonowane w fazie selekcji.
Intensywność selekcji – selection intensity:
Oczekiwana średnia wartość dostosowania populacji po zastosowaniu metody selekcji do znormalizowanego rozkładu Gaussa.
Wariancja selekcji – selection variance:
Oczekiwana wariancja rozkładu dostosowania populacji po zastosowaniu metody selekcji do znormalizowanego rozkładu Gaussa.
Слайд 18

Metoda rankingu liniowego Nind – liczba osobników w populacji, Pos –

Metoda rankingu liniowego

Nind – liczba osobników w populacji,
Pos – pozycja

osobnika w rozpatrywanej populacji. (najmniej dostosowany osobnik ma wartość Pos=1, a najlepiej dostosowany osobnik wartość Pos=Nind)
SP – presja selekcji.
Ranking liniowy:
Wartość funkcji dostosowania dla dowolnego osobnika jest wyznaczana wzorem:

Wartość SP (presji selekcji) mieści się w zakresie [1.0, 2.0].

Слайд 19

Ranking nieliniowy Dopuszcza większe wartości presji selekcji, przy funkcji dostosowania określonej

Ranking nieliniowy

Dopuszcza większe wartości presji selekcji, przy funkcji dostosowania określonej wzorem:


X jest pierwiastkiem wielomianu:

lub w innej postaci:

Ranking nieliniowy pozwala kształtować wartości presji selekcji (SP) w zakresie [1.0, Nind - 2.0].

Слайд 20

Funkcja dostosowania liniowego i nieliniowego rankingu

Funkcja dostosowania liniowego i nieliniowego rankingu

Слайд 21

Funkcja dostosowania liniowego i nieliniowego rankingu

Funkcja dostosowania liniowego i nieliniowego rankingu

Слайд 22

Funkcja dostosowania liniowego i nieliniowego rankingu

Funkcja dostosowania liniowego i nieliniowego rankingu

Слайд 23

Właściwości selekcji rankingowej liniowej Intensywność selekcji: Utrata różnorodności: Wariancja selekcji:

Właściwości selekcji rankingowej liniowej

Intensywność selekcji:
Utrata różnorodności:
Wariancja selekcji:

Слайд 24

Właściwości selekcji rankingowej

Właściwości selekcji rankingowej

Слайд 25

Selekcja koła ruletki Próbka 6 wylosowanych liczb: 0.81, 0.32, 0.96, 0.01,

Selekcja koła ruletki

Próbka 6 wylosowanych liczb:
0.81, 0.32, 0.96, 0.01, 0.65,

0.42.

Po selekcji tworzona populacja rodzicielska obejmuje osobników: 1, 2, 3, 5, 6, 9.

Слайд 26

Stochastyczne uniwersalne próbkowanie Dla wyselekcjonowania 6 osobników odległość pomiędzy wskaźnikami wynosi

Stochastyczne uniwersalne próbkowanie

Dla wyselekcjonowania 6 osobników odległość pomiędzy wskaźnikami wynosi 1/6=0.167.


Zatem próbka jednej liczby w zakresie [0, 0.167]:
0.1.

Po selekcji populacja rodzicielska zawiera następujące osobniki:
1, 2, 3, 4, 6, 8.

Слайд 27

Selekcja lokalna

Selekcja lokalna

Слайд 28

Selekcja odcięcia Zależność pomiędzy poziomem odcięcia a intensywnością selekcji Utrata różnorodności:

Selekcja odcięcia

Zależność pomiędzy poziomem odcięcia a intensywnością selekcji

Utrata różnorodności:
LossDivTrunc(Trunc) =

1-Trunc.
Wariancja selekcji:
SelVarTrunc(Trunc) = 1-SelIntTrunc(Trunc)·(SelIntTrunc(Trunc)-fc).
Слайд 29

Selekcja turniejowa W selekcji turniejowej pewna liczba Tour osobników zostaje losowo

Selekcja turniejowa

W selekcji turniejowej pewna liczba Tour osobników zostaje losowo wybrana

z populacji.
Następnie wybierana jest podgrupa najlepszych osobników populacji rodzicielskiej podobnie do turnieju. Proces może być powtarzany do momentu wypełnienia populacji rodzicielskiej.
Parametry: wielkość turnieju Tour. Tour przyjmuje wartość z zakresu 2 - Nind.
Слайд 30

Selekcja turniejowa

Selekcja turniejowa

Слайд 31

Rekombinacja Rekombinacja wartości rzeczywistych: rekombinacja dyskretna, rekombinacja pośrednia, rekombinacja liniowa, poszerzona

Rekombinacja

Rekombinacja wartości rzeczywistych:
rekombinacja dyskretna,
rekombinacja pośrednia,
rekombinacja liniowa,
poszerzona rekombinacja

liniowa.
Rekombinacja binarna/dyskretna (krzyżowanie):
krzyżowanie jednopunktowe,
krzyżowanie wielopunktowe,
krzyżowanie unormowane,
krzyżowanie typu tasowanie,
krzyżowanie ze zredukowanym surogatem.
Слайд 32

Rekombinacja wartości rzeczywistych – rekombinacja dyskretna Rekombinacja dyskretna dokonuje wymiany wartości

Rekombinacja wartości rzeczywistych – rekombinacja dyskretna

Rekombinacja dyskretna dokonuje wymiany wartości zmiennych

pomiędzy osobnikami.
Przykład: dwa osobniki z trzema zmiennymi (3 wymiary):
osobnik 1 12 25 5
osobnik 2 123 4 34
Dla każdej zmiennej wybór wartości jednego z rodziców jest dokonywana w sposób losowy z równym prawdopodobieństwem dla każdego z rodziców.
próbka 1 2 2 1
próbka 2 1 2 1
Po rekombinacji tworzone są nowe osobniki:
potomek 1 123 4 5
potomek 2 12 4 5
Слайд 33

Rekombinacja dyskretna

Rekombinacja dyskretna

Слайд 34

Rekombinacja pośrednia Potomne osobniki są zgodnie z następującą regułą: potomek =

Rekombinacja pośrednia

Potomne osobniki są zgodnie z następującą regułą:
potomek = rodzic

1 + α (rodzic 2 – rodzic 1),
gdzie α jest współczynnikiem skalującym wybieranym w sposób losowy z równym prawdopodobieństwem z zakresu [-d, 1 + d]. Dla rekombinacji pośredniej d = 0, dla rozszerzonej rekombinacji pośredniej d > 0. Dobrą wartością jest d = 0.25. Dla każdej zmiennej współczynnik α jest losowany oddzielnie.
Слайд 35

Rekombinacja pośrednia Przykład: Dwa osobniki, trzy zmienne: osobnik 1 12 25

Rekombinacja pośrednia

Przykład: Dwa osobniki, trzy zmienne:
osobnik 1 12 25 5


osobnik 2 123 4 34
Przykładowy wybór α :
próbka 1 0.5 1.1 -0.1
próbka 2 0.1 0.8 0.5

Nowe osobniki – potomne :
potomek 1 67.5 1.9 2.1
potomek 2 23.1 8.2 19.5

Слайд 36

Rekombinacja liniowa Współczynnik α dla wszystkich zmiennych taki sam Rekombinacja liniowa

Rekombinacja liniowa

Współczynnik α dla wszystkich zmiennych taki sam

Rekombinacja liniowa rozszerzona jest

poszerzeniem podprzestrzeni osobników potomnych wokół linii osobników rodzicielskich.
Слайд 37

Krzyżowanie jednopunktowe Dwa osobniki z 11 wartościami binarnymi: individual 1 0

Krzyżowanie jednopunktowe

Dwa osobniki z 11 wartościami binarnymi:
individual 1 0 1

1 1 0 0 1 1 0 1 0
individual 2 1 0 1 0 1 1 0 0 1 0 1
Wybrany zostaje punkt krzyżowania:
punkt krzyżowania 5
Po krzyżowaniu otrzymamy następujące osobniki potomne:
offspring 1 0 1 1 1 0| 1 0 0 1 0 1
offspring 2 1 0 1 0 1| 0 1 1 0 1 0
Слайд 38

Krzyżowanie wielopunktowe Osobniki z 11 binarnymi zmiennymi: individual 1 0 1

Krzyżowanie wielopunktowe

Osobniki z 11 binarnymi zmiennymi:
individual 1 0 1 1

1 0 0 1 1 0 1 0
individual 2 1 0 1 0 1 1 0 0 1 0 1
Wybieramy 3 punkty krzyżowania:
cross pos. (m=3) 2 6 10
Po krzyżowaniu otrzymujemy osobniki:
offspring 1 0 1| 1 0 1 1| 0 1 1 1| 1
offspring 2 1 0| 1 1 0 0| 0 0 1 0| 0
Слайд 39

Krzyżowanie unormowane Osobniki z 11 binarnymi zmiennymi: individual 1 0 1

Krzyżowanie unormowane

Osobniki z 11 binarnymi zmiennymi:
individual 1 0 1 1 1

0 0 1 1 0 1 0
individual 2 1 0 1 0 1 1 0 0 1 0 1
Dla każdej zmiennej losujemy osobnika rodzicielskiego z którego potomek otrzyma wartość binarną. W rezultacie otrzymujemy dwa słowa binarne o długości 11 dla każdego osobnika potomnego.
sample 1 0 1 1 0 0 0 1 1 0 1 0
sample 2 1 0 0 1 1 1 0 0 1 0 1
Po krzyżowaniu otrzymamy:
offspring 1 1 1 1 0 1 1 1 1 1 1 1
offspring 2 0 0 1 1 0 0 0 0 0 0 0
Слайд 40

Inne metody krzyżowania krzyżowanie typu tasowanie, krzyżowanie ze zredukowanym surogatem.

Inne metody krzyżowania

krzyżowanie typu tasowanie,
krzyżowanie ze zredukowanym surogatem.

Слайд 41

Mutacja Mutacja zmiennej rzeczywistej Zamiana wartości x na inną wygenerowaną losowo

Mutacja

Mutacja zmiennej rzeczywistej

Zamiana wartości x na inną wygenerowaną losowo z zakresu

(x-d, x+d) lub (xmin, xmax)
Слайд 42

Mutacja binarna/dyskretna Zamiana bitu 1 na 0 lub 0 na 1

Mutacja binarna/dyskretna

Zamiana bitu 1 na 0 lub 0 na 1

Слайд 43

Tworzenie nowej populacji strategia globalna strategia lokalna

Tworzenie nowej populacji

strategia globalna
strategia lokalna

Слайд 44

Strategia globalna wytworzenie takiej samej liczby potomków co osobników rodzicielskich i

Strategia globalna

wytworzenie takiej samej liczby potomków co osobników rodzicielskich i zastąpienie

osobników rodzicielskich przez osobniki potomne (uboga strategia).
wytworzenie mniejszej liczby potomków niż osobników rodzicielskich i zastąpienie tych osobników w sposób losowy jednolity (jednolita strategia).
wytworzenie mniejszej liczby potomków niż osobników rodzicielskich i zastąpienie najgorszych osobników osobnikami potomnymi (elitarna strategia).
wytworzenie większej liczby potomków niż potrzeba do zastąpienia osobników rodzicielskich i zastąpienie osobnikami najlepszymi (strategia oparta na dostosowaniu).
- Предыдущая
Особенности преподавания иностранного языка в условиях реализации государственной программы города Москвы
Следующая -
Земельный закон братьев Гракхов

Похожие презентации

Тип Кишечнополостные
Мутации тела Drosophila melanogaster
История физиологии
Первый и второй законы Менделя
Биохимия крови
Развитие эволюционного учения со времен Дарвина до наших дней
Современные представления о возникновении жизни Проверочная работа
Презентация на тему "Класс Птицы Внешнее строение" - скачать презентации по Биологии
Презентация на тему ЖИЗНЕДЕЯТЕЛЬНОСТЬ КЛЕТКИ
Биологические свойства вирусов
Аттестационная работа. Городские люди теряют связь с природой и гармонию с ритмом
Обмен веществ и энергии
Черепномозговые нервы
Цитоплазма и органеллы
Папоротникообразные. Высшие споровые растения
Возникновение жизни или абиогенез
Презентация на тему "Растём, цветём и пахнем" - скачать презентации по Биологии
Презентация на тему Сточные воды.
Презентация на тему Половое размножение растений 6-й класс
Как звери готовятся к зиме
АСЦИДИЯ Прежде асцидий делили на 3 на потряда: простые, или одиночные, асцидии (Monascidiae); сложные, или колониальные, асцидии (Synascididae) и
Генетический контроль оогенеза и имплантации
Многослойные сети. Алгоритмы обучения
Рецепторная функция. Постоянные межклеточные контакты. Цитоскелет
Презентация на тему "Обмен веществ в организме животных" - скачать презентации по Биологии
Игры и игровые ситуации на уроках биологии Подготовила учитель биологии Кирпичева Г. М. МОУ Новоаннинской СОШ № 1 2011 год.
Муравьи. Красный Огненный Муравей
Липиды – гетерогенная группа гидрофобных соединений
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть