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ń i jakość generowanych rozwiązań), 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ć na przedostatnich zajęciach laboratoryjnych w semestrze, ostatnie zajęcia laboratoryjne przeznaczone są na wystawienie oceny.