OPTYMALIZACJA KOMBINATORYCZNA - BIOINFORMATYKA


Data oddania projektu i sprawozdania (główne sprawozdanie) 16 lub 21.01.2025 zależnie od grupy

Dla pewnego porządku jak to wygląda dla poszczególnych grup. Poniżej w czterech rzędach, trzy daty w kolejności: data pierwszego labu (FDL, first day lab) kiedy wpisywaliście mi się na listę "obecności", druga data (LL, last lab) to wg kalendarza ostatni dzień kiedy mamy laboratorium (zaliczenie), trzecia data to deadline (DL) na przesłanie sprawozdania

  1. FDL: 7.10.2024; LL: 27.01.2025; DL: 21.01.2025
  2. FDL: 8.10.2024; LL: 28.01.2025; DL: 21.01.2025
  3. FDL: 28.10.2024; LL: 20.01.2025; DL: 16.01.2025
  4. FDL: 29.10.2024; LL: 21.01.2025; DL: 16.01.2025
  5. Jak widać, dla dwóch ostatnich grup słabo to wygląda. Dlatego proszę o kontakt jak już się te dwie grupy dogadają, czy teoretycznie moglibyście przyjść na określone godziny np. w czwartek 23.01, albo (absolutnie najpóźniej) środa 29.01, wtedy trzeba by mi oddać sprawozdania też do 21.01. Można też (jak wam pasuje, tj. grupy z przedostatniego tygodnia) w poniedziałek 27.01 po 15:00, albo we wtorek 28.01 przed 9:45 albo po 11:15. Wtedy deadline byłby dla was taki jak dla tych dwóch grup.
  6. Kiedy już spłyną maile do 21.01, to w okolicach 22/23.01 będę wysyłać odpowiedzi, w których będę proponować konkretny czas (co kwadrans) danego dnia. Czyli po 21.01 będę mieć jasny obraz ile w jaki dzień będę miał czasu na rozmowy, co szczególnie powinno interesować "poszkodowane" grupy które mają deadline teoretycznie na przedostatni tydzień.
Poniżej numery indeksów wpisane przez was dla poszczególnych grup, gdyby ktoś chciał się odnaleźć w tej rozpisce. Bo np. nie jesteście pewni kiedy właściwie się wpisywaliście na listę na pierwszym laboratoriu. Niektórzy gryzmolą - fakt, nie opinia, więc sorry jeśli numeru nie ma, bo nie potrafiłem poprawnie domyślić się cyferki :) Wtedy proszę o maila, dopiszę / poprawię.
  1. FDL: 7.10.2024: 155099, 159892, 159867, 159882, 144350, 159870, 159880, 155645, 159899, 159904, 159620, 158769, 159858
  2. FDL: 8.10.2024: 159909, 159855, 159865, 159853, 159871, 1591(?)03, 159856, 159878, 159854, 159900, 159885, 159884
  3. FDL: 28.10.2024: 159160, 159896, 159879, 159874, 159906, 159913, 159851, 160440, 159875
  4. FDL: 29.10.2024: 159872, 159869, 159860, 159907, 161375, 159861, 159857, 159894, 162385, 159903, 155766
Jeżeli kogoś nie ma na liście indeksów, to proszę o kontakt. Jeżeli jakaś grupa chce oddawać na inny termin niż data LL dla danej grupy, to prosze koniecznie mi to napisać w mailu i zaproponować jakiś inny termin. A jeśli coś się nie zgadza w moich datach LL względem daty FDL, też koniecznie mi napiszcie. USOS jest bezużyteczny (niespodzianka), mi np. pokazuje, że "szczęśliwa" grupa 4, która by to nie była ma wg niego zajęcia i w ostatni, i w przedostatni tydzień stycznia... Ostatnia sprawa: w czwartek i piątek 30.01 i 31.01 nie ma mnie na uczelni ani w Poznaniu... Stąd środa 29.01 to ostateczny termin I podejścia.

Data oddania w ramach II podejścia: 10(14? 18?).02.2025


Materiały dodatkowe:

Laboratorium #1

Program specyfikacje wersja 0.8 (21.10.2024)
Sprawozdania - ważne uwagi
Podsumowanie dla sprawozdania i projektu

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

  1. Projekty zaliczeniowe wykonywane są samodzielnie.
  2. Do wykonania jest projekt zaliczeniowy - w grupie dwuosobowej, zaimplementowany algorytm metaheurystyczny (na 5.0) 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. Należy przede wszystkim zaimplementować dowolny algorytm nie będący heurystyką (4.0 jeżeli tylko taki), próbujący zmierzyć się z problemem w sposób mniej lub bardziej ''siłowy''.
  5. Możliwe metaheurystyki: Algorytm Genetyczny (Strategia ewolucyjna), Ant Colony Optimization (ACO, Algorytm Mrówkowy), Tabu Search.
  6. Sprawozdanie musi być oddane w terminie. Będę wysyłać potwierdzenie otrzymania maila, więc jeśli w ciągu 24h nie odpiszę, to znaczy, że nie dotarł mail.
  7. Dozwolone języki programowania: C++, opcjonalnie Java/C# jeżeli ktoś zna (nie, Python NIE). Platforma: Windows (precyzyjniej: na Windowsie ma się też kompilować, napisany może być na czymkolwiek - w przypadku kodu programu konsolowego nie powinno być to problemem).
  8. Tego samego dnia co sprawozdanie projektu należy dostarczyć działający, pełny kod programu - przesłać mailem wraz ze sprawozdaniem.
  9. Zaliczenie projektu rozumiane jako rozmowa na zajęciach lub w innym terminie nie wcześniej niż 2-3 dni po wysłaniu sprawozdania. Można od razu pisać proponowany, wygodny termin w mailu jeżeli ma być on inny niż zajęcia. Deadline to jednak KONIEC SEMESTRU, czyli do końca STYCZNIA. Wynika to z tego, że wpisywanie ocen do I podejścia jest możliwe tylko do końca semestru, ale nie w sesji (luty).
  10. Aktualny i ostateczny termin pierwszego podejścia jest do północy w xxxxxxx xx.xx.2025. 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.
  11. Nie można używać cudzych implementacji algorytmów metaheurystycznych (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 jednak 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ć).
  12. Komunikacja mailowa: w tytule każdego maila proszę wpisać frazę "OK 2025" - 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.

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)