Συντάχθηκε 20-06-2012 13:16
από Galateia Malandraki
Email συντάκτη: gmalandraki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος ΑΡΜΗΧ.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Περιστερόπουλου Αθανάσιου
με θέμα
“ Aνάπτυξη Μεθοδολογίας και Συστήματος Χρονοπρογραμματισμού Ευφυών Πρακτόρων με Χρήση Μεθόδων Εμπνευσμένων από την Φύση.”
“Developing Methodology and System of Intelligent Agents using Nature-Inspired Methods”
Παρασκευή 22 Ιουνίου 2011, 13.00 μμ
Αίθουσα 2041, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Καθ. Γιώργος Σταυρακάκης (επιβλέπων)
Επ. Καθ. Μιχαήλ Λαγουδάκης
Καθ. Νικόλαος Ματσατσίνης μέλους (ΜΠΔ)
Περίληψη
Στη κλάση των μεθευρετικών αλγορίθμων ο ACO αποτελεί ένα σχετικά νέο πεδίο.Παρά την επιτυχία του σε εφαρμογές προβλημάτων συνδυαστικής βελτιστοποίησης ,όπως το Πρόβλημα του Πλανώδιου Πωλητή και το Πρόβλημα της Τετραγωνικής Ανάθεσης έχει διεξαχθεί περιορισμένη έρευνα στο πλαίσιο του JSP(Job Shop Problem) .Η ελαχιστοποίηση της πλειοψηφίας των κριτιρίων για ένα JSP,όπως η ελαχιστοποίηση του makespan και της συνολικής βραδύτερης περάτωσης, είναι σχετικά απλή από μαθηματικής άποψης και εύκολη προς την μοντελοποίηση της ,ωστόσο λόγω των πολλών « αυστηρών» περιορισμών της ,το JSP έχει λάβει την φήμη ενός ιδιαίτερα δύσκολου προβλήματος προς λύση.Συνεπώς αποτελεί σημείο αναφοράς στην ακαδημαική έρευνα, καθώς αντικατοπτρίζει με συνέπεια την υπολογιστική δυσκολία που συναντάται στην εύρεση του βέλτιστου χρονοπρογράμματος.Η ελαχιστοποίηση λοιπόν των προαναφερθέντων κριτηρίων συνιστά ένα σημαντικό μοντέλο στη θεωρία χρονοπρογραμματισμού που παρέχει το έδαφος για την δοκιμή νέων αλγοριθμικών ιδεών και ένα σημείο εκκίνησης για νέα ,περισσότερο πρακτικά μοντέλα.
Στην συγκεκριμένη διπλωματική εφαρμόσαμε μια κλασσική προσέγγιση των ACO αλγόριθμων ,τον ΑCS(Ant Colony System) ,στο JSP στοχεύοντας στην ελαχιστοποίηση δύο αντικειμενικών συναρτήσεων, του makespan και της συνολικής βραδύτερης περάτωσης ενός χρονοπρογράμματος.Κατόπιν προτείναμε μια μέθοδο βασισμένη στον single-objective ACS για την επίλυση του πολυκριτηριακού(multi-objective) JSP, με σκοπό την ταυτόχρονη ελαχιστοποίηση των δύο κριτηρίων.Η μέθοδος αναζητά ευρετικά σχεδόν-βέλτιστα χρονοπρογράμματα τα οποία βελτιστοποιούν ταυτόχρονα τα ζητούμενα κριτήρια ,επιστρέφοντας ένα σύνολο από Pareto βέλτιστες λύσεις.
Συνημμένα:
-
DErgasia-περιστεροπουλος.doc
Μεταφορτώσεις: 138,
Μέγεθος: 46 KB application/msword
