Ανάπτυξη Πολιτισμικών Αλγορίθμων ή Αλγορίθμων Κουλτούρας (Cultural Algorithms) και Εφαρμογή τους σε Προβλήματα Βελτιστοποίησης

Abstract

Στην παρούσα πτυχιακή θα ασχοληθούμε με έναν κλάδο της Εξελικτικής Υπολογιστικής ο οποίος είναι οι Πολιτισμικοί Αλγόριθμοι ή αλλιώς Αλγόριθμοι κουλτούρας (Cultural Algorithms). Οι Αλγόριθμοι Κουλτούρας προσομοιώνουν τον Πολιτισμό των ανθρώπων δηλαδή την Κουλτούρα και την Παράδοση τους. Όπως γνωρίζουμε ο Πολιτισμός είναι ένα σύστημα συσσώρευσης γνώσεων και εμπειρίας, το οποίο εξελίσσεται συνέχεια με την πάροδο του χρόνου. Όπως γνωρίζουμε ένας απόγονος εξαρτάται από τις γενετικές του καταβολές, δηλαδή το DNA που έχει κληρονομήσει από τους γονείς του καθώς και το περιβάλλον με το οποίο αλληλοεπιδρά, δηλαδή την κοινωνία στην οποία μεγαλώνει. Συνεπώς μπορούμε να πούμε ότι ο απόγονος μιας γενιάς έχει την ευκαιρία να διδαχθεί ή να δεχθεί την αλληλεπίδραση από τον Πολιτισμό στον οποίο μεγαλώνει αλλά ταυτόχρονα έχει την ευκαιρία να εμπλουτίσει τον Πολιτισμό έτσι, ώστε να βοηθήσει μελλοντικά τις επόμενες γενιές. Αυτή η διαδικασία, δηλαδή η αλληλεπίδραση του ατόμου με το περιβάλλον, είναι μια αμφίδρομη διαδικασία. Οι Αλγόριθμοι Κουλτούρας είναι επέκταση των Γενετικών Αλγορίθμων. Βασικά χρησιμοποιούν το μοντέλο των Γενετικών Αλγορίθμων και επιπλέον έναν χώρο μνήμης (belief space). Ο χώρος μνήμης είναι το μέρος στο οποίο αποθηκεύεται η αποκτώμενη εμπειρία κάθε γενιάς σύμφωνα με την επίλυση του προβλήματος, η οποία με την σειρά της είναι διαθέσιμη στους απογόνους και μπορεί να επιταχύνει σημαντικά την αναζήτηση προς το βέλτιστο. Κατ’ αυτόν τον τρόπο, οι απόγονοι που παράγονται σε κάθε γενιά έχουν την δυνατότητα να αλληλοεπιδράσουν με τον χώρο μνήμης και να βελτιώσουν την ποιότητά τους με απώτερο σκοπό την γρηγορότερη αναζήτηση του βέλτιστου. Στα πλαίσια της παρούσας πτυχιακής εργασίας θα αναπτυχθούν Αλγόριθμοι Κουλτούρας σε περιβάλλον Οπτικού Προγραμματισμού (Borland Builder C++). Επιπλέον, θα ελεγχθεί η απόδοσή τους εφαρμόζοντας μια σειρά από προβλήματα βελτιστοποίησης, τα οποία αποτελούν προβλήματα δοκιμών (benchmark problems). Τα προβλήματα βελτιστοποίησης που θα διεξαχθούν είναι τα εξής: 1. Rosenbrock Function 2. Rastrigin Function 3. Schwefel Funcrion 4. Ένα ρεαλιστικό πρόβλημα το οποίο είναι ένα Παραλληλόγραμμο σταθερού όγκου και ελάχιστης επιφάνειας. Στο Κεφάλαιο 2 θα γίνει εκτενέστερη περιγραφή των προαναφερθέντων συναρτήσεων. Όσον αναφορά την διαδικασία εκτέλεσης των δοκιμών, χρησιμοποιήσαμε τον συνδυασμό διαφόρων παραμέτρων του Αλγορίθμου και για κάθε συνδυασμό τρέξαμε τον Αλγόριθμο 10 φορές, διότι είναι στοχαστικός. Τα αποτελέσματα πάρθηκαν με βάση τον μέσο όρο των αποτελεσμάτων μετά από τις 10 φορές εκτέλεσης του Αλγόριθμου για κάθε συνδυασμό παραμέτρων και για κάθε πρόβλημα. Στο Κεφάλαιο 2 γίνεται πλήρης αναφορά στις παραμέτρους που συνετέλεσαν στην παραγωγή των αποτελεσμάτων. Στο Κεφάλαιο 3 παρουσιάζονται τα συμπεράσματα σχετικά με τις παραμέτρους που οδήγησαν το κάθε πρόβλημα στην βέλτιστη τιμή.