ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ
ΕΡΓΑΣΤΗΡΙΟ ΑΝΑΓΝΩΡΙΣΗΣ ΠΡΟΤΥΠΩΝ
ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
10 : Γλωσσαριο
· αδιάφορο σύμβολο: Είναι το σύμβολο *, το οποίο χρησιμοποιείται όταν η τιμή του γονιδίου μπορεί να πάρει είτε την τιμή 0 είτε την τιμή 1.
· ακρίβεια αναπαράστασης: Είναι ο καθορισμός των ψηφίων της συμβολοσειράς, τα οποία θα χρησιμοποιηθούν για την κωδικοποίηση μιας πραγματικής μεταβλητής.
· αναπαραγωγή: Είναι η πιο σημαντική λειτουργία του Γ.Α. που περιλαμβάνει την επιλογή, τη διασταύρωση και τη μετάλλαξη. Σε ορισμένα βιβλία, ως αναπαραγωγή θεωρείται μόνο η διαδικασία επιλογής.
· αναπαράσταση κινητής υποδιαστολής: Είναι η αναπαράσταση των γονιδίων με αριθμούς κινητής υποδιαστολής.
· αντικειμενική συνάρτηση: Είναι μια συνάρτηση που παίρνει σαν είσοδο μια αποκωδικοποιημένη συμβολοσειρά και επιστρέφει μια τιμή (συνήθως πραγματική), που είναι ανάλογη με το πόσο καλά λύνει το πρόβλημα η συγκεκριμένη συμβολοσειρά. Είναι δηλαδή μια συνάρτηση αξιολόγησης, που παίζει το ρόλο του περιβάλλοντος, κατατάσσοντας τα άτομα (τις λύσεις) με βάση την καταλληλότητά τους. Γι’ αυτό το λόγο λέγεται και συνάρτηση αξιολόγησης ή συνάρτηση καταλληλότητας ή συνάρτηση ικανότητας.
· αξιολόγηση: Η διαδικασία κατάταξης των γονότυπων (λύσεων) με βάση την καταλληλότητά (ικανότητά) τους.
· απόδοση σχήματος: Ορίζεται ως η μέση απόδοση όλων των συμβολοσειρών του πληθυσμού τη χρονική στιγμή (επανάληψη) t που ταιριάζουν με το σχήμα.
· απόδοση χρόνου: Η πολυπλοκότητα χρόνου που απαιτείται για τη υλοποίηση του Γ.Α., δηλαδή ο χρόνος CPU που απαιτείται για την εκτέλεση του αλγορίθμου.
· αποκωδικοποίηση: Είναι η αντίστροφη λειτουργία της κωδικοποίησης, δηλαδή η μετατροπή της δυαδικής συμβολοσειράς σε πραγματική τιμή.
· αρχικοποίηση: Είναι το βήμα στο οποίο δημιουργείται ο αρχικός πληθυσμός, πάνω στον οποίο θα λάβουν χώρα οι λειτουργίες του Γ.Α.
· γονίδια: Είναι τα μικρότερα μέρη από τα οποία αποτελούνται τα χρωμοσώματα. Στους Γ.Α. είναι τα ψηφία της συμβολοσειράς.
· γονότυπος (ή γενότυπος): Είναι το σύνολο της γενετικής πληροφορίας που είναι κωδικοποιημένο στα γονίδια.
· διασταύρωση: Είναι μια απλή λειτουργία (γενετικός τελεστής) ανταλλαγής γενετικού υλικού, μεταξύ δύο ατόμων (γονέων) του πληθυσμού, που ζευγαρώνουν με τυχαίο τρόπο δημιουργώντας έτσι δύο νέα χρωμοσώματα (παιδιά). Στόχος της είναι η νέα γενιά που θα προκύψει μετά την εφαρμογή της να περιλαμβάνει άτομα που θα διαφέρουν από τους γονείς τους και θα φέρουν συνδυασμό των καλύτερων χαρακτηριστικών τους. Στην πράξη χρησιμοποιείται με παραμετροποιημένη μορφή, δηλαδή λαμβάνει χώρα με πιθανότητα μικρότερη του 1, τη λεγόμενη πιθανότητα διασταύρωσης.
· δομικά στοιχεία: Είναι τα μικρού μήκους, χαμηλής τάξης και υψηλής απόδοσης σχήματα.
· ελιτισμός: Είναι η εξασφάλιση της αντιγραφής του καλύτερου ατόμου στην επόμενη γενιά, πριν τη διαδικασία επιλογής,.
· εξαναγκασμένη ρουλέτα: Είναι η υλοποίηση σε αλγοριθμική βάση του τελεστή επιλογής. Κάθε συμβολοσειρά (άτομο) του πληθυσμού αντιπροσωπεύεται σε ένα τμήμα της ρουλέτας, που είναι ανάλογο με την απόδοσή της.
· εξελικτικά προγράμματα: Είναι μια τροποποίηση των Γ.Α., που χρησιμοποιούν γονίδια κωδικοποιημένα με πραγματικές τιμές (δηλαδή εξελίσσουν δομές δεδομένων) και ειδικούς γενετικούς τελεστές που δημιουργήθηκαν ειδικά για αυτά.
· εξελικτικοί αλγόριθμοι: Είναι μια γενικευμένη κατηγορία αλγορίθμων εμπνευσμένων από τη θεωρία της εξέλιξης, οι οποίοι χρησιμοποιούν και άλλα είδη κωδικοποίησης εκτός της δυαδικής. Για παράδειγμα, η κωδικοποίηση ενός πληθυσμού από Νευρωνικά Δίκτυα, προκειμένου να εκπαιδευτούν με Γ.Α., απαιτεί την χρήση διασυνδεδεμένης λίστας. Σε αυτή την κατηγορία υπάγονται οι Γενετικοί Αλγόριθμοι, Ο Εξελικτικός Προγραμματισμός, οι Εξελικτικές Στρατηγικές, τα Συστήματα Ταξινόμησης και ο Γενετικός Προγραμματισμός.
· εξελικτικός προγραμματισμός: Είναι μια στοχαστική μέθοδος βελτιστοποίησης, παρόμοια με τους Γ.Α., που δίνει περισσότερο έμφαση στις σχέσεις συμπεριφοράς μεταξύ γονέων και απογόνων αντί να αναζητεί να εξομοιώσει γενετικούς τελεστές όπως παρατηρούνται στη φύση. Δεν χρησιμοποιεί διασταύρωση.
· επιλογή: Είναι η διαδικασία (γενετικός τελεστής) κατά την οποία επιλέγονται τα καταλληλότερα άτομα για τη δημιουργία του προσωρινού πληθυσμού. Στόχος της είναι να επιτρέπει εκθετική αύξηση των ικανότερων ατόμων και τελικά, μετά από αρκετές γενιές, την επικράτησή τους. Γ.Α. χωρίς επιλογή στην αναπαραγωγική του διαδικασία ισοδυναμεί με τυχαίο ψάξιμο.
· κριτήριο τερματισμού: Είναι η συνθήκη που πρέπει να ικανοποιηθεί, προκειμένου να σταματήσει η εκτέλεση του αλγορίθμου.
· κωδικοποίηση: Η διαδικασία μετατροπής της πραγματικής λύσης σε δυαδική συμβολοσειρά ορισμένου μήκους.
· μέθοδος ποινής: Είναι η μέθοδος ενσωμάτωσης ανισοτικών περιορισμών στην αντικειμενική συνάρτηση, εκχωρώντας χαμηλές αποδόσεις σε μη νόμιμα σημεία, δηλαδή σε σημεία που δεν ικανοποιούν τους περιορισμούς.
· μετάλλαξη: Είναι η λειτουργία (γενετικός τελεστής) που ενεργεί σε ένα μόνο χρωμόσωμα κάθε φορά. Καθώς αντιγράφονται δυαδικά ψηφία από το γονέα στον απόγονο, επιλέγεται τυχαία με μικρή πιθανότητα - τη λεγόμενη πιθανότητα μετάλλαξης - ένα ψηφίο και αντιστρέφεται (από 0 σε 1 και το αντίστροφο). Λειτουργεί ως ασφαλιστική δικλείδα για τις περιπτώσεις, κατά τις οποίες η επιλογή ή η διασταύρωση, ενδεχομένως, οδηγήσουν σε απώλεια κάποιων πολύτιμων γενετικών πληροφοριών.
· ντετερμινιστικοί κανόνες: Είναι οι κανόνες των οποίων το αποτέλεσμα ισχύει αιτιοκρατικά.
· οριστικό μήκος σχήματος: Είναι η απόσταση μεταξύ της πρώτης και της τελευταίας σταθερής θέσης σε ένα σχήμα.
· πιθανοθεωρητικοί κανόνες: Είναι οι κανόνες που ισχύουν τυχαία, με κάποια πιθανότητα.
· πιθανότητα διασταύρωσης: Είναι η πιθανότητα με την οποία γίνεται η διασταύρωση. Η τιμή της καθορίζεται από το σχεδιαστή του Γ.Α..
· πιθανότητα επιβίωσης σχήματος: Είναι η πιθανότητα επιβίωσης ενός σχήματος μετά την εφαρμογή του τελεστή διασταύρωσης και είναι συμπληρωματική της πιθανότητας καταστροφής.
· πιθανότητα καταστροφής σχήματος: Είναι η πιθανότητα να καταστραφεί ένα σχήμα, μετά την εφαρμογή του τελεστή διασταύρωσης και ορίζεται από το λόγο του οριστικού μήκους προς τον αριθμό των πιθανών σημείων διασταύρωσης.
· πιθανότητα μετάλλαξης: Είναι η πιθανότητα με την οποία γίνεται η μετάλλαξη. Η τιμή της καθορίζεται από το σχεδιαστή του Γ.Α..
· πλεονάζουσες τιμές: Είναι οι τιμές που περισσεύουν, επειδή το πλήθος των τιμών που μπορεί να πάρει η μεταβλητή δεν είναι δύναμη του 2. Οι κωδικοποιημένες πλεονάζουσες τιμές δεν αντιστοιχούν σε καμία τιμή της πραγματικής μεταβλητής.
· πραγματική αναπαράσταση: Είναι η αναπαράσταση των γονιδίων με πραγματικούς αριθμούς.
· στοχαστική ομοιόμορφη δειγματοληψία: Είναι ένας μηχανισμός επιλογής. Είναι παρόμοιος με την εξαναγκασμένη ρουλέτα, με τη διαφορά ότι οι «φέτες» είναι ίσες μεταξύ τους και ίσες στο πλήθος με τον πληθυσμό.
· σχήμα (πρότυπο) ομοιότητας: Είναι ένα πρότυπο (template) που επιτρέπει τον προσδιορισμό της ομοιότητας μεταξύ των χρωμοσωμάτων και κατασκευάζεται με τη χρήση του αδιάφορου συμβόλου * στο αλφάβητο Σ των γονιδίων (Σ={0, 1}). Ένα σχήμα αναπαριστά όλες τις συμβολοσειρές (ένα υπερεπίπεδο, επίπεδο ή άλλο υποσύνολο του χώρου αναζήτησης), οι οποίες ταιριάζουν σε όλες τις θέσεις εκτός από αυτές που περιέχουν το σύμβολο *.
· τάξη σχήματος: Είναι ο αριθμός των θέσεων με 0 και 1, που καλούνται σταθερές θέσεις, δηλαδή οι θέσεις που δεν περιέχουν το αδιάφορο σύμβολο *.
· τελεστής αντιστροφής: Είναι ένας γενετικός τελεστής, ο οποίος επιλέγει δύο σημεία μέσα σε μια συμβολοσειρά και αντιστρέφει την τάξη των ψηφίων μεταξύ των επιλεγμένων σημείων, αλλά θυμάται τη «σημασία» του ψηφίου. Αυτό επιτυγχάνεται διατηρώντας τα ψηφία, μαζί με μία αναφορά των αρχικών τους θέσεων.
· τεχνητά νευρωνικά δίκτυα (Τ.Ν.Δ): Είναι μοντέλα παράλληλης επεξεργασίας που η οργάνωσή τους προσπαθεί να μιμηθεί το δίκτυο των νευρώνων του ανθρώπινου εγκέφαλου. Στην κλασική τους μορφή περιέχουν πολλά επίπεδα αθροιστικών μονάδων (νευρώνες), όπου κάθε είσοδος πολλαπλασιάζεται με κάποιο βάρος και όλες μαζί αθροίζονται για να περαστεί το αποτέλεσμα στο επόμενο επίπεδο. Αν οι νευρώνες είναι αρκετοί, τότε το δίκτυο προσεγγίζει τη λύση ενός προβλήματος με ικανοποιητική ακρίβεια.
· υβριδικοί αλγόριθμοι: Είναι ο συνδυασμός Γενετικού Αλγόριθμου με άλλο αλγόριθμο αναζήτησης και βελτιστοποίησης.
· φαινότυπος: Είναι το σύνολο των «ορατών» χαρακτηριστικών του οργανισμού και της συμπεριφοράς του, που καθορίζονται από τις πληροφορίες των γονιδίων.
· χρωμόσωμα: Είναι μια συμβολοσειρά, η οποία αναπαριστά την κωδικοποίηση μιας λύσης. Συνήθως αποτελεί και ένα άτομο του πληθυσμού. Όταν η λύση αποτελείται από περισσότερες μεταβλητές, τότε ένα άτομο του πληθυσμού αναπαρίσταται από αντίστοιχο αριθμό χρωμοσωμάτων.