ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
1.5 Ερμηνεια των Γενετικων Αλγοριθμων
Η βασική ιδέα που κρύβεται πίσω από τους Γ.Α. είναι η μίμηση των μηχανισμών της φύσης. Ας πάρουμε, για παράδειγμα, τους λαγούς και πως αναπαράγονται και εξελίσσονται από γενιά σε γενιά [49]. Έστω ότι αρχίζουμε να παρατηρούμε ένα συγκεκριμένο πληθυσμό από λαγούς. Όπως είναι φυσικό, κάποιοι από αυτούς θα είναι πιο γρήγοροι και πιο εύστροφοι από τους άλλους. Αυτοί οι γρηγορότεροι και εξυπνότεροι λαγοί έχουν λιγότερες πιθανότητες να αποτελέσουν γεύμα κάποιας αλεπούς και άρα από τη στιγμή που καταφέρνουν να επιβιώσουν θα ασχοληθούν με την αναπαραγωγή του είδους τους. Φυσικά, θα υπάρχει και ένας μικρός αριθμός αργών και λιγότερο εύστροφων λαγών που θα καταφέρουν να επιβιώσουν μόνο και μόνο επειδή στάθηκαν τυχεροί. Όλοι αυτοί οι λαγοί, που έχουν καταφέρει να επιβιώσουν, θα αρχίσουν την παραγωγή της επόμενης γενιάς τους, μια γενιά που θα συνδυάζει όλα τα χαρακτηριστικά των μελών της προηγούμενης, συνδυασμένα με διάφορους τρόπους μεταξύ τους. Έτσι, μερικοί αργοί λαγοί θα αναμειχθούν με κάποιους γρήγορους, κάποιοι γρήγοροι με άλλους γρήγορους, κάποιοι εύστροφοι λαγοί με κάποιους μη εύστροφους και ούτω καθεξής. Οι μικροί λαγοί της επόμενης γενιάς θα είναι, κατά μέσο όρο, γρηγορότεροι και εξυπνότεροι από τους προγόνους τους, αφού από την προηγούμενη γενιά επιβίωσαν περισσότεροι γρήγοροι και έξυπνοι λαγοί. Ευτυχώς, για την διατήρηση της φυσικής ισορροπίας, και οι αλεπούδες υφίστανται την ίδια διαδικασία αναπαραγωγής, διαφορετικά οι λαγοί θα γινόντουσαν υπερβολικά γρήγοροι και έξυπνοι για να μπορούν να τους πιάσουν.
Οι Γ.Α. χρησιμοποιούν ορολογία δανεισμένη από το χώρο της Φυσικής Γενετικής. Αναφέρονται σε άτομα ή γενότυπα μέσα σε ένα πληθυσμό. Πολύ συχνά αυτά τα άτομα καλούνται επίσης χρωμοσώματα. Αυτό μπορεί να οδηγήσει μερικούς σε λάθος συμπεράσματα, αν γίνει παραλληλισμός με τους φυσικούς οργανισμούς, όπου κάθε κύτταρο κάθε συγκεκριμένου είδους περιέχει έναν συγκεκριμένο αριθμό χρωμοσωμάτων (τα ανθρώπινα κύτταρα για παράδειγμα περιέχουν 46 χρωμοσώματα). Στους Γ.Α. αναφερόμαστε σχεδόν πάντα σε άτομα με ένα μόνο χρωμόσωμα. Τα χρωμοσώματα αποτελούνται από διάφορα στοιχεία που ονομάζονται γονίδια και είναι διατεταγμένα σε γραμμική ακολουθία. Κάθε γονίδιο επηρεάζει την κληρονομικότητα ενός ή περισσότερων χαρακτηριστικών. Τα γονίδια που επηρεάζουν συγκεκριμένα χαρακτηριστικά γνωρίσματα του ατόμου βρίσκονται και σε συγκεκριμένες θέσεις του χρωματοσώματος που καλούνται loci. Κάθε χαρακτηριστικό γνώρισμα του ατόμου (όπως για παράδειγμα το χρώμα μαλλιών) έχει τη δυνατότητα να εμφανιστεί με διάφορες μορφές, ανάλογα με την κατάσταση στην οποία βρίσκεται το αντίστοιχο γονίδιο που το επηρεάζει. Οι διαφορετικές αυτές καταστάσεις που μπορεί να πάρει το γονίδιο καλούνται alleles (τιμές χαρακτηριστικού γνωρίσματος).
Κάθε γενότυπος (που στις περισσότερες περιπτώσεις είναι ένα μόνο χρωμόσωμα) αναπαριστά μια πιθανή λύση σε ένα πρόβλημα. Το μεταφρασμένο περιεχόμενο ενός συγκεκριμένου χρωμοσώματος καλείται φαινότυπος και καθορίζεται από την χρήση, ανάλογα με τις ανάγκες και τις απαιτήσεις του. Μια διαδικασία εξέλιξης που εφαρμόζεται πάνω σε ένα πληθυσμό χρωμοσωμάτων αντιστοιχεί σε ένα εκτενές ψάξιμο μέσα σε ένα διάστημα από πιθανές λύσεις. Απαραίτητη προϋπόθεση για την επιτυχημένη έκβαση ενός τέτοιου ψαξίματος αποτελεί η εξισορρόπηση δύο διαδικασιών που είναι προφανώς αντικρουόμενες, της εκμετάλλευσης και διατήρησης των καλύτερων λύσεων και της όσο το δυνατόν καλύτερης εξερεύνησης όλου του διαστήματος.
Η εκτενής χρησιμοποίηση των Γ.Α. ως εργαλείο βελτιστοποίησης είναι εύκολο να δώσει σε κάποιον την εντύπωση ότι οι Γ.Α. είναι πραγματικοί αλγόριθμοι βελτιστοποίησης. Αυτό, όμως, δεν ευσταθεί, διότι υπάρχουν πολλές περιπτώσεις, όπου οι Γ.Α. αποτυγχάνουν να βρουν μια προφανή βέλτιστη λύση μέσα σε ένα συγκεκριμένο διάστημα ψαξίματος. Για την αποφυγή δημιουργίας αυτής της λανθασμένης εντύπωσης, οι Γ.Α. πρέπει να αντιμετωπίζονται ως μια ιδεατή προσομοίωση μιας φυσικής διαδικασίας, τέτοια ώστε να μπορούν να ενσωματώνουν τους στόχους και τους σκοπούς της διαδικασίας αυτής. Παρ' όλ' αυτά, δεν πρέπει να παραγνωρίζουμε ότι η βελτιστοποίηση αποτελεί ένα πολύ σημαντικό κομμάτι των εφαρμογών των Γ.Α.
Κατά την διάρκεια της τελευταίας δεκαετίας, το ενδιαφέρον για τις διαδικασίες βελτιστοποίησης έχει αυξηθεί τόσο πολύ, ώστε να υπάρχουν πολύπλοκα και με πολύ αυστηρούς περιορισμούς προβλήματα, που να μπορούν να λυθούν μόνο προσεγγιστικά από τους σημερινούς υπολογιστές. Οι Γ.Α. αποσκοπούν στην εξυπηρέτηση τέτοιου είδους προβλημάτων. Εάν και ανήκουν στην κατηγορία των στοχαστικών αλγόριθμων, διαφέρουν σε πολύ μεγάλο βαθμό από τους αλγόριθμους που εφαρμόζουν τυχαίες μεθόδους απαρίθμησης και βελτιστοποίησης, αφού είναι σε θέση να συνδυάζουν στοιχεία και από άμεσες και από στοχαστικές τεχνικές αναζήτησης. Αυτός είναι και ο κύριος λόγος για τον οποίο οι Γ.Α. θεωρούνται πιο εύρωστοι από τις υπάρχουσες μεθόδους άμεσης αναζήτησης. Ένα άλλο εξίσου σημαντικό χαρακτηριστικό τους είναι ότι διατηρούν έναν πληθυσμό πιθανών λύσεων πάνω στον οποίο πειραματίζονται, σε αντίθεση με όλες τις άλλες μεθόδους αναζήτησης που επεξεργάζονται ένα μόνο σημείο του διαστήματος αναζήτησης.
Ένας Γ.Α. πραγματοποιεί αναζήτηση σε πολλές κατευθύνσεις με το να διατηρεί ένα πληθυσμό από πιθανές λύσεις και υποστηρίζει καταγραφή και ανταλλαγή πληροφοριών μεταξύ αυτών των κατευθύνσεων. Ο πληθυσμός υφίσταται μια προσομοιωμένη γενετική εξέλιξη. Σε κάθε γενιά, οι σχετικά "καλές" λύσεις αναπαράγονται, ενώ οι σχετικά "κακές" αφαιρούνται. Ο διαχωρισμός και η αποτίμηση των διαφόρων λύσεων γίνεται με την βοήθεια μιας αντικειμενικής συνάρτησης ή συνάρτησης ικανότητας (objective function), η οποία παίζει το ρόλο του περιβάλλοντος μέσα στο οποίο εξελίσσεται ο πληθυσμός.
Η δομή ενός απλού “παραδοσιακού” Γ.Α., που παρουσιάζεται στο σχήμα 1, έχει σε γενικές γραμμές ως εξής:
Κατά την διάρκεια της
επαναληπτικής εκτέλεσης , ο Γ.Α. διατηρεί ένα πληθυσμό
από
πιθανές λύσεις:
.
Κάθε λύση
αποτιμάται και δίνει ένα μέτρο της καταλληλότητας και
ορθότητάς της. Αφού ολοκληρωθεί η αποτίμηση όλων των στοιχείων του πληθυσμού,
δημιουργείται ένας νέος πληθυσμός (επαναληπτική εκτέλεση
) που προκύπτει από την επιλογή των πιο κατάλληλων στοιχείων
του πληθυσμού της προηγούμενης γενιάς. Μερικά μέλη από τον καινούριο αυτό
πληθυσμό υφίστανται μετατροπές με την βοήθεια των διαδικασιών της
διασταύρωσης και της μετάλλαξης σχηματίζοντας νέες πιθανές λύσεις. Η
διασταύρωση συνδυάζει τα στοιχεία δύο χρωμοσωμάτων γονέων για να δημιουργήσει
δύο νέους απογόνους ανταλλάσσοντας αντίστοιχα κομμάτια από τους γονείς. Για
παράδειγμα, έστω ότι δύο γονείς αναπαριστώνται με διανύσματα πέντε διαστάσεων
και
αντίστοιχα, τότε οι απόγονοι που θα προκύψουν από διασταύρωση
με σημείο διασταύρωσης (crossover point) το σημείο 2 είναι οι
και
. Διαισθητικά μπορούμε να πούμε ότι η διασταύρωση εξυπηρετεί
την ανταλλαγή πληροφοριών μεταξύ διαφορετικών πιθανών λύσεων.
Η διαδικασία της μετάλλαξης αλλάζει αυθαίρετα ένα ή περισσότερα γονίδια ενός συγκεκριμένου
BEGIN /* Γενετικός Αλγόριθμος */
Δημιουργία αρχικού πληθυσμού
Υπολογισμός της τιμής της αντικειμενικής συνάρτησης για κάθε άτομο
WHILE NOT ολοκληρωμένος DO
BEGIN /* Δημιουργία νέας γενιάς */
FOR μέγεθος πληθυσμού / 2 DO
BEGIN
Επιλογή δύο ατόμων από την προηγούμενη γενιά για ζευγάρωμα
/* Προτιμούνται τα άτομα με καλύτερη τιμή στην αντικειμενική συνάρτηση */
Συνδυασμός των δύο ατόμων και δημιουργία δύο καινούριων
Εφαρμογή μετάλλαξης σε κάποια από τα καινούρια άτομα
Εισαγωγή των καινούριων ατόμων στην νέα γενιά
END
IF ο πληθυσμός συγκλίνει σε επιθυμητό βαθμό THEN
ολοκληρωμένος := TRUE
END
END
Σχήμα 1.1: Ένας απλός “παραδοσιακός” Γενετικός Αλγόριθμος
χρωμοσώματος. Πραγματοποιείται
με τυχαία αλλαγή γονιδίων με πιθανότητα ίση με το ρυθμό μετάλλαξης (mutation
rate). Για παράδειγμα, έστω ότι ένας γονέας αναπαρίσταται με το διάνυσμα
πέντε διαστάσεων , τότε ο απόγονος που θα προκύψει με μετάλλαξη στη δεύτερη και
στην τέταρτη διάσταση είναι ο
. Διαισθητικά μπορούμε να πούμε ότι η μετάλλαξη εξυπηρετεί την
εισαγωγή νέων πιθανών λύσεων, διαφορετικών από τις υπάρχουσες, στον ήδη υπάρχον
πληθυσμό.
Ένας Γ.Α. για ένα συγκεκριμένο πρόβλημα πρέπει να αποτελείται από τα παρακάτω πέντε συστατικά:
1. Μια γενετική αναπαράσταση των πιθανών λύσεων του προβλήματος.
2. Ένα τρόπο δημιουργίας ενός αρχικού πληθυσμού των πιθανών λύσεων.
3. Μια αντικειμενική συνάρτηση αποτίμησης, που παίζει το ρόλο του περιβάλλοντος κατατάσσοντας τις λύσεις με βάση την καταλληλότητά τους.
4. Γενετικούς τελεστές που μετατρέπουν τη σύνθεση των παιδιών.
5. Τιμές για διάφορες παραμέτρους που χρησιμοποιεί ο Γ.Α. (μέγεθος πληθυσμού, πιθανότητες εφαρμογής των γενετικών τελεστών, κ.τ.λ.).