| Περίληψη: | Η διαδικασία της βελτιστοποίησης αποτελεί ζήτημα ζωτικής σημασίας σε όλους τους κλάδους των επιστημών και της τεχνολογίας. Κάποιες από τις εφαρμογές της είναι η μεγιστοποίηση του κέρδους αλλά και η ελαχιστοποίηση του κόστους παραγωγής κάποιας επιχείρησης, η εύρεση βέλτιστης τροχιάς κάποιου οχήματος ή αντικειμένου κ.α.. Στα προβλήματα βελτιστοποίησης, κατασκευάζεται μία συνάρτηση-εκπρόσωπος του προβλήματος, η οποία ονομάζεται αντικειμενική συνάρτηση και χρησιμοποιείται ως μέτρο σύγκρισης των πιθανών λύσεων. Σκοπός μας είναι να εντοπίσουμε τις τιμές των μεταβλητών στις οποίες η αντικειμενική συνάρτησή λαμβάνει την μέγιστη ή ελάχιστη τιμή, σε ένα πεδίο ορισμού.
Οι μέθοδοι γραμμικής αναζήτησης και οι μέθοδοι περιοχών εμπιστοσύνης αποτελούν τους κυριότερους εκπροσώπους των ντετερμινιστικών μεθόδων βελτιστοποίησης. Η βασική φιλοσοφία των μεθόδων γραμμικής αναζήτησης είναι η επιλογή κατάλληλης κατεύθυνσης κίνησης και στη συνέχεια μήκους βήματος έτσι ώστε η επόμενη τιμή της αντικειμενικής συνάρτησης να είναι μικρότερη (αν αντιμετωπίζουμε πρόβλημα ελαχιστοποίησης) από την προηγούμενη. Στις μεθόδους περιοχής εμπιστοσύνης αναζητούμε ένα τετραγωνικό μοντέλο το οποίο εμπιστευόμαστε ότι αντιπροσωπεύει επαρκώς την αντικειμενική συνάρτηση σε μία γειτονιά. Οπότε, σκοπός μας είναι η βελτιστοποίηση του μοντέλου-αντιπροσώπου.
Στην κατηγορία των στοχαστικών μεθόδων βελτιστοποίησης ανήκουν οι Γενετικοί Αλγόριθμοι (ΓΑ) και αποτελούν παρακλάδι των Εξελικτικών Αλγορίθμων. Η βασική ιδέα των ΓΑ είναι η μίμηση των διαδικασιών της εξέλιξης που συναντάμε στην φύση. Σύμφωνα με την Θεωρία Εξέλιξης των Ειδών του Δαρβίνου στη φύση επιβιώνει ο πιο δυνατός οργανισμός, οπότε, καθώς το φυσικό περιβάλλον μεταβάλλεται, οι οργανισμοί θα πρέπει να εξελίσσονται συνεχώς προκειμένου να επιβιώσουν. Βασισμένοι, λοιπόν σε αυτή την ιδέα, οι ΓΑ, διατηρούν ένα πληθυσμό πιθανών λύσεων ο οποίος σε κάθε επανάληψη του αλγορίθμου βελτιώνεται, με την έννοια ότι τα άτομα που τον αποτελούν πλησιάζουν όλο και περισσότερο στη λύση του προβλήματος.
Στην παρούσα διπλωματική εργασία θα ξεκινήσουμε κάνοντας μία σύντομη ανάλυση των μεθόδων γραμμικής αναζήτησης καθώς και των μεθόδων περιοχών εμπιστοσύνης (Κεφάλαιο 1). Στη συνέχεια, θα μελετήσουμε τους Γενετικούς Αλγόριθμους (Κεφάλαιο 2) και θα προτείνουμε μία παραλλαγή αυτών για την βελτιστοποίηση συναρτήσεων (Κεφάλαιο 3). Η διαφορά αυτής της νέας μεθόδου, έναντι των κλασσικών ΓΑ, έγκειται στην αρχικοποίηση του πληθυσμού για την εφαρμογή του αλγορίθμου. Τα σημεία που δίνουμε ως είσοδο στον ΓΑ (pivot σημεία) επιλέγονται με μία συγκεκριμένη και ιδιαιτέρως σημαντική ιδιότητα, την quasi – solution property, πράγμα το οποίο φαίνεται να βελτιώνει την απόδοση του κλασσικού ΓΑ. Η μέθοδος δοκιμάστηκε σε κάποια χαρακτηριστικά παραδείγματα και τα προκαταρκτικά αποτελέσματα που προέκυψαν είναι ενθαρρυντικά. Περαιτέρω έρευνα αξίζει να γίνει σε μία μελλοντική εργασία.
|
|---|
