Tournament Evolution Optimizer & Editor

[ČESKY] | ENGLISH

Aplikace v Pythonu pro optimalizaci přiřazování studentských projektů pomocí genetických algoritmů a simulovaného žíhání.

Funkce

• Vysoce optimalizované: Využívá genetické algoritmy akcelerované knihovnou numba k nalezení optimálního rozřazení projektů.
• GUI: Uživatelsky přívětivé rozhraní postavené na tkinter pro správu dat, konfiguraci a prohlížení výsledků.
• Vizualizace: Grafy a diagramy pro analýzu rozložení přiřazení.
• Konfigurovatelnost: Nastavitelné parametry optimalizace (míra mutace, počet generací atd.) přes config.json.

Instalace

1. Naklonujte repozitář:

   git clone https://github.com/Aknud3/project_week_optimizer.git
   cd project_week_optimizer

2. Vytvořte virtuální prostředí (doporučeno):

   python3 -m venv venv
   source venv/bin/activate  # Na Linuxu/Mac
   # venv\Scripts\activate  # Na Windows

3. Nainstalujte závislosti:

   pip install -r requirements.txt

   Poznámka: tkinter je obvykle součástí Pythonu. Pokud ne, možná jej budete muset nainstalovat samostatně (např. sudo apt-get install python3-tk na Ubuntu).

Použití

1. Spusťte aplikaci:

   python main.py

2. Načtěte data: Ujistěte se, že existuje soubor data.csv, nebo jej načtěte přes záložku "Editor Dat".
3. Konfigurujte: Upravte nastavení optimalizace v záložce "Konfigurace" nebo v postranním panelu.
4. Spusťte optimalizaci: Klikněte na "Spustit Optimalizaci" v postranním panelu.
5. Prohlédněte výsledky: Zkontrolujte záložku "Výsledky" pro statistiky a grafy.

Klíčové soubory

• main.py: Hlavní vstupní bod a ovladač GUI.
• optimizer.py: Jádro optimalizační logiky využívající genetické algoritmy.
• config.json: Konfigurační soubor pro kapacity projektů, třídy a parametry algoritmu.
• data.csv: Vstupní data obsahující volby studentů (ujistěte se o správném formátu).
• INFOGRAPHIC.md: Stránka s vizuálním přehledem projektu.

Jak funguje algoritmus (Detailní popis)

Aplikace využívá Hybridní Metaheuristiku, která kombinuje několik pokročilých optimalizačních technik pro nalezení nejlepšího možného rozřazení studentů. Jádro výpočtu je napsáno v Pythonu a akcelerováno pomocí knihovny numba (JIT kompilace), což umožňuje provádět miliony iterací během několika sekund.

1. Bodovací Systém (Fitness Function)

Cílem algoritmu je maximalizovat celkové skóre. Každé přiřazení studenta k projektu je ohodnoceno body:

Priorita	Body	Popis
1. Volba	500	Student dostal svůj vysněný projekt.
2. Volba	400	Student dostal svou druhou volbu.
3. Volba	100	Student dostal svou třetí volbu.
3. Volba (VIP)	100	VIP třída (např. maturanti) dostala až 3. volbu (penalizace).
Náhodný / Mimo	-10000	Student nebyl přiřazen k žádné ze svých voleb (obrovská penalizace).

Bonusy a Penalizace:

• Bonus za spolužáky: Pokud je v projektu více studentů ze stejné třídy, přičítá se (nebo odčítá, dle nastavení) bonus. Výchozí nastavení je -10 (penalizace), což podporuje míchání tříd.

2. Průběh Optimalizace

Algoritmus pracuje ve dvou fázích:

Fáze A: Konstrukce (Greedy Heuristika)

Nejprve se vytvoří validní "startovní" řešení:

1. Všem studentům se zkusí dát jejich 1. volba (pokud je místo).
2. Těm, co se nevešli, se zkusí dát 2. volba.
3. Následně 3. volba.
4. Zbytek je náhodně doplněn do volných projektů.

Fáze B: Evoluce a Lokální Hledání

Následuje cyklus vylepšování (např. 200 000 generací), kde se střídají různé operátory:

1. Simulované Žíhání (Simulated Annealing - SA):

   • Algoritmus přijímá i horší řešení s určitou pravděpodobností, která klesá s časem ("teplota"). To umožňuje uniknout z lokálních maxim.

2. Tabu Search (Zakázané tahy):

   • Aby se algoritmus necyklil (nepřesouval studenta tam a zpět), ukládá si nedávné tahy do "Tabu listu". Tyto tahy jsou po určitou dobu (např. 10 iterací) zakázané, pokud nevedou k rekordnímu zlepšení.

3. Large Neighborhood Search (LNS) - "Ruin & Recreate":

   • Pokud se řešení dlouho nezlepšuje (stagnace), algoritmus "rozbije" část řešení (vyhodí např. 20 % studentů) a znovu je poskládá. To způsobí velký skok v prohledávacím prostoru.

3. Operátory (Pohyby v prostoru řešení)

Algoritmus adaptivně vybírá (Adaptive Operator Selection), který typ změny provede:

• Swap (Výměna):

  • Vezme dva studenty a prohodí jim projekty.
  • Příklad: Student A (v P1) jde do P2, Student B (v P2) jde do P1.

• Chain (Řetězec / 3-cyklus):

  • Cyklická výměna tří studentů.
  • Příklad: A -> B -> C -> A. Užitečné, když prostá výměna není možná kvůli kapacitám.

• Ejection Chain (Vytěsňovací řetězec):

  • Nejsložitější operátor. Student A se "vnutí" do svého oblíbeného projektu P1, i když je plný.
  • Aby se tam vešel, musí být "vyhozen" Student B.
  • Student B se pak snaží dostat do svého oblíbeného projektu P2, čímž může vyhodit Studenta C...
  • Tento řetězec pokračuje, dokud se nenajde volné místo nebo se řetězec neuzavře.

4. Paralelizace

Aplikace spouští více turnajů (vláken) současně. Každý turnaj je nezávislá evoluce s vlastním náhodným semínkem. Na konci se vybere absolutně nejlepší výsledek ze všech turnajů.

---

English Section

CZECH | [ENGLISH]

A Python application for optimizing student project assignments using genetic algorithms and simulated annealing.

Features

• Optimization Engine: Uses numba-accelerated genetic algorithms to find optimal project assignments.
• GUI: User-friendly interface built with tkinter for managing data, configuration, and viewing results.
• Visualization: Charts and graphs to analyze the distribution of assignments.
• Configurable: Adjustable parameters for optimization (mutation rate, generations, etc.) via config.json.

Installation

1. Clone the repository:

   git clone https://github.com/your-username/tournament-optimizer.git
   cd tournament-optimizer

2. Create a virtual environment (recommended):

   python3 -m venv venv
   source venv/bin/activate  # On Linux/Mac
   # venv\Scripts\activate  # On Windows

3. Install dependencies:

   pip install -r requirements.txt

   Note: tkinter is usually included with Python. If not, you may need to install it separately (e.g., sudo apt-get install python3-tk on Ubuntu).

Upload to GitHub

To upload this project to your GitHub:

1. Create a repository on GitHub (do not initialize with README).
2. Initialize Git (if not already done):

   git init
   git add .
   git commit -m "Initial commit"

3. Link and Push:

   git remote add origin https://github.com/YOUR_USERNAME/REPO_NAME.git
   git push -u origin master

Usage

1. Run the application:

   python main.py

2. Load Data: Ensure data.csv is present or load it via the "Editor Dat" tab.
3. Configure: Adjust optimization settings in the "Konfigurace" tab or sidebar.
4. Start Optimization: Click "Spustit Optimalizaci" in the sidebar.
5. View Results: Check the "Výsledky" tab for statistics and charts.

Key Files

• main.py: Main entry point and GUI controller.
• optimizer.py: Core optimization logic using genetic algorithms.
• config.json: Configuration file for project capacities, classes, and algorithm parameters.
• data.csv: Input data containing student choices (ensure correct format).
• INFOGRAPHIC.md: A page with a visual overview of the project.

How the Algorithm Works (Detailed Description)

The application uses a Hybrid Metaheuristic that combines several advanced optimization techniques to find the best possible student assignment. The core calculation is written in Python and accelerated using the numba library (JIT compilation), allowing millions of iterations to be performed in seconds.

1. Scoring System (Fitness Function)

The goal of the algorithm is to maximize the total score. Each student assignment to a project is evaluated with points:

Priority	Points	Description
1st Choice	500	Student got their dream project.
2nd Choice	400	Student got their second choice.
3rd Choice	100	Student got their third choice.
3rd Choice (VIP)	100	VIP class (e.g., seniors) got their 3rd choice (penalty).
Random / Miss	-10000	Student was not assigned to any of their choices (huge penalty).

Bonuses and Penalties:

• Classmate Bonus: If there are multiple students from the same class in a project, a bonus is added (or subtracted, depending on settings). The default setting is -10 (penalty), which encourages mixing classes.

2. Optimization Process

The algorithm works in two phases:

Phase A: Construction (Greedy Heuristic)

First, a valid "starting" solution is created:

1. All students are attempted to be given their 1st choice (if there is space).
2. Those who didn't fit are attempted to be given their 2nd choice.
3. Subsequently, 3rd choice.
4. The rest are randomly filled into available projects.

Phase B: Evolution and Local Search

This is followed by an improvement cycle (e.g., 200,000 generations), where different operators alternate:

1. Simulated Annealing (SA):

   • The algorithm accepts even worse solutions with a certain probability that decreases over time ("temperature"). This allows escaping local maxima.

2. Tabu Search:

   • To prevent the algorithm from cycling (moving a student back and forth), it stores recent moves in a "Tabu list". These moves are forbidden for a certain time (e.g., 10 iterations) unless they lead to a record improvement.

3. Large Neighborhood Search (LNS) - "Ruin & Recreate":

   • If the solution does not improve for a long time (stagnation), the algorithm "breaks" part of the solution (e.g., ejects 20% of students) and reassembles them. This causes a large jump in the search space.

3. Operators (Moves in Solution Space)

The algorithm adaptively selects (Adaptive Operator Selection) which type of change to perform:

• Swap:

  • Takes two students and swaps their projects.
  • Example: Student A (in P1) goes to P2, Student B (in P2) goes to P1.

• Chain (3-cycle):

  • Cyclic exchange of three students.
  • Example: A -> B -> C -> A. Useful when a simple swap is not possible due to capacities.

• Ejection Chain:

  • The most complex operator. Student A "forces" themselves into their favorite project P1, even if it is full.
  • To fit there, Student B must be "ejected".
  • Student B then tries to get into their favorite project P2, which may eject Student C...
  • This chain continues until a free spot is found or the chain closes.

4. Parallelization

The application runs multiple tournaments (threads) simultaneously. Each tournament is an independent evolution with its own random seed. At the end, the absolute best result from all tournaments is selected.