Γενετικός Αλγόριθμος
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
 |
Έχει προταθεί αυτό το άρθρο ή τμήμα αυτού του άρθρου, να συγχωνευθεί με το Γενετικοί Αλγόριθμοι. (Σχολιάστε) |
| Αν πρόκειται να γίνει συγχώνευση σελίδων με μεγάλο ιστορικό, μην την κάνετε χειροκίνητα με «Αντιγραφή και Επικόλληση», αλλά ζητήστε την από τους διαχειριστές, προκειμένου να συγχωνευθεί και το ιστορικό των δύο σελίδων. |
Οι γενετικοί αλγόριθμοι είναι ένα πεπερασμένο σύνολο οδηγιών για την εκπλήρωση ενός έργου, το οποίο δεδομένης μιας αρχικής κατάστασης θα οδηγήσει σε μια αναγνωρίσιμη τελική κατάσταση, και το οποίο προσπαθεί να μιμηθεί την διαδικασία της βιολογικής εξέλιξης. Οι γενετικοί αλγόριθμοι Προσπαθούν να βρουν τη λύση ενός προβλήματος με το να προσομοιώνουν την εξέλιξη ενός πληθυσμού «λύσεων» του προβλήματος.
Είναι μια τεχνική προγραμματισμού που εισήγαγε στα τέλη της δεκαετίας του 1960 ο Τζον Χόλαντ, ερευνητής του Ινστιτούτου της Σάντα Φε (ΗΠΑ).
Οι γενετικοί αλγόριθμοι είναι μια από τις βάσεις των Προγραμμάτων Τεχνητής Ζωής. Συγκεκριμένα, επιχειρεί να αναπαράξει στους υπολογιστές τους μηχανισμούς της βιολογικής εξέλιξης με τον ίδιο τρόπο που η τεχνητή νοημοσύνη επιχειρεί να αναπαραστήσει και να μιμηθεί τις διαδικασίες της γνώσης.
Τα προγράμματα εξελίσσονται μέχρι να φτάσουν, μέσω μεταλλάξεων, διασταυρώσεων και φυσικής επιλογής, σε μια αποτελεσματική φόρμουλα η οποία θα εκτελεί με τον καλύτερο δυνατό τρόπο μια συγκεκριμένη εργασία
Πίνακας περιεχομένων |
[Επεξεργασία] Πως Λειτουργεί
Ο τρόπος λειτουργίας των Γενετικών Αλγορίθμων είναι εμπνευσμένος απο την βιολογία. Χρησιμοποιεί την ιδέα της εξέλιξης μέσω γενετικής μετάλλαξης, φυσικής επιλογής και διασταύρωσης.
Στην πράξη ο αλγόριθμος ξεκινά μ' ένα σύνολο λύσεων - ονομάζονται γονιδιώματα, δανειζόμενες το όνομά τους από τη βιολογία- οι οποίες συνιστούν τον "πληθυσμό". Κατόπιν ζητείται από τον υπολογιστή να δημιουργήσει μια σειρά τυχαίων ανασυνδυασμών και μεταλλάξεων των "γονιδιωμάτων".
Οι πιο ικανές λύσεις για ένα συγκεκριμένο πρόβλημα συνεχίζουν να εξελίσσονται και ανασυνδυάζονται τυχαία, μέχρις ότου "επιβιώσουν" οι καλύτερες. Συνήθως, όσο περισσότερες γενιές περνούν τόσο καλύτερες λύσεις βρίσκονται, μπορεί όμως ο αλγόριθμος να βρεθεί σε σημείο του πεδίου των λύσεων άπο όπου και δεν μπορεί να προχωρήσει λόγο του ότι βρίσκεται σε τοπικό μέγιστο. Για το λόγο αυτό έχουν υπάρχουν διαφορετικές εκδοχές του αλγόριθμου ανάλογα με τη μορφή του προβλήματος.
[Επεξεργασία] Τρόπος Υλοποίησηςτου Αλγορίθμου
Οι Γενετικοί Αλγόριθμοι είναι αρκετά απλοί στην υλοποίησή τους. Οι τιμές για τις παραμέτρους του συστήματος πρέπει να κωδικοποιούνται με τρόπο ώστε να αναπαραστηθούν απο μια μεταβλητή που περιέχει σειρά χαρακτήρων ή δυαδικών ψηφίων (0/1). Αυτη η μεταβλητή μιμείται το γενετικό κώδικα (γονιδίωμα) που ύπαρχει στους ζωντανούς οργανισμούς.
Αρχικά, ο Γενετικός Αλγόριθμος παράγει πολλαπλά αντίγραφα της μεταβλητής/γενιτικού κώδικα, συνήθως με τυχαιες τιμές, δημιουργώντας ενα πληθυσμό λύσεων. Κάθε λύση (τιμές για τις παραμέτρους του συστήματος) δοκίμαζεται για το πόσο κόντα φέρνει την αντίδραση του σύστηματος στην επιθυμητή, μέσω μιας συνάρτησης που δίνει το μέτρο ικανότητας της λύσης και η οποία ονομάζεται συνάρτηση ικανότητας (Σ.Ι).
Οι λύσεις που βρίσκονται πιο κοντά στην επιθυμητή, σε σχέση με τις άλλες, σύμφωνα με το μέτρο που μας δίνει η Σ.Ι, αναπαράγονται στην επόμενη γενιά λύσεων και λάμβανουν μια τυχαία μετάλλαξη. Επαναλαμβανοντας αυτη τη διαδικασία για αρκετές γενιές, οι τυχαίες μεταλλάξεις σε συνδυασμο με την επιβίωση και αναπαραγωγή των γονιδίωματων/λύσεων που πλησιάζουν καλύτερα το επιθυμητό αποτέλεσμα θα παράγουν ένα γονίδιο/λύση που θα περιέχει τις τιμες για τις παραμέτρους που ικανοποιούν όσο καλύτερα γίνεται την Σ.Ι.
[Επεξεργασία] Εκδοχές Αλγορίθμου
Υπάρχουν διάφορες εκδοχές της παραπάνω διαδικασίας για τους Γ.Α απο τις οποίες κάποιες περιλαμβάνουν και τη διασταύρωση (ζευγάρωμα) γονιδίων/λύσεων ώστε ο αλγόριθμος να φτάσει στο αποτέλεσμα πίο γρήγορα. Καθώς ύπαρχει το στοχαστικό (τυχαίο) συστατικό της μετάλλαξης και ζευγαρώματος, κάθε εκτέλεση του Γ.Α μπορεί να συγκλίνει σε διαφορετική λύση και σε διαφορετικό χρόνο. Η απόδοση του Γ.Α εξαρτάται επί το πλείστον από την συνάρτηση ικανότητας και συγκεκριμένα από το κατά πόσο το μέτρο της περιγράφει την βέλτιστη λύση.
[Επεξεργασία] Χαρακτηριστικά
Οι γενετικοί αλγόριθμοι δεν επιλύουν το πρόβλημα με αναλυτικό/ μαθηματικό τρόπο αλλά με βιολογικό. Συνεπώς έχουν μεγαλύτερη ενδογενή ευελιξία και ελευθερία να επιλέγουν μια επιθυμητή βέλτιστη λύση σύμφωνα με τις προδιαγραφές του προβλήματος. Ουσιαστικά οι γενετικό αλγόριθμοι είναι αλγόριθμοι αναζήτησης (heuristics) που προσπαθούν να αναζητήσουν την λύση του προβλήματος που τους αναθέτουμε.
[Επεξεργασία] Παράδειγμα
Έστω ότι έχουμε μια διεργασία Ε η οποία εξαρτάται από τις μεταβλητές x' ,x,x,x'. Η διεργασία Ε παράγει ένα προϊόν Α. Ποιες είναι οι τιμές των x',x,x,x' ώστε το κόστος του Α να είναι το μικρότερο δυνατό; Για να λύσει αυτό το πρόβλημα ο γενετικός αλγόριθμος, δημιουργεί κάποιες αρχικές τυχαίες λύσεις του προβλήματος. Δηλαδή, δημιουργεί ένα πληθυσμό χρωμοσωμάτων όπου το κάθε χρωμόσωμα αντιστοιχεί σε κάποιες τιμές των x. Για την εκτίμηση της καταλληλότητας του χρωμοσώματος αυτού, υπάρχει μια συνάρτηση καταλληλότητας (fitness function) η οποία και κρίνει το κατά πόσο είναι κατάλληλο το κάθε χρωμόσωμα. Κάθε χρωμόσωμα κρίνεται για την καταλληλότητά του, και στη συνέχεια επιλέγονται τα καλύτερα χρωμοσώματα. Αυτά «αναπαράγονται» χρησιμοποιώντας ορισμένους γενετικούς τελεστές, και παράγουν την επόμενη γενιά χρωμοσωμάτων. Μετά από πολλές γενιές, ο πληθυσμός θα έχει χρωμοσώματα τα οποία είναι αρκετά κατάλληλα για το πρόβλημα, οπότε μπορούμε να λάβουμε τα κατάλληλα x για την λύση του προβλήματος.
[Επεξεργασία] Εφαρμογές
Οι πιθανές εφαρμογές είναι πολλές:
- η καλύτερη δυνατή οργάνωση του ωραρίου ενός σχολείου,
- η μελέτη της βέλτιστης κατανομής ενός δικτύου από πλατφόρμες πετρελαίου αλλά και
- η δημιουργία υπολογιστών που θα βελτιώνουν τον τρόπο λειτουργίας τους "μαθαίνοντας" από την εμπειρία τους.
- εξερεύνηση των δυναμικών βιολογικών διαδικασιών, και της θεωρίας της εξέλιξης. Παράδειγμα ο Κάρλ Σήμς (1994) έκανε Γενετικους Αλγόριθμους που δημιούργησαν εικονικά "πλάσματα", κάποια απο τα οποία θυμίζουν πραγματικά. [1]
