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

Przeszukiwanie i optymalizacja

Informacje ogólne

Kod przedmiotu: 103A-INSZI-IOP-POP Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Przeszukiwanie i optymalizacja
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Przedmioty techniczne )---EITI
( Sztuczna inteligencja )-Sztuczna inteligencja-inż.-EITI
Punkty ECTS i inne: 4.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

POP

Numer wersji:

1

Skrócony opis:

Celem przedmiotu jest zapoznanie studentów z elementami teorii oraz podstawowymi algorytmami przeszukiwania i optymalizacji. Student zdobędzie umiejętność formułowania i rozwiązywania problemów jako zadania przeszukiwania bądź optymalizacji. Student potrafił będzie dobrać odpowiednią metodę do postawionego zadania.

Pełny opis:

Celem przedmiotu jest zapoznanie studentów z elementami teorii oraz podstawowymi algorytmami przeszukiwania i optymalizacji. Student zdobędzie umiejętność formułowania i rozwiązywania problemów jako zadania przeszukiwania bądź optymalizacji. Student potrafił będzie dobrać odpowiednią metodę do postawionego zadania.



Treść wykładu

  1. Wprowadzenie (2 godz.)
    Informacje o przedmiocie. Regulamin przedmiotu, literatura uzupełniająca. Podstawowe pojęcia: zadanie przeszukiwania, ciągłe i dyskretne i przestrzenie przeszukiwań, zagadnienie sformułowania funkcji celu, heurystyka, metaheurystyka, optymalizacja lokalna vs. globalna.
  2. Przeszukiwanie (2 godz.)
    Typowe zadania kombinatoryczne. Przeszukiwanie wyczerpujące vs. metody heurystyczne (powtórzenie i uzupełnienie).
  3. Optymalizacja z ograniczeniami (2 godz.)
    Geneza ograniczeń, sposoby ich uwzględniania poprzez przeformułowanie zadania optymalizacji lub modyfikacje metody przeszukiwania.
  4. Algorytmy optymalizacji z jednym punktem roboczym (4 godz.)
    Metoda największego spadku/wzrostu, metody uwzględniające gradient funkcji celu, metody pseudonewtonowskie, błądzenie przypadkowe, symulowane wyżarzanie.
  5. Modyfikacje jednopunktowych metod optymalizacji (2 godz.)
    Tabu, sąsiedztwo o zmiennym promieniu.
  6. Podstawowe wielopunktowe algorytmy optymalizacji (4 godz.)
    Simplex Neldera-Meada, algorytm ewolucyjny (powtórzenie i uzupełnienie), optymalizacja rojem cząstek, ewolucja różnicowa, strategie ewolucyjne (powtórzenie i uzupełnienie).
  7. Algorytmy optymalizacji bazujące na adaptacji rozkładu prawdopodobieństwa (2 godz.)
    EDA, CMA-ES.
  8. Ocena stochastycznych algorytmów optymalizacji (2 godz.)
    Specyfika metod stochastycznych, zadania benchmarkowe.
  9. Elementy składowe algorytmu ewolucyjnego (2 godz.)
    Metody selekcji, sukcesji, mutacji, krzyżowania. Ich wpływ na zdolności eksploatacji i eksploracji algorytmu. Zachowanie algorytmu na kilku przykładowych funkcjach celu. Algorytmy bezparametrowe.
  10. Hybrydyzacja metod optymalizacji (2 godz.)
    Połączenie kilku metod optymalizacji, w tym metody lokalnej i globalnej.
  11. Optymalizacja wielokryterialna (2 godz.)
    Metody optymalizacji wielokryterialnej, skalaryzacja.
  12. Źródła trudności zadań optymalizacyjnych (2 godz.).
    Cechy funkcji celu lub ograniczeń powodujące to, że zadanie optymalizacji jest trudne, np.: złe uwarunkowanie, klątwa wymiarowości, zwodniczość, zadania typu igła w stogu siana.



Zakres projektu

Celem projektu jest zdobycie doświadczeń praktycznych w zakresie implementowania i stosowania omawianych algorytmów.

  1. Eksperymenty z użyciem dostępnych bibliotek dostarczających implementacji algorytmów optymalizacji.
  2. Samodzielna implementacja lub modyfikacja dostępnej implementacji algorytmu przeszukiwania bądź optymalizacji i badanie jego właściwości.
  3. Analiza porównawcza metod optymalizacji bazująca na zestawach zadań testowych oraz analizie statystycznej wyników porównywanych metod.
Literatura:

  • J. Arabas: Wykłady z algorytmów ewolucyjnych. WNT, 2004.
  • K. Trojanowski: Metaheurystyki praktycznie, WSISIZ, 2008 (wyd. II).
  • P. Wawrzyński: Podstawy sztucznej inteligencji, OWPW, 2014.
Metody i kryteria oceniania:

Sprawdzanie założonych efektów kształcenia realizowane jest przez:

  • ocenę wiedzy i umiejętności związanych z realizacją zadania projektowego;
  • ocenę wiedzy wykazanej na dwóch kolokwiach pisemnych.

Zajęcia w cyklu "rok akademicki 2021/2022 - sem. zimowy" (jeszcze nie rozpoczęty)

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

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