OPTYMALIZACJA KOMBINATORYCZNA - BIOINFORMATYKA


Data oddania projektu i sprawozdania (główne sprawozdanie) 23.01.2026 (piątek)

Data oddania w ramach II podejścia: 16.02.2026


Materiały dodatkowe:

Laboratorium #1

[OLD] Specyfikacje v0.8 (wersja z 2024/2025) [2025.10.12: nowsza wersja później w październiku 2025]
Sprawozdania - ważne uwagi
Podsumowanie dla sprawozdania i projektu
Multiple Sequence Alignment (wersja 0.8.0, 24.11.2025).

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 (meta)heurystyczny zaprojektowany w celu rozwiązywania wybranego problemu (SBH na 4/4.5 lub MSA na 5) oraz sprawozdanie. Dodam tutaj, że problem MSA wydaje mi się osobiście łatwiejszy, niż walka z grafami w SBH. Ale to decyzja każdej grupy.
  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, Algorytm Mrówkowy), Tabu Search, inne np. GRASP. Tą ostatnią polecam tym, którzy totalnie polegli w starciu z teorią związane z poprzednimi.
  5. 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.
  6. Dozwolone języki programowania na bazie C: C++, Java, C# (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).
  7. Tego samego dnia co sprawozdanie projektu należy dostarczyć działający, pełny kod programu - przesłać mailem wraz ze sprawozdaniem.
  8. 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).
  9. Aktualny i ostateczny termin pierwszego podejścia jest do północy w xxxxxxx xx.xx.2026. 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 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ć).
  11. Komunikacja mailowa: w tytule każdego maila proszę wpisać frazę "OK 2026" - 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ń).
  12. Kryteria oceny: jeżeli jest metaheurystyka dla problemu SBH (Sequencing by Hybridization) - maksymalnie 4 (4.5 w bardzo rzadkim i idealnym przypadku sprawozdania i projektu); jeżeli jest metaheurystyka dla MSA (Multiple Sequence Alignment) - tutaj pełny zakres do 5.0

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.
  9. Dwa ważne linki: Sprawozdania - ważne uwagi oraz Podsumowanie dla sprawozdania i projektu

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)