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