Sztuczna Inteligencja - wyklady streszczenie, Sztuczna Inteligencja cz.2


Algorytmy ewolucyjne

Wprowadzenie

Algorytmy ewolucyjne - są to algorytmy, które opierają swoje działanie na genetyce (przekazywanie korzystnych cech potomstwu poprzez krzyżowanie i mutacje).

Są one wykorzystywane do rozwiązywania zagadnień optymalizacyjnych (czyli poszukiwania tych rozwiązań, które dziedziczą cechy po swoich rodzicach i „przeżywają”, ponieważ są najlepiej przystosowane).

Klasyczne metody optymalizacji

Klasyczne metody poszukiwania optymalnych rozwiązań dzielimy na : metody analityczne, przeglądowe, oraz losowe.

Metody analityczne - poszukiwane są lokalne ekstrema funkcji rozwiązując układy równań (zwykle

nieliniowych). Metody te mają swoje wady - są złożone i nie zawsze dadzą się zastosować.

Metody przeglądowe - polegają na obliczaniu wartości funkcji jakiegoś celu w całej przestrzeni po kolei.

Dla dużych przestrzeni jest to nieefektywne i niemożliwe.

Metody losowe - losowo przeszukują przestrzeń rozwiązań i zapamiętują wyniki, z których potem wybierane jest najlepsze. Metody te są również mało efektywne.

Idea algorytmów ewolucyjnych

Algorytmy te są oparte na zasadzie doboru naturalnego i dziedziczenia, gdzie wykorzystuje się ewolucyjną zasadę przeżycia osobników najlepiej przystosowanych.

Główne cechy algorytmów ewolucyjnych :

Podstawowe pojęcia (słowniczek) :

Funkcja przystosowania (także funkcja dostosowania, oceny) - pozwala ocenić stopień dopasowania osobnika populacji i wybrać wszystkie te najlepiej przystosowane (o największej wartości funkcji dopasowania) zgodnie z zasadą „przetrwa najsilniejszy”. (Odpowiednio w teorii sterowania - funkcja błędu a w teorii gier - funkcja kosztu).

W każdej iteracji algorytmu ewolucyjnego ocenia się przystosowanie osobnika za pomocą funkcji przystosowania i na tej podstawie tworzy się nową populację, jako zbiór potencjalnych rozwiązań.

Klasyczny algorytm genetyczny

0x08 graphic
Inicjacja - polega na losowym wyborze żądanej liczby chromosomów (osobników) reprezentowanych przez ciągi binarne o określonej długości.

Ocena przystosowania - polega na obliczeniu wartości funkcji przystosowania dla każdego chromosomu z populacji.

Sprawdzenie warunków zatrzymania - zależą one od zadania. Najczęściej jest to:

Selekcja chromosomów - odbywa się na podstawie wartości funkcji przystosowania, tych chromosomów, które będą tworzyć następne pokolenia. Najbardziej popularna metoda to metoda ruletki.

W wyniku tego procesu zostaje utworzona populacja rodzicielska o liczebności podobnej do bieżącej populacji.

Operatory genetyczne

Zastosowanie operatorów genetycznych do chromosomów (w procesie selekcji) prowadzi do utworzenia

nowej populacji potomków. Stosuje się dwa podstawowe operatory genetyczne: operator krzyżowania i

operator mutacji.

W klasycznym algorytmie genetycznym krzyżowanie występuje prawie zawsze (prawdopodobieństwo <0,5-1> a mutacje bardzo rzadko (prawdopodobieństwo na poziomie 0,1).

Operację mutacji stosujemy na populacji rodziców przed operacją krzyżowania, oraz na populacji potomków, już po krzyżowaniu.

Przykładowe operacje krzyżowania i mutacji

Przykład krzyżówki:

Chromosomy ch1 i ch2 mają po 10 genów. Stanowią one parę rodzicielską. W celu przeprowadzenia krzyżowania losujemy liczbę z przedziału [1,9]. Wylosowano nr.5.

0x01 graphic

Przykład mutacji:

Losujemy liczbę rzeczywistą z przedziału [0,1] dla każdego z dziesięciu genów. Wylosowano :

0.23 0.76 0.54 0.10 0.28 0.68 0.01 0.30 0.95 0.12

Przyjmijmy, że prawdopodobieństwo pm = 0,2. Do mutacji zostaną dopuszczone tylko te geny, gdzie

liczba jest pm<= 0,1 - tylko gen nr. 7 (czerwony).

0x01 graphic

Przykład wykorzystania algorytmu genetycznego

Zadanie :

Znaleźć maksimum funkcji y = 2*x +1 w przedziale liczb całkowitych [0,31]. Zbiorem potencjalnych rozwiązań (czyli przestrzenią poszukiwań) jest zbiór {0,1,2,…,32}. Każdy z elementów zbioru jest fenotypem. Fenotypy zakodujemy jako chromosom 5-bitowy (bo wartości 32 odpowiada [11111]).

0x08 graphic

  1. Losowanie populacji początkowej :

Ustalono początkową populacja na N=8

  1. Ocena funkcji dostosowania :

wartości funkcji dostosowania obliczono

wg. wagi wzoru F(chi)=2* chi+1

  1. Selekcja chromosomów :

Selekcji dokonano metodą koła ruletki.

(diagram poniżej).

0x08 graphic

Pola wycinków koła ruletki obliczono wg wzoru

0x01 graphic

Selekcja chromosomów - za pomocą koła ruletki odbywa się przez losowym zakręceniem koła ruletki

(tutaj ośmiu) liczb z przedziału [0,100]. Suma wszystkich wartości ( chi) jest równa 100%.

Wylosowano liczby : 79 44 9 74 45 86 48 23, które odpowiadają chromosomom :

ch6 ch4 ch2 ch6 ch5 ch6 ch5 ch3

Piąty wylosowany chromosom to ch5 ponieważ jako piątą wylosowano liczbę 45 , która jest większa od sumy granicznej 44,34.



Wyszukiwarka

Podobne podstrony:
Sztuczna Inteligencja - wyklady streszczenie, AL - najwazniejsze informacje
inteligencja cz 2
pytania dla inteligentnych cz 3
pytania dla inteligentnych cz 2
inteligencja cz 2(1)
Oszustwo katastrofy smolenskiej sztuczna mgla cz V
wykłady NA TRD (7) 2013 F cz`
Streszczenie ksia¬ki cz I
DYDAKTYKA- wykłady streszczenie do egzaminu, PEDAGOGIKA II ROK, dydaktyka
Wykład 10-Równania nieliniowe cz.1
Wykład 10, procesy poznawcze cz. II
01 Wykłady Pisma Świętego C. T. Russella (cz. 1-4), Wykłady Pisma Świętego C. T. Russella (cz. 1-4)
KINEZYTERAPIA- wykład 3, fizjoterapia materiały WSZYSTKO cz.2
Wykłady w streszczeniu, UWM Weterynaria, Biologia komórki
Streszczenia romantyzm, pozytywizm cz 1 Zwierz możliwe zagadnienia 2
wykład 5, Fizjologia układu kążenia cz III
Wykład 12, procesy poznawcze cz. II
Streszczenia romantyzm, pozytywizm cz 1 Zemsta

więcej podobnych podstron