Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

Przeszukiwanie i optymalizacja

Informacje ogólne

Kod przedmiotu: 103A-INSZI-ISP-POP
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Przeszukiwanie i optymalizacja
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Algorytmy i języki - albo - Projektowanie systemów )-Inżynieria systemów informatycznych-inż.-EITI
( Przedmioty obieralne )-Automatyka i robotyka-inż.-EITI
( Przedmioty techniczne )---EITI
( Sztuczna inteligencja )-Sztuczna inteligencja-inż.-EITI
Punkty ECTS i inne: 4.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
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 2023/2024 - sem. letni" (w trakcie)

Okres: 2024-02-19 - 2024-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć: (brak danych)
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna

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

Okres: 2023-10-01 - 2024-02-18
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 15 godzin, 88 miejsc więcej informacji
Wykład, 30 godzin, 88 miejsc więcej informacji
Koordynatorzy: Jarosław Arabas
Prowadzący grup: Jarosław Arabas, Kamil Deja, Stanisław Kozdrowski, Konrad Krawczyk, Eryk Warchulski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

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

Okres: 2022-10-01 - 2023-02-19
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 15 godzin, 60 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Jarosław Arabas
Prowadzący grup: Jarosław Arabas, Stanisław Kozdrowski, Eryk Warchulski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2021/2022 - sem. letni" (zakończony)

Okres: 2022-02-23 - 2022-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 15 godzin, 45 miejsc więcej informacji
Wykład, 30 godzin, 45 miejsc więcej informacji
Koordynatorzy: Jarosław Arabas
Prowadzący grup: Jarosław Arabas, Stanisław Kozdrowski, Konrad Krawczyk, Eryk Warchulski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103200 - Instytut Informatyki

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

Okres: 2021-10-01 - 2022-02-22
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 15 godzin, 90 miejsc więcej informacji
Wykład, 30 godzin, 90 miejsc więcej informacji
Koordynatorzy: Jarosław Arabas
Prowadzący grup: Jarosław Arabas, Kamil Deja, Stanisław Kozdrowski, Konrad Krawczyk, Eryk Warchulski
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.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl kontakt deklaracja dostępności USOSweb 7.0.0.0-7 (2024-03-18)