Algorytmy mrówkowe

Prowadzący

Patryk Hes, Paweł Kamiński

Opis

Istnieje wiele ciekawych problemów w informatyce, których nie da się rozwiązać w czasie wielomianowym — są to tak zwane problemy NP-zupełne. Nie zawsze jednak jest potrzeba by uzyskać rozwiązanie absolutnie najlepsze — można wtedy posłużyć się jakimś algorytmem heurystycznym, który znajdzie nam rozwiązanie przybliżone.

Na warsztatach zajmiemy się w ogólności analizą algorytmów heurystycznych dla problemów NP-zupełnych, jednak szczególny nacisk położymy na algorytmy mrówkowe.

220px-Safari_ants.jpg

Algorytmy mrówkowe (Ant colony optimization, ACO) to klasa algorytmów heurystycznych pozwalających rozwiązywać wiele problemów NP-zupełnych, które da się zobrazować jako grafy. Oprócz tego, ACO są także przykładem inteligencji rojowej (swarm intelligence).
Pewnie słyszałaś/eś o algorytmach genetycznych albo sieciach neuronowych — one często też nadają się do tych problemów, jednak nie radzą sobie tak dobrze jak ACO ze zmianami grafu w trakcie rozwiązywania problemu.

Oprócz analizy grafowych problemów NP-zupełnych oraz różnych wariacji ACO zajmiemy się ich implementacją i zrobimy zawody mrówek: sprawdzimy która wersja ACO lepiej sobie radzi z którym problemem.

Program zajęć

escher-m-c-ants.jpg
  • omówienie kilku problemów NP-zupełnych
  • omówienie kilku algorytmów heurystycznych ogólnego zastosowania
  • crash course z analizy matematycznej
  • zapoznanie z frameworkiem do algorytmów mrówkowych
  • implementacja mrówek w Javie
  • przeprowadzenie Warsztatowego Turnieju Mrówek Pracujących
  • analiza wyników

Wymagania

  • podstawowa znajomość programowania obiektowego i Javy
  • zainstalowane na komputerze środowisko Eclipse (tak, trzeba mieć swój komputer!)
  • znajomość pojęć z analizy, jak np. pochodna
  • wiara w to, że czasem wystarczą przybliżone rozwiązania danego problemu

Zadania kwalifikacyjne

22.05 - wrzucono zadanie Gniewne Ptaki
23.05 - poprawiono treść zadania Gniewne Ptaki
26.05 - wrzucono zadania matematyczne
17.06 - dodano hinta

FAQ

  • Czy rozwiązania zadań matematycznych mogą być spisane na kartce i zeskanowane?

Tak, można, ale czytelnie. Niemniej jednak kto nie pisał nigdy w LaTeX-u, polecam spróbować. Bardzo wygodnym środowiskiem do pisania w LaTeX-u jest TeXmaker, natomiast świetny tutorial można znaleźć na Wikiksiążkach: http://en.wikibooks.org/wiki/LaTeX/

  • Czy w zad. 2) trzeba po prostu pokazać, że potrafi się używać wzorów na np. pochodną iloczynu itd., czy należy również te wzory wyprowadzać?

Wystarczy umiejętność korzystania z pochodnych.

  • Mały hint do zadania Gniewne Ptaki: jeżeli ktoś korzysta z algorytmu genetycznego/ewolucyjnego, może sprawdzić różne metody krzyżowania i mutacji (tutaj widać różnicę):

hint.png

  • Czy zadanie 4) wymaga użycia rekurencji?

Być może się da rekurencyjnie, ale lepiej użyć kombinatoryki. Poza tym, istnieje wiele różnych kombinatorycznych rozwiązań!

  • Czy w zadaniu 5) można używać bignumów?

Można, o ile się je samemu zaimplementuje. Takie rozwiązanie nie będzie błędne, ale do zrobienia zadania wystarczą zwykłe double, ale żeby je efektywnie wykorzystać, warto poczytać o reprezentacji liczb zmiennoprzecinkowych oraz o przeprowadzanych na nich operacjach. Przy ocenianiu będę brał pod uwagę 20 cyfr po przecinku :>

Po warsztatach

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License