Σχεδίαση, ανάπτυξη και εφαρμογή αλγορίθμων υπολογιστικής νοημοσύνης σε προβλήματα εύρεσης βέλτιστου ωρολογίου προγράμματος σε σχολεία δευτεροβάθμιας εκπαίδευσης (school timetabling) και χρονοπρογραμματισμού (scheduling)

• Κύριος συγγραφέας: Τασσόπουλος, Ιωάννης
• Άλλοι συγγραφείς: Μπεληγιάννης, Γρηγόριος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2017
• Θέματα: Ωρολόγιο πρόγραμμα; Σχολεία δευτεροβάθμιας εκπαίδευσης; Υπολογιστική νοημοσύνη; Βελτιστοποίηση; Αλγόριθμος σμήνους; Timetabling; High school; Computational intelligence; Optimization; 006.3

Ο σκοπός της παρούσας Διδακτορικής Διατριβής είναι η διερεύνηση της συμπε-ριφοράς καινοτόμων αλγορίθμων της Υπολογιστικής Νοημοσύνης, όσον αφορά στην κατασκευή ποιοτικών ωρολογίων προγραμμάτων για σχολεία της Δευτεροβάθμιας Εκπαίδευσης. Είναι γεγονός ότι, τα τελευταία χρόνια, το δύσκολο έργο της κατασκευ-ής ωρολογίων προγραμμάτων σε λίγες μόνο περιπτώσεις επιτελείται χωρίς την βοή-θεια Η/Υ. Συνήθως χρησιμοποιείται κάποιο λογισμικό, το οποίο υλοποιεί έναν αλγό-ριθμο που είναι σε θέση να παράξει ένα ωρολόγιο πρόγραμμα, που να καλύπτει κατά το μεγαλύτερο μέρος τις λειτουργικές ανάγκες ενός σχολείου, μέσα σε διάστημα που κυμαίνεται από λίγα λεπτά έως λίγες ώρες. Στην διεθνή επιστημονική κοινότητα υ-πάρχει συνεχώς αυξανόμενο ενδιαφέρον για την ανάπτυξη νέων αλγορίθμων, οι οποί-οι θα βελτιώνουν διαρκώς την ποιότητα των ωρολογίων προγραμμάτων, θα εκμεταλ-λεύονται τις διαρκώς βελτιούμενες δυνατότητες των Η/Υ και θα στηρίζονται σε νέες θεωρητικές και πρακτικές ανακαλύψεις του χώρου της Πληροφορικής. Υπάρχει συνε-πώς πρόσφορο έδαφος για την ανακάλυψη νέων αλγορίθμων ή/και μεθοδολογιών που επιστρατεύονται για την λύση του αντίστοιχου προβλήματος. Το γεγονός αυτό γέννησε την ιδέα του πειραματισμού με αλγορίθμους της Υπολογιστικής Νοημοσύνης, οι οποίοι δεν έχουν εφαρμοστεί στο παρελθόν για την επίλυση του αντίστοιχου προ-βλήματος και της διερεύνηση της συμπεριφοράς τους. Η μεθοδολογία που ακολουθήθηκε, εν ολίγοις συνοψίζεται στην πρακτική και θεωρητική μελέτη του προβλήματος, στην ανασκόπηση της σχετικής διεθνούς βιβλιο-γραφίας, καθώς και στην επιλογή, τροποποίηση και εφαρμογή ενός καταξιωμένου αλ-γορίθμου σε παρεμφερή προβλήματα, που όμως να μην έχει εφαρμοστεί πριν στο συ-γκεκριμένο πρόβλημα. Επίσης, η μεθοδολογία συνίσταται στην εύρεση ενός αναγνω-ρισμένου συνόλου δεδομένων (data set) που να αντικατοπτρίζει ρεαλιστικές καταστά-σεις και που να έχει ήδη χρησιμοποιηθεί σε προγενέστερες ερευνητικές προσπάθειες. Με αυτόν τον τρόπο, είναι δυνατή η άμεση και δίκαιη σύγκριση των όποιων αποτελε-σμάτων της Διατριβής και η εξαγωγή ασφαλών συμπερασμάτων για την ποιότητα τους, σε πραγματικά προβλήματα. Στην παρούσα Διδακτορική Διατριβή παρουσιάζονται τρείς πρωτότυποι υβριδι-κοί αλγόριθμοι, οι οποίοι επιλύουν το πρόβλημα κατασκευής ωρολογίων προγραμμά-των σχολείων της Δευτεροβάθμιας Εκπαίδευσης κατά σχεδόν βέλτιστο τρόπο. Οι υ-βριδικοί αλγόριθμοι αυτοί βασίζονται στον γνωστό αλγόριθμο Particle Swarm Optimi-zation (PSO). Ο αλγόριθμος PSO μετασχηματίστηκε έτσι ώστε να μπορεί να εφαρμο-στεί στο διακριτό χώρο έρευνας του προβλήματος. Οι τρείς πρωτότυπες εκδοχές που παρουσιάζονται αποτελούν διαδοχικές προσπάθειες και προσεγγίσεις για την επίλυση του School Timetabling προβλήματος. Οι αλγόριθμοι και τα αποτελέσματα που παρή-χθησαν έχουν δημοσιευθεί σε έγκυρα διεθνή περιοδικά. Περισσότερες πληροφορίες για τις δημοσιεύσεις υπάρχουν στην ενότητα «Δημοσιεύσεις που πραγματοποιή-θηκαν στα πλαίσια της παρούσας Διατριβής και συμμετοχή σε Συνέδρια» του Παραρτήματος. Επίσης, με εργαλείο τον Μεικτό Ακέραιο Προγραμματισμό (MIP), επι-χειρήθηκε η εύρεση των ανώτατων ποιοτικών ορίων των ωρολογίων προγραμμάτων που αντιστοιχούν στα αντίστοιχα δεδομένα που επελέγησαν. Τέλος, τα παραχθέντα αποτελέσματα συγκρίνονται με αντίστοιχα άλλων ερευνητών καθώς και με αυτά που παράγει το λογισμικό aSc–Timetables. Το συγκεκριμένο λογισμικό χρησιμοποιείται ευρέως στα σχολεία της Ελληνικής επικράτειας και όχι μόνο. Όσον αφορά στην καινοτομία της παρούσας Διατριβής και στην συνεισφορά της στην ερευνητική κοινότητα, αυτή συνίσταται στην επιλογή του αλγορίθμου Particle Swarm Optimization (PSO), ο οποίος εφαρμόζεται για πρώτη φορά στο συγκεκριμένο πρόβλημα. Η πρωτότυπη προσαρμογή του PSO, ώστε αυτός να μπορεί να εφαρμο-στεί σε διακριτό χώρο, αποτελεί μια ακόμη καινοτομία. Άλλωστε, το γεγονός ότι, τελι-κά, τα αποτελέσματα που παρήχθησαν είναι μακράν καλύτερα από αντίστοιχα αποτε-λέσματα προγενέστερων ερευνητικών προσπαθειών, συνηγορούν υπέρ της καινοτο-μίας της Διατριβής. Επίσης, για πρώτη φορά επιχειρείται η εύρεση των τελικών βέλτι-στων ποιοτικών ορίων των ωρολογίων προγραμμάτων, τα οποία βασίζονται στα αρ-χεία εισόδου του data set το οποίο επελέγη και το οποίο έχει χρησιμοποιηθεί αρκετές φορές από άλλους ερευνητές. Η προσπάθεια εύρεσης των τελικών βέλτιστων ορίων στηρίζεται σε ακριβείς μεθόδους και μάλιστα σε μεθόδους του Μεικτού Ακέραιου Προ-γραμματισμού (MIP), όπως αναφέρθηκε παραπάνω. Τέλος, θα πρέπει να αναφερθεί ότι, στα πλαίσια Διπλωματικής εργασίας, αναπτύχθηκε ένα ολοκληρωμένο Πληροφο-ριακό σύστημα, το οποίο βασίζεται στους αλγορίθμους οι οποίοι αναπτύχθηκαν για τους σκοπούς της παρούσας Διατριβής, και δίνει πλέον την δυνατότητα σε σχολεία της Ελληνικής επικράτειας να δημιουργήσουν ωρολόγιο πρόγραμμα που θα καλύπτει τις ανάγκες τους και μάλιστα χωρίς χρέωση. Το γεγονός της δημιουργίας του εν λόγω Πληροφοριακού Συστήματος αναδεικνύει την πρακτική αξία της Διδακτορικής διατρι-βής.