New approaches in parallel algorithm portfolios for metaheuristic optimization

Abstract

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 population-based 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, το οποίο είναι ένα σημαντικό πρόβλημα στην κρυπτογραφία. Το δεύτερο μοντέλο είναι κατάλληλο για πλυθησμιακούς αλγορίθμους και εφαρμόζεται στο πρόβλημα χρονοπρογραμματισμού φωτεινών σηματοδοτών σε περιβάλλοντα έξυπνων πόλεων. Στο δεύτερο μέρος της εργασίας, προτείνονται δύο νέα παράλληλα μοντέλα χαρτοφυλακίων αλγορίθμων, τα οποία υλοποιούν νέους μηχανισμούς κατανομής υπολογιστικών πόρων. Το πρώτο μοντέλο είναι ένα χαρτοφυλάκιο αλγορίθμων βασισμένο σε συναλλαγές, το οποίο χρησιμοποιεί ένα νέο μηχανισμό κατανομής πόρων, σύμφωνα με τον οποίο οι αλγόριθμοί του μπορούν να πωλούν λύσεις κερδίζοντας επιπλέον χρόνο εκτέλεσης. Το μοντέλο είναι αυτόνομο και επιτρέπει στους αλγορίθμους να αλληλεπιδρούν όταν πληρούνται συγκεκριμένες συνθήκες (για παράδειγμα στασιμότητα αναζήτησης). Το μοντέλο εφαρμόζεται σε τρία απαιτητικά προβλήματα όπως η ανίχνευση κυκλικών πινάκων στάθμισης, ο προσδιορισμός μεγέθους παρτίδας σε συστήματα παραγωγής με επιστροφές και ανακατασκευή προϊόντων, καθώς και η μεταφορά εμπορευμάτων σε ανθρωπιστικές εφοδιαστικές αλυσίδες. Το δεύτερο προτεινόμενο μοντέλο είναι ένα χαρτοφυλάκιο αλγορίθμων βασισμένο σε προβλέψεις, το οποίο χρησιμοποιεί τεχνικές πρόβλεψης χρονοσειρών για την πρόβλεψη της απόδοσης των αλγορίθμων που το αποτελούν. Οι προβλέψεις χρησιμοποιούνται για τον κατάλληλο διαμοιρασμό των διαθέσιμων υπολογιστικών πόρων στους αλγορίθμους του χαρτοφυλακίου. Το μοντέλο εφαρμόζεται στην ανίχνευση κυκλικών πινάκων στάθμισης.