Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy metaheurystyczne
Koordynator przedmiotu:
Rajmund Kożuszek
Status przedmiotu:
Fakultatywny dowolnego wyboru
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne - zaawansowane
Kod przedmiotu:
AMHE
Semestr nominalny:
2 / 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 – 48 godz.,w tym: a. obecność na wykładach: 30 godz., b. udział w konsultacjach związanych z treścią wykładu: 3 godz., c. udział w spotkaniach projektowych: 15 godz., 2. praca własna studenta – 59 godz., w tym: a. przygotowanie do wykładów (przejrzenie materiałów z wykładu i dodatkowej literatury): 6 godz., b. realizacja projektu: 10 godz. (zapoznanie się z literaturą i oprogramowaniem) + 30 godz. (wykonanie zadań projektowych) + 5 godz. (sporządzenie dokumentacji) = 45 godz., c. przygotowanie do kolokwiów: 8 godz. Łączny nakład pracy studenta wynosi: 107 godz., co odpowiada 4 pkt. ECTS.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1.79 pkt. ECTS, co odpowiada 48 godz. kontaktowym
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
2.24 pkt. ECTS, co odpowiada 60 godz. realizacji projektu i spotkań projektowych
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
 Umiejętność programowania w przynajmniej jednym z języków: C, C++, Java, Python, R.  Znajomość podstaw statystyki opisowej i testowania istotności statystycznej.  Znajomość podstaw algorytmów ewolucyjnych, symulowanego wyżarzania, metody największego spadku, metody błądzenia przypadkowego.
Limit liczby studentów:
60
Cel przedmiotu:
Celem przedmiotu jest zapoznanie uczestników z zaawansowanymi zagadnieniami dotyczącymi metaheurystycznych metod optymalizacji. Omawiane zagadnienia dotyczyć będą analizy teoretycznej wybranych metod metaheurystycznych oraz badań empirycznych z uwzględnieniem benchmarków.
Treści kształcenia:
Wykład: 1. Wprowadzenie i rekapitulacja podstaw (4 godz.) Definicja przestrzeni przeszukiwań, funkcji celu, ograniczeń funkcyjnych. Rozszerzenie pojęcia funkcji celu na przypadek wielokryterialny oraz na przypadek kryterium porównawczego. Schemat ogólny metaheurystyki: pojęcia stanu, metod selekcji, wariacji i adaptacji stanu. 2. Analiza rozproszenia populacji algorytmu ewolucyjnego (8 godz.) Przypomnienie schematu działania algorytmu ewolucyjnego. Macierz kowariancji populacji jako definicja miary rozproszenia. Model eksploatacji (z populacją nieskończoną), eksploracji (dla funkcji stałej) oraz przekroczenia siodła. Omówienie wpływu wartości parametrów algorytmu ewolucyjnego na rozproszenie populacji. Punkt środkowy populacji jako estymator lokalnego optimum. 3. Analiza rozproszenia mutantów w ewolucji różnicowej oraz zaawansowane schematy tego algorytmu (4 godz.) Przypomnienie algorytmu ewolucji różnicowej. Analiza rozproszenia mutantów w różnych schematach algorytmu (np. DE/rand/1/bin, DE/best/1/bin, DE/rand-to-best). Archiwum punktów i sposób jego wykorzystania. Uzmiennienie współczynnika skalującego. Przegląd zaawansowanych metod ewolucji różnicowej (np. jDE, JADE, DEGL-SAW, SHADE). 4. Algorytm CMA-ES (4 godz.) Przypomnienie schematu alorytmu bazowego CMA-ES. Omówienie reguł strojenia zasięgu mutacji sigma, w tym reguła 1/5 sukcesów, metoda CSA, uproszczone CSA. Dyskusja różnych rozwiązań adaptacji macierzy kowariancji, w tym rozwiązania bazujące na przekształcaniu macierzy sfaktoryzowanej. Algorytm DES jako bezmacierzowy CMA-ES. 5. Uwzględnianie ograniczeń kostkowych i funkcyjnych (4 godz.) Przypomnienie metod uwzględniania ograniczeń. Analiza wpływu na rozproszenie populacji poszczególnych technik uwzględniania ograniczeń. Dyskusja wpływu na efektywność algorytmu interakcji techniki uwzględniania ograniczeń i schematu algorytmu bazowego. 6. Wielokryterialne warianty metod metaheurystycznych (2 godz.) Przypomnienie definicji zadania wielokryterialnego. Warianty wielokryterialne algorytmów ewolucyjnych, ewolucji różnicowej, CMA-ES. 7. Aspekty empirycznej oceny efektywności metod optymalizacyjnych (2 godz.) Przypomnienie popularnych zestawów benchmarkowych i technik oceny na ich podstawie. Wykorzystanie zadań benchmarkowych do analizy obciążeń algorytmów. Technika zastępczej funkcji celu. Projekt: Celem jest samodzielna modyfikacja wybranej metody metaheurystycznej i jej analiza empiryczna. Projekt realizowany w zespołach 2-osobowych będzie swoim zakresem obejmować:  eksperymenty z użyciem dostępnych bibliotek dostarczających implementacji metaheurystyk,  samodzielną implementację lub modyfikację dostępnej implementacji metody metaheurystycznej i badanie jej właściwości,  zadania wymagające doboru odpowiednich metod metaheurystycznych, ich zastosowania oraz analizy jakości uzyskanych wyników.
Metody oceny:
Realizacja przedmiotu obejmuje następujące formy zajęć:  wykład prowadzony w wymiarze 2 godz. tygodniowo,  projekt realizowany samodzielnie w zespołach,  konsultacje. Aktywizacji studentów służą:  interaktywna formuła wykładu,  wymóg konsultacji interpretacji tematu i zakresu projektu,  wymóg przedstawienia do oceny wstępnej dokumentacji projektu,  wymóg konsultacji zmian interpretacji tematu i zakresu projektu wprowadzanych po ocenie dokumentacji wstępnej. Sprawdzanie założonych efektów kształcenia realizowane jest przez:  ocenę wiedzy i umiejętności wykazanych na sprawdzianach pisemnych po upływie połowy semestru i na koniec semestru,  ocenę wiedzy i umiejętności związanych z realizacją zadań projektowych – ocena wykonanych prac implementacyjnych, eksperymentalnych i jakości dokumentacji
Egzamin:
nie
Literatura:
1. Sean Luke, Essentials of Metaheuristics, available online, 2013 2. Jarosław Arabas: Wykłady z algorytmów ewolucyjnych, WNT, 2004 3. Krzysztof Trojanowski: Metaheurystyki praktycznie, WSISIZ, 2008 (wyd. II) 4. El Ghazali Talbi: Metaheuristics. From design to implementation, Wiley, 2009 5. Artykuły z IEEE Transactions of Evolutionary Computation 6. Pakiety języka R. 7. Pakiety języka Python.
Witryna www przedmiotu:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103A-INSZI-MSP-AMHE
Uwagi:
(-)

Efekty uczenia się