Przeszukiwanie i optymalizacja

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.

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.