OPTYMALIZACJA KOMBINATORYCZNA - INFORMATYKA


Data oddania projektu i sprawozdania: : 10(11).01 (czwartek/piątek) styczeń 2019

Data oddania do drugiego podejścia: : 10.02 (niedziela) luty 2019



Zasady zaliczania    Sprawozdania    Tematy zadań    Uwagi ogólne   
Zasady zaliczania

  1. Projekty zaliczeniowe wykonywane są samodzielnie.
  2. Do wykonania jest projekt zaliczeniowy - samodzielnie zaimplementowany algorytm metaheurystyczny zaprojektowany w celu rozwiązywania wybranego problemu oraz sprawozdanie.
  3. W ramach projektu musi być także zaimplementowany sprawny generator instancji dla wybranego problemu.
  4. Możliwe metaheurystyki: Algorytm Genetyczny, Strategia ewolucyjna, Ant Colony Optimization (ACO), Tabu search.
  5. Sprawozdanie musi być oddane w terminie. Będę wysyłać potwierdzenie otrzymania maila ASAP, więc jeśli w ciągu 24h nie odpiszę, to znaczy, że nie dotarł mail.
  6. Dozwolone języki programowania: C++, Java, C#. Platforma: Windows (a ściślej: na Windowsie ma się kompilować, napisany może być na czymkolwiek).
  7. Tego samego dnia co sprawozdanie projektu należy dostarczyć działający, pełny kod programu - albo przynieść na zajęcia, albo przesłać drogą mailową.
  8. Zaliczenie projektu rozumiane jako rozmowa na zajęciach lub w innym terminie nie wcześniej niż 3 dni po wysłaniu sprawozdania - proszę od razu pisać proponowany termin w mailu.
  9. Spóźnienie do 1 tygodnia w oddaniu sprawozdania skutkuje obniżeniem maksymalnej oceny z projektu o 0.5 - 1.0 stopień (zależnie od jakości). Spóźnienie dalsze (powyżej 7 dni): oceną 2.0 w pierwszym podejściu. Drugie podejście: sprawozdanie i kod należy dostarczyć na tych samych zasadach. Rozmowa musi się odbyć najdalej tydzień po drugim terminie, więc od razu proszę się umawiać w mailu. Przekroczenie tych terminów skutkuje niezaliczeniem laboratorium.
  10. Nie wolno importować cudzych implementacji algorytmów od innych osób (tj. cudzego kodu rozwiązującego postawione zadanie, a co za tym najczęściej idzie - cudzego sprawozdania), a wykryty plagiat kodu i/lub sprawozdania skutkuje oceną 2.0 za dany projekt w pierwszym podejściu (lub drugim...) do laboratorium. Można korzystać z rozwiązań opisanych w książkach i artykułach, wówczas powinno się krótko podać źródło w sprawozdaniu. Decyduje data wysłania kodu, tj. 2.0 dostaje projekt który został wysłany z tym samym kodem jako drugi, trzeci, itd. wg daty/godziny maila, niezależnie kto tak naprawdę jest autorem (ponieważ i tak nie sposób tego wtedy stwierdzić).
  11. Komunikacja mailowa: w tytule każdego maila proszę wpisać frazę "OK 2019" - dzięki temu maile powędrują do odpowiedniego katalogu i szybciej będę mógł odpisać. W mailu proszę podawać informację o którą grupę LABORATORYJNĄ chodzi (np. nad czy pod kreską tydzień).

Format sprawozdania

Sprawozdanie ma zawierać:

  1. Przede wszystkim to co powiem, że ma zawierać :) - na drugim laboratorium dla każdej grupy. Między innymi jednak poniższe:
  2. Dane autora projektu, email do kontaktu, nazwę zadania i nazwę rozwiązania (np. algorytm genetyczny, tabu search, etc.).
  3. Opis metody rozwiązania problemu. Należy opisać zasady, na których opiera się zaimplementowana metaheurystyka (tj. nie interesują mnie teoria dotycząca np. operatorów dla algorytmu genetycznego, ale to JAK zostały one zaimplementowane w danej wersji metaheurystyki do zadanego problemu). Można tu włączyć istotne wyjątki z kodu. Docenione na pewno zostanie choćby ogólne opisanie rozwiązywanego problemu z punktu widzenia teorii złożoności obliczeniowej.
  4. Badania efektywności zastosowanej metody, tj. wyniki testów działania programu i jakości uzyskanych rozwiązań w zależności od użytych instancji (np. wiele zadań, inne parametry generatora, itd). Instancje należy generować wcześniej przygotowanym algorytmem, który musi wchodzić w skład głównego projektu. Przeprowadzenie obszernych testów i opisanie ich wraz z wnioskami jest jedną z podstaw zaliczenia.
  5. Wnioski, ciekawe spostrzeżenia nt. działania algorytmu, trudności konkretnych instancji problemu, itp.
  6. Załącznik w postaci kodu programu proszę przysłać pocztą (powinien być spakowany, z hasłem, które należy załączyć w mailu). W przypadku problemów z wysłaniem załącznika na adres (zwrot poczty, etc.) można plik umieścić w internecie i przesłać w mailu sam link.
  7. W mailu proszę napisać jak kompilować Państwa program i jak go uruchomić (o ile nie jest to np. gotowy projekt w ramach np. Visual Studio, Eclipse, czyli w zasadzie instrukcje te są potrzebne dla C++).
  8. Najważniejszą i najcenniejszą (w kwestii oceny) częścią sprawozdania są testy i ich wyniki. Wyniki powinny zajmować znaczną część sprawozdania, być nietrywialne, dotyczyć zarówno różnych instancji problemu, badania różnych parametrów algorytmu oraz ich kombinacji.

O SPRAWOZDANIACH

Problemy do wyboru

Ostatnia zmiana: 18-10-2018

Problemy (wersja z 18.10.2018)
Uwagi ogólne

  1. Jak określić kiedy metaheurystyka ma się zatrzymać?
  2. Strojenie (tuning) metaheurystyki. Jeżeli implementuje się jakąś metaheurystykę, to proszę zwrócić uwagę, że mają one szereg "magicznych" parametrów sterujących ich działaniem. Na przykład: tabu search - długość listy tabu, rozmiar przeszukiwanego sąsiedztwa, genetic search - rozmiar populacji, prawdopodobieństwo mutacji, simulated annealing - sposób zmieniania temperatury, wszystkie takie algorytmy - warunek stopu (np. liczba iteracji, czas działania do zatrzymania). Te wszystkie parametry trzeba sensownie dobrać. Zwykle wymaga to testowania i eksperymentalnego dobierania. Wyniki takich testów trzeba opisać i objaśnić w sprawozdaniu. Zwykle wiązanie ad hoc tych liczb ze strukturą instancji nie jest dobrym pomysłem. Brak strojenia oznacza, że metaheurystyka nie została prawidłowo użyta.
  3. Kilka przydatnych linków:
  4. Linki z punktu powyżej to tylko kilka przykładów. A skoro już podałem tu linki do wikipedii, słowo komentarza: najczęściej wiedza uzyskana z tego źródła to delikatnie mówiąc, trochę mało, aby opanować daną metodę. Dlatego proszę ze szczególną uwagą przejrzeć linki zewnętrzne (o ile są) z artykuły wikipedii, ponieważ najczęściej prowadzą to źródeł metody lub stron poświęconym w całości danemu podejściu.

    5. Ant Colony Optimization (ACO)


    Tabu Search (TS)