Techniki optymalizacji

Studia dzienne, magisterskie, spec. TWO

Rok akademicki 2013/14, semestr zimowy

Konkurs

Konkurs zostanie przeprowadzony w czwartek 30 stycznia 2014 r. Zgłoszenia należy wysyłać do godziny 10:00.

Każde zgłoszenie powinno zawierać archiwum ZIP, w którym znajdują się następujące elementy:

Kod źródłowy musi być napisany zgodnie ze specyfikacją zamieszczoną poniżej. Niespełnienie wymagań powoduje wypadnięcie z konkursu.

Specyfikacja (aktualizacja: 26 stycznia 2014)

Programy będą uruchamiane pod kontrolą Java HotSpot 64-bit Server VM w wersji 1.7.0_45. Proces będzie miał do dyspozycji 512 MB RAM i 4 rdzenie procesora. Czas pojedynczego uruchomienia: 1 sekunda. Limit liczby zgłoszonych rozwiązań na uruchomienie: 20.

Wyniki

Przeprowadzono obliczenia na podanych wcześniej instancjach. Ze względu na ograniczenia czasowe, nie będzie obliczeń na większej liczbie instancji.

Surowe wyniki zawierające wszystkie wygenerowane rozwiązania wszystkich programów konkursowych, zweryfikowane sprawdzarką (nieznaczny odsetek rozwiązań był niedopuszczalny): Dane (2,8 MB, aktualizacja: 31 stycznia 2014)

Każdy program na każdej instancji otrzymuje ranking. Najlepszy program otrzymuje miejsce 1., kolejny 2., itd. W sytuacji remisu, remisujące programy otrzymują taki sam ranking będący średnią z rankingów tych programów, gdyby remisu nie było (np. dwa programy remisujące na miejscu 1. otrzymują ranking 1.5).

Podsumowane wyniki: Podsumowanie (aktualizacja: 31 stycznia 2014)

Sprawdzarka

Do sprawdzania poprawności instancji problemu i rozwiązań można użyć sprawdzarki. W przypadku znalezienia błędów proszę o e-mail z podaniem wersji używanej sprawdzarki oraz danymi, dla których zachowuje się nieprawidłowo.

Sprawdzarka (2014-01-31_1)

Opis projektu

W zależności od grupy, do której zostaliście Państwo przypisani, rozwiązujecie jeden z problemów optymalizacyjnych:

Definicja problemu może być poprawiana oraz pojawiać się będą dodatkowe materiały (instancje, kod sprawdzacza), dlatego warto czasem zajrzeć na tę stronę. Informacje o aktualizacjach będą się pojawiać też na Twitterze (@pwesolek_PP).

Problem PP

Opis problemu (ostatnia aktualizacja: 23 stycznia 2014; spis zmian)

Przykładowe instancje (zbiór 1)

Problem ZS

Opis problemu (ostatnia aktualizacja: 16 stycznia 2014; spis zmian)

Przykładowe instancje (zbiór 1) (aktualizacja: 21 stycznia 2014)

Realizacja zajęć

Tydzień 1.

W pierwszym tygodniu należy przygotować odpowiednie struktury danych, napisać wczytywanie danych instancji oraz wypisywanie rozwiązania. Należy też opracować podstawowy algorytm tworzenia dopuszczalnego, niekiepskiego rozwiązania.

Na zakończenie tygodnia (czyli na zajęcia 20 stycznia) należy przygotować raport podsumowujący wyniki pracy. Powinien on zawierać:

Każde uruchomienie dla każdej instancji powinno zakończyć się w ciągu 1 sekundy. Dla uproszczenia można liczyć czas wewnątrz programu, od momentu rozpoczęcia wczytywania danych instancji do momentu zakończenia wypisywania wyniku. W celu zwiększenia odporności programu sugerowane jest niezależne wypisywanie najlepszego znalezionego rozwiązania w osobnym wątku co np. 0,1 sekundy i zakończenie działania obliczeń (np. pętli while wewnątrz której następuje konstrukcja jednego rozwiązania) kiedy osiągnięty zostanie limit czasu.

Raport powinien mieć postać dokumentu w formacie PDF.

Tydzień 2.

W drugim tygodniu bazujemy na wynikach z pierwszej, zachłannej wersji algorytmu; najprostszym rozszerzeniem jest randomizacja algorytmu: zamiast zachłannie wybierać konkretne umieszczenie paczki lub połączenie towarów na nośniku można dopuścić wybór losowy z kilku dobrych pozycji czy połączeń. Innym pomysłem jest przeszukiwanie podprzestrzeni zawierającej ruchy umieszczające dowolnie kilka paczek czy łączące kilka towarów na nośniku.

Na tym etapie warto skorzystać z kilku wątków obliczeniowych. Każdy z wątków niezależnie może wyliczać jakieś zrandomizowane rozwiązanie. Następnie z uzyskanych rozwiązań wybieramy to, które ma najniższy koszt. Proces ten możemy wielokrotnie powtarzać, dopóki mieścimy się w limicie czasu.

Do kontrolowanej losowości polecam używanie obiektu klasy java.util.Random utworzonego na podstawie ziarna, którego wartość (być może losowa, np. new Random().nextLong()) jest logowana w przebiegu procesu. Umożliwi to powtórzenie konkretnego uruchomienia algorytmu losowego, np. w celu znalezienia błędu lub odtworzenia struktury rozwiązania.

Do uruchamiania wielu zadań równolegle można skorzystać z API java.util.concurrent.ExecutorService. Metoda invokeAll() ułatwi napisanie kodu wielowątkowego w proponowanym prostym modelu synchronicznym (nad kodem asynchronicznym należy się trochę bardziej napracować).


© Przemysław Wesołek, 2004–2013

Valid HTML 4.01! Valid CSS!