🌳 Tree Keyboard Optimizer

Projekt porównuje cztery algorytmy optymalizacji metaheurystycznej w zadaniu ułożenia liter na klawiaturze w kształcie drzewa binarnego (31 węzłów). Celem jest zminimalizowanie liczby kliknięć potrzebnych do wpisania zadanego tekstu.

👥 Autorzy

Projekt został zrealizowany w zespole dwuosobowym. Podzieliliśmy się pracą nad głównymi silnikami optymalizacyjnymi:

• Wojciech Piwocha / WojtussToKox — implementacja dwóch algorytmów: Ant Colony Optimization (ACO) oraz Artificial Bee Colony (ABC).
• Wiktor Dembny / dembol23 — implementacja dwóch pozostałych algorytmów: Simulated Annealing (SA) oraz Genetic Algorithm (GA).

(Pozostała część projektu, system oceniania i wizualizacja oraz raport wyników była realizowana wspólnie).

---

Wymagania

• Python 3.10+
• pip

---

Struktura projektu

src/
├── main.py                    # Punkt wejścia — uruchamia porównanie algorytmów
├── tree_keyboard.py           # Model klawiatury-drzewa z funkcją fitness
├── simulated_annealing.py     # Algorytm SA
├── genetic_algorithm.py       # Algorytm GA
├── ant_algorithim.py          # Algorytm ACO
├── bees_algorithm.py          # Algorytm ABC
├── data.py                    # Dane bigramów, kolory, geometria drzewa
├── data/
│   ├── polish_bigrams_prob.json   # Prawdopodobieństwa bigramów (język polski)
│   └── polish_bigrams_counts.json # Liczności bigramów
├── samples/
│   ├── chat.txt               # Tekst testowy — styl potoczny
│   ├── sport.txt              # Tekst testowy — artykuł sportowy
│   └── scientific.txt         # Tekst testowy — tekst naukowy
└── results/                   # Wyniki zapisywane automatycznie po uruchomieniu

---

Uruchomienie

Przejdź do folderu src/ i uruchom główny skrypt:

cd src
python main.py

Skrypt wykona dla każdego pliku z folderu samples/:

1. Obliczenie punktów odniesienia (statyczne optimum, dynamiczny bigram).
2. Uruchomienie każdego z 4 algorytmów NUM_RUNS razy (domyślnie 10).
3. Zapis wyników do results/najlepsze_wyniki_<nazwa_pliku>.json.
4. Wyświetlenie wykresu porównawczego (zamknij okno, aby przejść do kolejnego pliku).

---

Konfiguracja

Parametry algorytmów i symulacji można dostosować bezpośrednio w pliku main.py:

STEPS = 500       # Liczba kroków / generacji każdego algorytmu
NUM_RUNS = 10     # Liczba powtórzeń dla statystyki

SA_CONFIG  = {"initial_temp": 2000.0, "cooling_rate": 0.995}
GA_CONFIG  = {"population": 100, "cross_rate": 0.90, "mutation_rate": 0.20}
ACO_CONFIG = {"ant_count": 50, "evaporation_rate": 0.20, "alpha": 1.0, "q_factor": 100000.0}
ABC_CONFIG = {"population_size": 40, "limit": 50}

---

Wyniki

Po zakończeniu działania skryptu w folderze results/ pojawią się:

• najlepsze_wyniki_<plik>.json — szczegółowe wyniki (najlepszy i średni fitness, czas, układ liter)
• wykres_<plik>.png — wykres porównawczy algorytmów

Przykładowe wyniki (tekst naukowy, 500 kroków, 10 uruchomień)

Algorytm	Najlepszy fitness	Średni fitness	Średni czas
SA	46 911	48 706	0.38 s
GA	46 619 ✅	46 619	37.67 s
ACO	48 325	49 886	19.55 s
ABC	46 619 ✅	46 636	64.42 s
Statyczne optimum	46 619	—	—
Dynamiczny bigram	40 992	—	—

Dynamiczny bigram (drzewo przebudowywane po każdym znaku na podstawie bigramów) stanowi górną granicę możliwości dla układów statycznych.

---

Zależności (requirements.txt)

Pakiet	Zastosowanie
PyQt6	Wizualizacja klawiatury-drzewa
matplotlib	Wykresy porównawcze algorytmów
numpy	Obliczenia statystyczne (średnia, argmin)