Metody Optymalizacji

Wykład

  1. Wprowadzenie do optymalizacji — OptWprowadzenie.pdf
  2. Programowanie matematyczne — MP.pdf
  3. Metoda Branch and BoundBB_DP.pdf
  4. Programowanie dynamiczne — BB_DP.pdf
  5. Optymalizacja lokalna (podstawy) — LS.pdf...
  6. ...SA.pdf, TS.pdf
  7. Algorytmy ewolucyjne i hybrydowe (podstawy) — MetaheuristicsSummary.pdf
  8. Optymalizacja wielokryterialna (podstawy) — MetaheurystykiPodsumowanie.pdf

Karta ECTS jest tu. Zaliczenie wykładu: egzamin.

Laboratorium – aktualne informacje są → tutaj

  1. Modelowanie (zapisywanie) matematyczne zadań "z treścią" oraz rozwiązywanie prostych zadań metodą graficzną
  2. Rozwiązywanie zadań programowania matematycznego (PM) za pomocą dostępnych programów, "solverów". Na kolejne zajęcia przygotowanie indywidualnego sprawozdania z rozwiązania LPM i analizy wrażliwości.
  3. Sprawdzian / implementacja losowego przeszukiwania oraz local search dla problemu QAP (dane, opis); pomiar czasu działania. Do 30.05 przygotowanie i przysłanie indywidualnego sprawozdania:

    Eksperymenty z algorytmem losowym R, greedy G i steepest S w trybie multi-random start. Dla chętnych również algorytm SA (prosta modyfikacja G). Ocena statystyczna na 8-10 instancjach, w każdym przypadku 10 przebiegów algorytmu w celu uzyskania miarodajnej informacji. Sprawozdanie – raport z eksperymentów: zwięzłe, konsekwentna notacja, odpowiednia liczba miejsc znaczących, sensowne i czytelne wykresy i tabele włączone w tekst.

    Algorytmowi R dajemy równe szanse czasowe, jak algorytmom G i S.

    1. krótki opis problemu, jego zastosowań i interpretacji, złożoności - do 20 linijek
    2. opis użytego operatora sąsiedztwa, wielkość sąsiedztwa
    3. porównanie działania 3 algorytmów na wybranych instancjach problemów
      • odległość od optimum (wg jakiej miary?), przypadek średni i najlepszy (a dla chętnych również najgorszy). Dla średnich oceniamy stabilność wyników (na wykresy średnich nanosimy odchylenia standardowe)
      • czas działania
      • GS: średnia liczba kroków algorytmu i liczba ocenionych (przejrzanych) rozwiązań
    4. wnioski (od ogólnych do szczegółowych) z przeprowadzonych doświadczeń
    5. trudności na jakie napotkano, propozycje udoskonaleń i ich spodziewane efekty.
  4. Indywidualne prezentacje: praktyczny problem i jego optymalizacja poznanymi metodami. Koniecznie skonsultuj swój pomysł z prowadzącym na poprzednich zajęciach (lub nawet wcześniej).
    1. Jak dokładnie reprezentować pojedyncze rozwiązanie na komputerze?
    2. Jak wyznaczyć ocenę pojedynczego rozwiązania?
    3. Ile jest wszystkich rozwiązań?
    4. Jak zrealizować przegląd wszystkich rozwiązań?
    5. Spróbuj zaproponować prostą heurystykę konstruującą szybko jak najlepsze rozwiązanie.
    6. Przedstaw zastosowanie algorytmu LS (sąsiedztwo); opisz problem dla metody PM i B&B (lub pokaż dlaczego się nie da).
    7. Oprócz kryterium z punktu 2, jakie jeszcze kryteria można wziąć pod uwagę?

Sprawdzian: A1. Zapisz zadanie z treścią jako zadanie PM, A2. Rozwiąż zadanie PM metodą graficzną, B. Odpowiedz na pytania z zakresu wykładu.

Zaliczenie laboratorium: ocena końcowa na podstawie oceny ze sprawdzianu (40%), sprawozdań (40%) i z prezentacji (20%). Każdy z tych trzech elementów należy zaliczyć.

Sprawozdania

Można wykorzystać [szablon]. Przed wysłaniem sprawozdania upewnij się, że:

  • Podałeś pochodzenie źródłowe wszystkich cytowanych w sprawozdaniu fragmentów i wykorzystanych materiałów (literatura)
  • Sprawdziłeś pisownię tekstu (spell-check)
  • Wykresy (i w miarę możliwości rysunki) są wektorowe (pdf, ps, svg itp.)
  • Zatytułowałeś mail tak:   [MO] sprawozdanie 1, Janek Kowalski
  • Wysyłasz do prowadzącej laboratorium (agnieszka.mensfelt at cs.put.poznan.pl) jeden lub dwa pliki:
    • sprawozdanie (pdf), nazwa zawiera numer sprawozdania i nazwisko autora:   1_Kowalski.pdf
    • źródła programu (zip – same źródła):   1_Kowalski.zip. Jeśli źródło to jeden plik, wyślij go bezpośrednio bez kompresowania.
  • Zwykle pdf powinien mieć < 1 MB, a zip < 50 KB.
Termin przysłania sprawozdania to dzień przed kolejnymi zajęciami; każdy tydzień opóźnienia obniża ocenę z tego sprawozdania o 0,5.

Materiały

Prezentacje wykładowe (pdf) tutaj, więcej o PM liniowym tu. Materiały wideo tu.