Υβριδικοί εξελικτικοί αλγόριθμοι βελτιστοποίησης και εφαρμογές σε προβλήματα συνδυαστικής βελτιστοποίησης
Authors: Πέτικας Ισίδωρος 
Published: August 2021

Αντικείμενο της παρούσας διατριβής αποτελεί η μελέτη και έρευνα αποτελεσματικών αλγοριθμικών προσεγγίσεων για την αντιμετώπιση υπολογιστικά δύσκολων προβλημάτων βελτιστοποίησης, μέσω της ανάλυσης και πρότασης μεθοδολογιών υβριδικών εξελικτικών αλγορίθμων και της διατύπωσης του πλαισίου εφαρμογής τους σε συγκεκριμένα προβλήματα. Στην κατεύθυνση αυτή, αρχικά εξετάζονται και αναλύονται διεξοδικά οι μηχανισμοί που διέπουν τις εξελικτικές μεθόδους και άλλες επιλεγμένες μετα-ευρετικές μεθόδους βελτιστοποίησης, με έμφαση στους αλγορίθμους τοπικής αναζήτησης, ενώ επίσης γίνεται εκτενής αναφορά στην εφαρμογή των μεθόδων αυτών σε κλασσικά και σύγχρονα προβλήματα συνδυαστικής βελτιστοποίησης, κατά κύριο λόγο στις συνδυαστικές τους μορφές.Αναλύεται και προτείνεται μια μεθοδολογία υβριδικής εξελικτικής προσέγγισης, η οποία έχει ως βασικό στόχο την αξιοποίηση των ξεχωριστών πλεονεκτημάτων και την αντιμετώπιση των αδυναμιών των εξελικτικών διαδικασιών και των αλγορίθμων τοπικής αναζήτησης, συνδυάζοντάς τους σε ένα ενιαίο υβριδικό αλγοριθμικό σχήμα. Η προσέγγιση περιλαμβάνει δύο στάδια: Κατά το πρώτο, η εξελικτική διαδικασία χρησιμοποιείται για την ολική εξερεύνηση του χώρου λύσεων, ενώ κατά το δεύτερο, η εφαρμοζόμενη μέθοδος τοπικής αναζήτησης αξιοποιεί τη γνώση που αποκτήθηκε από την εξερεύνηση αυτή. Για την υλοποίηση, την εφαρμογή και την αξιολόγηση της προσέγγισης, επιλέγονται ένας γενετικός αλγόριθμος και ένας αλγόριθμος γενικευμένης πρότυπης αναζήτησης, αντίστοιχα. Επιπρόσθετα, ανάλογα με τη φύση και τη διατύπωση του προβλήματος που εξετάζεται, πραγματοποιείται διάκριση των περιορισμών σε θεμελιώδεις και ελαστικούς και υιοθετείται διαφορετική αντιμετώπιση των προκυπτουσών λύσεων, που παραβιάζουν κάθε κατηγορία περιορισμών.Για την εκτίμηση της αποτελεσματικότητας της προτεινόμενης μεθοδολογίας, πραγματοποιείται εφαρμογή της σε δύο προβλήματα βελτιστοποίησης διαφορετικής φύσης, αναφορικά με τη μορφή του χώρου λύσεων και τη διατύπωση των περιοριστικών συνθηκών. Το πρόβλημα της οικονομικής κατανομής ηλεκτρικού φορτίου (ΕLD) αντιμετωπίζεται ως ένα συνεχές πρόβλημα βελτιστοποίησης με ενιαία θεώρηση περιορισμών, ενώ το πρόβλημα της βέλτιστης τοποθέτησης των ανεμογεννητριών σε ένα αιολικό πάρκο αντιμετωπίζεται ως ένα πρόβλημα ακέραιου προγραμματισμού με διάκριση των περιορισμών σε θεμελιώδεις και ελαστικούς. Παρουσιάζεται αναλυτικά ο τρόπος προσέγγισης και μοντελοποίησης του κάθε προβλήματος, δημιουργώντας ένα χρήσιμο πλαίσιο αντιμετώπισης τους εντός των παραδοχών που διατυπώνονται. Η ανάπτυξη και των δύο εφαρμογών πραγματοποιείται στο προγραμματιστικό περιβάλλον του Matlab©. Τα αποτελέσματα της εφαρμογής της προτεινόμενης προσέγγισης καταδεικνύουν τη βελτίωση των τελικών λύσεων σε σχέση με εκείνες που επιστρέφει ο αμιγής εξελικτικός αλγόριθμος και στις δύο περιπτώσεις. Η τάξη μεγέθους της βελτίωσης που προκύπτει είναι διαφορετική για καθένα από τα δύο προβλήματα, κάτι το οποίο οδηγεί στο συμπέρασμα, ότι τα οφέλη της προτεινόμενης υβριδικής προσέγγισης εξαρτώνται από τη φύση και τις ιδιαιτερότητες του υπό εξέταση προβλήματος βελτιστοποίησης.