Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Wstęp do algorytmów ewolucyjnych
Koordynator przedmiotu:
Dr hab. inż. Jarosław Arabas
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
1 / rok ak. 2017/2018
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1) godziny kontaktowe - obecność na wykładzie i zajęciach projektowych - 45 2) dodatkowe godziny przeznaczone na realizację projektu - 15 3) zapoznanie się z literaturą - 10h 4) przygotowanie prezentacji - 20h Razem nakład pracy studenta 90 = 4p. ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
a) obecność na wykładzie i zajęciach projektowych - 45 Razem: 45, co odpowiada 2 punktom ECTS.
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
a) zajęcia projektowe - 15 b) dodatkowe godziny przeznaczone na realizacje projektu - 15 Razem: 30, co odpowiada 1 punktowi 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:
Zakres tematyczny Wykładu 1. Zadanie optymalizacji kombinatorycznej i w Rn .Metoda optymalizacji jako sposób uszeregowania punktów z przestrzeni przeszukiwań. Ograniczenia funkcyjne i zbiór dopuszczalny. 2. 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. 3. 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 globalego. 4. Algorytm ewolucyjny: metody selekcji, operacje genetyczne dla optymalizacji w Rn  i {0,1}n 5. Techniki uwzględniania ograniczeń – zewnętrzna funkcja kary, specjalizowane kodowanie, naprawa rozwiązań niedopuszczalnych. 6. Technika poprawy zbieżności – hybrydyzacja z metodami optymalizacji lokalnej, darwinowski a lamarkowski schemat ewolucji. 7. 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 8. Dostosowywanie algorytmu ewolucyjnego do niestandardowych przestrzeni przeszukiwań – specjalizowane reprezentacje i operacje genetyczne. Jak projektować operacje genetyczne aby algorytm ewolucyjny działał prawidłowo. 9. Optymalizacja metodą immunologiczną – podobieństwa i różnice z algorytmem ewolucyjnym. 10. Optymalizacja metodą trajektorii cząstki. Optymaliazacja rojem cząstek. Podobieństwo z wielostartową metodą największego spadku. 11. Optymalizacja globalna algorytmem bazującym na grupowaniu (wg Toerna) 12. Usprawnianie metod  optymalizacji globalnej poprzez modyfikacje zbioru rozwiązań dopuszczalnych (metoda tabu) lub wprowadzanie funkcji kary skoncentrowanych w minimach lokalnych.   Zakres tematyczny Projektu 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:
Łączną ocenę punktową przelicza się na stopnie według poniższych zasad: b)  3.5 jeżeli uzyskali od 61 do 70  pkt. c)  4.0 jeżeli uzyskali od 71 do 80  pkt. d)  4.5 jeżeli uzyskali  od 81 do 90  pkt. e)  5.0 jeżeli uzyskali powyżej 90  pkt.
Egzamin:
tak
Literatura:
J. Arabas: Wykłady z algorytmów ewolucyjnych, WNT, 2001 Z. Michalewicz, D. Fogel: Jak to rozwiązać czyli nowoczesna heurystyka, WNT, 2005 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: