Ερευνητικά Προγράμματα

Επιστημονικός Υπεύθυνος:

Σπυρίδων Α. Καζαρλής

Συμμετέχοντες:

Πετρίδης Βασίλειος, Καθηγητής ΑΠΘ, Αδαμίδης Παναγιώτης, Καθηγητής ΤΕΙ Θεσσαλονίκης, Χειλάς Κωνσταντίνος, Αναπληρωτής Καθηγητής ΤΕΙ Κεντρικής Μακεδονίας, Ούτσιος Ευάγγελος, Καθηγητής Εφαρμογών ΤΕΙ Κεντρικής Μακεδονίας, Φράγκου Παυλίνα, Συνεργάτης,  Σαββόπουλος Μιχαήλ, Συνεργάτης, Χαράλαμπος Αλατάς, Συνεργάτης.

Περίοδος Εκπόνησης:

2005-2007

Περιγραφή:

Περιγραφή του αντικειμένου – Βιβλιογραφία

H διαδικασία κατασκευής ενός ωρολόγιου προγράμματος σπουδών ή εξετάσεων (Time Table) είναι μία εξαιρετικά πολύπλοκη και επίπονη διαδικασία που η πολυπλοκότητα και η δυσκολία της αυξάνεται εκθετικά με τον αριθμό των παραμέτρων του προβλήματος που είναι ο αριθμός των σπουδαστών, των μαθημάτων, των καθηγητών και των αιθουσών.

Η δυσκολία της επίλυσης τέτοιων προβλημάτων έγκειται σε δύο βασικούς λόγους:

α) Στον μεγάλο αριθμό των συνδυασμών / λύσεων που πρέπει να ελεγχθούν ώστε να βρεθεί μία ικανοποιητική λύση, ή μία βέλτιστη λύση με βάση τους στόχους που τίθενται, και

β) στον μεγάλο αριθμό των περιορισμών που πρέπει να ικανοποιούνται, που αφορούν διαθεσιμότητα και καταλληλότητα καθηγητών και αιθουσών, επικαλύψεις και ισοκατανομή ωρών,  κ.λ.π.

Συνδυαστικά προβλήματα (combinatorial problems) αυτού του τύπου θεωρούνται στην διεθνή ακαδημαϊκή κοινότητα ως NP complete, δηλαδή προβλήματα που δεν επιλύονται με γνωστές μεθόδους σε πολυωνυμικό χρόνο.

Μία οικογένεια μεθόδων που έχουν επιστρατευθεί τα τελευταία χρόνια για την επίλυση δύσκολων προβλημάτων είναι οι αλγόριθμοι της Εξελικτικής Υπολογιστικής και ιδιαίτερα οι Γενετικοί Αλγόριθμοι (ΓΑ). Οι ΓΑ αποτελούν σύγχρονα εργαλεία γενικής βελτιστοποίησης (Global Optimization) και αναζήτησης λύσεων (Search Algorithms) γενικής εφαρμογής που δανείζονται αρχές από την εξέλιξη των ειδών στην φύση για να πετύχουν την εξέλιξη βέλτιστων λύσεων σε δύσκολα προβλήματα.

Η εφαρμογή Γενετικών Αλγορίθμων σε προβλήματα Ωρολόγιου Προγράμματος (Time Tabling Problems) είναι ένα αντικείμενο ακαδημαϊκής έρευνας διεθνώς από το 1990 [A. Colorni, M. Dorigo, and V. Maniezzo 1990]. Έκτοτε αποτελεί ένα πεδίο έρευνας με ραγδαία ανάπτυξη με δικό του συνέδριο από το 1995 (PATAT).

Στις περισσότερες περιπτώσεις που αντιμετωπίζονται στην βιβλιογραφία, οι κλίμακες των προβλημάτων είναι μεγάλες και αφορούν Πανεπιστήμια. Για παράδειγμα στην εργασία [Nuno Mamede and Tiago Rente 1997] χρησιμοποιείται ένα πρόβλημα με 7000 σπουδαστές, 169 διαλέξεις, 211 μαθήματα, 98 καθηγητές και 396 ώρες.

Μία ανασκόπηση της σχετικής βιβλιογραφίας δημοσιεύτηκε από τους Carter και Laporte το 1995 [Michael W. Carter and Gilber Laporte 95] και το 1997 [Michael W. Carter and Gilber Laporte 1997]. Επίσης έχουν χρησιμοποιηθεί παράλληλοι ΓΑ [D. Abramson and J. Abela 1991],  υβριδικές μέθοδοι [E. K. Burke, D. G. Elliman, and R. F. Weare 1995 ], Μεμετικοί αλγόριθμοι (Memetic Algorithms) [E.K. Burke, J.P.Newall, and R.F.Weare 1995], προσομοιωμένη ανόπτηση (simulated annealing) [Nuno Mamede and Tiago Rente 1997 ] και έχουν αντιμετωπιστεί διάφορες παραλλαγές του προβλήματος όπως προγράμματα διαλέξεων [Adamidis P., Arapakis P. 1999], προγράμματα σχολείων [J P Caldeira and Agostinho C Rosa 1997], εξετάσεων [E.K. Burke, J.P.Newall, and R.F.Weare 1995], κ.λ.π.

 

Ορισμένες εργασίες έχουν οδηγήσει στην κατασκευή ολοκληρωμένων πακέτων λογισμικού όπως :

Το σύστημα ACT (Automated Class Timetabler) που αποτελεί ένα σύστημα επίλυσης ωρολόγιων προγραμμάτων Πανεπιστημίων, και αναπτύχθηκε στην Κορέα. Εφαρμόστηκε σε 15 Πανεπιστήμια στην Κορέα και το μεγαλύτερο πρόβλημα που έλυσε είχε 70 τμήματα, 700 καθηγητές και 4000 μαθήματα.

Το σύστημα Neeps and Tatties του Πανεπιστημίου Napier στο Εδιμβούργο (Napier University, in Edinburgh) [B.Paechter, H.Luchian, A.Cumming, and M.Petruic 1994],  [Ben Paechter, R C Rankin, and Andrew Cumming 1997]. Εφαρμόστηκε στο Πανεπιστήμιο Napier απο το 1997, για 2067 μαθήματα, 45 ώρες, 183 αίθουσες, 69 καθηγητές και 978 σπουδαστές. Το σύστημα αυτό βελτιστοποιεί περίπου 12 διαφορετικά κριτήρια/περιορισμούς.

Ένα άλλο σύστημα που αναπτύχθηκε στο Πανεπιστήμιο του Εδιμβούργου είναι το GATT (Genetic Algorithm Time Tabler), για τον προγραμματισμό των εξετάσεων. Επίσης χρησιμοποιήθηκε από το Harvard Business School, και ένα σχολείο του Βελγίου σε πρόβλημα 26 καθηγητών και 318 μαθημάτων.

Πρόσφατα υπήρξαν και δημοσιεύσεις ελλήνων ερευνητών [Adamidis P., Arapakis P. 1999] όπου επιλύονται προβλήματα έως και 180 μαθημάτων.

 

Στόχοι :

Α) Ανάπτυξη και εφαρμογή νέων μεθόδων Εξελικτικής Υπολογιστικής (Γενετικοί Αλγόριθμοι, Εξελικτικές Στρατηγικές κ.λ.π.) για την επίλυση προβλημάτων κατάρτισης ωρολόγιων προγραμμάτων σπουδών / εξετάσεων. Ενσωμάτωση άλλων μεθόδων όπως ειδικών αφαιρετικών αναπαραστάσεων των λύσεων, hill climbing, Μεταβλητής Συνάρτησης Ποιότητας, ειδικών γενετικών τελεστών κ.λ.π. Συσσώρευση εμπειρίας στην επίλυση δύσκολων συνδυαστικών προβλημάτων με περιορισμούς που μπορεί να εφαρμοστεί και σε άλλα συνδυαστικά προβλήματα ή προβλήματα χρονικού προγραμματισμού, όπως ο βέλτιστος χρονικός προγραμματισμός της βιομηχανικής παραγωγής, προβλήματα κοπής υλικών και φόρτωσης / συσκευασίας, προβλήματα ωρολόγιου προγράμματος εργασίας προσωπικού (βάρδιες), προβλήματα μεταφορών και διανομών, προβλήματα χωροθέτησης και κατανομής χώρου, προβλήματα δρομολόγησης τηλεπικοινωνιακής κίνησης, προβλήματα συγκοινωνιών και κυκλοφοριακών ρυθμίσεων κ.λ.π.

Β) Ανάπτυξη ενός ολοκληρωμένου πακέτου λογισμικού για την κατάρτιση ωρολόγιων προγραμμάτων. Η εφαρμογή θα είναι παραθυρική και θα επιτρέπει την εισαγωγή του προβλήματος την αυτόματη επίλυσή του, την εποπτεία των παραγόμενων λύσεων, την τροφοδοσία του με υφιστάμενες λύσεις, την μεταβολή στοιχείων και επαν-επίλυσή του και την λειτουργία μέσω διαδικτύου.

Γ) Συγκέντρωση στοιχείων για τις απαιτήσεις και τις προδιαγραφές για τα ωρολόγια προγράμματα διαφόρων ιδρυμάτων (ΑΕΙ & ΤΕΙ) όπως και υφιστάμενων προγραμμάτων-λύσεων για προσαρμογή του λογισμικού και έλεγχο της αποτελεσματικότητάς του. Πιλοτική εφαρμογή του λογισμικού στα ΤΕΙ Σερρών και Θεσσαλονίκης, καθώς και στο Α.Π.Θ.

 

Μεθοδολογία οργάνωσης, σχεδιασμού και υλοποίησης

Το έργο αναλύεται σε 4 στάδια :

  1. Έρευνα και ανάπτυξη νέων μεθόδων για την επίλυση προβλημάτων ωρολόγιων προγραμμάτων.
  2. Συγκέντρωση πραγματικών δεδομένων και πραγματικών ωρολόγιων προγραμμάτων διαφόρων ιδρυμάτων της χώρας (ΑΕΙ & ΤΕΙ)
  3. Ανάπτυξη του λογισμικού με ενσωμάτωση των μεθόδων και της εμπειρίας που αποκτήθηκε από τις πρώτες δύο φάσεις.
  4. Εκτεταμένες δοκιμές απόδοσης και πιλοτική εφαρμογή στα ΤΕΙ Σερρών και Θεσσαλονίκης και στο Α.Π.Θ..

 

Σημασία της έρευνας, συμβολή στην επιστήμη

Η εφαρμογή σύγχρονων μεθόδων Εξελικτικής Υπολογιστικής στα προβλήματα ωρολόγιου προγράμματος είναι ένας εξελισσόμενος τομέας με σημαντικά αποτελέσματα αλλά και μεγάλα περιθώρια για περαιτέρω έρευνα και ανάπτυξη νέων αποτελεσματικότερων και ταχύτερων μεθόδων. Τα αποτελέσματα της έρευνας αυτής μπορούν να αξιοποιηθούν τόσο στην πρακτική επίλυση του συγκεκριμένου προβλήματος όσο και σε μεγάλο αριθμό δύσκολων συνδυαστικών προβλημάτων και προβλημάτων χρονικού προγραμματισμού που έχουν μεγάλο ακαδημαϊκό, οικονομικό και κοινωνικό ενδιαφέρον.

 

Τίτλος:

ΕΞΕΛΙΚΤΙΚΟ ΥΛΙΚΟ (EVOLVABLE HARDWARE) – ΑΥΤΟΜΑΤΗ ΣΧΕΔΙΑΣΗ ΚΑΙ ΥΛΟΠΟΙΗΣΗ ΒΕΛΤΙΣΤΩΝ ΨΗΦΙΑΚΩΝ ΔΙΑΤΑΞΕΩΝ ΜΕ ΧΡΗΣΗ ΜΕΘΟΔΩΝ ΕΞΕΛΙΚΤΙΚΗΣ ΥΠΟΛΟΓΙΣΤΙΚΗΣ – (ΑΡΧΙΜΗΔΗΣ  ΙΙΙ  – Ενίσχυση Ερευνητικών Ομάδων στο ΤΕΙ Σερρών)

Επιστημονικός Υπεύθυνος:

Σπυρίδων Α. Καζαρλής

Συμμετέχοντες:

Πετρίδης Βασίλειος, Καθηγητής ΑΠΘ, Καλόμοιρος Ιωάννης, Αναπληρωτής Καθηγητής ΤΕΙ Κεντρικής Μακεδονίας, Μπαλουκτσής Αναστάσιος, Καθηγητής ΤΕΙ Κεντρικής Μακεδονίας, Μαστοροκώστας Πάρις, Καθηγητής ΤΕΙ Κεντρικής Μακεδονίας, Καλαιτζής Βασίλειος, Συνεργάτης, Πατσιάκος Αβραάμ, μέλος ΕΔΙΠ ΤΕΙ Κεντρικής Μακεδονίας, Βαλαής Αντώνιος, Φοιτητής ΤΕΙ Κ.Μ. Συνεργάτης, Μπογάς Δημήτριος, Φοιτητής ΤΕΙ Κ.Μ. Συνεργάτης.

Περίοδος Εκπόνησης:

2013-2015

Περιγραφή:

Η Εξελικτική Υπολογιστική (Evolutionary Computation) είναι ένας νέος και αναπτυσσόμενος κλάδος της Υπολογιστικής Νοημοσύνης (Computational Intelligence), που έχει ως στόχο την αυτόματη παραγωγή λύσεων σε δύσκολα προβλήματα του πραγματικού κόσμου, χρησιμοποιώντας αρχές εμπνευσμένες από την βιολογική εξέλιξη.

Επίσης η σύγχρονη τεχνολογία των ολοκληρωμένων κυκλωμάτων μας έχει δώσει την οικογένεια των FPGA (Field Programmable Gate Arrays) που είναι γενικευμένα «προγραμματιζόμενα» ψηφιακά κυκλώματα, αποτελούμενα από πίνακες καθοριζόμενων λογικών στοιχείων που μπορούν να συνδεθούν μεταξύ τους με επίσης καθοριζόμενο τρόπο, όντας έτσι ικανά να υλοποιήσουν ένα εξαιρετικά μεγάλο αριθμό πιθανών ψηφιακών σχεδιάσεων.

Ο συνδυασμός των δύο τεχνολογιών έχει δημιουργήσει τον κλάδο του Εξελικτικού Υλικού (Evolvable Hardware – EHW), σκοπός του οποίου είναι η χρήση εξελικτικών μεθόδων για την αυτόματη βέλτιστη σχεδίαση ψηφιακών διατάξεων, χωρίς την συνήθη διαδικασία της σχεδίασης από εξειδικευμένο άνθρωπο-σχεδιαστή.

Επιπρόσθετα, η δυνατότητα των FPGA να επανα-καθορίζονται δυναμικά με εξελικτικό τρόπο, παρέχει την δυνατότητα:

Α) της εξέλιξης της σχεδίασης και της αξιολόγησης των προτεινόμενων διατάξεων απευθείας στο υλικό,

Β) της συνεχούς εξέλιξης και βέλτιστης προσαρμογής τους στις εκάστοτε συνθήκες του περιβάλλοντος λειτουργίας,

Γ) την δυνατότητα ανάκαμψης μέσω αναπροσαρμογής από εσωτερικές αστοχίες υλικού, και

Δ) την πλήρη εκμετάλλευση των φυσικών ιδιοτήτων του υλικού για την επίτευξη της επιθυμητής συμπεριφοράς.

Στο υποέργο αυτό προτείνεται η υλοποίηση ενός συστήματος αυτόματης εξέλιξης ψηφιακών διατάξεων που θα υλοποιηθεί σε δύο επιμέρους φάσεις:

α) την δημιουργία ενός λογισμικού εξελικτικής σχεδίασης ψηφιακών κυκλωμάτων που θα λειτουργεί αυτόνομα σε έναν Η/Υ ως ένα εργαλείο αυτόματης ψηφιακής σχεδίασης. Στο λογισμικό αυτό ο χρήστης θα καθορίζει απλά την επιθυμητή συμπεριφορά της ψηφιακής διάταξης και αυτή θα σχεδιάζεται αυτόματα και βέλτιστα, με την εξέλιξη πολλών γενεών προτεινόμενων λύσεων, μέσω του εξελικτικού αλγόριθμου που θα αναπτυχθεί. Στην εφαρμογή αυτή οι προτεινόμενες ψηφιακές σχεδιάσεις θα αξιολογούνται μέσω προσομοιωτή. Για την υλοποίηση αυτή θα αναπτυχθούν και θα εφαρμοστούν προηγμένες τεχνικές εξελικτικής βελτιστοποίησης, καθώς και αρχές από τον Γενετικό Προγραμματισμό (Genetic Programming) για την αναπαράσταση των λύσεων. Η τελική βέλτιστη σχεδίαση μπορεί να μεταφέρεται στο FPGA (configuration) και να δοκιμάζεται σε πραγματικές συνθήκες. Η παραπάνω διαδικασία βέλτιστης εξελικτικής σχεδίασης ονομάζεται εξωτερική (extrinsic),

β) την δημιουργία ενός υβριδικού συστήματος Η/Υ και FPGA, όπου η εξέλιξη των πιθανών κυκλωμάτων-λύσεων θα γίνεται μέσω εξελικτικού αλγόριθμου που θα εκτελείται στον Η/Υ, όμως η αξιολόγηση των λύσεων θα γίνεται με μεταφορά σε πραγματικό χρόνο των κυκλωμάτων και υλοποίησή τους στο FPGA (configuration), αξιολόγηση της συμπεριφοράς κάθε προτεινόμενου κυκλώματος σε πραγματικές συνθήκες λειτουργίας, και τροφοδότηση των αποτελεσμάτων αξιολόγησης στο λογισμικό του εξελικτικού αλγόριθμου. Η παραπάνω διαδικασία βέλτιστης εξελικτικής σχεδίασης ονομάζεται εσωτερική (intrinsic).

Τόσο το λογισμικό της φάσης α) όσο και το σύστημα της φάσης β)  θα δοκιμαστούν στην υλοποίηση τυπικών ψηφιακών διατάξεων που χρησιμοποιούνται για δοκιμές, όπως ο πλήρης αθροιστής και ο πολλαπλασιαστής των 2 bits και θα διερευνηθεί η ικανότητά τους για την υλοποίηση πιο σύνθετων ψηφιακών διατάξεων.