Online parameter adaptation methods for population-based metaheurisistics

Abstract

Optimization problems lie in the core of scientific and technological development. They appear inalmost every decision-making process, under various types and forms. A multitude of algorithms have been proposed in relevant literature to solve optimization problems. However, theoretical evidence suggests that the development of an overall optimal algorithm is impossible. For this reason, problemspecific optimization algorithms have been developed, incorporating a variety of features and ad hoc operations that exploit specific properties of the corresponding optimization problem. Typically, optimization algorithms have control parameters that adjust their dynamic with critical impact on their performance. Thus, proper parameter tuning becomes the cornerstone of efficient problem solving. There is a continuous line of research on parameter tuning methods since the early development of optimization algorithms. The majority of these methods addresses the tuning problem offline, i.e., prior to the algorithm’s execution. Established offline methods are based on statistical methodologies to identify promising parameter configurations, and their results may be reusable in problems of similar type. However, they neglect the algorithm’s feed- back and performance fluctuations during its run. The alternative approach is the use of online methods that dynamically adapt the parameters during the algorithm’s run. These methods exploit real-time performance data and, hence, they can make informative decisions on the parameter adaptation. This usually comes at the cost of non-reusable decisions. The main goal of the present thesis is the development of new online parameter adaptation methods that can be particularly useful for the class of metaheuristic optimization algorithms. The first part of the dissertation comprises the necessary background information on the current state-of-the-art and the optimization algorithms that will be used for demonstration purpose. In the second part of the thesis, two new online parameter adaptation methods are proposed. The first method, called Grid-based Parameter Adaptation Method, is based on grid search in the parameter space. The proposed methodcan be used on any algorithm and tackles both scalar and discrete parameters (including categoricalones). The new method is demonstrated on two state-of-the-art metaheuristics. For this purpose, two established benchmark suites are also considered. The second proposed method, called Gradientbased Parameter Adaptation Method with Line Search, replaces the grid search with approximate gradient search in the parameter space. The search procedure is further equipped with a recently proposed gradient-free line search technique. These modifications offer additional performance improvement with respect to the grid-based method, as revealed by the relevant performance assessment.

Τα προβλήµατα βελτιστοποίησης βρίσκονται στον πυρήνα της επιστηµονικής και τεχνολογικής έρευνας. Εµφανίζονται σχεδόν σε κάθε διαδικασία λήψης αποφάσεων, υπό διάφορους τύπους καιµορφές. Για την επίλυση προβληµάτων βελτιστοποίησης έχουν προταθεί πολλοί αλγόριθµοι στησχετική βιβλιογραφία. Ωστόσο, θεωρητικές µελέτες έδειξαν ότι είναι αδύνατη η ανάπτυξη ενός καθολικά βέλτιστου αλγορίθµου. Για το λόγο αυτό, η έρευνα επικεντρώνεται στην ανάπτυξη αλγορίθµων βελτιστοποίησης για συγκεκριµένα προβλήµατα, οι οποίοι ενσωµατώνουν ποικίλα χαρακτηριστικά και ad hoc λειτουργίες που εκµεταλλεύονται συγκεκριµένες ιδιότητες του αντίστοιχου προβλήµατος βελτιστοποίησης. Τυπικά, οι αλγόριθµοι βελτιστοποίησης έχουν παραµέτρους ελέγχου που προσαρµόζουν τη δυναµική τους µε κρίσιµο αντίκτυπο στην απόδοσή τους. Έτσι, η σωστή προσαρµογή παραµέτρων αποτελεί ακρογωνιαίο λίθο για την αποτελεσµατική επίλυση προβληµάτων. Για το λόγο αυτό, υπάρχει συνεχές και αυξανόµενο ερευνητικό ενδιαφέρον για τις µεθόδους προσαρµογής παραµέτρων. Η πλειονότητα αυτών των µεθόδων αντιµετωπίζει το πρόβληµα προσαρµογής παραµέτρων offline, δηλαδή πριν από την εκτέλεση του αλγορίθµου. Καθιερωµένες µέθοδοι αυτού του τύπου βασίζονται σε στατιστικές µεθοδολογίες και τα αποτελέσµατά τους δύνανται να επαναχρησιµοποιηθούν σε παρόµοια προβλήµατα. Ωστόσο, δεν λαµβάνουν υπόψη δεδοµένα που προκύπτουν κατά την εκτέλεση του αλγορίθµου, καθώς και πιθανές διακυµάνσεις στην απόδοσή του. Η εναλλακτική προσέγγιση είναι η χρήση online µεθόδων που προσαρµόζουν δυναµικά τις παραµέτρους κατά την εκτέλεση του αλγορίθµου. Αυτές οι µέθοδοι εκµεταλλεύονται δεδοµένα απόδοσης του αλγορίθµου που προκύπτουν σε πραγµατικό χρόνο και, ως εκ τούτου, µπορούν να ενηµερώνουν άµεσα τις παραµέτρους. Ωστόσο, τα αποτελέσµατα αυτών των µεθόδων συνήθως δεν είναι επαναχρησιµοποιήσιµα σε παρόµοια προβλήµατα. Ο κύριος στόχος της παρούσας διατριβής είναι η ανάπτυξη νέων online µεθόδων προσαρµογής παραµέτρων, µε ιδιαίτερη στόχευση στις µεταευρετικές µεθόδους βελτιστοποίησης. Το πρώτο µέρος της διατριβής περιλαµβάνει τις απαραίτητες βασικές πληροφορίες σχετικά µε το τρέχον state-of-the-art και τους αλγορίθµους βελτιστοποίησης που θα χρησιµοποιηθούν για την επίδειξη των νέων µεθόδων. Στο δεύτερο µέρος της διατριβής προτείνονται δύο νέες µέθοδοι προσαρµογής παραµέτρων. Η πρώτηµέθοδος, που ονοµάζεται Grid-based Parameter Adaptation Method, βασίζεται στην αναζήτησηπλέγµατος στο χώρο των παραµέτρων. Η προτεινόµενη µέθοδος µπορεί να χρησιµοποιηθεί σεοποιονδήποτε αλγόριθµο και αντιµετωπίζει τόσο τις πραγµατικές όσο και τις διακριτές παραµέτρους(συµπεριλαµβανοµένων των κατηγορικών παραµέτρων). Η νέα µέθοδος εφαρµόζεται σε δύοδηµοφιλείς µεταευρετικούς αλγορίθµους. Για το σκοπό αυτό, χρησιµοποιούνται δύο βασικές σουίτεςδοκιµαστικών προβληµάτων. Η δεύτερη προτεινόµενη µέθοδος, η οποία ονοµάζεται Gradient-basedParameter Adaptation Method with Line Search, αντικαθιστά την αναζήτηση πλέγµατος µεπροσεγγιστική αναζήτηση παραγώγων στο χώρο των παραµέτρων. Η διαδικασία αναζήτησης είναιεπιπλέον εφοδιασµένη µε µια πρόσφατη τεχνική ευθύγραµµης αναζήτησης χωρίς παραγώγους. Οιπαραπάνω τροποποιήσεις προσφέρουν πρόσθετη βελτίωση απόδοσης σε σχέση µε τη µέθοδοπλέγµατος, όπως αποκαλύπτεται από τη σχετική πειραµατική αξιολόγηση.