Genetic Algorithm implementation in Python for university exam scheduling. Maximizes student satisfaction by avoiding same-day and consecutive-day exams. Includes naive scheduler comparison and extensible fitness function.

---

🎓 Αυτόματος Προγραμματισμός Εξεταστικής με Γενετικό Αλγόριθμο

📑 Πίνακας Περιεχομένων

1. Περίληψη
2. Δεδομένα Εισόδου
3. Το Project
4. Βασικά Χαρακτηριστικά
5. Γενετικός Αλγόριθμος
6. Αποτελέσματα
7. Εγκατάσταση & Εκτέλεση
8. Προσαρμογή & Επέκταση

---

📌 Περίληψη

Το παρόν project υλοποιεί ένα αυτοματοποιημένο σύστημα δημιουργίας εξεταστικού προγράμματος χρησιμοποιώντας Γενετικό Αλγόριθμο (Genetic Algorithm). Αναπτύχθηκε στο πλαίσιο πανεπιστημιακής εργασίας για το μάθημα ΠΛΗ31, με σκοπό τη μετάβαση από τη θεωρία στην πράξη.

📊 Δεδομένα Εισόδου

Το αρχείο imeres_exam.xls περιέχει ψεύτικα/ακαδημαϊκά δεδομένα:

• ΑΜ: Αριθμοί 1 έως 2500 (απλοί αριθμητικοί δείκτες ως αριθμούς μητρώου, όχι πραγματικοί φοιτητές)
• ΘΕ: Κωδικοί μαθημάτων (ΠΛΗ10, ΠΛΗ11, ...) των θεματικών ενοτήτων

Τα δεδομένα δημιουργήθηκαν αποκλειστικά για εκπαιδευτικούς σκοπούς στο πλαίσιο της εργασίας.

🎯 Το project

Σε μια εξεταστική περίοδο, κάθε φοιτητής έχει δηλώσει συγκεκριμένες Θεματικές Ενότητες (ΘΕ). Ένας φοιτητής θεωρείται ευχαριστημένος όταν:

• ✅ Δεν έχει δύο εξετάσεις την ίδια ημέρα
• ✅ Δεν έχει δύο εξετάσεις σε συνεχόμενες ημέρες (π.χ., Τρίτη & Τετάρτη)

Ποινή (penalty): +10 για κάθε παραβίαση

Στόχος: Μεγιστοποίηση του ποσοστού των ευχαριστημένων φοιτητών

✨ Βασικά Χαρακτηριστικά

1. Αφελής Προγραμματισμός (Naive Scheduling)

• Δοκιμάζει 5 διαφορετικές τυχαίες διατάξεις των ΘΕ
• Μία χωρίς ανάμειξη (αρχική σειρά) + τέσσερις με ανάμειξη
• Χρησιμοποιεί απλή αντιστοίχηση: πρώτη ΘΕ → Ημέρα 1, δεύτερη → Ημέρα 2, κ.ο.κ.

2. Γενετικός Αλγόριθμος (Genetic Algorithm)

Παράμετροι Ρύθμισης

Παράμετρος	Τιμή	Επεξήγηση
max_days	10	Μέγιστος αριθμός ημερών εξεταστικής
population_size	50	Αριθμός προγραμμάτων που εξετάζονται ταυτόχρονα
generations	100	Αριθμός γενεών (επαναλήψεων)

Βήματα Αλγορίθμου

1. Αρχικοποίηση Πληθυσμού Δημιουργούνται 50 τυχαία εξεταστικά προγράμματα. Παράδειγμα: Πρόγραμμα 1: ΠΛΗ10→3, ΠΛΗ11→7, ΠΛΗ12→1, ΠΛΗ20→5 Πρόγραμμα 2: ΠΛΗ10→8, ΠΛΗ11→2, ΠΛΗ12→4, ΠΛΗ20→1 ...

2. Υπολογισμός Fitness (Βαθμός Προσαρμογής) για κάθε φοιτητή: υπολόγισε ποινή (ίδια ή συνεχόμενη ημέρα) Κάθε παράβαση προσθέτει +10 στην ποινή penalty = 10 + 10 + ... (για κάθε παράβαση) άρα penalty = αριθμός_παραβιάσεων × 10

fitness = 1 / (1 + penalty)

Παράδειγμα Υπολογισμού συνάρτησης καταλληλότητας (fitness):

Δεδομένου ότι έχουμε πρόβλημα ελαχιστοποίησης (θέλουμε ελάχιστες ποινές), πρέπει να το μετατρέψουμε σε πρόβλημα μεγιστοποίησης (θέλουμε μέγιστο fitness).

• Φοιτητής 1076: δήλωσε [ΠΛΗ11, ΠΛΗ12, ΠΛΗ21]
• ΠΛΗ11→Ημέρα 2, ΠΛΗ12→Ημέρα 2 (ίδια μέρα) → +10
• ΠΛΗ12→Ημέρα 2, ΠΛΗ21→Ημέρα 3 (συνεχόμενες) → +10
• Συνολική ποινή = 20
• fitness = 1/(1+20) = 0.0476

3. Επιλογή (Selection)

• Ταξινόμηση 50 προγραμμάτων με βάση το fitness (από μεγαλύτερο σε μικρότερο)
• Κράτηση του καλύτερου μισού (25 προγράμματα)
• Τα υπόλοιπα 25 "πεθαίνουν" (διαγράφονται)

4. Διασταύρωση (Crossover) Από τα 25 καλύτερα προγράμματα, επιλέγονται τυχαία ζευγάρια γονέων: Παράδειγμα Γονέας 1: {ΠΛΗ10:1, ΠΛΗ11:3, ΠΛΗ12:5} Γονέας 2: {ΠΛΗ10:2, ΠΛΗ11:1, ΠΛΗ12:4} Τυχαίοι αριθμοί: [0.3, 0.8, 0.4] Απόγονος: {ΠΛΗ10:1, ΠΛΗ11:1, ΠΛΗ12:5}

5. Μετάλλαξη (Mutation) - 20% πιθανότητα Πριν: {ΠΛΗ10:3, ΠΛΗ11:2, ΠΛΗ12:4} Μετά: {ΠΛΗ10:8, ΠΛΗ11:2, ΠΛΗ12:4} (άλλαξε η ΠΛΗ10)

6. Επανάληψη

• Ο νέος πληθυσμός (25 γονείς + 25 παιδιά = 50 προγράμματα)
• Επανάληψη για 100 γενιές
• Κράτηση του καλύτερου προγράμματος

📊 Αποτελέσματα

Μέθοδος	Ποσοστό Ικανοποίησης
Αφελής (μέσος όρος 5 διατάξεων)	30-40%
Γενετικός Αλγόριθμος (100 γενιές)	80-90%

Παράδειγμα Εξόδου

ΠΛΗΘΟΣ ΦΟΙΤΗΤΩΝ : 45 ΠΛΗΘΟΣ ΘΕΜΑΤΙΚΩΝ ΕΝΟΤΗΤΩΝ : 12

Κάθε ΘΕ σε ξεχωριστή ημέρα (5 διαφορετικές διατάξεις) 1η διάταξη: 35.56% (16/45 ευχαριστημένοι) 2η διάταξη: 31.11% (14/45 ευχαριστημένοι) 3η διάταξη: 40.00% (18/45 ευχαριστημένοι) 4η διάταξη: 28.89% (13/45 ευχαριστημένοι) 5η διάταξη: 37.78% (17/45 ευχαριστημένοι)

=== ΕΚΚΙΝΗΣΗ ΓΕΝΕΤΙΚΟΥ ΑΛΓΟΡΙΘΜΟΥ === Παράμετροι: max_days=10, population=50, γενιές=100

Γενιά 0: 42.22% ευχαριστημένοι (19/45) Γενιά 5: 64.44% ευχαριστημένοι (29/45) Γενιά 10: 71.11% ευχαριστημένοι (32/45) Γενιά 20: 80.00% ευχαριστημένοι (36/45) Γενιά 50: 86.67% ευχαριστημένοι (39/45) Γενιά 100: 88.89% ευχαριστημένοι (40/45)

ΤΕΛΙΚΟ ΑΠΟΤΕΛΕΣΜΑ Ποιότητα: 88.89% Ευχαριστημένοι φοιτητές: 40/45

Η ΚΑΛΥΤΕΡΗ ΔΙΑΤΑΞΗ ΑΝΑ ΗΜΕΡΑ: Ημέρα 1: ['ΠΛΗ10', 'ΠΛΗ15'] Ημέρα 2: ['ΠΛΗ22', 'ΠΛΗ31'] Ημέρα 3: ['ΠΛΗ11'] ...

🧠 Επεξήγηση Γενετικού Αλγορίθμου Βήμα-Βήμα Παράδειγμα με μικρό πληθυσμό Αρχικός Πληθυσμός (4 προγράμματα):

text P1: ΠΛΗ10→1, ΠΛΗ11→2, ΠΛΗ12→3 (fitness: 0.50) P2: ΠΛΗ10→1, ΠΛΗ11→1, ΠΛΗ12→4 (fitness: 0.33) P3: ΠΛΗ10→3, ΠΛΗ11→5, ΠΛΗ12→2 (fitness: 0.25) P4: ΠΛΗ10→2, ΠΛΗ11→4, ΠΛΗ12→6 (fitness: 0.20) Επιλογή (κρατάμε τα 2 καλύτερα):

Επιλεγμένα: P1 (0.50), P2 (0.33) Διασταύρωση P1 & P2:

P1: {ΠΛΗ10:1, ΠΛΗ11:2, ΠΛΗ12:3} P2: {ΠΛΗ10:1, ΠΛΗ11:1, ΠΛΗ12:4} Random: [0.4, 0.7, 0.2] C1: {ΠΛΗ10:1, ΠΛΗ11:1, ΠΛΗ12:3} Μετάλλαξη (20% πιθανότητα):

C1: {ΠΛΗ10:1, ΠΛΗ11:1, ΠΛΗ12:3} → {ΠΛΗ10:5, ΠΛΗ11:1, ΠΛΗ12:3} Νέος Πληθυσμός: P1, P2, C1, C2

Εγκατάσταση & Εκτέλεση

Προαπαιτούμενα

Βεβαιώσου ότι έχεις εγκαταστημένη την Python 3.7 ή νεότερη έκδοση.

Στη συνέχεια, εγκατέστησε τις απαραίτητες βιβλιοθήκες:

pip install pandas xlrd

---

Εκτέλεση

1. Κλωνοποίησε το repository (ή κατέβασε τα αρχεία)
2. Τοποθέτησε το αρχείο imeres_exam.xls στον ίδιο φάκελο με τον κώδικα
3. Εκτέλεσε το πρόγραμμα:

python main.py

---

📊 Παράδειγμα Εξόδου

ΠΛΗΘΟΣ ΦΟΙΤΗΤΩΝ : 45
ΠΛΗΘΟΣ ΘΕΜΑΤΙΚΩΝ ΕΝΟΤΗΤΩΝ : 12

Κάθε ΘΕ σε ξεχωριστή ημέρα (5 διαφορετικές διατάξεις)
1η διάταξη: 35.56% (16/45 ευχαριστημένοι)
2η διάταξη: 31.11% (14/45 ευχαριστημένοι)
...

=== ΕΚΚΙΝΗΣΗ ΓΕΝΕΤΙΚΟΥ ΑΛΓΟΡΙΘΜΟΥ ===
Γενιά 0: 42.22% ευχαριστημένοι
Γενιά 20: 80.00% ευχαριστημένοι
Γενιά 100: 88.89% ευχαριστημένοι

ΤΕΛΙΚΟ ΑΠΟΤΕΛΕΣΜΑ
Ποιότητα: 88.89%

---

🔧 Προσαρμογή & Επέκταση

Αλλαγή Παραμέτρων

best = genetic_algorithm( foitites, all_the, max_days=14, # 2 εβδομάδες εξεταστική population_size=100, # Μεγαλύτερος πληθυσμός generations=200 # Περισσότερες γενιές )

---

Προσθήκη Νέας Συνάρτησης Ποιότητας

def extended_quality_score(programma, foitites, room_capacity): """ Επέκταση με: - Χωρητικότητα αιθουσών - Διάρκεια εξετάσεων - Ελάχιστο διάστημα μεταξύ εξετάσεων """

score, happy = quality_score(programma, foitites)
penalty = 0

# Έλεγχος χωρητικότητας αιθουσών
for th, students in get_course_enrollment().items():
    if students > room_capacity[th]:
        penalty += 100  # Μεγάλη ποινή

adjusted_score = score / (1 + penalty)

return adjusted_score