New approaches in parallel algorithm portfolios for metaheuristic optimization
Φόρτωση...
Ημερομηνία
Συγγραφείς
Σουραβλιάς, Δημήτριος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Optimization problems are ubiquitous in science and engineering. Their plethora and diversity have
offered ample ground for the development of numerous optimization methods, leading to an increasing
expansion of the available algorithmic artillery. However, both theoretical and experimental evidence
suggest that the existence of a universal optimization algorithm capable of tackling all optimization
problems equally well is highly improbable. Thus, the ability to identify the most appropriate algorithm
eventually determines the boundary between success and failure when challenging optimization
problems are confronted.
A crucial decision in solving optimization problems is the selection of an appropriate optimization
algorithm. This is a non-trivial task and usually requires deep knowledge of the problem and experience
from the practitioner's side. Whenever the available information on the problem is limited, preliminary
experimentation is needed for the selection of the most promising algorithm among a set of candidates
through a trial-and-error procedure. This phase is error-prone as well as time-consuming. In fact, it may
require more time than the solution of the problem itself due to the computational intensity of the
involved statistical methodologies. Moreover, it does not take directly into consideration the online
dynamic of each algorithm, i.e., its performance fluctuations during execution.
Algorithm Portfolios were proposed as models that combine a number of algorithms into a joint
algorithmic framework. Their constituent algorithms are either interchangeably executed on a single
processing unit or run concurrently on multiple processors, according to a prescribed resources
allocation plan. This plan is usually determined prior to the portfolio’s application based on preliminary
experiments or historical performance data of the algorithms. However, the assignment of predefined
portions of computational resources may be inefficient, since it neglects the online dynamic of the constituent algorithm. In such cases, the dynamic allocation of resources during the execution of the
portfolio can be highly beneficial.
The main goals of the dissertation are the justification of the use of metaheuristic algorithm portfolios in
demanding optimization problems of various types, and the development of new parallel algorithm
portfolio models with adaptive resources allocation plans. Firstly, motivation for the use of algorithm
portfolios is provided. The impact of appropriate computational budget allocation in contemporary
metaheuristics is identified, and two simplistic parallel algorithm portfolio models are introduced. The
first one can be used with any optimization algorithm and it is demonstrated on the design of bijective
S-boxes, which is an important problem in cryptography. The second model is suitable for populationbased
algorithms and it is demonstrated on the traffic light scheduling problem.
Secondly, two new parallel algorithm portfolio models with sophisticated resources allocation
mechanisms are proposed. The first model defines an algorithm portfolio with trading-based budget
allocation, which introduces a market-based environment where the constituent algorithms of the
portfolio can trade their solutions for additional running time. The model is autonomous and allows the
algorithms to individually interact whenever specific conditions (e.g., search stagnation) are met. It is
demonstrated on three challenging problems, namely the detection of circulant weighing matrices in
combinatorics, the lot-sizing planning in production environments with returns and remanufacturing,
and the transportation of commodities in humanitarian logistics. The second proposed model is a
forecasting-based parallel algorithm portfolio where time series forecasting techniques are employed to
predict the performance of its constituent algorithms. The predictions are used to assign computational
resources to the constituent algorithms, accordingly. The model is demonstrated on the detection of
circulant weighing matrices in combinatorics.
Τα προβλήματα βελτιστοποίησης είναι πανταχού παρόντα στην επιστήμη και στη μηχανική. Εμφανίζονται σε διάφορους τύπους και μορφές σε όλες σχεδόν τις διαδικασίες λήψης αποφάσεων. Η αφθονία και η ποικιλομορφία των προβλημάτων βελτιστοποίησης έχουν δώσει πρόσφορο έδαφος για την ανάπτυξη καινοτόμων μεθόδων και τεχνικών επίλυσης. Διάφορες μέθοδοι βελτιστοποίησης έχουν προταθεί τις τελευταίες δεκαετίες, καταγράφοντας διαρκή αύξηση των διαθέσιμων αλγορίθμων. Ωστόσο, τόσο θεωρητικές όσο και πειραματικές μελέτες καταλήγουν στο συμπέρασμα ότι η ύπαρξη ενός καθολικού αλγορίθμου βελτιστοποίησης ικανού να αντιμετωπίσει εξίσου καλά όλα τα δυνατά προβλήματα βελτιστοποίησης είναι απίθανη. Έτσι, ο προσδιορισμός του κατάλληλου αλγορίθμου καθορίζει το όριο μεταξύ επιτυχίας και αποτυχίας όταν ο στόχος είναι η επίλυση απαιτητικών προβλημάτων βελτιστοποίησης. Μια από τις πιο σημαντικές αποφάσεις της διαδικασίας επίλυσης είναι η επιλογή του αλγορίθμου βελτιστοποίησης που θα χρησιμοποιηθεί. Πρόκειται για μια δύσκολη επιλογή που συνήθως απαιτεί βαθιά γνώση του προβλήματος αλλά και εμπειρία. Σε περίπτωση που οι διαθέσιμες πληροφορίες για το πρόβλημα είναι περιορισμένες, συνήθως απαιτείται προκαταρκτική πειραματική μελέτη για την επιλογή του καταλληλότερου αλγορίθμου από ένα σύνολο υποψηφίων, μέσω μιας διαδικασίας δοκιμής- σφάλματος. Αυτή η διαδικασία είναι επιρρεπής σε λάθη καθώς και χρονοβόρα. Στην πράξη μπορεί να απαιτεί περισσότερο χρόνο ακόμη κι από τη διαδικασία επίλυσης του ίδιου του προβλήματος, λόγω του υπολογιστικού φόρτου των χρησιμοποιούμενων στατιστικών μεθόδων. Επιπλέον, δε λαμβάνει άμεσα υπόψη την δυναμική του κάθε αλγορίθμου σε πραγματικό χρόνο, δηλαδή τις διακυμάνσεις της απόδοσης κατά την εκτέλεσή του. Τα Χαρτοφυλάκια Αλγορίθμων αποτελούν σχήματα που ενσωματώνουν διαφορετικούς αλγορίθμους ή διαφορετικές εκδοχές του ίδιου αλγορίθμου, οι οποίες εκτελούνται σειριακά (σε μία μονάδα επεξεργασίας) ή παράλληλα (όταν περισσότερες μονάδες επεξεργασίας είναι διαθέσιμες). Στην πρώτη περίπτωση, οι αλγόριθμοι του χαρτοφυλακίου εναλλάσσουν την εκτέλεσή τους, καταναλώνοντας ο καθένας εκ περιτροπής ένα τμήμα των διαθέσιμων υπολογιστικών πόρων (συναρτησιακοί υπολογισμοί ή χρόνος). Στη δεύτερη περίπτωση, οι μονάδες επεξεργασίας και οι υπολογιστικοί πόροι μοιράζονται μεταξύ των αλγορίθμων σύμφωνα με ένα προκαθορισμένο πλάνο, προσφέροντας προφανή πλεονεκτήματα ως προς το χρόνο εκτέλεσης. Το πλάνο κατανομής πόρων καθορίζεται συνήθως πριν από την εφαρμογή του χαρτοφυλακίου, διαμέσου προκαταρκτικής πειραματικής μελέτης ή ιστορικών δεδομένων απόδοσης των αλγορίθμων. Ωστόσο, η εκχώρηση προκαθορισμένων τμημάτων των υπολογιστικών πόρων μπορεί να είναι μη αποτελεσματική, καθώς δεν λαμβάνει υπόψη τη δυναμική του κάθε αλγορίθμου σε πραγματικό χρόνο. Σε τέτοιες περιπτώσεις, η δυναμική κατανομή πόρων κατά την εκτέλεση του χαρτοφυλακίου μπορεί να αποδειχθεί ιδιαίτερα επωφελής. Οι κύριοι στόχοι της διατριβής είναι η αιτιολόγηση της χρήσης χαρτοφυλακίων μεταευρετικών αλγορίθμων σε προβλήματα βελτιστοποίησης διαφόρων τύπων και η ανάπτυξη νέων μοντέλων παράλληλων χαρτοφυλακίων αλγορίθμων με δυναμικά προσαρμοζόμενα σχέδια κατανομής υπολογιστικών πόρων. Στο πρώτο μέρος της διατριβής δίνονται κίνητρα για τη χρήση χαρτοφυλακίων αλγορίθμων, διερευνάται η χρησιμότητα των μηχανισμών κατανομής υπολογιστικών πόρων σε μεταευρετικούς αλγορίθμους και προτείνονται δύο απλά παράλληλα μοντέλα χαρτοφυλακίων αλγορίθμων. Το πρώτο μοντέλο μπορεί να χρησιμοποιηθεί με οποιονδήποτε αλγόριθμο βελτιστοποίησης και εφαρμόζεται στο σχεδιασμό κρυπτογραφικά ισχυρών S-boxes, το οποίο είναι ένα σημαντικό πρόβλημα στην κρυπτογραφία. Το δεύτερο μοντέλο είναι κατάλληλο για πλυθησμιακούς αλγορίθμους και εφαρμόζεται στο πρόβλημα χρονοπρογραμματισμού φωτεινών σηματοδοτών σε περιβάλλοντα έξυπνων πόλεων. Στο δεύτερο μέρος της εργασίας, προτείνονται δύο νέα παράλληλα μοντέλα χαρτοφυλακίων αλγορίθμων, τα οποία υλοποιούν νέους μηχανισμούς κατανομής υπολογιστικών πόρων. Το πρώτο μοντέλο είναι ένα χαρτοφυλάκιο αλγορίθμων βασισμένο σε συναλλαγές, το οποίο χρησιμοποιεί ένα νέο μηχανισμό κατανομής πόρων, σύμφωνα με τον οποίο οι αλγόριθμοί του μπορούν να πωλούν λύσεις κερδίζοντας επιπλέον χρόνο εκτέλεσης. Το μοντέλο είναι αυτόνομο και επιτρέπει στους αλγορίθμους να αλληλεπιδρούν όταν πληρούνται συγκεκριμένες συνθήκες (για παράδειγμα στασιμότητα αναζήτησης). Το μοντέλο εφαρμόζεται σε τρία απαιτητικά προβλήματα όπως η ανίχνευση κυκλικών πινάκων στάθμισης, ο προσδιορισμός μεγέθους παρτίδας σε συστήματα παραγωγής με επιστροφές και ανακατασκευή προϊόντων, καθώς και η μεταφορά εμπορευμάτων σε ανθρωπιστικές εφοδιαστικές αλυσίδες. Το δεύτερο προτεινόμενο μοντέλο είναι ένα χαρτοφυλάκιο αλγορίθμων βασισμένο σε προβλέψεις, το οποίο χρησιμοποιεί τεχνικές πρόβλεψης χρονοσειρών για την πρόβλεψη της απόδοσης των αλγορίθμων που το αποτελούν. Οι προβλέψεις χρησιμοποιούνται για τον κατάλληλο διαμοιρασμό των διαθέσιμων υπολογιστικών πόρων στους αλγορίθμους του χαρτοφυλακίου. Το μοντέλο εφαρμόζεται στην ανίχνευση κυκλικών πινάκων στάθμισης.
Τα προβλήματα βελτιστοποίησης είναι πανταχού παρόντα στην επιστήμη και στη μηχανική. Εμφανίζονται σε διάφορους τύπους και μορφές σε όλες σχεδόν τις διαδικασίες λήψης αποφάσεων. Η αφθονία και η ποικιλομορφία των προβλημάτων βελτιστοποίησης έχουν δώσει πρόσφορο έδαφος για την ανάπτυξη καινοτόμων μεθόδων και τεχνικών επίλυσης. Διάφορες μέθοδοι βελτιστοποίησης έχουν προταθεί τις τελευταίες δεκαετίες, καταγράφοντας διαρκή αύξηση των διαθέσιμων αλγορίθμων. Ωστόσο, τόσο θεωρητικές όσο και πειραματικές μελέτες καταλήγουν στο συμπέρασμα ότι η ύπαρξη ενός καθολικού αλγορίθμου βελτιστοποίησης ικανού να αντιμετωπίσει εξίσου καλά όλα τα δυνατά προβλήματα βελτιστοποίησης είναι απίθανη. Έτσι, ο προσδιορισμός του κατάλληλου αλγορίθμου καθορίζει το όριο μεταξύ επιτυχίας και αποτυχίας όταν ο στόχος είναι η επίλυση απαιτητικών προβλημάτων βελτιστοποίησης. Μια από τις πιο σημαντικές αποφάσεις της διαδικασίας επίλυσης είναι η επιλογή του αλγορίθμου βελτιστοποίησης που θα χρησιμοποιηθεί. Πρόκειται για μια δύσκολη επιλογή που συνήθως απαιτεί βαθιά γνώση του προβλήματος αλλά και εμπειρία. Σε περίπτωση που οι διαθέσιμες πληροφορίες για το πρόβλημα είναι περιορισμένες, συνήθως απαιτείται προκαταρκτική πειραματική μελέτη για την επιλογή του καταλληλότερου αλγορίθμου από ένα σύνολο υποψηφίων, μέσω μιας διαδικασίας δοκιμής- σφάλματος. Αυτή η διαδικασία είναι επιρρεπής σε λάθη καθώς και χρονοβόρα. Στην πράξη μπορεί να απαιτεί περισσότερο χρόνο ακόμη κι από τη διαδικασία επίλυσης του ίδιου του προβλήματος, λόγω του υπολογιστικού φόρτου των χρησιμοποιούμενων στατιστικών μεθόδων. Επιπλέον, δε λαμβάνει άμεσα υπόψη την δυναμική του κάθε αλγορίθμου σε πραγματικό χρόνο, δηλαδή τις διακυμάνσεις της απόδοσης κατά την εκτέλεσή του. Τα Χαρτοφυλάκια Αλγορίθμων αποτελούν σχήματα που ενσωματώνουν διαφορετικούς αλγορίθμους ή διαφορετικές εκδοχές του ίδιου αλγορίθμου, οι οποίες εκτελούνται σειριακά (σε μία μονάδα επεξεργασίας) ή παράλληλα (όταν περισσότερες μονάδες επεξεργασίας είναι διαθέσιμες). Στην πρώτη περίπτωση, οι αλγόριθμοι του χαρτοφυλακίου εναλλάσσουν την εκτέλεσή τους, καταναλώνοντας ο καθένας εκ περιτροπής ένα τμήμα των διαθέσιμων υπολογιστικών πόρων (συναρτησιακοί υπολογισμοί ή χρόνος). Στη δεύτερη περίπτωση, οι μονάδες επεξεργασίας και οι υπολογιστικοί πόροι μοιράζονται μεταξύ των αλγορίθμων σύμφωνα με ένα προκαθορισμένο πλάνο, προσφέροντας προφανή πλεονεκτήματα ως προς το χρόνο εκτέλεσης. Το πλάνο κατανομής πόρων καθορίζεται συνήθως πριν από την εφαρμογή του χαρτοφυλακίου, διαμέσου προκαταρκτικής πειραματικής μελέτης ή ιστορικών δεδομένων απόδοσης των αλγορίθμων. Ωστόσο, η εκχώρηση προκαθορισμένων τμημάτων των υπολογιστικών πόρων μπορεί να είναι μη αποτελεσματική, καθώς δεν λαμβάνει υπόψη τη δυναμική του κάθε αλγορίθμου σε πραγματικό χρόνο. Σε τέτοιες περιπτώσεις, η δυναμική κατανομή πόρων κατά την εκτέλεση του χαρτοφυλακίου μπορεί να αποδειχθεί ιδιαίτερα επωφελής. Οι κύριοι στόχοι της διατριβής είναι η αιτιολόγηση της χρήσης χαρτοφυλακίων μεταευρετικών αλγορίθμων σε προβλήματα βελτιστοποίησης διαφόρων τύπων και η ανάπτυξη νέων μοντέλων παράλληλων χαρτοφυλακίων αλγορίθμων με δυναμικά προσαρμοζόμενα σχέδια κατανομής υπολογιστικών πόρων. Στο πρώτο μέρος της διατριβής δίνονται κίνητρα για τη χρήση χαρτοφυλακίων αλγορίθμων, διερευνάται η χρησιμότητα των μηχανισμών κατανομής υπολογιστικών πόρων σε μεταευρετικούς αλγορίθμους και προτείνονται δύο απλά παράλληλα μοντέλα χαρτοφυλακίων αλγορίθμων. Το πρώτο μοντέλο μπορεί να χρησιμοποιηθεί με οποιονδήποτε αλγόριθμο βελτιστοποίησης και εφαρμόζεται στο σχεδιασμό κρυπτογραφικά ισχυρών S-boxes, το οποίο είναι ένα σημαντικό πρόβλημα στην κρυπτογραφία. Το δεύτερο μοντέλο είναι κατάλληλο για πλυθησμιακούς αλγορίθμους και εφαρμόζεται στο πρόβλημα χρονοπρογραμματισμού φωτεινών σηματοδοτών σε περιβάλλοντα έξυπνων πόλεων. Στο δεύτερο μέρος της εργασίας, προτείνονται δύο νέα παράλληλα μοντέλα χαρτοφυλακίων αλγορίθμων, τα οποία υλοποιούν νέους μηχανισμούς κατανομής υπολογιστικών πόρων. Το πρώτο μοντέλο είναι ένα χαρτοφυλάκιο αλγορίθμων βασισμένο σε συναλλαγές, το οποίο χρησιμοποιεί ένα νέο μηχανισμό κατανομής πόρων, σύμφωνα με τον οποίο οι αλγόριθμοί του μπορούν να πωλούν λύσεις κερδίζοντας επιπλέον χρόνο εκτέλεσης. Το μοντέλο είναι αυτόνομο και επιτρέπει στους αλγορίθμους να αλληλεπιδρούν όταν πληρούνται συγκεκριμένες συνθήκες (για παράδειγμα στασιμότητα αναζήτησης). Το μοντέλο εφαρμόζεται σε τρία απαιτητικά προβλήματα όπως η ανίχνευση κυκλικών πινάκων στάθμισης, ο προσδιορισμός μεγέθους παρτίδας σε συστήματα παραγωγής με επιστροφές και ανακατασκευή προϊόντων, καθώς και η μεταφορά εμπορευμάτων σε ανθρωπιστικές εφοδιαστικές αλυσίδες. Το δεύτερο προτεινόμενο μοντέλο είναι ένα χαρτοφυλάκιο αλγορίθμων βασισμένο σε προβλέψεις, το οποίο χρησιμοποιεί τεχνικές πρόβλεψης χρονοσειρών για την πρόβλεψη της απόδοσης των αλγορίθμων που το αποτελούν. Οι προβλέψεις χρησιμοποιούνται για τον κατάλληλο διαμοιρασμό των διαθέσιμων υπολογιστικών πόρων στους αλγορίθμους του χαρτοφυλακίου. Το μοντέλο εφαρμόζεται στην ανίχνευση κυκλικών πινάκων στάθμισης.
Περιγραφή
Λέξεις-κλειδιά
Παράλληλα χαρτοφυλάκια αλγορίθμων, Μεταευρετικοί αλγόριθμοι, Υπολογιστική βελτιστοποίηση, Parallel algorithm portfolios, Metaheuristic algorithms, Computational optimization
Θεματική κατηγορία
Computer algorithms
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Παρσόπουλος, Κωνσταντίνος
Εξεταστική επιτροπή
Παρσόπουλος, Κωνσταντίνος
Alba, Enrique
Λαγαρής, Ισαάκ
Kotsireas, Ilias
Δημακόπουλος, Βασίλειος
Παπαγεωργίου, Δημήτριος
Σκούρη, Κωνσταντίνα
Alba, Enrique
Λαγαρής, Ισαάκ
Kotsireas, Ilias
Δημακόπουλος, Βασίλειος
Παπαγεωργίου, Δημήτριος
Σκούρη, Κωνσταντίνα
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία : σ. 155-170
Ονόματα συντελεστών
Αριθμός σελίδων
175 σ.