Zaawansowane techniki optymalizacji

Informacje ogólne


  • W kwestiach nieopisanych tutaj obowiązują ogólne zasady prowadzenia zajęć
  • Zasady i harmonogram zajęć [PDF].
  • Lista problemów [PDF].
  • Kody źródłowe generatorów instancji (z wyjątkiem zajęć 1–2) [ZIP].
  • Skrypt do generacji twarzy Chernoffa (na zajęcia 13–14) [PLIK].
  • Poradnik badania i tworzenia wykresów [PLIK].
  • Kod LaTeX do wizualizacji [LINK].

Instrukcje laboratoryjne


  • Temat 1 (zajęcia 1–2): MS Excel [PDF].
  • Temat 2 (Zajęcia 3–4): ILOG [PDF].
  • Temat 3 (Zajęcia 5–6): CPLEX [PDF].
  • Temat 4 (Zajęcia 7–8): Drzewa [PDF].

Struktury danych (wykład)

Prezentacje z wykładu


Administrowanie sieciowymi systemami operacyjnymi (laboratorium)

Informacje ogólne


  • W kwestiach nieopisanych tutaj obowiązują ogólne zasady prowadzenia zajęć
  • Na każdym laboratorium (z wyjątkiem pierwszych zajęć) należy wykonać zadania z instrukcji.
  • Praca odbywa się z użyciem maszyn wirtualnych i systemu operacyjnego Debian w wersji 9 lub nowszego.
  • Pracujemy bez trybu graficznego (chyba że zadanie jawnie na to pozwala).
  • Podstawą oceny są sprawozdania (opisane poniżej).

Sprawozdania


  • Zasadniczym celem sprawozdania jest objaśnienie ogólnej metody wykonywania zadania i wykonanych czynności (formuła zbliżona do instrukcji laboratoryjnej).
  • Sprawozdanie powinno zawierać opis najważniejszych wykonanych czynności (wykonane komendy, edycja plików). Uzyskane efekty można ukazać za pomocą zrzutów ekranu.
  • Dobrze jest zawczasu podczas laboratorium wykonywać zrzuty ekranu lub wspomóc się poleceniem script, które zapisuje sesję pracy z konsolą (zarówno wejście jak i wyjście).
  • Strona estetyczna sprawozdania nie jest bardzo istotna, należy jednak zwracać uwagę na stosowanie odpowiedniego języka (techniczny, nie potoczny).
  • Sprawozdania wyłącznie w postaci PDF-a należy przesyłać na adres prowadzącego z tematem maila postaci [asso][indeks]lab], gdzie indeks to 6-cyfrowy numer indeksu a lab to numer laboratorium (od 2 do 8). Przykładowy temat maila: [asso][123456][2].
  • W przypadku laboratoriów 2–7, termin presłania sprawozdania to 2 tygodnie. Sprawozdanie z labratorium 8 (ostatniego) należy przesłać możliwie szybko ze względu na konieczność wystawienia ocen w systemie.

Instrukcje laboratoryjne


  1. Zajęcia 2 (instalacja systemu operacyjnego)

    • Instrukcja: [PDF].
    • Przy aktualizacji pakietów może wystąpić "błąd" próby pobrania repozytorium z cdrom. W takim przypadku należy wyedytować plik /etc/apt/sources.list (wymaga to uprawnień roota, patrz poniżej). Edycja będzie najłatwiejsza przy użyciu edytora nano. Należy zakomentować znakiem # linijkę odpowiedzialną za repozytoria cdromu (albo przesunąć ją na sam dół) i odkomentować 2 linijki repozytoriów przy końcu pliku. Jeśli to nie pomoże konieczne może być dodanie innych repozytoriów. Plik po edycji należy zapisać.
    • W przypadku konieczności wykonania komendy z uprawnieniami roota można posłużyć się jednym z poniższych sposobów:
      1. Zalogować się jako root w top-level console. Aby przejść do logowania można albo przełączyć się na inną top-level konsolę (poprzez Ctrl+F1 do F8) albo całkowicie wylogować się przez komendę exit (do skutku).
      2. Wykonanie komendy su. Komenda domyślnie przełączy nas na roota (poprawność można sprawdzić komendą id). Ważne: podajemy hasło tego na kogo się przełączamy (czyli zwykle roota).
      3. Wykonanie komendy sudo. W tym przypadku najczęściej podaje się od razu komendę do wykonania. Ważne: podajemy nasze hasło (użytkownika wykonującego sudo), a nie hasło roota. Głównym problemem jednak jest to, że sudo może być "zablokowane". Aby dało się tę komendę wykonać należy zrobić jedno z dwojga:
        • dodać naszego użytkownika do grupy sudo np. poprzez odpowiednie użycie komendy typu usermod, adduser lub useradd.
        • dokonać edycji pliku /etc/sudoers poprzez dodanie na końcu linijki postaci user ALL=(ALL:ALL) ALL, gdzie user to nazwa naszego użytkownika.
    • Jeśli system nie wykrywa komendy, mimo że powinna być, to należy sprawdzić czy nie można jej wywołać z jawną ścieżką (np. /bin/komenda, /bin/usr/komenda lub /sbin/komenda).

  2. Zajęcia 3 (organizacja systemu operacyjnego)

  3. Zajęcia 4 (sieć, NAT, DHCP)

  4. Zajęcia 5 (użytkownicy)

Administrowanie sieciowymi systemami operacyjnymi (wykład)

Prezentacje z wykładu


  • Wykład 1 (wprowadzenie do zajęć) [PDF]
  • Wykład 2 (system, moduły, powłoka) [PDF]
  • Wykład 3 (konfiguracja sieci) [PDF]
  • Wykład 4 (NAT i system plików) [PDF]
  • Wykład 5 (użytkownicy i autoryzacja) [PDF]

Algorytmy optymalizacji (projekt)

Informacje ogólne


  • W kwestiach nieopisanych tutaj obowiązują ogólne zasady prowadzenia zajęć.
  • Zajęcia polegają na implementacji i kalibracji zadanego algorytmu metaheurystycznego dla zadanego problemu optymalizacji dyskretnej oraz wykonaniu badań.
  • Projekt realizowany jest indywidualnie (grupy jednosobowe).
  • Etapy oraz ich terminy opisane są w dalszej częsci strony.
  • Po uzyskaniu pozytywnej oceny z implementacji, kod źródłowy należy przesłać na email prowadzącego. Email musi być wysłany z domeny @student.pwr.edu.pl, a jego nagłówek musi zawierać ciąg w formie [ao][album][kod] gdzie album to 6-cyfrowy numer indeksu studenta. Przykładowy nagłówek: [ao][123456][kod]. Nie należy stosować dodatkowych spacji i innych znaków.
  • Przesłanie sprawozdania odbywa się podobnie, z tym, że nagłówek maila ma formę [ao][album][spr] i odwrotna jest kolejność (najpierw wysyłane jest sprawozdanie, a potem wystawiana jest z niego ocena).

Etap 1. Ustalenie tematu.


  • W odpowiednim terminie (harmonogram poniżej) należy ustalić temat tzn. rozwiązywany problem oraz stosowaną metaheurystykę. Zasady przydziału podane zostaną na zajęciach.
  • Możliwe są następjące problemy optymalizacji dyskretnej:
    • TSP – ogólny problem komiwojażera.
    • ETSP – euklidesowy problem komiwojażera.
    • VRP – problem marszrutyzacji (minimalizacja maksymalnej trasy, jedna baza, dowolna liczba pojazdów, brak ograniczeń pojemności i długości trasy dla pojazdów).
    • wiTi – jednomaszynowy problem minimalizacji ważonego spóźnienia zadań.
    • PFSP – permutacyjny problem przepływowy (dla dowolnej liczby maszyn).
    • DKP – dyskretny problem plecakowy.
  • Możliwe są następjące metody metaheurystyczne:
    • TS – poszukiwanie z zakazami.
    • SA – symulowane wyżarzanie.
    • GA – algorytm genetyczny.
    • ACO – algorytm mrówkowy.
    • ABC – sztuczna kolonia pszczół.
    • ILS – iterated local search.
    • VNS – variable neighborhood search.
  • Wolne tematy:
    • Dla TSP – brak.
    • Dla ETSP – brak.
    • Dla VRP – wszystko poza GA, SA i ABC.
    • Dla wiTi – wszystko poza TS i GA.
    • PFSP – wszysko poza GA.
    • DKP – wszystko poza GA i SA.

Etap 2. Implementacja.


  • Etap polega na implementacji (i ewentualnie wstępnej kalibracji) zadanego algorytmu metaheurystycznego dla zadanego problemu.
  • Etap obejmuje też przygotowanie sposobu wczytania/generacji danych wejściowych.
  • Celem jest stworzenie algorytmu dopracowanego wysokiej jakości, należy więc zadbać, by można było konrolować różne aspekty algorytmu (wartość i typ warunku stopu, rodzaj sąsiedztwa/operatora genetycznego, kontrola parametrów, warianty z optymalizacją lub bez, wykorzystanie szczególnych cech problemu itd.).
  • Można stworzyć kilka wariantów algorytmu (każdy z odpowiednimi argumentami do kontroli działania), albo jeden wariant z większą liczbą parametrów sterujących.
  • Można korzystać z równoleglenia obliczeń, ale nie jest to wymagane (dla wielu algorytmów jest to trudne).
  • Należy pamiętać, że dla niektórych parametrów (np. liczba iteracji, rozmiar populacji) możliwymi wartościami są nie tylko stałe (20, 30), ale wartości zależne od rozmiaru problemu N np. sqrt(N), 10(sqrt(N), sqrt(10N), N, 10N itd.
  • Ocena zależy też od zaawansowanie algorytmu (w sensie użytych technik), przy czym możliwości są zależne od zadanej metaheurystyki/problemu.
  • Poniżej jest lista elementów/parametrów/mechanizmów możliwych do zaimplementowania/ustawiania (pomijając podstawowe parametry liczbowe dla każdego z algrorytmów):
    • TS – poszukiwanie z zakazami:
      • typ sąsiedztwa/ruchu,
      • część (procent) sąsiedztwa która podlega przeglądowi,
      • rodzaj listy tabu (pamięci krótkoterminowej,
      • kryterium aspiracji,
      • pamięć długoterminowa,
      • rozwiązanie początkowe,
      • optymalizacje (np. dla niektórych problemów/sąsiedztw można przyspieszyć czas liczenia wartości funkcji celu sąsiada).
    • SA – symulowane wyżarzanie:
      • typ sąsiedztwa/ruchu,
      • schemat chłodzenia,
      • temperatura początkowa,
      • epoki,
      • przeciwdziałanie stagnacji (np. podnoszenie temperatury),
      • rozwiązanie początkowe,
      • optymalizacje (np. dla niektórych problemów/sąsiedztw można przyspieszyć czas liczenia wartości funkcji celu sąsiada).
    • GA – algorytm genetyczny:
      • typ operatora krzyżowania,
      • typ operatora mutacji,
      • typ operatora selekcji (sposób wyboru rodziców i/lub sposób określenia nowej populacji na podstawie starej),
      • skład populacji początkowej,
      • poprawa rozwązania (algorytm memetyczny),
      • podpopulacje (algorytm wyspowy),
      • elitaryzm.
    • ACO – algorytm mrówkowy:
      • strategia określenia począkowego feromonu,
      • strategia dodawania feromonu (w tym częstość i ilość),
      • strategia parowania feromonu.
    • ABC – sztuczna kolonia pszczół:
      • sposób wyboru modyfikacji rozwiązania (często sprowadza się to do typu sąsiedztwa jak w TS/SA lub typu operatora krzyżowania jak w GA).
      • strategia tworzenia nowych rozwiązań (inna niż całkowicie losowe rozwiązanie).
  • Algorytm powininen na początku wydrukować wynik początkowy (wartość funkcji celu początkowego rozwiązania/najlepszego rozwiązania z populacji początkowej), a potem na bieżąco raportować wartość funkcji celu, pokazując poprawy (i tylko poprawy!) najlepszego znanego rozwiązania wraz z numerem iteracji. Na koniec należy pokazać właściwe uzyskane rozwiązanie (np. permuacja dla problemu komiwojażera). Przykład dla problemu komiwojażera dla 10 miast:
    • 0    2149
    2    2123
    4    2098
    9    2075
    17   2042
    28   2029
    35   2015
    37   2008
    53   1983
    84   1972
    115  1932
    176  1895
    3, 4, 9, 6, 1, 7, 8, 0, 5, 2

Etap 3. Badania i sprawozdanie.


  • Etap polega na wykonaniu badan zaimplementowanego algorytmu z użyciem istniejących lub wygenerowanych instancji (danych) testowych.
  • Badamy wpływ parametrów/wariantów algorytmu na jego jakość oraz złożoność czasową.
  • Należy przedstawić wnioski oraz zalecany sposób kalibracji algorytmu (wariant, który działał najlepiej).
  • Ocena zależy też od wiarygodności uzyskanych wyników (dobór danych testowych, sposób wykonywania pomiarów, analiza wyników, testy statystyczne itp.).

Harmonogram zajęć



Poniżej znajdują się terminy poszczególnych etapów dla poszczególnych grup. Etapy można oddawać przed terminem. Spóźnienie wiąże się z obniżeniem oceny o co najmniej 0.5.

Grupa Nieparzysta (nr 8) Parzysta (nr 7)
Ustalenie tematu 13.03 06.03
Implementacja 08.05 15.05
Badania 05.06 12.06