| Περίληψη: | Η βελτιστοποίηση χρησιμοποιείται κατά κόρον στο πεδίο των μαθηματικών αλλά και σε πολλούς άλλους τομείς της επιστήμης, όπως στη διοίκηση επιχειρήσεων, την οικονομία, τη βιολογία, κ.α.. Δεν είναι λίγες οι φορές που ακούμε ότι εταιρείες ή το κράτος ενεργούν για την βελτιστοποίηση της χρήσης των πληροφοριών, της τεχνολογίας, της διαχείρισης των ανθρώπινων πόρων, του προσωπικού, των παρεχόμενων υπηρεσιών και των διαδικασιών.
Το εύρος των εφαρμογών της βελτιστοποίησης την καθιστά περιοχή που παρόλο που έχουν προταθεί πολλές μέθοδοι η έρευνα έχει ακόμα μεγάλη σημασία. Αντικείμενο της παρούσας διατριβής είναι η επίλυση προβλημάτων βελτιστοποίησης χωρίς περιορισμούς με τη χρήση επαναληπτικών μεθόδων. Ένα μεγάλο πρόβλημα πολλών επαναληπτικών αλγορίθμων βελτιστοποίησης είναι το γεγονός ότι η επιτυχία τους εξαρτάται άμεσα από την αρχική προσέγγιση της λύσης. Στην εργασία αυτή, προτείνουμε τεχνικές οι οποίες διευθετούν αυτό το πρόβλημα και παρουσιάζουμε μία νέα οικογένεια αλγορίθμων βελτιστοποίησης χωρίς περιορισμούς. Στις παρουσιαζόμενες τεχνικές, ευρέως γνωστοί αλγόριθμοι βελτιστοποίησης ενσωματώνονται μέσα στις προτεινόμενες τεχνικές με αποτέλεσμα να ενισχύονται τα καλά τους χαρακτηριστικά και να βελτιώνεται η αποδοτικότητά τους.
Tο πρώτο κεφάλαιο της παρούσας διατριβής αποτελεί ένα εισαγωγικό κεφάλαιο στο οποίο, παρουσιάζονται βασικές έννοιες που βοηθούν στην καλύτερη κατανόηση των επόμενων κεφαλαίων.
Στο δεύτερο κεφάλαιο, αρχικά δίνεται η κύρια ιδέα των αλγορίθμων της παρούσας διατριβής, σύμφωνα με την οποία, γνωστές μέθοδοι βελτιστοποίησης συνδυάζονται με τέτοιον τρόπο ώστε οι κατευθύνσεις που δίνονται από αυτές, να δημιουργούν μια νέα κατεύθυνση πάνω στην οποία αναζητείται το βέλτιστο. Για την υλοποίηση της προτεινόμενης ιδέας ορίζονται γενικές αρχές και ακολουθώντας αυτές τις αρχές προκύπτουν προσεγγιστικά προβλήματα του δοθέντος. Το σημείο που χρησιμοποιείται ως αρχικό για την επίλυση του δοθέντος προβλήματος από μια μέθοδο βελτιστοποίησης είναι αυτό που προκύπτει από ένα προπαρασκευαστικό βήμα, του οποίου τα σταδια είναι τα εξής: (α) η κατασκευή προσεγγιστικών
προβλημάτων, των οποίων οι αντικειμενικές συναρτήσεις αναφέρονται και ως εμπλεκόμενες αντικειμενικές συναρτήσεις (β) η απόδοση προτεραιοτήτων στα προσεγγιστικά προβλήματα και (γ) η ακολουθιακή και μη εξαντλητική επίλυση των προσεγγιστικών προβλημάτων.
Στο ίδιο κεφάλαιο παρουσιάζεται η προτεινομένη τεχνική του Lexicographic Optimization (LexOpt) αλγορίθμου, όπου οι εμπλεκόμενες αντικειμενικές συναρτήσεις εξάγονται με τη χρήση μιας από τις προταθείσες αρχές, την αθροιστική αρχή. Συγκρίνοντας τα αποτελέσματα του LexOpt αλγορίθμου με τα αποτελέσματα των μεθόδων βελτιστοποίησης που χρησιμοποιεί, παρατηρείται διαφορετική συμπεριφορά σύγκλισης, είτε στο υπολογιστικό κόστος είτε στο πλήθος των ελαχίστων που συγκλίνει ή και στα δύο. Αξιοσημείωτο είναι ότι από την πλειοψηφία των συναρτήσεων δοκιμών διαπιστώνεται ότι υπάρχει τρόπος με τον οποίο ο LexOpt αλγόριθμος συγκλίνει, ξεκινώντας από τα ίδια αρχικά σημεία, σε μεγαλύτερο πλήθος ελαχίστων απ' ότι οι μέθοδοι που χρησιμοποιεί και μάλιστα με τέτοιο υπολογιστικό κόστος που μας οδηγεί σε καταφατική απάντηση στο ερώτημα αν χρειάζεται να υπάρξει συνέχιση της έρευνας ως προς τη συμπεριφορά του.
Στο τρίτο κεφάλαιο της διατριβής παρουσιάζεται η προτεινομένη τεχνική του Taylor Lexicographic Sequential Optimization (TLSO) αλγορίθμου, όπου οι εμπλεκόμενες αντικειμενικές συναρτήσεις εξάγονται με τη χρήση μιας άλλης προτεινόμενης αρχής, την ακολουθιακή αρχή. Στον αλγόριθμο αυτό αξιοποιείται η πληροφορία που περικλείεται στους άπειρους όρους του αναπτύγματος Taylor αποφεύγοντας τον υπολογισμό τους. Όπως ο LexOpt έτσι και ο TLSO αλγόριθμος αν εφαρμοστούν επιλέγοντας τυχαία αρχικά σημεία από μια περιοχή συγκλίνουν σε περισσότερα σημεία από ότι συγκλίνει η μέθοδος βελτιστοποίησης που χρησιμοποιούν, αν και αυτή ξεκινήσει από τα ίδια αρχικά σημεία. H κύρια διαφορά των LexOpt και TLSO αλγορίθμων είναι ότι στον LexOpt αλγόριθμο οι αντικειμενικές συναρτήσεις των προβλημάτων του προπαρασκευαστικού βήματος κατασκευάζονται από τον τύπο
της αντικειμενικής συνάρτησης του δοθέντος προβλήματος, ενώ στον TLSO αλγόριθμο κατασκευάζονται από την προσέγγιση κατά Taylor της αντικειμενικής συνάρτησης του δοθέντος προβλήματος.
Με κίνητρο το να μειωθεί το υπολογιστικό κόστος των αλγορίθμων που ήδη αναφέρθηκαν, προτάθηκε η τεχνική του Trust Lexicographic Optimization (TrustLexOpt) αλγορίθμου. Ο TrustLexOpt αλγόριθμος βασίζεται στον LexOpt αλγόριθμο και παρουσιάζεται στο τέταρτο κεφάλαιο της παρούσας διατριβής. Με τον αλγόριθμο αυτό μειώνεται το πλήθος των προβλημάτων που χρησιμοποιούνται στο προπαρασκευαστικό βήμα και παράλληλα προτείνεται η χρήση ενός συνδυασμού trust region και line search μεθόδων. Σε σχέση με τους αλγορίθμους που έχουν ήδη προταθεί ο TrustLexOpt αλγόριθμος χρησιμοποιεί ένα υποπρόβλημα, δηλαδή το ελάχιστο δυνατό πλήθος υποπροβλημάτων και συνδυάζει μεθόδους που χρησιμοπομοιούν διαστήματα εμπιστοσύνης (trust region) και μεθόδους γραμμικής αναζήτησης (line search) προκειμένου να καταλήξει στο σημείο θα χρησιμοποιήσει ως αρχικό για την εφαρμογή επαναληπτικής μεθόδου βελτιστοποίησης στο δοθέν πρόβλημα. Στο ίδιο κεφάλαιο, προτείνεται και ένας τρόπος υπολογισμού της ακτίνας της χρησιμοποιούμενης trust region μεθόδου.
Η διατύπωση των συμπερασμάτων του τετάρτου κεφαλαίου καθώς και της διατριβής εν γένει, γίνεται υιοθετώντας την αρχή ότι συγκρίνοντας δύο αλγορίθμους, θεωρούμε ότι έχει καλύτερη συμπεριφορά ο αλγόριθμος ο οποίος συγκλίνει στο μεγαλύτερο πλήθος ελαχίστων. Επίσης, αν δύο αλγόριθμοι συγκρινόμενοι μεταξύ τους συγκλίνουν στον ίδιο αριθμό ελαχίστων τότε θεωρούμε ότι ο αλγόριθμος με το μικρότερο υπολογιστικό κόστος είναι αυτός που υπερέχει έναντι των δύο αυτών αλγορίθμων. Υπό αυτή την οπτική γωνία, καταλήξαμε ότι υπάρχει τουλάχιστον ένας συνδυασμός των στοιχείων που προκύπτουν εφαρμόζοντας την αθροιστική αρχή, όπου ο TrustLexOpt γενικότερα υπερέχει έναντι των TLSO και LexOpt αλγορίθμων. Βάσει των αριθμητικών αποτελεσμάτων της παρούσας διατριβής, προτείνεται να γίνει περισσότερη μελέτη και έρευνα για το ποιος είναι ο κατάλληλος συνδυασμός
στοιχείων που αν χρησιμοποιηθούν από τον TrustLexOpt αλγόριθμο βελτιώνουν την απόδοσή του. Επίσης προτείνεται να διερευνηθεί ο λόγος για τον οποίο όταν ο TrustLexOpt αλγόριθμος χρησιμοποιεί την προτεινόμενη στη διατριβή trust region ακτίνα έχει καλύτερη συμπεριφορά από ότι αν χρησιμοποιηθεί η trust region ακτίνα που συνήθως χρησιμοποιείται.
Στο τελευταίο κεφάλαιο της διατριβής προτείνονται οι αλγόριθμοι Modified Lexicographic Optimization (MLX), Relaxation Lexicographic Optimization (RLX) και Modified Relaxation Lexicographic Optimization (MRLX). Ο λόγος για τον οποίο προτείνονται είναι προκειμένου να μελετήσουμε την επίδραση της προσθήκης βαρών σε τμήματα των αντικειμενικών συναρτήσεων που χρησιμοποιούνται στο προπαρασκευαστικό στάδιο του LexOpt αλγορίθμου.
Επίσης, προτείνονται προκειμένου να μελετηθεί η επίδραση του γεγονότος ότι οι αντικειμενικές συναρτήσεις των προβλημάτων του προπαρασκευαστικού βήματος δεν έχουν κοινούς όρους. Η προσθήκη βαρών υλοποιήθηκε χρησιμοποιώντας παραμέτρους τις οποίες ονομάσαμε
παράμετρους χαλάρωσης (relaxation parameters). Στη συνεχεια υπολογίσαμε το λόγο της απόλυτης τιμής της μεγαλύτερης προς τη μικρότερη ιδιοτιμή της αντικειμενικής συνάρτησης του δοθέντος προβλήματος στα σημεία που προκύπτουν από το προπαρασκευαστικό στάδιο. Από μια πρώτη μελέτη του λόγου αυτού, προκύπτει ότι αν χρησιμοποιηθούν παράμετροι χαλάρωσης, επιτυγχάνεται μια υπεροχή των αλγορίθμων LexOpt και MLX έναντι των RLX και MRLX. Τα αποτελέσματα και η μελέτη που παρουσιάζονται στο κεφάλαιο αυτό δεν έχουν δημοσιευτεί μέχρι σήμερα.
Συμπερασματικά, στην παρούσα διατριβή παρουσιάζονται τεχνικές για την βελτίωση της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς. Από τη μελέτη των αριθμητικών αποτελεσμάτων της εφαρμογής των τεχνικών αυτών σε γνωστές συναρτήσεις δοκιμών, προέκυψε ότι σημαντικό ρόλο για τα αποτελέσματα των προτεινόμενων αλγορίθμων παίζει ο τρόπος που δίνονται προτεραιότητες στο προπαρασκευαστικό στάδιο των αλγορίθμων. Έτσι, ο τρόπος απόδοσης προτεραιοτήτων θεωρείται ένα θέμα για το οποίο αξίζει να δαπανηθεί χρόνος για να μελετηθεί περαιτέρω. Ένα σημείο που αξίζει επίσης να μελετηθεί είναι το ποιος είναι ο ιδανικός αριθμός βημάτων που πρέπει να εφαρμοστεί μια επαναληπτική διαδικασία στο προπαρασκευαστικό βήμα. Ένα πεδίο για περαιτέρω έρευνα είναι η υλοποίηση και των υπολοίπων γενικών αρχών που προτείνονται στο δεύτερο κεφάλαιο της παρούσας διατριβής. Επίσης, προτείνεται να μελετηθεί η συμπεριφορά των αλγορίθμων που παρουσιάστηκαν στην παρούσα διατριβή με τον δυναμικό επαναπροσδιορισμό (dynamic redefinition) των εμπλεκόμενων προβλημάτων. Τέλος, ένα ενδιαφέρον θέμα έρευνας είναι η εφαρμογή των όσων προτείνονται στην παρούσα διατριβή στην επίλυση προβλημάτων μονοκριτηριακής βελτιστοποίησης με περιορισμούς.
|
|---|
