Celem ćwiczeń laboratoryjnych jest projektowanie, implementacja i numeryczne badanie algorytmów przybliżonych wyznaczających w czasie rzeczywistym decyzje sterujące.
Program:
Zajęcia 1.
I. Wprowadzenie w tematykę zajęć w ramach LBO:
II. Ogólna postać liniowego zdania dyskretnego.
III. Złożoność obliczeniowa algorytmów.
IV. Klasy złożoności obliczeniowej.
a. Podział problemów na klasy złożoności obliczeniowej – maszyna Turinga,
b. Klasy zagadnień decyzyjnych i optymalizacyjnych. Zagadnienia: P, NP, NP- zupełne, NP-trudne,
V. Podział studentów na grupy laboratoryjne oraz przydzielenie tematów opracowywanych algorytmów.
VI. Konsultacje przydzielonych tematów w ramach grup – modyfikacje zagadnienia.
Zajęcia 2.
I. Metody dokładne v. Metody przybliżone:
a. Algorytmy dedykowane
b. Metody dokładne i ich ograniczenia
II. Metody przybliżone – podział metod przybliżonych
III. Konsultacje tematów przydzielonych w ramach laboratorium
Zajęcia 3.
I. Geneza zastosowania heurystyk w rozwiązywaniu dyskretnych zagadnień optymalizacyjnych.
II. Omówienie genezy i zastosowania metod ograniczonego przeglądu, metod konstrukcyjnych oraz algorytmu popraw
·
Metody ograniczonego przeglądu LEM (ang. Limited Enumeration Methods).
· Metody konstrukcyjne - CM (ang. Construction Methods).
· Algorytmy lokalnych popraw.
III. Konsultacje tematów przydzielonych w ramach laboratorium.
Zajęcia 4.
I. Algorytm Taboo Search jako technika pozwalająca na ominięcie lokalnych optimów. Podstawowe elementy składające się na algorytm TS, omówienie wariantów algorytmu TS.
II. Zastosowanie heurystyk do rozwiązywania zagadnienia przydziału.
III. Konsultacje tematów przydzielonych w ramach laboratorium.
Zajęcia 5.
I. Algorytm symulowanego wyżarzania – SA (ang. simulation annealing) jako przykład zastosowania analogii pomiędzy mechaniką statystycznej a optymalizacją kombinatoryczną. Algorytm podstawowy, omówienie cech algorytmu SA.
II. Zastosowanie heurystyk do rozwiązywania zagadnienie komiwojażera.
III. Konsultacje tematów przydzielonych w ramach laboratorium.
Zajęcia 6.
I. Algorytmy ewolucyjne – EA (ang. evolution algorithms) jako przykład metody poszukiwania rozwiązań zagadnień kombinatorycznych mającej korzenie w genetyce oraz naturalnej selekcji. Podstawowe elementy EA, podział EA, cechy algorytmów ewolucyjnych.
II. Zastosowanie heurystyk do rozwiązywania problemu harmonogramowania - PFn||Cmax .
III. Konsultacje tematów przydzielonych w ramach laboratorium.
Zajęcia 7.
I. Kryteria oceny projektów w ramach LBO:
· Algorytm: poprawność implementacji, propozycje własnych rozwiązań, wielowariantowość, dostosowanie do specyfiki problemu
· Aplikacja: sposób prezentacji uzyskanych rozwiązań, istotnych parametrów algorytmu, poprawność działania, strona graficzna, złożoność, funkcjonalność.
II. Dokumentacja: kompletność, adekwatność do wymagań, strona edytorska.
III. Konsultacje tematów przydzielonych w ramach laboratorium.
Zajęcia 8.
I. Algorytmy mrówkowe - AS (ang. Ant System) jako przykład metody poszukiwania rozwiązań zagadnień kombinatorycznych w oparciu mającej korzenie w genetyce oraz naturalnej selekcji. Podstawowe elementy EA, podział EA, cechy algorytmów ewolucyjnych.
II. Zastosowanie heurystyk dla rozwiązywania zagadnienie plecakowego całkowitoliczbowego.
III. Konsultacje tematów przydzielonych w ramach laboratorium.
Zajęcia 9.
I. Metodyka testowania algorytmów przybliżonych:
· Określenie reprezentatywnego zestawu zadań, parametry charakteryzujące zagadnienia testowe,
· przypadki „złośliwe”, statystyka testów, analiza efektywności wariantów algorytmu.
II. Konsultacje tematów przydzielonych w ramach laboratorium
Zajęcia 10.
Prezentacja, omówienie oraz ocena projektów wykonanych przydzielonych poszczególnym grupom.
Bibliografia:
1. Materiały prowadzącego– opisy algorytmów i problemów optymalizacyjnych dostarczane indywidualnie poszczególnym studentom.