Metody Optymalizacji
Laboratorium 3 – przeszukiwanie lokalne
Implementacja losowego przeszukiwania oraz local search dla problemu QAP (dane, opis); pomiar czasu działania. Do 02.06 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.
Sprawozdanie
- 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.
Można wykorzystać szablon.
Implementacja
Można wykorzystać szkielet rozwiązania (Java). Proszę pamiętać o załączeniu źródeł programu do maila ze sprawozdaniem.