Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Wstęp do algorytmów ewolucyjnych
Koordynator przedmiotu:
Dr hab. inż. Jarosław Arabas, prof. PW
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka i Systemy Informacyjne
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-INMSI-MSP-0125
Semestr nominalny:
1 / rok ak. 2022/2023
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. godziny kontaktowe – 50 h; w tym a) obecność na wykładzie – 30 h b) obecność na zajęciach projektowych – 15 h c) konsultacje – 3 h d) obecność na egzaminie – 2 h 2. praca własna studenta – 50 h; w tym a) dodatkowe godziny przeznaczone na realizację projektu – 15 h b) przygotowanie prezentacji projektu – 15 h c) przygotowanie do egzaminu, zapoznanie się z literaturą – 20 h Razem 100 h, co odpowiada 4 pkt. ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1. obecność na wykładzie – 30 h 2. obecność na zajęciach projektowych – 15 h 3. konsultacje – 3 h 4. obecność na egzaminie – 2 h Razem 50 h, co odpowiada 2 pkt. ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
1. obecność na zajęciach projektowych – 15 h 2. dodatkowe godziny przeznaczone na realizację projektu – 15 h Razem 30 h, co odpowiada 1 pkt. ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
Podstawowe informacje z zakresu rachunku prawdopodobieństwa i analizy matematycznej
Limit liczby studentów:
Bez limitu
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z metodami ewolucyjnymi i ich wykorzystaniem w optymalizacji globalnej. W ramach przedmiotu studenci poznają: - podstawowe odmiany algorytmów ewolucyjnych, - elementy analizy teoretycznej algorytmów ewolucyjnych, - wybrane metaheurystyki, - techniki benchmarkowania stochastycznych metod optymalizacji.
Treści kształcenia:
Wykład Zadanie optymalizacji kombinatorycznej i w Rn .Metoda optymalizacji jako sposób uszeregowania punktów z przestrzeni przeszukiwań. Ograniczenia funkcyjne i zbiór dopuszczalny. Przegląd metod optymalizacji w Rn jako ilustracja zasady uszeregowania punktów z przestrzeni. Wzmiankowane metody to sympleks Neldera-Meada oraz metody dwufazowe, np. największego spadku i zmiennej metryki. Metoda symulowanego wyżarzania. Zadanie optymalizacji globalnej jako zadanie opuszczania obszaru przyciągania minimum lokalnego (przekraczania siodeł). Sprzeczność między zbieżnością do minimum lokalnego a zdolnością odnajdowania minimum globalnego. Algorytm ewolucyjny: metody selekcji, operacje genetyczne dla optymalizacji w Rn i {0,1}n. Techniki uwzględniania ograniczeń – zewnętrzna funkcja kary, specjalizowane kodowanie, naprawa rozwiązań niedopuszczalnych. Technika poprawy zbieżności – hybrydyzacja z metodami optymalizacji lokalnej, darwinowski a lamarkowski schemat ewolucji. Metody analizy algorytmu ewolucyjnego – twierdzenie o schematach, analiza bazująca na dynamice rozkładu próbkowania populacji nieskończonej, analiza wykorzystująca model Markowa (wg Vose'a), inne podejścia. Dostosowywanie algorytmu ewolucyjnego do niestandardowych przestrzeni przeszukiwań – specjalizowane reprezentacje i operacje genetyczne. Jak projektować operacje genetyczne aby algorytm ewolucyjny działał prawidłowo. Optymalizacja metodą immunologiczną – podobieństwa i różnice z algorytmem ewolucyjnym. Optymalizacja metodą trajektorii cząstki. Optymalizacja rojem cząstek. Podobieństwo z wielostartową metodą największego spadku. Optymalizacja globalna algorytmem bazującym na grupowaniu (wg Toerna). Usprawnianie metod optymalizacji globalnej poprzez modyfikacje zbioru rozwiązań dopuszczalnych (metoda tabu) lub wprowadzanie funkcji kary skoncentrowanych w minimach lokalnych. Projekt Testowanie wybranego algorytmu optymalizacji na zadaniach testowych. Algorytm wymaga zakodowania w języku programowania (np. C/C++ i pochodne lub R). W ramach projektu przygotowane jest jedno lub kilka zadań praktycznych, wymagających nietypowego użycia.
Metody oceny:
Do zdobycia jest w sumie 100 punktów, w tym 50 punktów w ramach projektu oraz 50 punktów z egzaminu. Warunkiem z koniecznym zaliczenia jest zdobycie w sumie co najmniej 10 punktów z egzaminu i co najmniej 10 punktów z projektu. Egzamin polega na samodzielnym rozwiązaniu zadań. Pod warunkiem spełnienia kryteriów opisanych wcześniej, ocena ustalana jest wg następującego przelicznika: - 91-100 – bardzo dobra (5,0) - 81-90 – ponad dobra (4,5) - 71-80 – dobra (4,0) - 61-70 – dość dobra (3,5) - 51-60 – dostateczna (3,0) - 0-50 – niedostateczna (2,0)
Egzamin:
tak
Literatura:
1. J. Arabas, Wykłady z algorytmów ewolucyjnych, WNT, 2001. 2. Z. Michalewicz, D. Fogel, Jak to rozwiązać czyli nowoczesna heurystyka, WNT, 2005. 3. A. Stachurski, A. Wierzbicki, Podstawy optymalizacji, PW, 2001.
Witryna www przedmiotu:
brak
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W01
Zna zaawansowane metody uczenia maszynowego, metody ewolucyjne oraz metody inteligencji obliczeniowej
Weryfikacja: ocena z egzaminu oraz wykonania i prezentacji projektu
Powiązane charakterystyki kierunkowe: I2SI_W02
Powiązane charakterystyki obszarowe:
Charakterystyka W02
Zna techniki przeprowadzania i oceny eksperymentów badających skuteczność algorytmów ewolucyjnych.
Weryfikacja: ocena wykonania, prezentacji i dyskusji projektu
Powiązane charakterystyki kierunkowe: I2SI_W01
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka U01
Posiada umiejętność gromadzenia, selekcji i krytycznej interpretacji informacji technicznej oraz zdolność formułowania poglądów, idei, problemów i ich rozwiązań oraz zdolność ich wyrażania i prezentowania specjalistom i niespecjalistom
Weryfikacja: ocena z egzaminu oraz wykonania i prezentacji projektu
Powiązane charakterystyki kierunkowe: I2_U01
Powiązane charakterystyki obszarowe:
Charakterystyka U02
Potrafi zaplanować, przygotować i przeprowadzić eksperyment badawczy
Weryfikacja: ocena wykonania, prezentacji i dyskusji projektu
Powiązane charakterystyki kierunkowe: I2_U07
Powiązane charakterystyki obszarowe:
Charakterystyka U03
Potrafi projektować systemy informatyczne oparte o algorytmy genetyczne i metody ewolucyjne
Weryfikacja: ocena wykonania, prezentacji i dyskusji projektu
Powiązane charakterystyki kierunkowe: I2SI_U02, I2SI_U07
Powiązane charakterystyki obszarowe:
Charakterystyka U04
Potrafi stosować metaheurystyczne metody optymalizacyjne
Weryfikacja: ocena wykonania, prezentacji i dyskusji projektu
Powiązane charakterystyki kierunkowe: I2SI_U03
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka K01
Ma świadomość potrzeby samokształcenia w ramach procesu kształcenia ustawicznego.
Weryfikacja: ocena wykonania, prezentacji i dyskusji projektu
Powiązane charakterystyki kierunkowe: I2_K01, I2_K02
Powiązane charakterystyki obszarowe:
Charakterystyka K02
Ma świadomość odpowiedzialności za wspólnie realizowane zadania w ramach pracy zespołowej
Weryfikacja: ocena wykonania, prezentacji i dyskusji projektu
Powiązane charakterystyki kierunkowe: I2_K05
Powiązane charakterystyki obszarowe: