Zaawansowane programowanie - zaliczenie

Przedmiot prowadzony jest wspólnie z dr. Marcinem Radomem, którego wymagania obowiązują niezależnie od poniżej sformułowanych. Ocena końcowa z projektu realizowanego na laboratorium zostanie wystawiona wspólnie przez prowadzących. Na zajęciach laboratoryjnych każda osoba pracuje indywidualnie.

Realizacja projektu obejmuje zaprojektowanie, zaimplementowanie i przetestowanie jednej metaheurystyki − algorytmu genetycznego albo tabu search, o wielomianowej złożoności czasowej − dla jednego wybranego problemu spośród podanych. Algorytm musi zwracać na wyjściu całe rozwiązanie wraz z wartością funkcji celu. Dodatkowo należy zaimplementować procedurę generującą nietrywialne instancje w sposób losowy, z parametrami pozwalającymi na utworzenie instancji o różnym stopniu trudności, zwłaszcza dużych. Generator instancji powinien mieć opcję wprowadzenia zadanej liczby błędów do instancji, o której wiadomo, jakie rozwiązanie optymalne posiada, w celu umożliwienia późniejszego oszacowania (w przybliżeniu) jakości uzyskanych rozwiązań. Powinna istnieć możliwość wprowadzenia zmian przez użytkownika do wygenerowanej losowo instancji w wybranych przez niego miejscach, także wypełnienia jej w całości przez użytkownika (edycja pustego wzorca). Instancja podawana na wejście metaheurystyki musi zostać odpowiednio przesortowana w celu utraty informacji o oryginalnym rozwiązaniu. Metaheurystyki mają być specjalizowane, tzn. dostosowane do właściwości konkretnego problemu w celu optymalizacji jakości otrzymywanych rozwiązań. Na ocenę wpłynie m.in. oryginalność i zaawansowanie metod, jakość generowanych rozwiązań (odległość od optimum wartości funkcji celu otrzymanego rozwiązania) i czas obliczeń.

W sprawozdaniu należy zamieścić m.in. opis słowny metod zastosowanych do rozwiązania problemu oraz do generowania instancji, wyniki obszernych testów na instancjach o różnym stopniu trudności (czas obliczeń, wartość funkcji celu, odległość od optimum), wnioski obejmujące plusy i minusy zaproponowanej metaheurystyki. Pożądane są zrzuty ekranowe kluczowych etapów programu (ustawianie parametrów generatora instancji, ustawianie parametrów metaheurystyki, wizualizacja rozwiązania, itp.). Testy powinny zostać przeprowadzone na instancjach, dla których możemy w przybliżeniu oszacować optymalną wartość funkcji celu, w celu porównania z wygenerowanym rozwiązaniem przybliżonym. Rozmiar instancji powinien rosnąć aż do momentu, gdy metaheurystyka zacznie generować słabe rozwiązania. Dla każdego testowanego rozmiaru należy wygenerować instancje o różnym odsetku błędów. Dla każdego zestawu takich samych wartości parametrów generatora instancji należy wygenerować po co najmniej 10 różniących się losowo instancji (w celu uśrednienia wyników). Należy przetestować różne zestawy wartości parametrów metaheurystyki. Sprawozdanie należy oddać w przedostatnim tygodniu zajęć w semestrze, odbiór projektów i wystawienie oceny nastąpią w ostatnim tygodniu zajęć.

Na zaliczenie wszystkie wymienione elementy projektu muszą być zrealizowane, ale można pójść łatwiejszą ścieżką w opcji na ocenę 3.0 i zrealizować je na minimalnym poziomie nadal spełniającym postawione wymagania: prostsza wersja metaheurystyki, mniej testów, mniej wniosków. Przy wyborze tej opcji proszę ją zaznaczyć na wstępie sprawozdania. W szczególności za takie prostsze podejście zostaną uznane metaheurystyki, w których nie położono odpowiedniego nacisku na dostosowanie do właściwości rozwiązywanego problemu (stosunkowo przypadkowe dobranie komponentów metody, brak uzasadnienia ich użycia), pozbawione zostały bardziej wyrafinowanych mechanizmów wychodzenia z lokalnego optimum, w efekcie uzyskiwane rozwiązania okazują się bardzo dalekie od oczekiwań (ale zawsze muszą być rozwiązaniami dopuszczalnymi dla danego problemu).