- 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