To tylko jedna z 27 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 Aspekty praktyczne Inteligencja obliczeniowa 2 In te lig e n c ja o b lic z e n io w a 2 Zastosowania Praktyczne aspekty GA Reprezentacja Funkcja dopasowania ZróŜnicowanie dopasowania Selekcja Operatory Treść wykładu 3 In te lig e n c ja o b lic z e n io w a Ekstrema funkcji numerycznych Tradycyjne zastosowanie GA, szczególnie dla trudnych, nieciągłych, o wielu ekstremach funkcji. Rozpoznawanie obrazów W kryminalistyce - do rozpoznawania twarzy przestępców. GA losowo generuje serię twarzy, spośród których świadek wybiera najbardziej podobne do podejrzanych. Poprzez krzyŜówki i mutacje otrzymujemy pokolenia twarzy coraz bardziej zbliŜone do poszukiwanej. Tutaj rolę funkcji dopasowania spełnia świadek. EA - zastosowania 4 In te lig e n c ja o b lic z e n io w a Optymalizacja kombinatoryczna Zagadnienia te obejmują problemy rozmieszczenia dyskretnych obiektów w czasie i/lub przestrzeni. Najszerzej znanym jest problem komiwojaŜera (TSP). Problem załadunku (BBP) ma duŜe znaczenie praktyczne. Szeregowanie zadań produkcyjnych. Problem transportowy. Kontrola lotów. Planowanie ruchu pacjentów w szpitalu. Sterowanie pracą centrali telefonicznej. Podział godzin w szkole. Zagadnienia te wymagają stosowania niestandardowych reprezentacji i operatorów. EA - zastosowania 5 In te lig e n c ja o b lic z e n io w a Projektowanie Zagadnienia te moŜna traktować jako połączenie optymalizacji kombinatorycznej i funkcyjnej. Znane zastosowania dotyczą: - projektowanie mostów, - optymalizacja dyszy węŜa ppoŜ., - projektowanie struktury sieci neuronowej, - projektowanie sieci elektrycznej, - projektowanie sieci zaopatrzenia w wodę. EA - zastosowania 6 In te lig e n c ja o b lic z e n io w a Projektując zastosowanie GA nie wystarczy posłuŜyć się standardowym schematem. Badania empiryczne dowiodły, Ŝe krytyczne są następujące elementy: - reprezentacja, - postać funkcji dopasowania, - zróŜnicowanie dopasowania, - technika wyboru rodziców, - technika wyboru pokolenia potomków. Praktyczne aspekty EA 7 In te lig e n c ja o b lic z e n io w a Dostosowana do problemu. Powinna kodować jak najwięcej informacji specyficznych dla problemu. MoŜe wymagać specjalizowanych operatorów. Reprezentacja 8 In te lig e n c ja o b lic z e n io w a Dopasowanie osobnika jest obliczone na podstawie
(…)
… dopasowanie jest wysokie, a róŜnica
między najlepszym i najgorszym osobnikiem - niewielka. W
konsekwencji brak impulsu do skierowania EA ku maksimum.
Wyjściem jest rozszerzenie efektywnego zróŜnicowania wartości
funkcji dopasowania przez jej skalowanie.
Inteligencja obliczeniowa
Dominacja dobrych (ale nie optymalnych) kilku chromosomów
powoduje utknięcie w lokalnym ekstremum. Gdyby populacja…
… dopasowania zmniejsza przedwczesną zbieŜność,
ale w przypadku, gdy mamy do czynienia tylko z jednym
wybitnym osobnikiem, skalowanie zbyt spłaszcza zmodyfikowaną
funkcję dopasowania, co pogarsza efektywność algorytmu.
Inteligencja obliczeniowa
Skalowanie dopasowania
12
Techniki wyboru rodziców
Inteligencja obliczeniowa
Skalowanie dopasowania
13
Techniki wyboru rodziców
Inteligencja obliczeniowa
Ranking dopasowania
Osobniki są sortowane wg czystych wartości funkcji, po
czym reprodukcyjne dopasowania są przyporządkowywane
zgodnie z tym rankingiem. MoŜna to robić liniowo bądź
ekspotencjalnie. Badania wykazują, Ŝe ta technika jest
lepsza od skalowania, aczkolwiek zbyt róŜnicuje osobniki
bliskie pod względem dopasowania.
14
Selekcja na zasadzie turnieju
W najprostszej wersji para osobników jest losowana…
… wyboru potomstwa
16
Techniki krzyŜowania
Wielopunktowe krzyŜówki słuŜą intensywniejszemu przeszukiwaniu
przestrzeni rozwiązań. Szczególnie dobrze działa krzyŜówka
dwupunktowa.
Punkty krzyŜowania
Rodzice
1011100100
1001011101
Potomstwo
1011011100
1001100101
Inteligencja obliczeniowa
Punkty krzyŜowania
17
Techniki krzyŜowania
KrzyŜówka ujednolicająca (ang. uniform crossover) tworzy
potomków…
… - PMX
21
Techniki krzyŜowania - OX
KrzyŜówka OX (Order Crossover). Zaproponował ją Davis;
buduje potomstwo przez wybór podciągu z uszeregowania i
zachowanie względnej kolejności zadań z innego rodzica.
Np. dwoje rodziców:
R1 = ( 1 2 3 | 4 5 6 7 | 8 9 )
R2 = ( 4 5 2 | 1 8 7 6 | 9 3 )
kopiowane do potomków:
P1 = ( x x x | 4 5 6 7 | x x )
P2 = ( x x x | 1 8 7 6 | x x )
Inteligencja obliczeniowa…
... zobacz całą notatkę
Komentarze użytkowników (0)