Badania Operacyjne - Laboratorium

Studia Stacjonarne, Automatyka i Robotyka, Semestr 5.

 

Cel zajęć:

  1. Projektowanie i implementacja aplikacji: „komputerowy system wspomagania procesu decyzyjnego”,
  2. Komputerowe badanie jakości wykonanych aplikacji

 

Zadania:

(1) w zakresie projektowania i kodowania. Wykonać aplikację realizującą następujące funkcje: 1. Wybór instancji problemu (z pliku, z klawiatury, losowo); 2. Wybór wariantu algorytmu konstrukcyjnego; 3. ustalenie parametrów algorytmu popraw; 4. Obliczenia (proces optymalizacji); 5. Prezentacja wyników obliczeń na monitorze komputera (funkcja celu, rozwiązanie, wykresy charakteryzujące przebieg procesu optymalizacji,...) 6. Konstrukcja menu obsługi aplikacji.

(2) w zakresie badania jakości wykonanej aplikacji. Badanie wpływu na przebieg/jakość procesu optymalizacji zastosowanego algorytmu konstrukcyjnego, sąsiedztwa w algorytmach popraw, operatorów genetycznych w badanych algorytmach ewolucyjnych i parametrów algorytmów.

(3) opracowanie sprawozdania. Sprawozdanie z ćwiczeń powinno zawierać kod aplikacji i zwięzły opis: 1) badanego problemu optymalizacji (zwykle jest to problem NP-trudny) 2)zastosowanej metody rozwiązania, 3)struktury algorytmu, 4)funkcji procedur algorytmu, 5)instrukcji obsługi aplikacji, 6)przykład numeryczny i/lub wnioski z przeprowadzonych eksperymentów komputerowych.

 

Bibliografia: materiały powielane (indywidualne dla każdego studenta) nt.

  1. analizowanego problemu
  2. algorytmów optymalizacji

 

Szczegółowy harmonogram zajęć: Badania Operacyjne – laboratorium:

Zajęcia 1.

Przedstawienie celu ćwiczeń laboratoryjnych. Przykłady rzeczywistych problemów optymalizacyjnych i decyzyjnych, wymagania dla czasu i jakości wyznaczonego rozwiązania. Złożoność obliczeniowa algorytmów (czasowa i pamięciowa). Metody przybliżone. Sprawy organizacyjne (tryb zaliczania, sposób przygotowania dokumentacji, kryteria oceny, ustalenie godzin konsultacji, podział na zespoły)

Zajęcia 2.

Modelowanie rzeczywistych problemów optymalizacyjnych i decyzyjnych. Celem zajęć jest sformułowanie dyskretnego modelu wybranego (rzeczywistego lub abstrakcyjnego) zagadnienia NP.-trudnego tzn. określenie: istotnych parametrów problemu, charakteru zależności między parametrami, ograniczeń zasobowych, funkcji celu (optymalizacja jedno lub wielokryterialna) oraz postaci rozwiązania. Implementacja struktur danych zgodnie z zadanym modelem.

Zajęcia 3.

Przykładowe algorytmy optymalizacji lokalnej – omówienie implementacji metody popraw (metody inauguracyjne, konstrukcja sąsiedztwa rozwiązania, poszukiwanie w głąb – z powrotami, wielostart). Przeprowadzenie eksperymentów obliczeniowych na stanowisku badawczym (implementacja algorytmu popraw) dla zestawu zadań testowych. Celem ćwiczenia jest włączenie do algorytmu dodatkowych mechanizmów, które przeciwdziałają „pułapce” ekstremum lokalnego.

Zajęcia 4.

Algorytm symulowanego wyżarzania – omówienie implementacji, parametrów algorytmu oraz interpretacji pierwowzoru metody. Przeprowadzenie eksperymentów obliczeniowych na stanowisku badawczym (implementacja algorytmu SA) dla zestawu zadań testowych. Celem ćwiczenia jest prawidłowy dobór parametrów algorytmu (temperatura początkowa, schemat chłodzenia, liczba iteracji w serii).

Zajęcia 5.

Algorytm poszukiwania z zabronieniami  (Tabu Search)– omówienie implementacji, parametrów algorytmu oraz mechanizmu zabronień. Przeprowadzenie eksperymentów obliczeniowych na stanowisku badawczym (implementacja algorytmu TS) dla zestawu zadań testowych. Celem ćwiczenia jest prawidłowy dobór mechanizmu zabronień, kryterium aspiracji i wielkości sąsiedztwa oraz określenie roli pamięci krótko-, długo- i średnio-terminowej.

Zajęcia 6.

Algorytmy ewolucyjne – omówienie głównych grup: algorytmy genetyczne, ewolucyjne i strategie ewolucyjne – różnice i cechy charakterystyczne.  Przykłady implementacji algorymu, sposób kodowania rozwiązania, przetwarzania populacji, typy operatorów, parametrów algorytmu oraz interpretacja pierwowzoru metody. Przeprowadzenie eksperymentów obliczeniowych na stanowisku badawczym (implementacja algorytmu AE) dla zestawu zadań testowych. Celem ćwiczenia jest prawidłowy dobór elementów i parametrów algorytmu (wielkość populacji, mechanizm selekcji, zbiór operatorów, prawdopodobieństwo ich użycia).

Zajęcia 7.

Metody hybrydowe – omówienie sposobów hybrydyzacji algorytmów. Celem ćwiczenia jest określenie możliwych schematów hybrydyzacji dwóch wybranych typów algorytmów.

Zajęcia 8/9.

Indywidualne omówienie implementacji zadanej metody przybliżonej dla zdefiniowanego wcześniej modelu zagadnienia. Implementacja algorytmu przy użyciu wybranego narzędzia programistycznego.

Zajęcia 10/11.

Interfejs oprogramowania optymalizacyjnego (omówienie) – podstawowe funkcje, wizualizacja wyników, prezentacja przebiegu procesu optymalizacji i istotnych parametrów do oceny efektywności algorytmu. Opracowanie i implementacja interfejsu  dla wcześniej zadanego zagadnienia i algorytmu.

Zajęcia 12/13.

Testowanie algorymu (omówienie) – rodzaje zadań testowych, przypadki złośliwe, statystyczne opracowanie wyników eksperymentu, badanie efektywności algorytmu dla różnych wartości parametrów (dobór), określenie złożoności czasowej i pamięciowej.

Zaprojektowanie i przeprowadzenie eksperymentów oraz opracowanie wyników (wnioski).

Zajęcia 14/15.

Prezentacja wykonanego oprogramowania, dokumentacji i wyników przeprowadzonych badań testowych. Dyskusja i ocena.