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.5 (P.Rzechonek)
  1. 12 marca 2009: Zadania decyzyjne i optymalizacyjne (S.Fabiszewska).
  2. 19 marca 2009: Metoda podziału i ograniczeń (S.Zawadzki).
  3. 26 marca 2009: Algorytmy z nawrotami (Ł.Piątek).
  4. 26 marca 2009: Klasyfikacja heurystyk przeszukiwania. Algorytmy przeszukiwania lokalnego. (S.Góra)
  5. 2 kwietnia 2009: Systemy mrówkowe (M.Imos).
  6. 9 kwietnia 2009: Przeszukiwanie z tabu (M.Kupisiewicz).
  7. 16 kwietnia 2009: Symulowane wyżarzanie (M.Krupowicz).
  8. 23 kwietnia 2009: Przeszukiwanie rozproszone (P.Caban).
  9. 30 kwietnia 2009: Algorytmy ewolucyjne (B.Szymanek).
  10. 7 maja 2009: EDA (D.Boszko).
  11. 21 maja 2009: Rój cząsteczek (E.Balewicz).
  12. 28 maja 2009: Systemy immunologiczne (J.Cecki).
  13. 28 maja 2009: Sztuczne życie (M.Charatonik).
  14. 4 czerwca 2009: Sieci neuronowe (R.Szampera).
  15. 18 czerwca 2009: Systemy ekspertowe (M.Chęciński).

Seminarium

Zasady
przydział tematów
Na pierwszych zajęciach studenci wybierają tematy do opracowania. Student powinien zapoznać się z tematami przed pierwszymi zajęciami (lista tematów jest dostępna na tej stronie). Do jednego tematu mogą się zgłosić co najwyżej dwie osoby.
prezentacja
W wyznaczonym terminie student powinien dać wykład na wybrany przez siebie temat. 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). 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ólową 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 (70%),
  2. wystąpienie przed słuchaczami (30%) oraz
  3. obecność i aktywność na zajęciach.
Warunkiem koniecznym uzyskania zaliczenia jest obecność na 70% zajęć i zaakceptowane przeze mnie pisemne opracowanie wybranego zagadnienia.
Tematy
  1. Zadania decyzyjne i optymalizacyjne. Klasy problemów P i NP. Weryfikacja w czasie wielomianowym. Redukowalność problemów. Problemy NP-zupełne. (S.Fabiszewska)
  2. Algorytmy z nawrotami. Metoda podziału i ograniczeń. [temat mogą opracować 2 osoby] (Ł.Piątek, S.Zawadzki)
  3. Algorytm pełnego przeglądu zbioru rozwiązań. Pojęcie heurystyki. Klasyfikacja heurystyk przeszukiwania. Algorytmy przeszukiwania lokalnego. [temat mogą opracować 2 osoby] (S.Góra)
  4. Symulowane wyżarzanie. (M.Krupowicz)
  5. Przeszukiwanie z tabu. (M.Kupisiewicz)
  6. Algorytmy ewolucyjne. (B.Szymanek)
  7. EDA. (D.Boszko)
  8. Przeszukiwanie rozproszone. (P.Caban)
  9. Systemy mrówkowe. (M.Imos)
  10. Rój cząsteczek. (E.Balewicz)
  11. Systemy immunologiczne. (J.Cecki)
  12. Sieci neuronowe. (R.Szampera)
  13. Sztuczne życie. (M.Charatonik)
  14. Systemy ekspertowe. (M.Chęciński)
Opracowania
  1. S.Fabiszewska: zadania decyzyjne i optymalizacyjne. (12.03.2009)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
  2. Ł.Piątek: Algorytmy z nawrotami. (26.03.2009)
    brak materiałów
  3. S.Zawadzki: Metoda podziału i ograniczeń. (19.03.2009)
    opracowanie (pdf)
  4. S.Góra: Klasyfikacja heurystyk przeszukiwania. Algorytmy przeszukiwania lokalnego. (26.03.2009)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowe programy (rar)
  5. M.Imos: Systemy mrówkowe. (2.04.2009)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowe programy (rar)
  6. M.Kupisiewicz: Przeszukiwanie z tabu. (9.04.2009)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    inne materiały: [1] [2] [3]
  7. M.Krupowicz: Symulowane wyżarzanie. (16.04.2009)
    slajdy z prezentacji (pdf)
    przykładowy program (py)
  8. P.Caban: Przeszukiwanie rozproszone. (23.04.2009)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowy program (zip)
  9. B.Szymanek: Algorytmy ewolucyjne. (30.04.2009)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowe programy (rar)
  10. D.Boszko: EDA. (7.05.2009)
    brak materiałów
  11. E.Balewicz: Rój cząsteczek. (21.05.2009)
    brak materiałów
  12. J.Cecki: Systemy immunologiczne. (28.05.2009)
    slajdy z prezentacji (pps)
    opracowanie (pdf)
  13. M.Charatonik: Sztuczne życie. (28.05.2009)
    slajdy z prezentacji (pdf)
    opracowanie (pdf)
    przykładowe programy (rar)
  14. R.Szampera: Sieci neuronowe. (4.06.2009)
    slajdy z prezentacji (odp)
    opracowanie (pdf)
    przykładowe programy (zip)
Ranking

Ogłoszenia

26.02.2009
Pierwsze wystąpienie zaplanowane jest na 12.03.2009.
1.02.2009
W tym miejscu będą się pojawiać ogłoszenia organizacyjne dotyczące mojej grupy seminaryjnej.

powrót na początek strony