Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

Πολυτεχνική Σχολή - Πανεπιστήμιο Ιωαννίνων

Σεμινάριο Τμήματος με τίτλο: «Πολυ-αλγοριθμική Υπολογιστική Βελτιστοποίηση: Διαμοιρασμός πόρων σε χαρτοφυλάκια αλγορίθμων»

Περιγραφή

Στο πλαίσιο της διοργάνωσης των σεμιναρίων του τμήματος θα πραγματοποιηθεί διαδικτυακά μέσω της εφαρμογής Ms Teams την Παρασκευή 24/09/2021 και ώρα 11:00, ομιλία με τίτλο «Πολυ-αλγοριθμική Υπολογιστική Βελτιστοποίηση: Διαμοιρασμός πόρων σε χαρτοφυλάκια αλγορίθμων». Ομιλητής θα είναι ο  κ. Κωνσταντίνος Παρσόπουλος, Αναπληρωτής Καθηγητής, Τμήμα Μηχανικών Η/Υ & Πληροφορικής. Μπορείτε να παρακολουθήσετε την ομιλία μέσω του παρακάτω συνδέσμου: Link MsTeams

ΠΕΡΙΛΗΨΗ

Τα πολυ-αλγοριθμικά σχήματα κερδίζουν συνεχώς δημοφιλία στο πεδίο της υπολογιστικής βελτιστοποίησης, με τα χαρτοφυλάκια αλγορίθμων (algorithm portfolios) να βρίσκονται στο επίκεντρο του ενδιαφέροντος. Ένα πολυ-αλγοριθμικό σχήμα αποτελείται από περισσότερους του ενός αλγορίθμους (επιλυτές), οι οποίοι εκτελούνται ταυτόχρονα ή εναλλάξ στο ίδιο πρόβλημα διαμοιράζοντας τμηματικά τους υπολογιστικούς πόρους μεταξύ τους. Ο κύριος στόχος είναι η απαλλαγή του χρήστη από την ανάγκη επιλογής βέλτιστου αλγορίθμου, αλλά και η δυνατότητα αξιοποίησης των ιδιαίτερων χαρακτηριστικών των επιλυτών προκειμένου να επιτευχθεί συνολικά καλύτερη απόδοση ως προς την ποιότητα και την ταχύτητα εύρεσης προσεγγιστικών λύσεων.

Κρίσιμο στοιχείο στην κατασκευή πολυ-αλγοριθμικών σχημάτων αποτελεί ο μηχανισμός διαμοιρασμού πόρων μεταξύ των αλγορίθμων, ο οποίος θα πρέπει να κάνει ανάθεση των πόρων αναλογικά, με βάση την απόδοσή τους. Ενώ οι offline εκδοχές τέτοιων μηχανισμών τυπικά βασίζονται σε πειραματικά δεδομένα από πρότερη εφαρμογή των αλγορίθμων, στις online εκδοχές τους είναι αναγκαία η άμεση αξιολόγηση των αλγορίθμων και η κατάταξή τους με βάση την τρέχουσα απόδοση αλλά και  βραχυπρόθεσμες εκτιμήσεις των μελλοντικών τιμών αυτής.

Στην παρούσα ομιλία θα παρουσιαστούν οι βασικές αρχές σχεδίασης πολυ-αλγοριθμικών σχημάτων και πιο συγκεκριμένα των χαρτοφυλακίων αλγορίθμων. Στη συνέχεια θα παρουσιαστεί ένα ιδιαίτερα απλό αλλά αποδοτικό σχήμα online διαμοιρασμού πόρων μεταξύ των αλγορίθμων, το οποίο βασίζεται σε εκτιμήσεις της απόδοσής τους με χρήση απλών τεχνικών εξομάλυνσης (smoothing) χρονοσειρών. Επίσης, θα παρουσιαστούν ενδεικτικά αποτελέσματα από την εφαρμογή του σχήματος σε ένα ιδιαίτερα απαιτητικό συνδυαστικό πρόβλημα βελτιστοποίησης, καθώς και ορισμένες υπό ανάπτυξη επεκτάσεις του.