Συντάχθηκε 22-09-2021 09:42
Τόπος: Η παρουσίαση θα γίνει με τηλεδιάσκεψη
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 24/09/2021 09:00
Λήξη: 24/09/2021 10:00
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΒΑΣΙΛΕΙΟΣ ΛΥΜΠΕΡΑΚΗΣ
θέμα
Μία Καινοτόμος Μετα-ευρετική Μέθοδος Αναζήτησης για Καθολική Βελτιστοποίηση Συνεχών Συναρτήσεων
A Novel Meta-heuristic Search Algorithm for Global Continuous Optimization
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Βασίλειος Σαμολαδάς
Επίκουρος Καθηγητής Αθανάσιος Άρης Παναγόπουλος (Σχολή Computer Science, California State University, Fresno, CA)
Περίληψη
Ένας εκ των παραδοσιακών πυλώνων της Τεχνητής Νοημοσύνης είναι αυτός που ασχολείται με τεχνικές αναζήτησης και βελτιστοποίησης, που επιχειρούν την εύρεση της βέλτιστης λύσης εντός ενός ευρέος φάσματος επιλογών. Η καθολική συνεχής βελτιστοποίηση ασχολείται με την επίλυση προβλημάτων βελτιστοποίησης πολύπλοκων συνεχών συναρτήσεων. Οι μετα-ευρετικοί αλγόριθμοι χρησιμοποιούνται ευρέως για την επίλυση τέτοιων προβλημάτων. Οι περισσότεροι όμως μετα-ευρετικοί αλγόριθμοι, έχουν σχεδιαστεί για την επίλυση διακριτών προβλημάτων και αργότερα αναπροσαρμόστηκαν για τη χρήση τους σε συνεχή προβλήματα. Αυτό αυξάνει το χρονικό κόστος εξεύρεσης λύσης. Επίσης, η πιθανότητα να καταλήξουν σε τοπικά βέλτιστα αυξάνεται με την πολυπλοκότητα του χώρου. Ακόμη, τείνουν να αποδέχονται χειρότερες λύσεις, για να επιτύχουν πιο ευρεία εξερεύνηση του χώρου. Αυτό έχει σαν αποτέλεσμα να αποτελούν συνήθως μεθόδους αναζήτησης, οι οποίες δεν βελτιώνονται συνεχώς με την πάροδο του χρόνου. Ως εκ τούτου, μια πιθανή πρόωρη διακοπή της ροής του αλγορίθμου, μπορεί να καταστήσει μεγάλο μέρος της υπολογιστικής διαδικασίας πριν την διακοπή της διαδικασίας κενού νοήματος αφού οι τελευταίες λύσεις μπορεί να είναι χειρότερες από την καλύτερη που έχει βρεθεί ως εκείνη τη στιγμή.
Στην παρούσα διπλωματική εργασία προτείνεται ένας νέος μετα-ευρετικός αλγόριθμος μονής-λύσης που είναι σχεδιασμένος για να λύνει συνεχή προβλήματα και που μπορεί να διακοπεί ανά πάσα στιγμή με την εγγύηση ότι η τελευταία λύση θα είναι πάντα καλύτερη από τις προηγούμενες. Ο αλγόριθμός μας, επονομαζόμενος "ελαττωματικό φλιπεράκι", είναι εμπνευσμένος από το διαδεδομένο παιχνίδι φλίπερ, όπου εφαρμόζεται ένας τρόπος εύρεσης με τη δημιουργία τροχιάς και κάθε καινούρια λύση βελτιώνει την ήδη υπάρχουσα. Αξιολογήσαμε τον αλγόριθμό μας σε πλείστες κλασσικές συναρτήσεις συνεχούς βελτιστοποίησης, και συγκρίναμε τις επιδόσεις του με αυτές κάποιων από τους πιο διαδεδομένους μετα-ευρετικούς αλγορίθμους αναζήτησης: την προσομοιωμένη ανόπτηση, την αποδοχή ορίου, και την βελτιστοποίηση σμήνους σωματιδίων. Η συστηματική διαδικασία αξιολόγησής μας, αποδεικνύει την αποτελεσματικότητα του αλγορίθμου μας σε καθολικά συνεχή προβλήματα, και ιδιαίτερα την σημαντική υπεροχή του έναντι των ανταγωνιστών του ειδικά σε πολύπλοκους χώρους αναζήτησης.
Abstract
Artificial intelligence research in optimization and search is concerned with reaching the maxima or minima of an objective function, while potentially searching among a vast range of value choices for the function’s variables. Global continuous optimization methods, in particular, seek to reach the optima of complex continuous mathematical functions. Meta-heuristics are commonly used in order to solve such problems. Typically, however, meta-heuristics originally designed for solving discrete optimization problems are later adapted to continuous tasks, which consumes considerable time. Also, there is a chance that they will get stuck to local optima as the complexity of configuration spaces increases. Furthermore, generally meta-heuristics accept worse solutions, in order to achieve a broader exploration of the configuration space. This results in algorithms that do not improve in an anytime manner, and an arbitrary interruption of the algorithm’s flow, can lead to a waste of computation time as the current solution might be worse than a solution discovered earlier on.
In this work, a novel single-point meta-heuristic is proposed, which is specifically designed to tackle continuous optimization problems. Our algorithm, Buggy Pinball, is an anytime algorithm inspired by the well-known pinball game: It employs a trajectory-based search, and each proposed solution ensures the improvement of the configuration space. In order to evaluate our algorithm, we used a number of standard testbed functions, which can also be applied on multiple dimensions. We compared our results to the performance of some of the most widely used meta-heuristics, namely simulated annealing, threshold accepting, and particle swarm optimization. Our systematic evaluation shows that our algorithm is very efficient in global continuous optimization tasks, with performance that is particularly successful in complex configuration spaces.
Meeting ID: 910 5594 9139
Password: 974282
