- Nazwa przedmiotu:
- Przeszukiwanie i optymalizacja
- Koordynator przedmiotu:
- Rajmund Kożuszek
- Status przedmiotu:
- Fakultatywny ograniczonego wyboru
- Poziom kształcenia:
- Studia I stopnia
- Program:
- Informatyka
- Grupa przedmiotów:
- Sztuczna inteligencja
- Kod przedmiotu:
- POP
- Semestr nominalny:
- 5 / rok ak. 2021/2022
- Liczba punktów ECTS:
- 4
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 1. liczba godzin kontaktowych – 35 godz., w tym
obecność na wykładach: 30 godz.,
udział w spotkaniach i konsultacjach przygotowujących do kolokwiów oraz związanych z realizacją przedmiotu: 1 godz.
konsultacje z prowadzącym projekt – dyskusja zadania projektowego oraz odbiór etapów projektu: 4 godz.
2. praca własna studenta – 65 godz., w tym
realizacja zadań projektowych: 55 godz. (obejmuje także zapoznanie się z niezbędną literaturą oraz oprogramowaniem)
przygotowanie do kolokwiów: 10 godz.
Łączny nakład pracy studenta wynosi 100 godz., co odpowiada 4 pkt. ECTS.
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 1,25 pkt. ECTS, co odpowiada 35 godz. kontaktowym
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- 2 pkt. ECTS, co odpowiada 55 godz. realizacji projektu
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład30h
- Ćwiczenia0h
- Laboratorium0h
- Projekt15h
- Lekcje komputerowe0h
- Wymagania wstępne:
- Podstawy Informatyki i Programowania, Probabilistyka, Wprowadzenie do Sztucznej Inteligencji
- Limit liczby studentów:
- 60
- Cel przedmiotu:
- Celem przedmiotu jest zapoznanie studentów z elementami teorii oraz podstawowymi algorytmami przeszukiwania i optymalizacji.
Student zdobędzie umiejętność formułowania i rozwiązywania problemów jako zadania przeszukiwania bądź optymalizacji. Student potrafił będzie dobrać odpowiednią metodę do postawionego zadania.
- Treści kształcenia:
- WYKŁADY:
1. Wprowadzenie (2 godz.)
Informacje o przedmiocie. Regulamin przedmiotu, literatura uzupełniająca. Podstawowe pojęcia: zadanie przeszukiwania, ciągłe i dyskretne i przestrzenie przeszukiwań, zagadnienie sformułowania funkcji celu, heurystyka, metaheurystyka, optymalizacja lokalna vs. globalna
2. Przeszukiwanie (2 godz.)
Typowe zadania kombinatoryczne. Przeszukiwanie wyczerpujące vs. metody heurystyczne (powtórzenie i uzupełnienie).
3. Optymalizacja z ograniczeniami (2 godz.)
Geneza ograniczeń, sposoby ich uwzględniania poprzez przeformułowanie zadania optymalizacji lub modyfikacje metody przeszukiwania.
4. Algorytmy optymalizacji z jednym punktem roboczym (4h)
Metoda największego spadku/wzrostu, metody uwzględniające gradient funkcji celu, metody pseudonewtonowskie, błądzenie przypadkowe, symulowane wyżarzanie
5. Modyfikacje jednopunktowych metod optymalizacji (2h)
Tabu, sąsiedztwo o zmiennym promieniu
6. Podstawowe wielopunktowe algorytmy optymalizacji (4h)
Simplex Neldera-Meada, algorytm ewolucyjny (powtórzenie i uzupełnienie), optymalizacja rojem cząstek, ewolucja różnicowa, strategie ewolucyjne (powtórzenie i uzupełnienie).
7. Algorytmy optymalizacji bazujące na adaptacji rozkładu prawdopodobieństwa (2h)
EDA, CMA-ES
8. Ocena stochastycznych algorytmów optymalizacji (2 h)
Specyfika metod stochastycznych, zadania benchmarkowe.
9. Elementy składowe algorytmu ewolucyjnego (2 h)
Metody selekcji, sukcesji, mutacji, krzyżowania. Ich wpływ na zdolności eksploatacji i eksploracji algorytmu. Zachowanie algorytmu na kilku przykładowych funkcjach celu
Algorytmy bezparametrowe.
10. Hybrydyzacja metod optymalizacji (2h)
Połączenie kilku metod optymalizacji, w tym metody lokalnej i globalnej.
11. Optymalizacja wielokryterialna (2h)
Metody optymalizacji wielokryterialnej, skalaryzacja
12. Źródła trudności zadań optymalizacyjnych (2h).
Cechy funkcji celu lub ograniczeń powodujące to, że zadanie optymalizacji jest trudne, np.: złe uwarunkowanie, klątwa wymiarowości, zwodniczość, zadania typu igła w stogu siana.
Projekt:
Celem projektu jest zdobycie doświadczeń praktycznych w zakresie implementowania i stosowania omawianych algorytmów.
Zakres projektu
1. Eksperymenty z użyciem dostępnych bibliotek dostarczających implementacji algorytmów optymalizacji.
2. Samodzielna implementacja lub modyfikacja dostępnej implementacji algorytmu przeszukiwania bądź optymalizacji i badanie jego właściwości.
3. Analiza porównawcza metod optymalizacji bazująca na zestawach zadań testowych oraz analizie statystycznej wyników porównywanych metod.
- Metody oceny:
- Realizacja przedmiotu obejmuje następujące formy zajęć:
- wykład prowadzony w wymiarze 2 godz. tygodniowo. Podczas wykładu wprowadzane będą elementy personalizacji. Istotna będzie interakcja z prowadzącym, co pozwoli na uzyskanie sprzężenia zwrotnego w czasie rzeczywistym, co z kolei pozwoli na dostosowanie tematyki i tempa wykładu do rzeczywistych potrzeb.
- Projekt w wymiarze 1 godz. tygodniowo; w ramach realizacji projektu studenci dobiorą się w zespoły dwuosobowe i będą zobowiązani do wspólnego rozwiązania zadania. Zastosowana będzie tu metoda nauczania opartego na badaniach (ang. research-based teaching). Studenci będą brali udział w pracach badawczych, przez co w większym stopniu dotkną problemu niejednoznaczności zadań optymalizacji. Pozwoli im to łatwiej zrozumieć, że nie zawsze istnieją proste odpowiedzi i rozwiązania problemów. W części projektów zostanie również wdrożona idea, gamifikacji, tj. wyniki optymalizacji uzyskane przez każdą z grup będą ze sobą konkurować. Przez osiągnięciem wyznaczonego terminu, każdy zespół będzie mógł wielokrotnie poprawiać uzyskane przez siebie wyniki.
Sprawdzanie założonych efektów kształcenia realizowane jest przez:
• ocenę wiedzy i umiejętności związanych z realizacją zadania projektowego;
• ocenę wiedzy wykazanej na dwóch kolokwiach pisemnych.
- Egzamin:
- nie
- Literatura:
- • J. Arabas: Wykłady z algorytmów ewolucyjnych. WNT, 2004
• Krzysztof Trojanowski: Metaheurystyki praktycznie, WSISIZ, 2008 (wyd. II)
• P. Wawrzyński: Podstawy sztucznej inteligencji, OWPW, 2014
- Witryna www przedmiotu:
- https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103A-INSZI-ISP-POP
- Uwagi:
- (-)
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Charakterystyka W01
- ma szczegółową wiedzę obejmującą algorytmy heurystyczne i optymalizacyjne
Weryfikacja: kolokwium, ocena projektu
Powiązane charakterystyki kierunkowe:
W06
Powiązane charakterystyki obszarowe:
P6U_W, I.P6S_WG.o
Profil ogólnoakademicki - umiejętności
- Charakterystyka U01
- potrafi, przy identyfikowaniu problemów i formułowaniu specyfikacji zadań inżynierskich oraz problemów badawczych, w tym zadań i problemów złożonych i nietypowych, związanych z systemami informatycznymi oraz ich rozwiązywaniu:
a) wykorzystywać posiadaną wiedzę z zakresu nauk podstawowych oraz nauk technicznych,
b) pozyskiwać uzupełniające tę wiedzę informacje z literatury, baz danych i innych źródeł; dokonywać ich selekcji, interpretacji i krytycznej oceny, integrować uzyskane informacje, a także wyciągać wnioski oraz formułować i uzasadniać opinie
Weryfikacja: projekt
Powiązane charakterystyki kierunkowe:
U01
Powiązane charakterystyki obszarowe:
P6U_U, I.P6S_UW.o, III.P6S_UW.o
- Charakterystyka U02
- potrafi planować i przeprowadzać eksperymenty (symulacje komputerowe), analizować i interpretować uzyskane wyniki oraz wyciągać wnioski
Weryfikacja: projekt
Powiązane charakterystyki kierunkowe:
U03
Powiązane charakterystyki obszarowe:
P6U_U, I.P6S_UW.o, III.P6S_UW.o
- Charakterystyka U03
- potrafi pracować indywidualnie i w zespole, potrafi dotrzymywać terminów
Weryfikacja: projekt
Powiązane charakterystyki kierunkowe:
U08
Powiązane charakterystyki obszarowe:
P6U_U, I.P6S_UO
- Charakterystyka U04
- potrafi opracować dokumentację dotyczącą realizacji zadania inżynierskiego, przygotować tekst zawierający m.in. omówienie uzyskanych wyników oraz rzetelnie przedstawić zalety i wady proponowanego rozwiązania
Weryfikacja: projekt
Powiązane charakterystyki kierunkowe:
U09
Powiązane charakterystyki obszarowe:
P6U_U, I.P6S_UK
Profil ogólnoakademicki - kompetencje społeczne
- Charakterystyka K01
- rozumie znaczenie wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz potrzebę zasięgania opinii ekspertów w przypadku trudności w samodzielnym rozwiązywaniu problemu; ma świadomość ważności zachowania w sposób profesjonalny
Weryfikacja: projekt
Powiązane charakterystyki kierunkowe:
K03
Powiązane charakterystyki obszarowe:
P6U_K, I.P6S_KK, I.P6S_KR