Nazwa przedmiotu:
Algorytmy ewolucyjne
Koordynator przedmiotu:
Przemysław MIAZGA
Status przedmiotu:
Fakultatywny ograniczonego wyboru
Poziom kształcenia:
Studia I stopnia
Program:
Inżynieria Biomedyczna
Grupa przedmiotów:
Przedmioty techniczne
Kod przedmiotu:
AE
Semestr nominalny:
7 / rok ak. 2014/2015
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- udział w wykładach: 15 x 2 h = 30 h, - udział w zajęciach projektowych: 15 x 1 h = 15 h, - przygotowanie do wykładu (przegląd notatek i dodatkowej literatury, rozwiązanie podanych na wykładzie mini-problemów): 14 x 1 h = 14 h - udział w konsultacjach: 2 h , - przygotowanie i prezentacja projektu: 48 h łącznie: 30 + 15 + 14 + 2 + 48 = 109 h - 4 ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- udział w wykładach: 15 x 2 h = 30 h, - udział w zajęciach projektowych: 15 x 1 h = 15 h, udział w konsultacjach: 2 h Razem 47 godz - 2 ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- udział w zajęciach projektowych: 15 x 1 h = 15 h, - przygotowanie i prezentacja projektu: 48 h Razem 63h - 3 ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
Umiejętność programowania w języku C++ lub C# lub Python
Limit liczby studentów:
36
Cel przedmiotu:
- zapoznanie studentów z podstawowymi technikami metod obliczeniowych optymalizacji numerycznej, ze szczególnym uwzględnieniem algorytmów heurystycznych, - ukształtowanie wśród studentów zrozumienia konieczności doboru właściwego dla założonego problemu modelu zadania oraz metody optymalizacji, - zapoznanie studentów z przykładami rozwiazywania zadań optymalizacji produkcji, finansów, projektowania obwodów elektronicznych i rozwiązywania zagadnień bio-medycznych, z wykorzystaniem wybranych algorytmów programowania liniowego, kwadratowego, nieliniowego oraz metod heurystycznych.
Treści kształcenia:
Wstęp do metod optymalizacji numerycznej: modelowanie zagadnienia, parametryzacja, wymiarowość zadania, kryteria optymalizacji i funkcja celu, zagadnienie poszukiwania optimum, problemy wielokryterialne, otoczenie i optima lokalne, optymalizacja globalna, przekraczanie punktu siodłowego, dynamicznie zmieniające się otoczenie. (2h) Klasyczne metody optymalizacji: przeszukiwanie lokalne, metody najszybszego spadku, programowanie nieliniowe, stochastyczne metody optymalizacji, (4h) Meta-heurystyczne metody optymalizacji: poszukiwanie optimum globalnego, symulowane wyżarzanie, tabu search, metody subgradientowe, controlled random search. (2h) Algorytmy genetyczne: generatory liczb losowych, kodowanie binarne, prosty algorytm genetyczny, (2) Zagadnienie podróżującego handlowca: kodowanie całkowitoliczbowe, algorytmy naprawy chromosomu (traveling salesman problem TSP). (1h) Kryteria oceny algorytmu optymalizacyjnego: koszt funkcji celu, ocena zbieżności. (1h) Strategie ewolucyjne i programowanie ewolucyjne: kodowanie rzeczywisto-liczbowe, strategia (1+1), strategia (?+?) i (?,?), programowanie ewolucyjne, ewolujace programy. (2h) Kodowanie i operatory genetyczne: reprezentacja genotypowa i fenotypowa, wektory symboli/liczb, permutacje, wrażenia symboliczne, mutacja i perturbacja (krzyżowanie). (2h) Kotrola Populacji: inicjacja, reprodukcja, sukcesja, eksploracja i eksploatacja. Wykorzystanie właściwości problemu. (2h) Optymalizacja z ograniczeniami: znajdowanie rozwiązania dopuszczalnego, algorytmy naprawy, karanie niedopuszczalnych osobników, specjalne operatory wariacyjne do kontroli populacji, dekodery, (2h) Algorytmy Hybrydowe: Algorytmy wielostartowe, operator poszukiwania lokalnego. (1h) Przetwarzanie równoległe: zrównoleglanie algorytmu ewolucyjnego, algorytm wyspowy, zagadnienie migracji, modele dyfuzyjne. (1h) Dostrajanie algorytmu ewolucyjnego: przedwczesna zbieżność, efekt Baldwin, podejście Lamarkistowskie, techniki kontroli algorytmu, parametry kontrolne, algorytmy samoadapcyjne(2h) Systemy samouczące: ewoluujące systemy nadzoru i kontroli produkcji. (2h) Ewolucja Molekularna: wstęp. (2h)
Metody oceny:
- ocenę wiedzy i umiejętności związanych z realizacją zadań projektowych – ocenę sprawozdań z realizacji projektu (poszczególnych zadań projektowych), - ocenę wiedzy i umiejętności wykazanych na kolokwiach w trakcie wykładu - formatywną ocenę związaną z interaktywną forma prowadzenia wykładu
Egzamin:
nie
Literatura:
- David E. Goldberg, "Algorytmy genetyczne i ich zastosowanie",WNT. 1995 - Zbigniew Michalewicz, "Algorytmy genetyczne + struktury danych =programy ewolucyjne", WNT 1996 - Andrzej Stachurski, "Wprowadzenie do optymalizacji", WPW. 2009 - Andrzej Karbowski, Ewa Niewiadomska, "Programowanie równoległe irozproszone", WPW. 2009 - Zbigniew Michalewicz, David B. Fogel,"Jak rozwiązać, czylinowoczesna heurystyka", WNT 2006
Witryna www przedmiotu:
https://studia.elka.pw.edu.pl/priv/11Z/AE.A/
Uwagi:
W ramach wykładu zawarty jest przegląd metod rozwiązywania zadań inżynierskich dla osób nieobeznanych z metodami optymalizacji numerycznej. Główny nacisk położony jest na rozwinięcie umiejętności kreatywnego myślenia, a w szczególności umiejętności określenia ram zagadnienia, wydzielenie celów oraz dobranie najbardziej dogodnej reprezentacji problemu. Na początku rozważane są zagadnienia podstawowe: model, i jego znaczenie, reprezentacja, cel i funkcja celu. Następnie przedstawiany jest przegląd klasycznych metod optymalizacji. Na zakończenie prezentowane są metody heurystyczne, takie jak metoda symulowanego wyżarzania, poszukiwań z tabu, kontrolowane przeszukiwanie przypadkowe i algorytmy ewolucyjne. Rozważane algorytmy są łatwe do zrozumienia i implementacji dla każdego inżyniera ze znajomością podstaw programowania.

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt W1
Student potrafi opisać sposób działania wybranych metod optymalizacji numerycznej oraz zakres ich zastosowania, podać przykłady zastosowania tych algorytmów
Weryfikacja: kolokwia, zadania testowe, projekt
Powiązane efekty kierunkowe: K_W01
Powiązane efekty obszarowe: T1A_W01, T1A_W07
Efekt W2
Student potrafi wskazać ograniczenia klasycznych metod optymalizacji oraz określić metody ich przezwyciężenia
Weryfikacja: projekt
Powiązane efekty kierunkowe: K_W01
Powiązane efekty obszarowe: T1A_W01, T1A_W07

Profil ogólnoakademicki - umiejętności

Efekt U1
Student potrafi odnaleźć niezbędne dla rozwiązania problemu optymalizacji informacje w literaturze i Internecie
Weryfikacja: projekt
Powiązane efekty kierunkowe: K_U01
Powiązane efekty obszarowe: T1A_U01
Efekt U2
Student potrafi wybrać właściwą do rozwiązania problemu optymalizacji metodę optymalizacji numerycznej oraz model problemu
Weryfikacja: kolokwia, zadania testowe, projekt
Powiązane efekty kierunkowe: K_U02
Powiązane efekty obszarowe: T1A_U02, T1A_U07
Efekt U3
Student potrafi zaimplementować wybraną metodę optymalizacji i przeprowadzić testy zbieżności algorytmu
Weryfikacja: projekt
Powiązane efekty kierunkowe: K_U06
Powiązane efekty obszarowe: T1A_U09

Profil ogólnoakademicki - kompetencje społeczne

Efekt K1
Student potrafi pracować indywidualnie i w zespole
Weryfikacja: Udział w zajęciach projektowych i wykładzie
Powiązane efekty kierunkowe: K_K07
Powiązane efekty obszarowe: T1A_K03