algorytmy heurystyczne

Wiele zagadnień algorytmicznych, inżynierskich czy ekonomicznych ma postać zadań optymalizacyjnych. W zadaniach optymalizacyjnych mamy do czynienia ze zbiorem rozwiązań i funkcją ich oceny, która każdemu rozwiązaniu przypisuje wartość, będącą miarą jego jakości. Zadanie optymalizacyjne polega na znalezieniu rozwiązania najlepszego pod względem jakości. W zależności od tego jak się określi jakość, zadanie sprowadza się do znalezienia rozwiązania o minimalnej albo maksymalnej wartości funkcji oceny.

Istnieją wyspecjalizowane metody algorytmiczne do efektywnego rozwiązywania pewnych grup zadań optymalizacyjnych. Algorytm jest efektywny, jeśli koszt jego wykonania mierzony czasem wykonania jest wielomianowo wielki względem rozmiaru danych. Dla wielu ważnych z praktycznego punktu widzenia zadań optymalizacyjnych nie znaleziono jednak żadnych efektywnych algorytmów, a perspektywa ich odkrycia w przyszłości wydaję się bardzo wątpliwa. Grupę takich problemów w wersji decyzyjnej nazywamy problemami NP-zupełnymi.

Dla zadań, w których mamy do czynienia z dużymi przestrzeniami rozwiązań, ważne jest wczesne odrzucenie nieobiecujących kierunków poszukiwania. Zapewnia to ogromne oszczędności na kosztach obliczeniowych, a w rezultacie przyspiesza znalezienie rozwiązania. Alternatywą dla tradycyjnych algorytmów rozwiązujących zadania optymalizacyjne są metody heurystyczne. Heurystyka to zbiór specyficznych dla danego zadania reguł, które mogą dopomóc w odkryciu jak najlepszego rozwiązania. Tradycyjne sposoby przeszukiwania zbioru rozwiązań zależały jedynie od informacji dostarczanej przez dotychczas zbadane elementy tego zbioru. Można jednak stworzyć inny rodzaj strategii, która dzięki odpowiedniej heurystyce pozwala uwzględnić informacje o niezbadanej jeszcze części przestrzeni rozwiązań. Heurystyki są to więc wszelkie metody pozwalające algorytmowi poszukującemu rozwiązania pójść "na skróty". Skuteczności kroków heurystycznych nie można w pełni udowodnić teoretycznie, można jedynie pokazać doświadczalnie ich trafność.

Terminarz

  • seminarium: czwartek 10-12 s.103
  1. 4 marca 2010: Przydział tematów.
  2. 11 marca 2010: Trudne zadania decyzyjne i optymalizacyjne (B.Kobyłecki).
  3. 18 marca 2010: Algorytmy z nawrotami (K.Sornat).
  4. 25 marca 2010: Metoda podziału i ograniczeń (M.Macheta).
  5. 1 kwietnia 2010: Algorytmy przeszukiwania lokalnego (M.Kulus).
  6. 8 kwietnia 2010: Symulowane wyżarzanie (K.Kaniewski).
  7. 22 kwietnia 2010: Przeszukiwanie z tabu (Ł.Perzyński).
  8. 29 kwietnia 2010: Przeszukiwanie rozproszone (Ł.Kornek).
  9. 6 maja 2010: Algorytmy ewolucyjne (A.Łańcucki).
  10. 20 maja 2010: Systemy mrówkowe (K.Piecuch).
  11. 27 maja 2010: Rój cząsteczek (T.Wasilczyk).
  12. 17 czerwca 2010: Oceny zaliczeniowe.

Seminarium

Zasady
przydział tematów
Na pierwszych zajęciach studenci wybierają tematy do opracowania. Student powinien zapoznać się z tematami na pierwszych zajęciach (lista tematów jest dostępna na tej stronie). Do niektórych tematów mogą się zgłosić dwie osoby.
prezentacja
W wyznaczonym terminie student powinien dać wykład na wybrany przez siebie temat; do wykładu powinna być przygotowana prezentacja. Tydzień przed wykładem należy ze mną skonsultować treść prezentowanego materiału.
opracowanie
Wybrany temat student ma opracować pisemnie i dostarczyć mi to opracowanie w formie elektronicznej (należy go przygotować w LaTeX'u lub innym popularnym formacie i dostarczyć mi plik źródłowy oraz pdf'a). Opracowanie powinno zawierać następujące elementy:
  1. imię i nazwisko prelegenta,
  2. ogólny opis prezentowanej metody czy zagadnienia,
  3. rys historyczny badań związanych z omawianym zagadnieniem,
  4. prezentacje algorytmu, jego analizę i przykłady zadań rozwiązywanych tą metodą,
  5. przykład programu wykorzystującego przedstawioną metodę do rozwiązania wybranego zadania,
  6. szczegółową bibliografię.
Gotowe opracowanie należy przesłać mi mailem (pliki tex i pdf) po wygłoszonym wykładzie. Opracowania te będę udostępniać w sieci (na tej stronie).
oceny
Ocenie będzie podlegać:
  1. przede wszystkim pisemne opracowanie zagadnienia,
  2. wystąpienie przed słuchaczami,
  3. program rozwiązujący wybrane zadanie za pomocą opracowanej metody,
  4. obecność i aktywność na zajęciach.
Warunkiem koniecznym uzyskania zaliczenia jest obecność na 70% zajęć z wystąpieniami oraz starannie zrobione opracowanie pisemne wybranego zagadnienia.
Opracowania
  1. B.Kobyłecki: trudne zadania decyzyjne i optymalizacyjne. (11.03.2010)
    - - - brak materiałów !!!
  2. K.Sornat: algorytmy z nawrotami. (18.03.2010)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowe programy: kod źródłowy (haskell) / kod źródłowy (prolog)
  3. M.Macheta: metoda podziału i ograniczeń. (25.03.2010)
    - - - brak materiałów !!!
  4. M.Kulus: algorytmy przeszukiwania lokalnego. (1.04.2010)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowy program: archiwum rar (C#)
  5. K.Kaniewski: symulowane wyżarzanie. (8.04.2010)
    - - - brak materiałów !!!
  6. Ł.Perzyński: przeszukiwanie z tabu. (22.04.2010)
    slajdy z prezentacji (pdf)
    - brak opracowania -
    - brak przykładowego programu -
  7. Ł.Kornek: przeszukiwanie rozproszone. (29.04.2010)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowy program: kod źródłowy (python)
  8. A.Łańcucki: algorytmy ewolucyjne. (6.05.2010)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowy program: archiwum tar (C++)
  9. K.Piecuch: systemy mrówkowe. (20.05.2010)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowy program: kod źródłowy (C++)
  10. T.Wasilczyk: rój cząsteczek. (27.05.2010)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    - brak przykładowego programu -
  11. M.Skórzewski: sortowanie adaptywne. (10.06.2010)
    slajdy z prezentacji (pdf)
    artykuł przeglądowy: A Survey of Adaptive Sorting Algorithms (pdf)
Ranking

Ogłoszenia

1.06.2010
Na ostatnim spotkaniu seminaryjnym 10.06.2010 Marcin Skórzewski opowie o sortowaniu adaptacyjnym.
24.05.2010
Kolejne najbiższe spotkanie w przyszłym tygodniu na 27.05.2010 odbędzie się o godzinie 8:45 w sali 325.
15.05.2010
Najbiższe spotkanie w przyszłym tygodniu na 20.05.2010 odbędzie się o godzinie 9:00 w sali 325.
4.03.2010
Pierwsze wystąpienie już w przyszłym tygodniu na 11.03.2010! Proszę o punktualne przybycie.
4.03.2010
Są jeszcze nieobsadzone tematy (to te przy których widnieje wielokropek zamiast nazwiska).
1.03.2010
W tym miejscu będą się pojawiać ogłoszenia organizacyjne dotyczące mojej grupy seminaryjnej.

powrót na początek strony