Kierunek: Automatyka i Robotyka
Specjalność: Modelowanie komputerowe układów i procesów (AB3)
Punkty ECTS: 3
Prowadzący: dr hab. inż. Witold Beluch

Opis przedmiotu

Algorytmy genetyczne (AG) i algorytmy ewolucyjne (AE) w pewnym naśladują naturalne procesy ewolucji, których celem jest maksymalne dopasowanie osobników do istniejących warunków życia. Łączą w sobie ewolucyjną zasadę przeżycia najlepiej przystosowanych osobników z systematyczną, choć zawierającą elementy losowości, wymianą informacji.

AG i AE są algorytmami optymalizacji, często traktowanymi jako „algorytmy ostatniej szansy” – stosuje się je zazwyczaj wówczas, gdy tradycyjne metody optymalizacji, zazwyczaj oparte na obliczeniach gradientu funkcji celu, zawodzą. Proces ewolucyjny zachodzący w populacji osobników odpowiada przeszukiwaniu przestrzeni potencjalnych rozwiązań. Poszukiwanie takie wymaga pogodzenia dwóch sprzecznych celów:

• skorzystania z najlepszych dotychczas rozwiązań (jak metody analityczne);
• możliwie szerokiego przeszukania przestrzeni potencjalnych rozwiązań (jak metody enumeracyjne i losowe).

W algorytmach ewolucyjnych i genetycznych korzysta się ze słownictwa zaczerpniętego bezpośrednio z biologii. W procesie ewolucyjnym przetwarzana jest populacja osobników, z których każdy reprezentuje potencjalne rozwiązanie zadania. Początkowa populacja jest tworzona zwykle losowo. Każdy z osobników jest oceniany za pomocą funkcji przystosowania i przypisywana jest mu wartość liczbowa. Przystosowanie osobnika rzutuje na jego prawdopodobieństwo wejścia do populacji pomocniczej w wyniku procesu zwanego selekcją. Wyselekcjonowane (niektóre więcej niż raz, niektóre raz, niektóre wcale) osobniki są następnie poddawane działaniu tzw. operatorów genetycznych/ewolucyjnych, jak krzyżowanie i mutacja. Powoduje powstanie nowych, choć niekoniecznie lepszych rozwiązań. Nowo powstała populacja jest oceniana i proces powtarzany jest aż do spełnienia warunku zatrzymania. Uzyskany w procesie ewolucji najlepszy wynik uważany jest za rozwiązanie zadania optymalizacji.

Do najczęściej stosowanych algorytmów naśladujących procesy zachodzące w naturze należą:

·         programowanie ewolucyjne,

·         algorytmy genetyczne,

·         strategie ewolucyjne,

·         symulowane wyżarzanie,

·         sztuczne sieci neuronowe,

·         algorytmy mrówkowe,

·         algorytmy immunologiczne

·         algorytmy rojowe.

Program przedmiotu

• Wykład: 9 godzin w semestrze
• Laboratorium: 9 godzin w semestrze

Warunki zaliczenia

1. Zaliczenie na ocenę pozytywną ćwiczeń (warunki podaje prowadzący na zajęciach)

2. Egzamin z wykładu.

 OCENA KOŃCOWA: O=0.5E+0.5L

E - ocena z egzaminu (musi być pozytywna)

L - ocena z ćwiczeń

Tematyka wykładów

•  Inteligencja obliczeniowa i sztuczna inteligencja, test Turinga. Optymalizacja i metody optymalizacji. Algorytmy genetyczne (AG) – sposób działania.

• Binarne kodowanie liczb rzeczywistych. Schematy i twierdzenie o schematach. Wpływ operacji genetycznych na schematy. Zbieżność AG.

• Liczebność populacji. Metody uwzględniania ograniczeń. Kodowanie. Algorytmy ewolucyjne (AE).

• Metody reprodukcji i sukcesji. Eksploracja i eksploatacja. Ocena działania algorytmu. Kryteria zatrzymania algorytmu. Funkcje testowe. Operatory krzyżowania i mutacji.

• Optymalizacja wielomodalna. Równoległość w AE. Połączenie AE z metodami lokalnymi. Inne typy AE: Przykłady zastosowań AG i AE.

Literatura

• L. Rutkowski, Metody i techniki sztucznej inteligencji, Wydawnictwa Naukowe PWN, Warszawa, 2006.

• J. Arabas, Wykłady z algorytmów ewolucyjnych, WNT, Warszawa, 2001.

• Z. Michalewicz, Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa, 1996.

Odnośniki:

·         http://wazniak.mimuw.edu.pl/index.php?title=Sztuczna_inteligencja - wykład dotyczący sztucznej inteligencji

·         http://www.tsp.gatech.edu/ - problem komiwojażera

Do pobrania