To tylko jedna z 31 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Wydzia Wydzi ł Zarz Zar ądzania AGH dzania AG Katedra Informatyki Stosowanej Algorytmy ewolucyjne Inteligencja obliczeniowa 2 In te lig e n c ja o b lic z e n io w a 2 Wprowadzenie Zasada działania Podział EA Cechy EA Algorytm genetyczny Treść wykładu 3 In te lig e n c ja o b lic z e n io w a Algorytmy ewolucyjne (ang. Evolutionary Algorithms - EA) są szeroko stosowaną techniką (często o charakterze heurystycznym) przeszukiwania i optymalizacji opartą na zasadach przejętych z teorii ewolucji. Naturalność oraz prostota działania sprawiły, Ŝe algorytmy te są chętnie wykorzystywane w naukach zarządzania do rozwiązywania problemów optymalizacji kombinatorycznej, a w szczególności - do szeroko rozumianych problemów alokacji zasobów. Algorytmy ewolucyjne nie gwarantują znalezienia optimum globalnego, jednak generalnie zapewniają znalezienie rozwiązania wystarczająco dobrego w akceptowalnym przedziale czasu. Stąd głównym zastosowaniem tych algorytmów powinny być problemy, dla których nie istnieją techniki specjalizowane. Nawet jeśli techniki takie istnieją, moŜna osiągnąć poprawę ich działania poprzez ich połączenie z algorytmami ewolucyjnymi. EA - wprowadzenie 4 In te lig e n c ja o b lic z e n io w a Drogą rozwoju przyrody oŜywionej jest ewolucja czyli metoda prób i błędów oparta na doborze naturalnym. Najlepiej udokumentowanym mechanizmem doboru naturalnego jest proces genetyczny: moŜna go postrzegać jako proces optymalizacyjny, w którym osobniki najlepiej dostosowane do środowiska mają największe szanse przeŜycia i utworzenia potomków. Nośnikiem informacji o cechach indywidualnych osobnika są geny - bloki DNA - tworzące chromosomy: kod ten determinuje budowę osobnika i jego rozwój, a w szczególności - jego dopasowanie do środowiska naturalnego. Istnieje silna zaleŜność między chromosomem osobnika a jego Ŝywotnością i zdolnością do przekazywania genotypu kolejnym pokoleniom. Zasada działania 5 In te lig e n c ja o b lic z e n io w a Ewolucyjny rozwój populacji chromosomów odbywa się poprzez mechanizm reprodukcji, na który składają się procesy krzyŜowania (ang. crossover), mutacji (ang. mutation) i inwersji (ang. inversion). W procesie krzyŜowania, z dwóch chromosomów rodzicielskich wybierane są geny, które po zespoleniu tworzą jeden lub więcej chromosomów potomnych. W procesie mutacji dochodzi do przekłamania kodu poprzez zmianę jednego genu lub ich ciągu, natomiast inwersja odwraca fragment
(…)
… jest maksymalizacja wartości
funkcji dwóch zmiennych F(x,y), reprezentacją kaŜdej
zmiennej moŜe być 10-bitowa liczba binarna. Tak więc
chromosom będzie się składał z 2 genów i liczył 20 cyfr
binarnych.
Inteligencja obliczeniowa
Reprezentacja
18
Algorytm genetyczny - podstawy
Reprezentacja liczby rzeczywistej
d – dokładność obliczeń,
min, max – dolna, górna granica przedziału,
m – długość chromosomu (ile bitów),
xb – wartość dziesiętna liczby binarnej.
Znajdujemy najmniejszą liczbę całkowitą m taką, Ŝe:
Wartość rzeczywista liczby x z przedziału [min, max]:
x = min + xb*(max – min)/(2m – 1)
Udowodnić!
Inteligencja obliczeniowa
(max – min)*10d <= 2m – 1
19
Algorytm genetyczny - podstawy
Reprezentacja binarna
Podstawowym problemem przy takiej reprezentacji jest
bardzo moŜliwa duŜa odległość między reprezentacją…
… Graya:
21
Algorytm genetyczny - podstawy
Inteligencja obliczeniowa
Reprezentacja binarna – kod Gray’a
22
Algorytm genetyczny - podstawy
Inne reprezentacje
Dla prostych problemów kolejnościowych naturalną
reprezentacją jest lista uporządkowana:
13247568
Podstawowy problem - nie działają klasyczne operatory.
Inteligencja obliczeniowa
Czy ciąg liczb rzeczywistych moŜe być reprezentacją dla
takich…
... zobacz całą notatkę
Komentarze użytkowników (0)