Online parameter adaptation methods for population-based metaheurisistics
Loading...
Date
Authors
Τάτσης, Βασίλειος
Journal Title
Journal ISSN
Volume Title
Publisher
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Abstract
Type
Type of the conference item
Journal type
Educational material type
Conference Name
Journal name
Book name
Book series
Book edition
Alternative title / Subtitle
Description
Optimization problems lie in the core of scientific and technological development. They appear in
almost 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 method
can be used on any algorithm and tackles both scalar and discrete parameters (including categorical
ones). 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-based Parameter Adaptation Method with Line Search, αντικαθιστά την αναζήτηση πλέγματος με προσεγγιστική αναζήτηση παραγώγων στο χώρο των παραμέτρων. Η διαδικασία αναζήτησης είναι επιπλέον εφοδιασμένη με μια πρόσφατη τεχνική ευθύγραμμης αναζήτησης χωρίς παραγώγους. Οι παραπάνω τροποποιήσεις προσφέρουν πρόσθετη βελτίωση απόδοσης σε σχέση με τη μέθοδο πλέγματος, όπως αποκαλύπτεται από τη σχετική πειραματική αξιολόγηση.
Τα προβλήματα βελτιστοποίησης βρίσκονται στον πυρήνα της επιστημονικής και τεχνολογικής έρευνας. Εμφανίζονται σχεδόν σε κάθε διαδικασία λήψης αποφάσεων, υπό διάφορους τύπους και μορφές. Για την επίλυση προβλημάτων βελτιστοποίησης έχουν προταθεί πολλοί αλγόριθμοι στη σχετική βιβλιογραφία. Ωστόσο, θεωρητικές μελέτες έδειξαν ότι είναι αδύνατη η ανάπτυξη ενός καθολικά βέλτιστου αλγορίθμου. Για το λόγο αυτό, η έρευνα επικεντρώνεται στην ανάπτυξη αλγορίθμων βελτιστοποίησης για συγκεκριμένα προβλήματα, οι οποίοι ενσωματώνουν ποικίλα χαρακτηριστικά και ad hoc λειτουργίες που εκμεταλλεύονται συγκεκριμένες ιδιότητες του αντίστοιχου προβλήματος βελτιστοποίησης. Τυπικά, οι αλγόριθμοι βελτιστοποίησης έχουν παραμέτρους ελέγχου που προσαρμόζουν τη δυναμική τους με κρίσιμο αντίκτυπο στην απόδοσή τους. Έτσι, η σωστή προσαρμογή παραμέτρων αποτελεί ακρογωνιαίο λίθο για την αποτελεσματική επίλυση προβλημάτων. Για το λόγο αυτό, υπάρχει συνεχές και αυξανόμενο ερευνητικό ενδιαφέρον για τις μεθόδους προσαρμογής παραμέτρων. Η πλειονότητα αυτών των μεθόδων αντιμετωπίζει το πρόβλημα προσαρμογής παραμέτρων offline, δηλαδή πριν από την εκτέλεση του αλγορίθμου. Καθιερωμένες μέθοδοι αυτού του τύπου βασίζονται σε στατιστικές μεθοδολογίες και τα αποτελέσματά τους δύνανται να επαναχρησιμοποιηθούν σε παρόμοια προβλήματα. Ωστόσο, δεν λαμβάνουν υπόψη δεδομένα που προκύπτουν κατά την εκτέλεση του αλγορίθμου, καθώς και πιθανές διακυμάνσεις στην απόδοσή του. Η εναλλακτική προσέγγιση είναι η χρήση online μεθόδων που προσαρμόζουν δυναμικά τις παραμέτρους κατά την εκτέλεση του αλγορίθμου. Αυτές οι μέθοδοι εκμεταλλεύονται δεδομένα απόδοσης του αλγορίθμου που προκύπτουν σε πραγματικό χρόνο και, ως εκ τούτου, μπορούν να ενημερώνουν άμεσα τις παραμέτρους. Ωστόσο, τα αποτελέσματα αυτών των μεθόδων συνήθως δεν είναι επαναχρησιμοποιήσιμα σε παρόμοια προβλήματα. Ο κύριος στόχος της παρούσας διατριβής είναι η ανάπτυξη νέων online μεθόδων προσαρμογής παραμέτρων, με ιδιαίτερη στόχευση στις μεταευρετικές μεθόδους βελτιστοποίησης. Το πρώτο μέρος της διατριβής περιλαμβάνει τις απαραίτητες βασικές πληροφορίες σχετικά με το τρέχον state-of-the-art και τους αλγορίθμους βελτιστοποίησης που θα χρησιμοποιηθούν για την επίδειξη των νέων μεθόδων. Στο δεύτερο μέρος της διατριβής προτείνονται δύο νέες μέθοδοι προσαρμογής παραμέτρων. Η πρώτη μέθοδος, που ονομάζεται Grid-based Parameter Adaptation Method, βασίζεται στην αναζήτηση πλέγματος στο χώρο των παραμέτρων. Η προτεινόμενη μέθοδος μπορεί να χρησιμοποιηθεί σε οποιονδήποτε αλγόριθμο και αντιμετωπίζει τόσο τις πραγματικές όσο και τις διακριτές παραμέτρους (συμπεριλαμβανομένων των κατηγορικών παραμέτρων). Η νέα μέθοδος εφαρμόζεται σε δύο δημοφιλείς μεταευρετικούς αλγορίθμους. Για το σκοπό αυτό, χρησιμοποιούνται δύο βασικές σουίτες δοκιμαστικών προβλημάτων. Η δεύτερη προτεινόμενη μέθοδος, η οποία ονομάζεται Gradient-based Parameter Adaptation Method with Line Search, αντικαθιστά την αναζήτηση πλέγματος με προσεγγιστική αναζήτηση παραγώγων στο χώρο των παραμέτρων. Η διαδικασία αναζήτησης είναι επιπλέον εφοδιασμένη με μια πρόσφατη τεχνική ευθύγραμμης αναζήτησης χωρίς παραγώγους. Οι παραπάνω τροποποιήσεις προσφέρουν πρόσθετη βελτίωση απόδοσης σε σχέση με τη μέθοδο πλέγματος, όπως αποκαλύπτεται από τη σχετική πειραματική αξιολόγηση.
Description
Keywords
Metaheuristics, Optimization, Online parameter adaptation, Parameter control, Differential evolution, Particle swarm optimization, Grid-search, Gradient estimations, Line search, Μεταευρετικοί, Βελτιστοποίηση, Online προσαρμογή παραμέτρων, Ρύθμιση παραμέτρων, Διαφοροεξελικτικός αλγόριθμος, Αλγόριθμος βελτιστοποίησης σμήνους σωματιδίων, Αναζήτηση πλέγματος, Προσεγγιστική αναζήτηση παραγώγων, Ευθύγραμμης αναζήτησης
Subject classification
Optimization
Citation
Link
Language
en
Publishing department/division
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Advisor name
Παρσόπουλος, Κωνσταντίνος Ε.
Examining committee
Παρσόπουλος, Κωνσταντίνος Ε.
Bartz-Beielstein, Thomas
Kotsireas, Ilias S.
Λαγαρής, Ισαάκ
Μπλέκας, Κωνσταντίνος Δ.
Παπαγεωργίου, Δημήτριος
Σκούρη, Κωνσταντίνα
Bartz-Beielstein, Thomas
Kotsireas, Ilias S.
Λαγαρής, Ισαάκ
Μπλέκας, Κωνσταντίνος Δ.
Παπαγεωργίου, Δημήτριος
Σκούρη, Κωνσταντίνα
General Description / Additional Comments
Institution and School/Department of submitter
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Table of contents
Sponsor
Bibliographic citation
Βιβλιογραφία: σ. 89-98
Name(s) of contributor(s)
Number of Pages
126 σ.