Metody Optymalizacji
Wykład
- Wprowadzenie do optymalizacji —
OptWprowadzenie.pdf
- Programowanie matematyczne —
MP.pdf
- Metoda Branch and Bound —
BB_DP.pdf
- Programowanie dynamiczne —
BB_DP.pdf
- Optymalizacja lokalna (podstawy) —
LS.pdf
... - ...
SA.pdf, TS.pdf
- Algorytmy ewolucyjne i hybrydowe (podstawy) —
MetaheuristicsSummary.pdf
- Optymalizacja wielokryterialna (podstawy) —
MetaheurystykiPodsumowanie.pdf
Karta ECTS jest tu. Zaliczenie wykładu: egzamin.
Laboratorium – aktualne informacje są → tutaj
- Modelowanie (zapisywanie) matematyczne zadań "z treścią" oraz rozwiązywanie prostych zadań metodą graficzną
- 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.
- 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.
- krótki opis problemu, jego zastosowań i interpretacji, złożoności - do 20 linijek
- opis użytego operatora sąsiedztwa, wielkość sąsiedztwa
- 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ń
- wnioski (od ogólnych do szczegółowych) z przeprowadzonych doświadczeń
- trudności na jakie napotkano, propozycje udoskonaleń i ich spodziewane efekty.
- 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).
- Jak dokładnie reprezentować pojedyncze rozwiązanie na komputerze?
- Jak wyznaczyć ocenę pojedynczego rozwiązania?
- Ile jest wszystkich rozwiązań?
- Jak zrealizować przegląd wszystkich rozwiązań?
- Spróbuj zaproponować prostą heurystykę konstruującą szybko jak najlepsze rozwiązanie.
- Przedstaw zastosowanie algorytmu LS (sąsiedztwo); opisz problem dla metody PM i B&B (lub pokaż dlaczego się nie da).
- 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.
- sprawozdanie (pdf), nazwa zawiera numer sprawozdania i nazwisko autora:
- Zwykle pdf powinien mieć < 1 MB, a zip < 50 KB.