Particle Swarm Optimization (PSO) | timetabling construction | Artificial intelligence
The swarm intelligence is a part of artificial intelligence and it is often used in order to study and solve very difficult problems that most of them are NP-Complete. Scheduling problems belongs to this category. More specifically to this type is the construction of timetabling that relates to many activities in daily life. This thesis is studying and trying to solve the problem of constructing timetabling for secondary schools. The difficulty to this relates to satisfy a set of constraints. A constructed timetable is a feasible solution only if it meets all hard constraints that are imposed. Also it becomes so efficient as it can satisfy as many of soft constraints.
This thesis uses an existing PSO algorithm and the problem is modeled to it trying to find the better solution that it can be found. Additionally, a program was developed with VisualBasic.NET which is a full Object Oriented Language. This application gives the opportunity to the user to handle and parameterize either the execution of algorithm or input data.
Finally the application is executed using as input the data of ten real secondary schools of Patras and the extracted results are recorded.
Η νοημοσύνη σμήνους είναι ένας από τους κλάδους της τεχνητής νοημοσύνης και βρίσκει εφαρμογή στην μελέτη και επίλυση πολύ δύσκολων προβλημάτων, τα οποία στην συντριπτική τους πλειονότητα είναι NP-Complete. Σε αυτήν την κατηγορία προβλημάτων ανήκουν και τα προβλήματα χρονοδρομολόγησης. Η κατάρτιση ωρολογίου προγράμματος είναι τέτοιου είδους πρόβλημα και αφορά σε πλήθος δραστηριοτήτων στην καθημερινή ζωή. Στην παρούσα εργασία μελετάται και αντιμετωπίζεται το πρόβλημα της κατάρτισης ωρολογίου προγράμματος για σχολεία της δευτεροβάθμιας εκπαίδευσης. Η δυσκολία κατάρτισης ενός ωρολογίου προγράμματος για σχολείο έγκειται αφενός στην ικανοποίηση ενός συνόλου περιορισμών. Το πρόγραμμα είναι αποδεκτό μόνο αν ικανοποιεί τους ανελαστικούς περιορισμούς που τίθενται ενώ γίνεται τόσο ποιοτικότερο, όσο αυξάνει το πλήθος των ελαστικών περιορισμών που ικανοποιεί.
Στην παρούσα εργασία γίνεται χρήση ενός υφιστάμενου PSO αλγορίθμου και το πρόβλημα μοντελοποιείται σε αυτόν, με στόχο την αναζήτηση της βέλτιστης λύσης του. Επιπλέον με χρήση της αντικειμενοστρεφούς γλώσσας VisualBasic.NET αναπτύσσεται κατάλληλη εφαρμογή η οποία προσφέρει εύχρηστο περιβάλλον όχι μόνο για την εκτέλεση του αλγορίθμου, αλλά και για τη διαχείριση τόσο των παραμέτρων αυτού, όσο και των δεδομένων εισόδου. Τέλος γίνεται εκτέλεση του αλγορίθμου χρησιμοποιώντας ως είσοδο δεδομένα από δέκα πραγματικά σχολεία της Πάτρας και καταγράφονται τα αποτελέσματα.
Hellenic Open University
Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.
