Algorytmy ewolucyjne

Nasza ocena:

3
Pobrań: 49
Wyświetleń: 756
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Algorytmy ewolucyjne - strona 1 Algorytmy ewolucyjne - strona 2 Algorytmy ewolucyjne - strona 3

Fragment notatki:

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)

Zaloguj się, aby dodać komentarz