algorytmy heurystyczne (semestr letni 2010/11)

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ść.

Wymagane przygotowanie

• Zaliczony przedmiot algorytmy i struktury danych.
• Zaliczony przedmiot matematyka dyskretna.

Literatura

Literatura podstawowa:

• K.Trojanowski: Metaheurystyki praktycznie. Wydawnictwo WIT, Warszawa 2005.

Literatura uzupełniająca:

• K.Grygiel: Metaheurystyki. Notatki do wykładu. Uniwersytet Warszawski 2004.
• D.E.Goldberg: Algorytmy genetyczne i ich zastosowania. WNT, Warszawa 2003.
• Z.Michalewicz: Algorytmy genetyczne + struktury danych = programy ewolucyjne. WNT, Warszawa 2003.
• J.Arabas: Wykłady z algorytmów ewolucyjnych. WNT, Warszawa 2004.

Terminarz

Cotygodniowe spotkania seminaryjne: środa 14-16 s.104

• 2 marca 2011: Spotkanie organizacyjne. Przydział tematów do opracowania.
• referaty:
  • 16 marca 2011: Andrzej Kasiewicz
    Algorytmy z powrotami.
  • 16 marca 2011: Mateusz Łyczek
    Metoda podziału i ograniczeń.
  • 30 marca 2011: Piotr Gajowiak, Paweł Kacprzak
    Algorytmy przeszukiwania lokalnego.
  • 6 kwietnia 2011: Izabela Biczysko
    Symulowane wyżarzanie.
  • 6 kwietnia 2011: Przemysław Gospodarczyk
    Przeszukiwanie z tabu.
  • 13 kwietnia 2011: Paweł Kalinowski
    Przeszukiwanie rozproszone.
  • 20 kwietnia 2011: Bartłomiej Kobyłecki
    Coevoluion.
  • 4 maja 2011: Adam Kaczmarek
    Algorytmy ewolucyjne.
  • 11 maja 2011: Daniel Błaszkiewicz
    Systemy mrówkowe.
  • 18 maja 2011: Adam Grycner
    Rój cząsteczek.
  • 18 maja 2011: Krzysztof Szularz
    Systemy immunologiczne.
  • 1 czerwca 2011: Paweł Sobiegraj
    Multiobjective optimization.
  • 8 czerwca 2011: Bartłomiej Gałkowski
    Sieci neuronowe.
  • 8 June 2011: Nha Nam Ngoc Nguyen (Vietnam)
    Genetic algorithms.
• 15 czerwca 2011: Podsumowanie seminarium. Wpisywanie ocen do indeksów.

Seminariumum

Organizacja zajęć

Przydział tematów:

Na pierwszych zajęciach studenci wybierają tematy do opracowania. 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 mają być przygotowane slajdy. Tydzień przed wykładem można ze mną skonsultować treść prezentowanego materiału.

Opracowanie:

Wybrany temat student ma opracować pisemnie i dostarczyć mi sporządzoną notatkę w formie elektronicznej (notatkę należy przygotować w LaTeX'u lub innym popularnym formacie i przesłać mi plik źródłowy oraz pdf'a). Opracowanie powinno zawierać następujące elementy:

1. imię i nazwisko prelegenta,
2. datę i temat wystąpienia,
3. ogólny opis prezentowanej metody,
4. rys historyczny badań związanych z omawianym zagadnieniem,
5. prezentacje algorytmu, jego analizę i przykłady zadań rozwiązywanych tą metodą,
6. przykład programu wykorzystującego przedstawioną metodę do rozwiązania wybranego zadania,
7. szczegółową bibliografię.

Gotowe opracowanie należy przesłać mi mailem po wygłoszonym wykładzie. Opracowania będę udostępniać w sieci na tej stronie.

Oceny:

Ocenie będzie podlegać:

1. wystąpienie przed słuchaczami,
2. pisemne opracowanie zagadnienia,
3. program rozwiązujący wybrane zadanie za pomocą omawianej metody,
4. obecność i aktywność na zajęciach.

Warunkiem koniecznym uzyskania zaliczenia jest oczywiście rzetelne zapoznanie się z wybranym tematem, przystępne opowiedzenie go na forum grupy, starannie zrobiona notatka z omawianego zagadnienia i napisany program rozwiązujący przykładowy problem obliczeniowy, a także obecność na co najmniej 60% zajęć z wystąpieniami.

Opracowania

• Andrzej Kasiewicz: Algorytmy z powrotami. (16 marca 2011)
  • slajdy (pdf)
  • przykładowe programy (zip/java)
  • opracowanie -
• Mateusz Łyczek: Metoda podziału i ograniczeń. (16 marca 2011)
  • slajdy (pdf)
  • przykładowe programy (zip/java)
  • opracowanie (pdf)
• Piotr Gajowiak, Paweł Kacprzak: Algorytmy przeszukiwania lokalnego. (30 marca 2011)
  • slajdy (pdf)
  • przykładowe programy (zip/python)
  • opracowanie (pdf)
• Izabela Biczysko: Symulowane wyżarzanie. (6 kwietnia 2011)
  • slajdy -
  • przykładowe programy -
  • opracowanie -
• Przemysław Gospodarczyk: Przeszukiwanie z tabu. (6 kwietnia 2011)
  • slajdy (ppt)
  • przykładowe programy (cpp)
  • opracowanie (pdf)
• Paweł Kalinowski: Przeszukiwanie rozproszone. (13 kwietnia 2011)
  • slajdy (ppt)
  • przykładowe programy -
  • opracowanie (pdf)
• Bartłomiej Kobyłecki: Algorytmy koewolucyjne. (20 kwietnia 2011)
  • slajdy -
  • przykładowe programy -
  • opracowanie -
• Adam Jan Kaczmarek: Algorytmy ewolucyjne. (4 maja 2011)
  • slajdy -
  • przykładowe programy -
  • opracowanie -
• Daniel Błaszkiewicz: Systemy mrówkowe. (11 maja 2011)
  • slajdy (pdf)
  • przykładowe programy (cpp)
  • opracowanie (pdf)
• Adam Grycner: Rój cząsteczek. (18 maja 2011)
  • slajdy (pdf)
  • przykładowe programy (zip/python)
  • opracowanie (pdf)
• Krzysztof Szularz: Systemy immunologiczne. (18 maja 2011)
  • slajdy (pdf)
  • przykładowe programy (zip/python)
  • opracowanie (pdf)
• Paweł Sobiegraj: Multiobjective optimization. (1 czerwca 2011)
  • slajdy -
  • przykładowe programy -
  • opracowanie -
• Bartłomiej Gałkowski: Sieci neuronowe. (8 czerwca 2011)
  • slajdy (pdf)
  • przykładowe programy (zip/java)
  • opracowanie (pdf)
• Nha Nam Ngoc Nguyen (Vietnam): Genetic algorithms. (8 June 2011)
  • slajdy (pdf)
  • przykładowe programy (zip/cs)
  • opracowanie -

Udostępniam katalog z z ksiązkami, opracowaniami i pracami naukowymi związanymi z tematyką poruszną na seminarium o algorytmach heurystycznych (hasło: materialy).

Instytut Informatyki