Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Współczesne techniki heurystyczne

Informacje ogólne

Kod przedmiotu: 103A-INIIT-MSP-WMH Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Współczesne techniki heurystyczne
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Przedmioty techniczne )---EITI
( Przedmioty zaawansowane obieralne )-Radiokomunikacja i techniki multimedialne-mgr.-EITI
( Przedmioty zaawansowane ogólne )--dr.-EITI
( Przedmioty zaawansowane techniczne )--mgr.-EITI
Punkty ECTS i inne: 5.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

WMH

Numer wersji:

1

Skrócony opis:

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.

Pełny opis:

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ść wykładu

  • Wstęp (2h). Przykłady problemów trudnych obliczeniowo. Definicje i rodzaje złożoności obliczeniowej. Zadania metod heurystycznych:

klasyfikacja,

aproksymacja,

optymalizacja.

  • Podstawowe problemy metod heurystycznych (2h). Dokładność modeli. Metody klasyczne

metody lokalne i globalne,

metody dokładne i przybliżone,

metody Monte Carlo.

  • Podstawowe algorytmy optymalizacyjne (2h). Podstawowe operacje w metodach lokalnych

metody pełnego przeglądu,

metody wspinania się po wzgórzu,

metody k-optymalne.

  • Metody poszukiwania rozwiązań dokładnych (2h).

algorytmy z powrotami,

metoda podziału i oszacowań,

algorytm A*.

  • Sieci neuronowe (4h). Modele neuronów. Rodzaje sieci neuronowych i ich wykorzystanie w heurystykach. Metody uczenia sieci.

Sieci jednokierunkowe (perceptrony).

Sieci rekurencyjne (Hopfielda).

Sieci w uczeniu bez nadzoru.

  • Programowanie liniowe. Metoda sympleks (2h)

  • Kolokwium 1 (2h)

  • Metody budowania rozwiązań cząstkowych (2h)

Strategia Divide and Conquer.

  • Metody unikania lokalnych optimów (2h): symulowane wyżarzanie
    oraz tabu search.

  • Algorytmy genetyczne i ewolucyjne, programowanie ewolucyjne (2h).

Kodowanie chromosomu: reprezentacja genetyczna i ewolucyjna.

Operatory genetyczne, mechanizm selekcji.

Wybrane zastosowania: Problem komiwojażera, problem routingu w
sieci telekomunikacyjnej.

Programowanie ewolucyjne.

Strategie ewolucyjne.

  • Swarm Inteligence. Kolonie mrówek. Zastosowanie w systemach w
    routingu sieci teleinformatycznej. Obliczenia Parasitic Computing (2h).

  • Systemy oparte na zbiorach rozmytych (2h).

Podstawowe definicje.

Zmienne lingwistyczne.

Operacje na zbiorach rozmytych.

Funkcje przynależności i singletony.

  • Wnioskowanie rozmyte (2h).

Systemy Mamdaniego, Takagi-Sugeno i Larsena.

Reguły rozmyte.

Operacje rozmywania, wyostrzania i agregacji.

Przykłady działania systemu.

  • Kolokwium (2h).


  • Zakres projektu
    Projekt programistyczny obejmuje implementację wybranego algorytmu
    heurystycznego (przedstawianego na wykładzie) do rozwiązania zadania z
    zakresu optymalizacji, klasyfikacji lub aproksymacji. Zaliczenie
    obejmuje wykonanie trzyetapowej dokumentacji oraz napisanie i
    prezentację programu prowadzącemu projekt. Etapy projektu obejmują
    następujące czynności:

    1. Rozpoznanie tematu projektu, zrozumienie problemu do rozwiązania oraz zapoznanie się z metodami stosowanymi do jego rozwiązania.

    2. Implementacja konkretnych algorytmów w ustalonym wcześniej jezyku
      programowania. Proces obejmuje również określenie, jakiego rodzaju
      struktury danych zostaną wykorzystane, jakie będą wymagania pamięciowe
      programu oraz jakiego rodzaju funkcjonalności wymaga się od gotowego
      projektu.

    3. Testowanie gotowego programu, określenie, jak należy dobrać jego
      parametry, aby uzyskać najlepsze wyniki.

Literatura:

    1. Z. Michalewicz, David B. Fogel, "How To Solve It: Modern Heuristics" Springer 2000

    2. Colin R. Reeves, "Modern Heuristics Techniques for Combinatorial Problems ", McGraw-Hill 1995

    3. Andries P. Engelbrecht, "Computational Intelligence. An Introduction." Wiley 2002

    4. J. Arabas, "Wykłady z algorytmów ewolucyjnych" WNT 2000


Metody i kryteria oceniania:

Za każde z dwóch kolokwium można uzyskać po 15 punktów, zaś za projekt - 30, sumaryczna liczba punktów do uzyskania z przedmiotu wynosi 60. Zaliczenie przedmiotu wymaga uzyskania co najmniej 50 % punktów możliwych do zdobycia podczas trwania przedmiotu, przy czym konieczne jest również uzyskanie minimum 50 % punktów z kolokwiów wykładowych

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (w trakcie)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 48 miejsc więcej informacji
Wykład, 30 godzin, 48 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)

Okres: 2018-10-01 - 2019-02-17
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 48 miejsc więcej informacji
Wykład, 30 godzin, 48 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. zimowy" (zakończony)

Okres: 2017-10-01 - 2018-02-18
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 48 miejsc więcej informacji
Wykład, 30 godzin, 48 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. zimowy" (zakończony)

Okres: 2016-10-01 - 2017-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 48 miejsc więcej informacji
Wykład, 30 godzin, 48 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2015/2016 - sem. zimowy" (zakończony)

Okres: 2015-10-01 - 2016-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 48 miejsc więcej informacji
Wykład, 30 godzin, 48 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. zimowy" (zakończony)

Okres: 2014-09-29 - 2015-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 46 miejsc więcej informacji
Wykład, 30 godzin, 46 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2013/2014 - sem. zimowy" (zakończony)

Okres: 2013-10-01 - 2014-02-23
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 40 miejsc więcej informacji
Wykład, 30 godzin, 40 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2012/2013 - sem. zimowy" (zakończony)

Okres: 2012-10-01 - 2013-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 72 miejsc więcej informacji
Wykład, 30 godzin, 72 miejsc więcej informacji
Koordynatorzy: Sebastian Kozłowski
Prowadzący grup: Sebastian Kozłowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.