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
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1030-INMSI-MSP-0012
Semestr nominalny:
2 / rok ak. 2015/2016
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
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 kryteriow 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

Efekt W2_01
zna zaawansowane metody uczenia maszynowego, metody ewolucyjne oraz metody inteligencji obliczeniowej
Weryfikacja: ocena z egzaminu i projektu
Powiązane efekty kierunkowe: SI_W10
Powiązane efekty obszarowe:

Profil ogólnoakademicki - umiejętności

Efekt U2_01
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 i projektu
Powiązane efekty kierunkowe: SI_U01
Powiązane efekty obszarowe:
Efekt U2_02
potrafi projektować systemy informatyczne oparte o algorytmy genetyczne i metody ewolucyjne
Weryfikacja: ocena z projektu
Powiązane efekty kierunkowe: SI_U16
Powiązane efekty obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Efekt K2_01
Ma świadomość odpowiedzialności za wspólnie realizowane zadania w ramach pracy zespołowej
Weryfikacja: ocena z projektu
Powiązane efekty kierunkowe: SI_K04
Powiązane efekty obszarowe: