Politechnika
Warszawska

Katalog
ECTS

Nazwa przedmiotu:

Współczesne techniki heurystyczne

Koordynator przedmiotu:

dr inż. Piotr Bilski

Status przedmiotu:

Obowiązkowy

Poziom kształcenia:

Studia II stopnia

Program:

Telekomunikacja

Grupa przedmiotów:

Przedmioty techniczne - zaawansowane

Kod przedmiotu:

WMH

Semestr nominalny:

4 / rok ak. 2012/2013

Liczba punktów ECTS:

5

Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:

30 godzin - uczestnictwo w wykładzie oraz kolokwia ch 15 godzin - uczestnictwo w konsultacjach prohjektowych 20 godzin - wykonywanie projektu w domu (analiza literatury opisującej algorytm, tworzenie kodu programu, pisanie dokumentacji projektu, testowanie programu na danych) 10 godzin - analiza materiałów wykładowych w domu 20 godzin - przygotowanie do kolokwiów 20 godzin - przygotowanie do egzaminu 2 godziny - uczestnictwo w egzaminie Razem: 117 godzin (5 punktów ETCS)

Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:

3 punkty ECTS (uczestnictwo w wykładach, kolokwiach, egzaminie oraz prezentacja projektów)

Język prowadzenia zajęć:

polski

Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:

2 punkty ECTS (tworzenie i testowanie projektu, pisanie dokumentacji)

Formy zajęć i ich wymiar w semestrze:

• Wykład30h
• Ćwiczenia0h
• Laboratorium0h
• Projekt30h
• Lekcje komputerowe0h

Wymagania wstępne:

- znajomość podstaw programowania, umiejętność programowania w języku wysokiego poziomu (C++/C#/Java itp.) lub języku obliczeń naukowych (Matlab/R itp.) - umiejętność projektowania i implementacji algorytmów, znajomość struktur danych wykorzystywanych w programie komputerowym - znajomość matematyki na poziomie pozwalającym zrozumieć metody przedstawiane na przedmiocie (optymalizacja, klasyfikacja, regresja, logika rozmyta itp.)

Limit liczby studentów:

60

Cel przedmiotu:

Przedmiot ma na celu zapoznanie studentów z najpopularniejszymi metodami heurystycznymi stosowanymi obecnie w naukach technicznych. Omawiane są zagadnienia z dziedziny optymalizacji, klasyfikacji oraz aproksymacji, prezentuje się również metody sztucznej inteligencji do rozwiązywania takich problemów. Przedmiot zawiera zarówno omówienie teoretyczne algorytmów, jak i przykłady ich praktycznych implementacji. Bezpośrednie efekty kształcenia to nabycie przez studentów ogólnej wiedzy na temat współczesnych algorytmów heurystycznych wykorzystywanych w różnych dziedzinach nauki i techniki. Ponadto studenci zyskają umiejętność projektowania i testowania konkretnych metod.

Treści kształcenia:

1. Wstęp. Definicja heurystyk. Przykłady problemów trudnych obliczeniowo (np. SAT, TSP). Definicje i rodzaje złożoności obliczeniowej. Zadania metod heurystycznych: o Klasyfikacja o Aproksymacja o Optymalizacja 2. Klasyfikacja problemów. Zasady tworzenia metody heurystycznej. Reprezentacja rozwiązania oraz funkcji oceny. Definicja sąsiedztwa. Rozwiązania dopuszczalne, funkcje kary. 3. Podstawowe problemy metod heurystycznych. Dokładność i stacjonarność modeli. Metody klasyczne o metody lokalne i globalne o metody dokładne i przybliżone o metody Monte Carlo 4. Podstawowe algorytmy optymalizacyjne. Podstawowe operacje w metodach lokalnych o Metody pełnego przeglądu o metody wspinania się po wzgórzu o metody k-optymalne 6. Sieci neuronowe. Modele neuronów. Rodzaje sieci neuronowych i ich wykorzystanie w heurystykach. Metody uczenia sieci o Sieci jednokierunkowe (perceptrony) o Sieci rekurencyjne (Hopfielda) o Sieci w uczeniu bez nadzoru 7. Programowanie liniowe. Metoda simpleks. 8. Metody budowania rozwiązań cząstkowych (2h) o Strategia Divide and Conquer o Metoda Branch and Bound o Metody optymalizacji drzew (algorytm A*) 9. Metody unikania lokalnych optimów: symulowane wyżarzanie oraz przeszukiwanie z tabu. 10. Algorytmy genetyczne i ewolucyjne, programowanie ewolucyjne: o Kodowanie chromosomu: reprezentacja genetyczna i ewolucyjna o Operatory genetyczne, mechanizm selekcji o Wybrane zastosowania: Problem komiwojażera, problem routingu w sieci telekomunikacyjnej. o Programowanie ewolucyjne o Strategie ewolucyjne 11. Systemy oparte na zbiorach rozmytych. o Podstawowe definicje o Zmienne lingwistyczne o Operacje na zbiorach rozmytych o Funkcje przynależności i singletony 12. Wnioskowanie rozmyte. o Systemy Mamdaniego, Takagi-Sugeno i Larsena o Reguły rozmyte o Operacje rozmywania, wyostrzania i agregacji o Przykłady działania systemu

Metody oceny:

- dwa kolokwia pisemna w czasie trwania semestru - ocena projektu programistycznego na podstawie prezentacji działającego programu oraz dokumentacji opisującej projekt. - egzamin pisemny w sesji

Egzamin:

tak

Literatura:

Z. Michalewicz, D. B. Fogel, „Jak to rozwiązać, czyli nowoczesna heurystyka”, WNT, Warszawa, 2006. B. S. Butkiewicz, „Metody wnioskowania przybliżonego. Właściwości i zastosowanie”, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa, 2001. S. Osowski, „Sieci neuronowe do przetwarzania informacji”, Oficyna Wydawnicza Politechniki Warszawskiej, Warszwa, 2006. J. Hertz, A. Krogh, R.G. Palmer, „Wstęp do teorii obliczeń neuronowych”, WNT, Warszawa, 1993. J. Arabas, „Wykłady z algorytmów ewolucyjnych”, WNT Warszawa, 2001.

Witryna www przedmiotu:

http://berni.ire.pw.edu.pl/WMH/

Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt W01

Posiada wiedzę na temat współczesnych algorytmów heurystycznych (w szczególności metod lokalnych, sieci neuronowych, algorytmów ewolucyjnych i logiki rozmytej) oraz ich potencjalnych zastosowań w telekomunikacji i dziedzinach pokrewnych.
Weryfikacja: kolokwia pisemne, egzamin pisemny
Powiązane efekty kierunkowe: K_W01, K_W03, K_W08, K_W14
Powiązane efekty obszarowe: T2A_W01, T2A_W02, T2A_W03, T2A_W07

Efekt W02

Rozumie potrzebę stosowania technik heurystycznych do rozwiązywania problemów techniki (optymalizacyjnych, klasyfikacyjnych i aproksymacyjnych).
Weryfikacja: kolokwia pisemne, egzamin pisemny
Powiązane efekty kierunkowe: K_W03, K_W04, K_W12, K_W14
Powiązane efekty obszarowe: T2A_W02, T2A_W03, T2A_W04, T2A_W07, T2A_W03, T2A_W04, T2A_W07, T2A_W07

Efekt W03

Ma wiedzę na temat umiejscowienia metod heurystycznych w dziedzinie sztucznej inteligencji oraz trendów rozwojowych w nich zachodzących.
Weryfikacja: egzamin pisemny
Powiązane efekty kierunkowe: K_W03, K_W13, K_W14
Powiązane efekty obszarowe: T2A_W02, T2A_W05, T2A_W07

Profil ogólnoakademicki - umiejętności

Efekt U01

Potrafi zaimplementować wybrany algorytm heurystyczny w języku programowania wysokiego poziomu lub języku obliczeń inżynierskich i naukowych.
Weryfikacja: projekt programistyczny
Powiązane efekty kierunkowe: K_U01, K_U06, K_U09, K_U12, K_U14
Powiązane efekty obszarowe: T2A_U01, T2A_U03, T2A_U04, T2A_U07, T2A_U09, T2A_U05, T2A_U07, T2A_U09, T2A_U15, T2A_U15, T2A_U16, T2A_U17, T2A_U18, T2A_U19, T2A_U11

Efekt U02

Potrafi zbadać złożoność obliczeniową zaimplementowanego algorytmu na podstawie pomiarów eksperymentalnych z udziałem danych trenujących i testujących.
Weryfikacja: sprawozdanie projektu programistycznego
Powiązane efekty kierunkowe: K_U02, K_U09, K_U10, K_U14
Powiązane efekty obszarowe: T2A_U02, T2A_U03, T2A_U04, T2A_U05, T2A_U07, T2A_U09, T2A_U15, T2A_U07, T2A_U09, T2A_U15, T2A_U11

Efekt U03

Umie stworzyć dokumentację wytworzonego oprogramowania oraz przedstawić je podczas ustnej prezentacji.
Weryfikacja: sprawozdanie projektu programistycznego
Powiązane efekty kierunkowe: K_U02, K_U05, K_U09
Powiązane efekty obszarowe: T2A_U02, T2A_U03, T2A_U04, T2A_U02, T2A_U07, T2A_U05, T2A_U07, T2A_U09, T2A_U15

Efekt U04

Potrafi rozwiązywać proste problemy obliczeniowe wymagające zastosowania jednej z metod heurystycznych i dopasowania jej do konkretnej sytuacji.
Weryfikacja: kolokwium pisemne
Powiązane efekty kierunkowe: K_U05, K_U14
Powiązane efekty obszarowe: T2A_U02, T2A_U07, T2A_U11

Profil ogólnoakademicki - kompetencje społeczne

Efekt K01

Rozumie znaczenie metod heurystycznych w poprawie jakości ludzkiego życia.
Weryfikacja: egzamin pisemny
Powiązane efekty kierunkowe: K_K02
Powiązane efekty obszarowe: T2A_K07